next up previous
Next: Optimizing Byzantine Agreement Up: Byzantine Failures in Previous: Oral Messages

Written Messages

With written messages, consensus is always possible (assuming, of course, that there are at least two loyal generals between whom to have a consensus). The model here is that when a general is relaying information, he can not send a message, but he cannot change a message. (Messages are signed and any change would detected by the receiving general.)

If we go back to our previous example of one commander and two lieutenants, a loyal lieutenant will always know who is a traitor. If he gets a ``0'' from the commander and a ``The commander said `1','' or ``The commander did not send anything,'' message from the other lieutenant, then clearly the commander is a traitor and some default value, say 0, is assumed by both lieutenants. If the loyal lieutenant does not receive anything from the other lieutenant, then that lieutenant is a traitor and the commander's order stands.

In practice, written messages are implemented with cryptographic techniques of authentication, such as RSA [13]. The number of messages stay the same as the case for oral messages, and as this number is exponential with n, we'd like to find an alternative algorithm which uses fewer messages.

Lawrence Kesteloot
Fri Jan 20 16:38:32 EST 1995