# 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.

### More Insights

 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.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>