The Byzantine Generals Problem

A More Complicated Example

Getting a good understanding of the algorithm really requires walking through an example that has at least three ranks. Let's consider an example with n=7 and m=2. We'll continue with the convention that the General is P₁, and instead of having a faulty general, we'll have P₆ and P₇ be faulty processes. After the initial three rounds of information exchange, each process has the three-ranked tree in Figure 4.

The important thing to note in these trees is that I've inserted the value X for the input values of any input value that comes from the two faulty processes. We don't know what P₆ and P₇ might send in any given round, so in general, we'll try to evaluate this without pinning the result down.

You'll see that at rank 1, the values from path 17 and 16 are both set to X. In the first round, the two faulty processes communicated possibly false values to all other processes, and may have arbitrarily changed the values sent to different processes to skew the results.

As a result of those bad values in rank 1, we see their frequent occurrence in rank 2. In addition, there are additional bad values in rank 2 that resulted from other messages from the faulty processes.

Figure 4: A tree with n=7, m=2, and faulty processes P₆ and P_7.

All in all, at the leaf nodes, we have 18 deceptive values at the leaf nodes, and only 12 accurate messages that trace their way all the way back to the general through nothing but correct processes. Obviously, if we just voted on the majority of the messages we had received, we would be susceptible to falling for the wrong value.

Fortunately, the layout of the tree guarantees that we will actually get a correct value. In Figure 4, the rollup of the output values hasn't occurred yet, so every node has a question mark in the output value. In Figure 5, the output values are shown. The leaf rank has the output values set to the input values, with X used to indicate unknown values from faulty processes.

Figure 5: The tree after calculating the output values.

When the leaf rank is rolled up to the second rank, the nodes with paths 12, 13, 14, and 15 all have clear majority values of 0 for their output values, with 16 and 17 set to X, as their values are uncertain.

The final rollup to the top rank successfully sets the output value to 0, as four of the inputs are set to 0 and only 2 are set to X. Mission accomplished.

The Sample Code

I've included a C++ program (available online at www.ddj.com/code/) that implements this algorithm. It has a Process class used to send/receive messages, as well as to roll up the decision tree. A Traits class defines the number of processes, number of faulty processes, source process, and values the faulty processes sent in various rounds.

To help with visualization, the program outputs the tree for a given process in the format used by the graphviz program called dot (part of the free Graphviz program; www.graphviz.org). You can then use dot to create a picture of the output graph (all the figures in this article were created with dot).

As supplied, the program has n=7 and m=2. These are some good exercises to perform while experimenting with it :

• Attempt to invalidate the program or the algorithm by getting incorrect results with some particular combination of faulty messages.
• Add a third faulty process and show that it is relatively easy to get invalid output when n=7 and m=3.
• Reduce n to 6 and show that it is relatively easy to get invalid output with two faulty processes.
• Move up to m=3 and n=10. Experiment with various combinations of faulty Generals and lieutenants and see if you can create incorrect results.