Tuesday 6 April 2010

The Byzantine Cake Problem

It's Dereks birthday! As is the normal case for these events, we "secretly" have a collection and the person who collects up the money, goes and "secretly" buys a cake for the birthday boy.

This was until my boss, Craig, sent this out to the office by email...

"Can someone go to shop please as I’m busy all afternoon."

This results in an interesting logical problem.

There is an implied condition in the phraseology he's used that the person that goes is therefore not busy all afternoon. If they're not and he doesn't know about it, they are admitting being covertly lazy!

Aside from this immediate conflict of interest, all of the listeners who received the message (which by the way is not guaranteed) have no way to discuss in public who is going to go to the shop, as the targets act as listeners also and must not be aware of any discussion.

Now every time someone leaves the room, there is no way to tell if they have gone to get the cake. Craig is already gone as he is apparently "busy", but so is the money. No-one can know for sure whether he, or an another unknown "shopper" has taken it.

(Incidentally, Derek who's birthday it is, has now just left and so potentially he's stolen the money and is away to buy a cake, or new car, for himself. A potential security problem here too.)
In the end, the money acts a flag, but without some form of centralised co-ordination everyone in the office can go as far as the point of contention, all standing in the queue at Sainsburys with cakes and no money, either waiting eternally for Craig to turn up, or a race condition if he does, resulting in abandoned cake purchases and dead bodies all over the place.

The question from a protocol design point-of-view (given the Two Generals problem and it's proof of impossibility) is... "Has Craig mitigated the uncertainty inherent in the communication channel to an acceptable degree?"

Update: Craig has returned to the office, put on his coat and left.

Update 2: He's back! With a cake!

1 comment: