It may seem strange that programming, which has long been a bastion of exact algorithms behaving in precisely the same manner every time, occasionally turns to probability to solve some of its more difficult problems.
In some people's minds, algorithms should be proveably correct at all times and for all inputs (as with defect-free programming and formal methods). Probabilistic algorithms give up this property. There is always a chance that the algorithm will produce a false result. But this chance can be made as small as desired. If the chance of the software failing is made smaller than the chance of the hardware failing (or of the user spontaneously combusting, or whatever), there's little to worry about.
The Dining Philosophers Problem
Imagine a bevy of philosophers sitting around a large, round table. In the middle of the table is a bowl of spaghetti. Between each pair of philosophers is a single fork. (If you prefer your philosophers Chinese, substitute a bowl of rice and a single chopstick.) All these philosophers do is one of two things: think and eat. (They already have tenure, so publishing is not important.)
To eat, they need to use the fork on either side of them, which they can only pick up if their neighbor isn't using it. (Hygienists are requested to keep their hangups to themselves.) There is no communication between the philosophers. (Arguments are not conducive to their digestion.) Is there any protocol that can be implemented to ensure that all the philosophers can eat, and that none ever dies of starvation? Imagine that the philosophers have this simple eating protocol:
IF hungry REPEAT (take left fork if available) UNTIL (holding left fork) REPEAT (take right fork if available) UNTIL (holding right fork) REPEAT eat UNTIL NOT hungry (drop right fork) (drop left fork)
This is all well and good. When philosophers are hungry, they start grabbing forks. When they have both of them, they start eating. When finished eating, they drop both forks. No problem, until everyone gets hungry at the same time. In that case, everyone grabs for their left forks and waits for their right fork to become available. But since that fork has been grabbed by another philosopher, the system locks up forever. All the philosophers starve while waiting for the colleague on their right to drop his or her fork. In fact, you can prove that any deterministic algorithm for the philosophers has the potential to lock up the system. There are solutions that involve additional resources: buying more forks, limiting the number of philosophers at the table so there is always an empty seat, or hiring a waiter to make sure that everyone gets the chance to eat. Some solutions also require each philosopher to follow a different algorithm. But no fully distributed, fully symmetric solution to the problem exists that does not involve additional processors. To solve the problem we need something more.
D. Lehman and M.O. Rabin found that something more in probability. Each philosopher randomly picks up either the left fork first or the right fork first and drops the fork if the other is not available. The procedure is repeated until the philosopher has both forks. Then he or she eats until content and drops both forks. This method ensures that every philosopher gets the chance to eat. Although theoretically possible, in reality, no philosopher will ever starve:
IF hungry
(flip a coin to choose left or right at random)
IF left THEN
REPEAT (take left fork if available)
UNTIL (holding left fork)
ELSE
REPEAT (take right fork if available)
UNTIL (holding right fork)
IF (other fork is available) THEN
(pick up other fork)
REPEAT eat UNTIL NOT hungry
(drop left fork)
(drop right fork)
ELSE
(drop fork)
(exit and re-enter procedure)
Big deal, you might rightly say. We now know how to hold dinner parties for philosophers. Send your solution off to Miss Manners. What in the world does it have to do with programming?
Plenty. This kind of problem comes up all the time in computer networks, where different processors compete for shared resources. How do you make sure that every processor can access a file server or printer in such a way that the system doesn't lock up? Probabilistic algorithms.
