Question

Consider the following variant of the Byzantine Generals Protocol with one general and seven lieutenants:

1. The General announces his proposal to the Lieutenants.

2. Each Lieutenant forwards the General’s announcement to the other six.

3. Each Lieutenant outputs the majority of the seven received announcements.

Show that if two of the parties are corrupt (either the general and one lieutenant, or two lieutenants) then the protocol is not secure: There is an execution of the protocol in which the lieutenants do not all agree on the same value.

Answer 1

The First Stage

The first stage of the algorithm 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 idly 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, <ID₁, ID₂, … ID_n>. What the path means in this context is that in Round N, PID_N is saying that was told in round N-1 that P_IDN-1 was told by P_ID1 that the command value was v. (This is very 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, let’s suppose that in Round 0 that P₁, a faulty general told P₂, P₃, and P₄ that the command value was 0, and told P₅, P₆, and P₇ that the command value was 1. In round 1, the following messages 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

The number of messages goes up in in the second round. From the previous iteration, we know that each process now has six values that it received in the previous round — one message from each of the six other non-source 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 the previous table I showed the messages being sent to all six processes, which is fairly redundant, since the same messages are broadcast to all processes. For round 2, I’ll just show you the set of messages that each process sends to all of its neighbors.

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

Table 2 — Messages sent by all six processes in round 2

The six messages that P₂ received in round 1 were {0,12}, {0,13}, {0,14}, {1,15}, {1,16}, and {1,17}. According to the earlier definition, P₂ 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 P₂ is sending in round 2, {0,132}, is equivalent to saying “P₂ is telling you that in round 1 P₃ told it that in round 0 that P₁ (the General) told it that the value was 0”. The five messages shown in P₂’s column in the table are sent to all six lieutenant processes, include itself.

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, (N-1)·(N-2)·(N-3) in round 3. That can add up to a lot of messages in a big system.

The Second Stage

While sending messages in each round, processes are also accumulating incoming messages. The messages are stored in a tree format, with each round of messages occupying one rank of the tree. Figure 3 shows the layout of the tree for a simple configuration with six processes, one of which can be faulty. Since m=1, there are just two rounds of messaging: the first, in which the general sends a value to each lieutenant process, and a second, in which each process broadcasts its value to all the other processes. Two rounds of messaging are equivalent to two ranks in the tree.

Each node in the tree has three elements: an input value, a path, and an output value. The input value and path are defined in the first stage of the algorithm - they are simply the messages received from the peer processes. The output value is left undetermined until the second stage of the algorithm, which I am defining here. Note that in the figure below, the output values are initially set to ‘?’, indicating that they are presently unknown.

Figure 3 — The Tree Layout for 5 processes with 1 faulty process

In Figure 3, there are six processes, and the General (P₁) is faulty — sending a 1 to the first three lieutenants and 0 to the last two. The subsequent round of messaging results in P₂having an information tree that looks just like that shown in Figure 3. (Because only the General is faulty, in this case all other processes will have an identical tree.)

Once a process has completed building its tree, it is ready to decide on a value. It does this by working its way up from the leaves of the tree, calculating the majority value at each rank and assigning it to the rank above it. The output value at each level is the third item in the data structure attached to each node, and those values are all undefined during the information gathering stage.

Calculating the output values is a three step process:

1. Each leaf node in the tree (all values at rank m) copies its input value to the output value.
2. Starting at rank m-1 and working down to 0, the output value of each internal node is set to be the majority of the output values of all its children. In the event of a tie, an arbitrary tie-breaker is used to assign a default value. The same default value must be used by all processes.
3. When complete, the process has a decision value in the output of the sole node at rank 0.

In Figure 3, step 1 of the process assigns the initial values to the leaf nodes. In the next step, the majority value of { 1, 1, 1, 0, 0 } is evaluated and returns a value of 1, which is assigned to the output value in rank 0. Because that is the top rank, the process is done, and P₁ decides on a value of 1.

Every lieutenant value in a given exercise will have the same paths for all its nodes, and in this case, since only the General is faulty, we know that all lieutenants will have the same input values on all its leaves. As a result, all processes will agree on the same value, 1, which fulfills the agreement property.