Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

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 P1, and instead of having a faulty general, we'll have P6 and P7 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 P6 and P7 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 P6 and P7.

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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.