The Byzantine Generals Problem

The Second Stage

While sending messages in each round, processes are also accumulating incoming messages. The messages are stored in a tree format, with each round of messages occupying one rank of the tree. Figure 3 shows the layout of the tree for a simple configuration with six processes, one of which can be faulty. Because m=1, there are just two rounds of messaging: The first, in which the general sends a value to each lieutenant process, and a second, in which each process broadcasts its value to all the other processes. Two rounds of messaging are equivalent to two ranks in the tree.

In Figure 3, there are six processes, and the General (P₁) is faulty—sending a 1 to the first three lieutenants and 0 to the last two. The subsequent round of messaging results in P₂ having an information tree that looks just like that in Figure 3. (Because only the General is faulty, in this case all other processes will have an identical tree.)

Once a process has completed building its tree, it is ready to decide on a value. It does this by working its way up from the leaves of the tree, calculating the majority value at each rank, and assigning it to the rank above it. The output value at each level is the third item in the data structure attached to each node, and those values are all undefined during the information gathering stage.

Figure 3: The Tree Layout for 5 processes with 1 faulty process.

Calculating the output values is a three-step process:

1. Each leaf node in the tree (all values at rank m) copies its input value to the output value.
2. Starting at rank m-1 and working down to 0, the output value of each internal node is set to be the majority of the output values of all its children. In the event of a tie, an arbitrary tie-breaker is used to assign a default value. The same default value must be used by all processes.
3. When complete, the process has a decision value in the output of the sole node at rank 0.

In Figure 3, step 1 of the process assigns the initial values to the leaf nodes. In the next step, the majority value of {1,1,1,0,0} is evaluated and returns a value of 1, which is assigned to the output value in rank 0. Because that is the top rank, the process is done, and P₁ decides on a value of 1.

Every lieutenant value in a given exercise will have the same paths for all its nodes, and in this case, because only the General is faulty, we know that all lieutenants will have the same input values on all its leaves. As a result, all processes will agree on the same value, 1, which fulfills the agreement property.