# The Crypto-Anarchists Cookbook

### From Telecomix Crypto Munitions Bureau

## Contents |

### [edit] Pea soup

Cooking time: O(1)

one day before

- Put all the peas in water (add more water than you think is suitable)
- Wait one day for the peas to get normal again

then

- Get a huge cauldron
- Put water, salt and peas into the cauldron and boil it
- Optional: Add diced bodyparts into cauldron
- Wait about an hour, one-and-a-half hour or so..
- Remove the bubbles on top of the boiling water
- Cut a leek, onions, broth, thymus and optionally at most 2
^{32}-1 items of anything else you wish and put into the water - Boil it until you think it is complete (30 minutes?)
- Eat

Note: It tastes *wonderful* the first day, while it is hot. If you put it in the refrigurator and eats it several days later it will not taste very good at all.

### [edit] PanNcakes

Cooking time: O(N) when number of eggs approach infinity

- Select an N from the natural numbers
- Get a large bowl, an empty stack (a dish) and a pan
- Select one and only one of the following lines to execute:
- Put N eggs, 2N deciliters of milk and N deciliters of flour into the bowl
- Put 3N eggs, 7N deciliters of milk and 5N deciliters of flour into the bowl

- Put salt into the bowl
- Mix the content of the bowl
- Until the bowl is empty do:
- Pour some of the content of the bowl into the pan
- Wait until the content of the pan no longer is liquid
- Flip the panncake and fry the other side
- Push panncake

- Eat

### [edit] Random Kaos Soup

Cooking time: O(n log n) when lim items -> infinity.

- Boil water
- Add salt and spice
- Select any number of delicious items
- Sort the items into how hard they are (hardness = boiling time)
- Let P be the passed time since this line was last evaluated, T be the estimated boiling time of the hardest item, and T
_{i}be the estimated boiling time of item I. - Until all items are in the boiling water do:
- Get the hardest item I remaining and optionally cut it into pieces
- Wait until T - (T
_{i}+ P) is less than or equal to zero - Add item I into the boiling water

- Wait until you think it is OK to eat
- Eat

### [edit] Dining Crypto-Anarchists

**Scenario:** A group of crypto-anarchists wish to eat the food from a common bowl. There are N forks and N crypto-anarchists. They sit in a circle around a table so that crypto-anarchist I's left fork is the crypto-anarchist (I+1 modulo N)s right fork. Each crypto-anarchist can only eat from the bowl if they have two forks. Each crypto-anarchist performs the following task:

- think
- try to grab two forks, one at a time
- eat
- return the forks, and then go thinking again

**Constraints:**

- At most one crypto-anarchist may hold a fork.
- If a crypto-anarchist tries to pick up a fork that is not on the table, she will be confused and wait until the fork is there and then grab it.
- A crypto-anarchist starves if she is confused for all eternity.
- It is assumed that a crypto-anarchist will finish eating once she has begun.

**Problem description:**
Describe a protocol and optional additional environment settings for avoiding starvation. In particular: In which order should the crypto-anarchists pick up the forks so that it is guaranteed that there is no possibility of starvation?

*Below follows a set of such solutions, called proofs.*

#### [edit] Proof of Dining Room

**Solution:** We introduce the concept of a dining room. K crypto-anarchists can be in the room at any time. If more than K crypto-anarchists wish to be in the room, they will form a queue outside the room. When a crypto-anarchist leaves the room, if there are any crypto-anarchists standing in queue, the first crypto-anarchist in the queue will enter the room. We also decide that each crypto-anarchist will try to grab the left fork first.

**Proof:**

- If a crypto-anarchist is confused from trying to grab the left fork, it means that the crypto-anarchist to the left has successfully grabbed her right fork, and thus also the left fork, since they all tries to grab the left fork first. This means that the crypto-anarchist is eating or is just about to begin eating. This in turn, means that the crypto-anarchist holding the fork will soon let go of it. Thus, eventually each crypto-anarchist will have her left fork.
- If a crypto-anarchist is confused from trying to grab her right fork, it means that the crypto-anarchist to the right has successfully grabbed her left fork. If we (because we wish to make a proof by contradiction) assume that the crypto-anarchist to the right is forever confused from never being able to also pick up her right fork, this means that the crypto-anarchist two seats to the right is also forever confused from having to wait at her right fork, and so on. Since there are only at most K crypto-anarchists in the room, this means that for crypto-anarchist K-1, the crypto-anarchist to the right is not in the room, and can thus not hold any forks. So, eventually, the crypto-anarchist will also have her right fork.
- A hungry crypto-anarchist standing in queue to enter the room will not starve, since all crypto-anarchists in the room will eventually have their forks as shown above, then eat, and then leave the room.

Cases 1-3 covers all possibilities of starvation.

#### [edit] Proof of Asymmetric Crypto-Anarchist

**Solution:** Any crypto-anarchist sitting on the first chair will grab her right fork first. Every other crypto-anarchist will try to grab their left forks first.

**Proof:**

- If the crypto-anarchist is confused from trying to grab her left fork, it means that the crypto-anarchist to the left has successfully grabbed her right fork. If we assume that the crypto-anarchist to the left is also confused, then it means that the crypto-anarchist two seats to the left is also confused, and so on. Since the crypto-anarchists sit in a ring, someone will be sitting to the left of the first crypto-anarchist. Only If the crypto-anarchist sitting besides the first crypto-anarchist is forever confused, then everyone starves.
- The same applies to the right hand side.
- A crypto-anarchist sitting besides the first crypto-anarchist is confused from trying to grab a fork that the first crypto-anarchist has taken. That the first crypto-anarchist has taken the fork means that she holds both forks, since she tried to grab the other fork first. If the first crypto-anarchist holds two forks, then she is about to eat, or is eating. This means she will eventually be finished eating.
- If the first crypto-anarchist is confused from trying to grab any of her two forks, then the other crypto-anarchist will soon return her forks, since that crypto-anarchist hold both forks (like case 3, but opposite).

This means that no starvation may occur.

#### [edit] Proof of The Infinite Number of Random Crypto-Anarchists

**Solution:** An infinite number of crypto-anarchists sit at the table. Each one will grab with equal probability the left or the right fork first.

**Proof**

- The probability that everyone will try to grab the left fork at the same time is lim x -> infinity, (1/2)^x = 0. The same applies to the right fork.
- If the crypto-anarchist is confused from grabbing the left fork, then for her to starve, the only possibility is that every other crypto-anarchist is also forever confused from grabbing the left fork. The same applies to the right fork. This possibility is zero, as shown in the previous bullet.

Thus, no one will starve.