Distributed Randomized Algorithms

The Dining Philosophers Problem (Breaking the symmetry)

Problem Description:
Once upon a time, there were n philosophers P0, P1, ..., Pn-1 seated around a circular table in a clockwise fashion. To the left of each philosopher lay a stick, and in the center stood a large bowl of spaghetti. A philosopher was expected to spend most of his time thinking; but when he felt hungry, he needed to pick up both the left fork and right fork to eat the spaghetti. When he was done with his meal, he would put down both sticks and continue thinking. Of course, a fork can be used by only one philosopher at a time. If the other philosopher wants it, he just has to wait until the fork is available again.

More discussion on the problem:
Two goals to achieve in solving the problem:

1. deadlock free -- if at any time there is a hungry philosopher, then eventually some philosopher will eat.
2. lockout free -- every hungry philosopher eventually gets to eat.

The configuration of philosophers and sticks for the case of n = 5 is illustrated below:

Solutions:

1. Deterministic algorithms: No way out???
As is proven in D. Lehman and M. O. Rabin's paper in 1981, no fully distributed and symmetric deterministic algorithm for dining philosophers is possible. We can prove it using the following example by introducing the role of an adversary. There can be an evil adversary, who contrives to produce deadlock. For example, the adversary can come up with the following "clever" strategy:

1. all n philosophers become hungry at the same moment
2. they each pick up their left fork simultaneously
3. because of the symmetry and the fact that each philosopher's behavior is strictly deterministic, they have no choice but to put down their sticks and try again later still precisely at the same time.

By repeating this cycle constantly, the adversary will be able to bring deadlock into this problem, thus makes any deterministic algorithms fail to work.

2. Randomized algorithm: The ONLY one !!!

The pseudo code is as follows:

main()
{
    while(TRUE)
    {
         /* thinking section */
         trying = TRUE;
         while(trying)
         {
              choose side randomly and uniformly from {0,1};
              otherside = complement of side;
              wait until (forkkAvailable[i-side] is TRUE 
              and change it to FALSE);
              if (forkAvailable[i-otherside] is TRUE and change it to FALSE)
                 then trying = FALSE;
                 else  forkAvailable[i-side] = TRUE;
         }
          /* eating section */
         forkAvailable[i-1] = forkAvailable[i] = TRUE;
     }
}

Note:

1. forkAvailable[i] is a Boolean variable for each Pi - Pi+1 pair, which indicates whether the fork between them is available.
2. The subtractions and addtions are to be interpreted modulo n.

Above is the Lehman and Rabin's algorithm. We toss a coin when the hungry philosopher decides whether to pick up the left fork or the right one first. This randomization prevents any evil adversary's scheme. We can show that the algorithm is deadlock free. The proof is based on that the coin tosses made by philosophers are independent random events. Thus, even if the adversary scheduler tries to bring on deadlock, a combination of tosses will finally arise that enables some philosopher to obtain two sticks. As the index number (0,1,...i) attached to a philosopher is for naming only, the algorithm is totally symmetric.

However, this algorithm is not lockout free. There can exist a very greedy philosopher Pi, and he tries to prevent his neighbor from eating by always beating him in the race of picking up the stick. Therefore, we need some more parameters to improve this algorithm. We can add two variables for each pair of philosophers, one lets Pi to inform Pi+1 of his desire to eat, and vice versa. The other shows which of the two eats last. In this way, we can achieve both the deadlock free and lockout free. Finally we've reached a Las Vegas algorithm for this problem.

A nice dining philosopher applet has been created by Sun. Click here to check it out.