The Byzantine Generals’ Dilemma

Something fascinating I learnt from computer science that says a lot about the nature of communication. There are 2 Byzantine generals (say Manuel Monomachus and Basil Ducas) wishing to overthrow the tyrannical empress Theodora Comnena. Manuel and Basil each have a mercenary army and have snuck up to Theodora’s holiday residence in Smyrna, one army from either side. Theodora has her Imperial Guard. Now, if Manuel and Basil combine their armies they will crush Theodora. But each army by itself is no match for Theodora’s forces. The only trouble is the armies are on either side of Smyrna. How will they coordinate the attack if each general wants to make sure he is only attacking if the other will support him?

The surprising answer: they can never coordinate the attack! Say Manuel sends a pigeon to Basil with a message: “I’ll attack at dawn tomorrow, join me”. He cannot attack yet. He’s not sure if Basil agrees or has even received the message. He gets a reply. “I want to join you, brave Manuel”. Can he attack now? No, because he knows Basil hasn’t received his confirmation, Basil can’t be sure his response was agreed to. Manuel sends a second message to Basil: “I’ve received your message and therefore will DEFINITELY attack at dawn.” Can he attack now? No! If Manuel’s pigeon was shot down, Basil would still be unsure whether Manuel will attack. Each message requires a confirmation, ad infinitum. This is the Two Generals’ Problem. (Note that the problem assumes Manuel and Basil trust each other 100%. Even with full trust, communicating-with-certainty is impossible.)

And lest you think that this is a fanciful case, here’s a more real example. You’ve arranged to meet a friend for lunch at noon but haven’t decided on a restaurant. You SMS her: “let’s go to the Singapore Chilli Crabhouse”. The same dilemma applies: until you get confirmation you’re not quite sure if she knows where to go. The practical solution is when you get a reply saying “ok” you assume she will assume you got the confirmation. This works because the stakes are not high. If it was life-threatening that you meet at the same restaurant, you’d probably call rather than SMS.

But hang on — is calling better? Or, come to think of it, does face to face communication solve the General’s Problem? Sorry, nope. Even if she is right there and you tell her the meeting place and she says “sure, see you there”, by the same problem it’s not enough for you to turn up to the restaurant with 100% certainty. Of course the odds are greatly in your favour since the message so rarely gets lost in face to face communication. Or does it? It wouldn’t be out of the question for your friend to mishear, misinterpret and the like.

The human conclusion from this piece of communications theory is that bulletproof communication is impossible. It is the tragedy of the human condition (as well as its glory) that all communication, perception and experience takes place in a world of high uncertainty. We use so many social norms and assumptions to try negotiate this uncertainty that it’s amazing that anything gets done at all! But now we can add to the list of norms the ones listed above. Eg. that in most contexts people are ok with just one level of confirmation and assume this confirmation was received. (The alternative is to spend all day saying “do you copy?” to someone else asking you “do you copy?”.) ‘Tis just another way in which our species is evolution’s sub-optimal solution.

5 comments ↓

#1 Takis Konstantopoulos on 03.19.09 at 10:43 pm

Two comments spring up to mind as a result of your interesting posting:

1. PROBABILITY REASONING: Every decision is taken with a certain degree of risk. As human beings (even if we are unaware of the mathematical theory of Probability) we tend to form empirical estimates of probability and, based on these, we take action. For example, a good backgammon player knows the strong positions, empirically. If I send a message and receive 100 acks, as a response of an equal number of acks, then I know that, with extraordinarily high probability, the message has gone through. This is, of course, based on some assumptions (such as that the acks are not sent by an evil guy). And, of course, I also assume that I’m not anally retentive to want to have probability exactly equal to 100% before I take action; which takes me to the second remark.

2. BUREAUCRACY, ADMINISTRATION AND REAL ABILITIES: It is well-known that there is a negative correlation between the amount of bureaucratic tendencies of a person (an Academic, say, who wants to communicate his/her decisions by dozens of formal letters written according to the Law) and this person’s real abilities. In other words, when someone does not want to take an action based on intuitive (obvious) criteria but, rather, waits to follow exactly an endless series of procedures (always justifying them as being what the Law says), then this person is called a Bureaucrat. This person is a hindrance to Civilization. Politicians are like this. Academics (in more and more universities around the world) are like this too. Byzantine rulers were like this. It is, merely, convenient for someone to become a bureaucrat. It is an excuse for avoiding to do real work. Or to think.

P.S. As a counterexample to my alluding that the Byzantines were entirely useless (they mostly were), please see my latest posting.

#2 michael on 03.21.09 at 4:57 pm

I don’t understand #2: if there’s a negative correlation wouldn’t that mean that the best actions or the actions of the most able people are ones that are most at odds with any type of law or system? And if you meant this to reflect on the example I wrote about, what would be the “obvious” criteria?

Maybe I’m just biased because I love the Byzantines and don’t think they were useless at all.

#3 Takis Konstantopoulos on 03.22.09 at 1:52 am

Michael, you are partially right: my comment was only loosely related to your post. It was prompted by it only. What I am saying is this: There are many people out there who abuse their positions and always appeal to the Law (whatever this means–sometimes in a metaphorical sense [c.f. Kafka], that’s why I capitalized it) in order to avoid doing real work. I am not saying that most able people are at odds with the (common, say) law. I am saying that hiding behind the “Law”, many people justify their “crimes” or crimes. I think that if we had a lengthier discussion you’d agree with me (knowing a bit how you think, based on your blog). To take a (trite) example, Bush said: “I am right to invade Iraq because God told me so”.

As for the Byzantines, as a whole, I don’t think that this long-lived empire has produced much. My opinion is that it was a religious state and, as such, it prevented real progress rather than aid it. Of course, some of them were able. They did have an apparently good way of living. When, at times, western Europeans had forgotten how to use sanitation systems, the Byzantines where much cleaner. But still, these were “dark” ages. One can argue that it was still darker in the east, but the Byzantine (emperors, say) were not that enlightened either.

It’s interesting to hear that you “love” the Byzantines. Perhaps I’m biased: I admit that. I see Byzantine stuff all around me in Greece and I can’t quite understand what’s so great.

#4 michael on 03.23.09 at 10:45 pm

I see, I guess “bureaucracy” might be a more descriptive word without the implications of “law”.

On the Byzantines, isn’t your criticism that they were a religious state a bit whiggish? I can’t think of any non-religious states at the time (of note) — what I like them for is they had a rich intellectual tradition and were a lot more cosmopolitan than Europe and most other civilisations at the time.

Not sure the dark ages would apply to Byzantium, I don’t think there was ever the same stagnation as in Europe. And wouldn’t the “east” be on the same reasonably level as Byzantium? This is why I like [find interesting] the Abbasid Caliphate as well — these were two civilisations that had a lot going for them at a time when the Europeans were barbarians.

#5 michael on 03.23.09 at 10:46 pm

And yes maybe some of it comes from the great art, architecture etc. and the fact that I’ve never even been to Greece, Turkey, the relevant parts of Italy and so forth.

Leave a Comment

Sorry, the spam got too much!
Once you do this, future comments from you won't need this: