The Dining Ambassadors Problem

This was originally circulated as a joke e-mail among a group of researchers who were looking at "Rampart", a security protocol for replicating a computation on several servers who really, really don't trust each other. It has since become notorious, and I keep being asked for copies of it, so here it is.

So, what sort of application really needs the service provided by Rampart?

Pretty nearly everything I could think of either only needed a much simpler mechanism (which doesn't bother to give you shared consistent ordering of events), or else needed even stronger mechanisms.

Then, it came to me. For years, we have persecuted students with questions on the Byzantine Generals Problem or the Dining Philosphers Problem.

Now, at last, we have the opportunity to combine the worst aspects of both in the "Dinning Ambassadors Problem":

• After a hard day discussing European pasta quotas, the 5 Ambassadors go out for dinner at the same Italian restuarant frequented by the dinning philosophers.
• While the philosophers are all good friends and have impeccable table manners, the Ambassadors are perfectly capable of such breaches of etiqutte as smuggling in additional chopsticks or attempting to eat with their hands. Such breaches of etiquette will, however, be looked down on severely and anyone caught doing so will be expelled from the restaurant on a 2/3 majority vote.
• An ambassador may attempt to make it appear as though one of the others has violated the rules of etiquette, in order to discredit them.
• With a real resturant this is too easy to solve.Instead, we will do this in a networked virtual restaurant, where insiders and outsiders can insert, delete, modify or re-order messages, destroy communications channels and even destroy end systems.
• The waiter would like to know who is currently holding the chopsticks.

Exercize: program a solution using Rampart.