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

Parallel

The Byzantine Generals Problem


The First Stage

The first stage is simply one of data gathering. The algorithm defines m+1 rounds of messaging between all the processes.

In Round 0, the General sends the order to all of its lieutenants. Having completed his work, the General now retires and stands by waiting for the remaining work to complete. Nobody sends any additional messages to the General, and the General won't send any more messages.

In each of the remaining rounds, each lieutenant composes a batch of messages, each of which is a tuple containing a value and a path. The value is simply a 1 or a 0. The path is a string of process IDs, <ID1, ID2,...,IDn>. What the path means in this context is that in Round N, PID1 is saying that it was told in Round N-1 that PIDN-1 was told by P that the command value was v. (This is much like the classic party game in which a message is whispered from ear to ear through a chain of players, becoming slightly mangled along the way.) No path can contain a cycle. In other words, if ID1 is 1, no other ID in the string of process IDs will be a 1.

The message definition is easy in Round 1. Each process broadcasts a message to all the other processes, including itself, but excluding the General, with the value it received from the General and its own process ID.

In subsequent rounds, things get more complicated. Each process takes all the messages it received from the previous round, appends its process ID where allowed, and sends those messages to all other processes, including itself. (The "where allowed" just means that the process skips any messages where adding its process ID to the list would create a cycle in the string of process IDs.)

For example, suppose that in Round 0 that P1, a faulty general, told P2, P3, and P4 that the command value was 0, and told P5, P6, and P7 that the command value was 1. In Round 1, the messages in Table 1 would be sent.

Sender = P2 Sender = P3 Sender = P4 Sender = P5 Sender = P6 Sender = P7
Dest Msg Dest Msg Dest Msg Dest Msg Dest Msg Dest Msg
P2 {0,12} P2 {0,13} P2 {0,14} P2 {1,15} P2 {1,16} P2 {1,17}
P3 {0,12} P3 {0,13} P3 {0,14} P3 {1,15} P3 {1,16} P3 {1,17}
P4 {0,12} P4 {0,13} P4 {0,14} P4 {1,15} P4 {1,16} P4 {1,17}
P5 {0,12} P5 {0,13} P5 {0,14} P5 {1,15} P5 {1,16} P5 {1,17}
P6 {0,12} P6 {0,13} P6 {0,14} P6 {1,15} P6 {1,16} P6 {1,17}
P7 {0,12} P7 {0,13} P7 {0,14} P7 {1,15} P7 {1,16} P7 {1,17}

Table 1: Messages sent by all six lieutenant processes in Round 1.

Things get more complicated in the second round. From the previous rule, we know that each process now has six values that it received in the previous round—one message from each of the three processes—and it needs to send each of those messages to all of the other processes, which might mean each process would send 36 messages out.

In Table 1, I showed the messages being sent to all six processes, which is redundant because the same messages are broadcast to all processes. For Round 2, I just show the set of messages that each process sends to all of its neighbors.

The six messages that P2 received in Round 1 were {0,12}, {0,13}, {0,14}, {1,15}, {1,16}, and {1,17}. According to the earlier definition, P2 will append its process ID to the path and forward each resulting message to all other processes. The possible messages it could broadcast in Round 2 are {0,122}, {0,132}, {0,142}, {1,152}, {1,162}, and {1,172}. The first message, {1,122}, contains a cycle in the path value of the tuple, so it is tossed out, leaving five messages to be sent to all processes.

The first message that P2 is sending in Round 2, {0,132}, is equivalent to saying, "P2 is telling you that in round 1 P3 told it that in round 0 that P1 (the General) told it that the value was 0." The five messages shown in P2's column in Table 2 are sent to all six lieutenant processes, including itself.

Sender = P2 Sender = P3 Sender = P4 Sender = P5 Sender = P6 Sender = P7
{0,132} {0,123} {0,124} {0,125} {0,126} {0,127}
{0,142} {0,143} {0,134} {0,135} {0,136} {0,137}
{1,152} {1,153} {1,154} {0,145} {0,146} {0,147}
{1,162} {1,163} {1,164} {1,165} {1,156} {1,157}
{1,172} {1,173} {1,174} {1,175} {1,176} {1,167}

Table 2: Messages sent by all six processes in Round 2.

It's easy to see that as the number of processes increases, the number of messages being exchanged starts to go up rapidly. If there are N processes, each process sends N-1 messages in Round 1, then (N-1)*(N-2) in Round 2, and (N-1)*(N-2)*(N-3) in Round 3. That can add up to a lot of messages in a big system.


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.