Ben-Or’s Randomized Byzantine Agreement Protocol (n >= 5t +1)

Procedure Agreement (vote)

round := 1

Do forever

Send (1,round,vote) to all processors

Wait until n-t messages of type (1,round,*) are received

If more than (n+t)/2 messages have the value v then

Send (2,round,v,D) to all processors

Else

Send (2,round,?) to all processors

Endif

Wait until n-t messages of type (2,round,*) are received

If there are at least t+1 D-messages with value v

Then vote := v

Else vote := coin toss

Endif

If there are at least 3t+1 D messages with value v then

DECIDE v and exit

Endif

round := round +1 Send (2,round,v,D) to all processors

end_do_forever

Lemma 1: if all correct processors have the same value in vote, they all decide on that value in this round.

Lemma 2: No two correct processors send different D-messages in the same round

Lemma 3: No two processors decide on different values.

Theorem: Ben-Or’s protocol correctly solves Byzantine agreement problem.