Implementation of Byzantine agreement

The protocol for consistent broadcast can be used to implement Byzantine agreement in 2f+3 rounds. Time is divided into f+1 phases, denoted by s in the range 1 to f+1 for the rest of this section. Each phase consists of 2 rounds, and one extra round is needed at the end of the protocol.

Correct processes start by broadcasting an ATTACK! message if their initial assessment is to attack, i.e. the input bit is 1. In the remaining phases, the protocol prescribes that processes an ATTACK! message if and only if they have received ATTACK! messages from f+s-1 different processes so far. Notice that the threshold increases by one every phase. Correct processes $p \in L$ messages at odd rounds only, i.e., at the first round of every phase. At the final round, processes decide 1 if they have received messages from at least 2f+1 different processes.

As before, the inputs to the algorithm (the generals' opinions) are x_p, and the outputs are d_p. Below is a description of the protocol, which runs concurrently with the protocol for consistent broadcast described before.

round 1

Processes p for which x_p=1 do (ATTACK!,p,1).

round 2s-1, (s>1) (odd rounds)

Let M_p,2s-1 be the number of different processes from which process p has accepted messages at round 2s-1 or earlier. If $M_{p,2s-1}\geq f+s-1$, and the process p has not broadcast already, then process p does (ATTACK!,p,2s-1).

round 2f+3 (final round)

Let M_p,2f+3 be defined as above. Now, process p decides ATTACK! (i.e., d_p=1) if $M_{p,2f+3}\geq 2f+1$; otherwise, it decides not to attack (i.e. d_p=0.

Notice that every correct process broadcasts at most once. We now prove the three properties we require: non-triviality, agreement, and limited bureaucracy.

First observe, that if at any round 2s-1, for $1\leq s\leq f+1$, all correct processes have broadcast, all correct processes will eventually decide 1. This follows from the correctness property of consistent broadcast which ensures that a message sent by a correct process is accepted within after two rounds.

The non-triviality follows since if x_p=1 for all $p \in L$, all correct processes start by broadcasting, and the observation above applies. If x_p=0 for all $p \in L$, none of the correct processes will ever start broadcasting because (a) at round 1 no correct process broadcasts and (b) the threshold for broadcasting at subsequent phases is $f+s-1 \ge f+1$. Therefore no correct process will receive the 2f+1 messages needed to decide on 1.

For the agreement property, we prove that for $p \in L$ we have that if p decides 1, then all correct processes decide 1. If d_p=1, process p has accepted messages from at least 2f+1 processes by round 2f+3. Let I denote the set of correct processes from which p has accepted messages; we have $\vert I\vert\geq f+1$.

If all processes in I had input 1, every correct process accepts f+1 messages at round 3 and then broadcasts, so again, the observation above applies and we are done.

Otherwise, there is a process q for which x_q=0. Thus, process q broadcasts at round 2s-1 for some $2\leq s \leq f+1$, which means that at round 2s-1, process q has accepted messages from at least f+s-1 processes other than itself. These messages are accepted by all other correct processes at round 2s (because of the relay property of consistent broadcast), and the message from q itself reaches all other correct processes by round 2s+1 (because of correctness of consistent broadcast). It follows that at round 2s+1 (phase s+1), each correct process has accepted messages from at least f+s processes, and thus broadcasts since the new threshold for phase s+1 is reached (if s<f+1), or decides 1 (if s=f+1).

Finally, the bureaucracy is limited by 2f+3 rounds.