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