Byzantine agreement (consensus protocols)

Two generals, one decider:
- both need to attack same time
- need to send:
  o time: (easy: msg and an ack)
  o agreement to attack (hard)

A sends to B "attack at 10"
   But did B get it? Can't go unless sure.

B sends an ack, but did A get the ack?

=============================================================================

Impossibility proof.

Look at sequence of msg-ack-ack......

Assume there is some subset of i msgs that constitutes a proof, and
that both would attack.  

However, what if the last msg not delivered?
  - receiver presumably would not attack
  - sender, though, sees same msgs as the i-sequence, and so
  attacks....

=============================================================================

How to work it?

- A sends a whole bunch, assume one gets through

- A and B send and ack a while

=============================================================================

Generalization is the byzantine generals (or General and the
lieutenants). Idea is:

- a general makes a decision, tells everyone
- lieutenants talk amongst themselves about what they know

- easy to tell if someone is evil; hard to tell whether it's the
  general or a lieutenant

=============================================================================

First, let's show impossible with three:

A tells B go, C nogo. 
B and C tell each other what A said. 
Both B and C know someone is lying, but can't tell who.
(draw pictures)

=============================================================================

Now w/ 4:

(draw pictures)

It works!

=============================================================================
Sketch out extension to 3n+1;

=============================================================================
What about if we have signatures?
  others can not lie about what the leader said.

If I have 7 (one general, 6 lieut), how many liars can I tolerate?

3 bad:

General good, 3 bad lieu: 
- a "good" lieu rcvs from gen, 3 good lieu => general must be good

General bad: 2 bad lieu:

General tells