title: "Byzantine Generals' Problem: De-mystifying Leslie Lamport's Solution"
subtitle: A step-by-step walkthrough with visual examples
date: 2024-12-07
authors:
  - "[[Harsh Devisha]]"
tags:
  - distributed-systems
  - consensus
  - fault-tolerance
  - algorithms

Byzantine Generals' Problem: De-mystifying Leslie Lamport's Solution

Motivation

Distributed systems are everywhere in our modern digital infrastructure, from cloud computing to blockchain networks. However, a fundamental challenge in these systems is achieving consensus when some components might be faulty or malicious.

The Byzantine Generals' Problem, introduced by Leslie Lamport, Robert Shostak, and Marshall Pease in 1982, elegantly captures this challenge through a military metaphor. Understanding this problem and its solution is crucial for anyone working with distributed systems, blockchain technology, or fault-tolerant computing.

This blog focuses specifically on the solution using unsigned messages, the most challenging scenario where messages carry no authentication. We'll examine a non-trivial instance with the most adversarial case: where the commander is a traitor and strategically sends conflicting commands to create maximum confusion.

The unsigned message solution is particularly fascinating because it operates under the loosest guarantees. Unlike solutions that rely on cryptographic signatures or other forms of authentication, this approach must achieve consensus through pure logic and majority reasoning, making it both intellectually stimulating and practically relevant.

Our goal is not to reprove any of the results from the original paper, but rather to walk through detailed examples that illustrate how the protocol functions step by step. We hope this can serve as a companion for readers trying to better understand the original proofs, especially since those proofs, while rigorous, offer limited worked-out examples beyond the basic four-general case.

Introduction

Imagine a scenario where several Byzantine generals have surrounded an enemy city. They must decide collectively whether to Attack or Retreat. To succeed, all loyal generals must agree on the same plan of action: either all Attack or all Retreat. A split decision would be disastrous.

The generals can only communicate through messengers, and some generals might be traitors (potentially including the commander) who seek to prevent the loyal generals from reaching agreement. These traitors can:

• Send different messages to different generals
• Collude with other traitors
• Lie about messages they claim to have received

The challenge is to design an algorithm that ensures all loyal generals reach the same decision despite these traitors. This is the essence of the Byzantine Generals' Problem.

The solution we explore does not rely on message signatures or authentication. Instead, it uses a recursive message-passing approach called Oral Message (OM) algorithm that can withstand up to $t$ traitors in a system with at least $3t+1$ generals.

Terminology

Before diving into the solution, let's establish some terminology:

• Generals: The participants in the system, denoted as $G_i$ where $i$ is the general's identifier.
• Commander: The general who initiates the decision process (usually $G_0$).
• Lieutenants: All other generals who must follow the commander's decision.
• Loyal ($\mathcal{L}$): Generals who follow the algorithm correctly.
• Traitors ($\mathcal{T}$): Generals who may behave arbitrarily and maliciously.
• Commands: The possible decisions, typically Attack or Retreat.
• OM($m$): The Oral Message algorithm with recursion depth $m$.

The Byzantine Generals' Problem has two key requirements:

1. Agreement: All loyal generals must agree on the same decision. On receiving equal number of Attack and Retreat messages the loyal generals default to predetermined decision, Retreat.
2. Validity: If the commander is loyal, all loyal generals must follow the commander's order.

Lamport proved that with oral (unsigned) messages, we need at least $3t+1$ generals to tolerate $t$ traitors, and the algorithm requires $t+1$ rounds of message exchanges.

The Algorithm

The Oral Message algorithm (OM) works recursively:

OM(0)

1. The commander sends an order to all lieutenants
2. Each lieutenant uses the message received or uses Retreat if receives no message.

OM($m$), for $m > 0$:

1. The commander sends a message to each lieutenant.
2. Each lieutenant acts as a commander in the OM($m-1$) algorithm to share the message they received with all other lieutenants.
3. Each lieutenant determines the majority value reported for each commander and uses that as their final decision.

The algorithm guarantees correct operation if $n \geq 3t+1$ where $n$ is the total number of generals and $t$ is the maximum number of traitors.

The recursive nature of this algorithm creates a tree of message exchanges that grows exponentially with $m$. For a system with $n$ generals, the message complexity is $O(n^{m+1})$, which makes it practical only for small values of $t$ and thus $m$.

The Problem

Let's examine a specific instance of the Byzantine Generals' Problem:

• Total generals: $N = 7$
• Traitors: $t = 2$
• Loyal generals: $N - t = 5$

In our scenario:

• Commander $G_0$ is a traitor
• Lieutenant $G_1$ is also a traitor
• Lieutenants $G_2$ through $G_6$ are loyal

This is a particularly challenging case because the commander, who initiates the algorithm, is malicious. The commander's strategy is to create maximum confusion by sending conflicting commands:

• Commander $G_0$ sends Attack (A) to generals $G_2$, $G_4$, and $G_6$
• Commander $G_0$ sends Retreat (R) to generals $G_1$, $G_3$, and $G_5$

Additionally, the second traitor $G_1$ will also attempt to confuse the loyal generals by inconsistently relaying messages during the second round.

With $t = 2$ traitors, we need at least $3t+1 = 7$ generals, which is exactly what we have. According to the theory, OM(2) should be sufficient to achieve consensus among loyal generals. Let's see how this works in practice.

The Algorithm in Play

Round 0

In round 0 of the algorithm, the commander $G_0$ sends commands to all lieutenants. Since the commander is a traitor, it can send different commands to different lieutenants.

flowchart TB
    G0["G₀ Traitor Commander"]

    G1["G₁ Traitor"]
    G2["G₂ Loyal"]
    G3["G₃ Loyal"]
    G4["G₄ Loyal"]
    G5["G₅ Loyal"]
    G6["G₆ Loyal"]

    G0 -->|R| G1
    G0 -->|A| G2
    G0 -->|R| G3
    G0 -->|A| G4
    G0 -->|R| G5
    G0 -->|A| G6

    style G0 fill:#f88,stroke:#333,color:#000
    style G1 fill:#f88,stroke:#333,color:#000
    style G2 fill:#8f8,stroke:#333,color:#000
    style G3 fill:#8f8,stroke:#333,color:#000
    style G4 fill:#8f8,stroke:#333,color:#000
    style G5 fill:#8f8,stroke:#333,color:#000
    style G6 fill:#8f8,stroke:#333,color:#000

Figure 1: In Round 0 the traitor commander $G_0$ sends inconsistent messages to lieutenants. Red = Traitor, Green = Loyal. R = Retreat, A = Attack.

As shown in Figure 1, the traitor commander $G_0$ sends:

• Retreat (R) to generals $G_1$ (traitor), $G_3$, and $G_5$
• Attack (A) to generals $G_2$, $G_4$, and $G_6$

At this point, each lieutenant only knows what the commander told them directly. The table below represents this initial knowledge state, with each lieutenant recording the message they received on the diagonal.

Table 1: Diagonal cells show the message that each lieutenant ($G_1$ - $G_6$) receives from the traitor commander ($G_0$). Off-diagonal cells are empty, to be filled by messages exchanged between lieutenants in the next rounds.

Round 1

In this round each lieutenant takes turns acting as the commander for the round and tells all other lieutenants the message they received from the commander of the previous round (In this case Round 0 and the original commander $G_0$).

Table 2: Displays all the scenarios for Round 1 of the example

Note that each lieutenant while acting as the commander does not send out any new commands, but instead just reports what they claim the commander of the previous round (In this case, the original commander $G_0$) sent them.

flowchart TB
    G0["G₀ Traitor Commander"]
    G1["G₁ Traitor - Acting Commander"]

    G2["G₂"]
    G3["G₃"]
    G4["G₄"]
    G5["G₅"]
    G6["G₆"]

    G0 -->|R| G1
    G1 -->|R| G2
    G1 -->|A| G3
    G1 -->|R| G4
    G1 -->|A| G5
    G1 -->|R| G6

    style G0 fill:#f88,stroke:#333,color:#000
    style G1 fill:#f88,stroke:#333,color:#000
    style G2 fill:#8f8,stroke:#333,color:#000
    style G3 fill:#8f8,stroke:#333,color:#000
    style G4 fill:#8f8,stroke:#333,color:#000
    style G5 fill:#8f8,stroke:#333,color:#000
    style G6 fill:#8f8,stroke:#333,color:#000

Figure 2: Round 1 when $G_1$ acts as commander. Being a traitor, it deliberately sends contradicting messages (R and A) to different lieutenants.

Round 2

Round 2 will take place for every iteration of Round 1 as the lieutenants of Round 1 take turn acting as the commander.

During the final round, Round 2, lieutenants of the round instead of acting as the commander simply gossip about what they received from the commander of the previous round ($G_1$ in our example).

Continuing the example instance we considered for Round 1 where $G_1$ acts as the commander, we will now demonstrate what happened during the instance of Round 2 where $G_1$ is the commander and $G_2, G_3, G_4, G_5$ & $G_6$ are the lieutenants.

As $m = 2$ for our example, Round 2 will act as the final round, so instead of taking turns acting as the commander in the recursive fashion like earlier rounds, lieutenants $G_2, G_3, G_4, G_5$ & $G_6$ simply relay the message that they received from the acting commander $G_1$.

Table 3: Round 2 gossip where each cell shows the message the sender (row) tells the receiver (column) that it received from the acting commander $G_1$. Bold diagonal: sender's own message from $G_1$. Grey cells (—): $G_1$ is the acting commander and does not participate in consensus.

In our table visualization, the row headers are marked as Senders and the column headers are marked as Receivers, as each lieutenant gossips by filling out the rows (telling the other lieutenant what it received from the acting commander, $G_1$ in this case). Thus, the diagonals will simply contain the value that the lieutenant received from the acting commander, $G_1$.

Since each of the lieutenants in Round 2 is loyal, they just send out the exact same message that they received from the acting commander $G_1$.

After the gossip is over each lieutenant takes the majority of all the messages that they received during the gossip and treats it as the truth. In Table 3 a column represents the messages that a lieutenant receives from other lieutenants along with the message that they received from the acting commander $G_1$. The values in the last row contains the majority of the messages in that column.

Back To Round 1

The majority that was obtained from the Round 2 during the iteration of Round 1 (In our example, when $G_1$ was acting as the commander) is then used by the lieutenants for the same iteration of Round 1. In the example that we consider the majority that was obtained from Round 2 when the commander was $G_1$ is then used by the lieutenants as the truth values for Round 1 when $G_1$ was acting as the commander.

Table 4: The majority obtained from Round 2 is now used as the truth in Round 1 when $G_1$ completes acting as the commander.

To formalize, The majority from round $O(m)$ is then used as the truth in $O(m - 1)$.

Like mentioned earlier, each lieutenant acts as the commander in Round 1 that will result in a similar Round 2 where other lieutenants will gossip about the message that the new acting commander sends them.

Second Iteration of Round 1

For the sake of completeness of the example, we will now carry out the same process for the second iteration of Round 1 when $G_2$ (a Loyal lieutenant) acts as the commander.

flowchart TB
    G0["G₀ Traitor Commander"]
    G2["G₂ Loyal - Acting Commander"]

    G1["G₁"]
    G3["G₃"]
    G4["G₄"]
    G5["G₅"]
    G6["G₆"]

    G0 -->|A| G2
    G2 -->|A| G1
    G2 -->|A| G3
    G2 -->|A| G4
    G2 -->|A| G5
    G2 -->|A| G6

    style G0 fill:#f88,stroke:#333,color:#000
    style G1 fill:#f88,stroke:#333,color:#000
    style G2 fill:#8f8,stroke:#333,color:#000
    style G3 fill:#8f8,stroke:#333,color:#000
    style G4 fill:#8f8,stroke:#333,color:#000
    style G5 fill:#8f8,stroke:#333,color:#000
    style G6 fill:#8f8,stroke:#333,color:#000

Figure 3: Round 1 when $G_2$ acts as commander. Being loyal, it sends the same message (A) it received from $G_0$ to all lieutenants.

Round 2, Again

Like in the previous iteration, the rest of the lieutenants ($G_1, G_3, G_4, G_5$ & $G_6$) will gossip about the message that they receive from the new acting commander $G_2$. The only difference is that $G_1$ being a traitor, it will send contradicting messages to other lieutenants, lying about what it received from $G_2$ to create confusion.

Table 5: Round 2 gossip when $G_2$ is commander. $G_1$ lies but loyal lieutenants form the correct majority.

Once again exactly like before, the lieutenants use the majority of the messages that they receive (represented by column of the table) and this majority is used by the lieutenants for the iteration of Round 1 when $G_2$ was acting as the commander.

Table 6: The majority obtained from Round 2 (when $G_2$ is acting commander) is incorporated into the knowledge table for Round 1.

Concluding the Example

After all lieutenants have completed acting as the commander in Round 1 and obtaining the majority from their respective Round 2, the final knowledge table for Round 1 is:

Table 7: Final Table. The last row shows the majority decision for each lieutenant.

Every loyal lieutenant will now take the majority of messages that were obtained from all the Round 2 (recorded in the respective column) and use that as the final decision. In our example, the amount of Retreat and Attack messages are the same for all loyal lieutenants hence they will all use a predetermined decision which is Retreat for the algorithm. As guaranteed all the loyal lieutenants ($G_2, G_3, G_4, G_5, G_6$) finally concluded to the same decision which proves the correctness of the algorithm even when the commander $G_0$ itself was a traitor.

To summarize, the traitor lieutenant $G_1$ (who received Retreat from $G_0$) continues the deception by:

• Telling some lieutenants that it received Attack from the commander
• Telling other lieutenants that it received Retreat from the commander

Meanwhile, all loyal lieutenants honestly relay the commands they received. After this round, each lieutenant has:

• Their original command from the commander, $G_0$ from Round 0.
• Reports from all other lieutenants about what they claim to have received

The final table shows what each lieutenant knows after all Round 2 and Round 1 messages have been exchanged.

This demonstrates the power of the OM(2) algorithm: despite having a traitor commander and a traitor lieutenant, all loyal lieutenants reach the same conclusion. The Byzantine Generals' Problem is solved for this instance!

A Second Example: Loyal Commander with Collaborating Traitors

To completely solidify our understanding of the algorithm let's examine a different but also crucial scenario where the commander is loyal but traitor lieutenants collaborate to disrupt consensus.

• Total generals: $N = 7$
• Traitors: $t = 2$
• Loyal generals: $N - t = 5$

In this scenario:

• Commander $G_0$ is loyal
• Lieutenants $G_1$ and $G_4$ are traitors
• Lieutenants $G_2$, $G_3$, $G_5$, and $G_6$ are loyal

We'll execute the OM(2) algorithm for this scenario and observe how the loyal lieutenants achieve consensus despite the traitors' attempts to disrupt it.

Round 0

In Round 0, the loyal commander $G_0$ sends the same command to all lieutenants. For this example, the commander issues an Attack order.

flowchart TB
    G0["G₀ Loyal Commander"]

    G1["G₁ Traitor"]
    G2["G₂ Loyal"]
    G3["G₃ Loyal"]
    G4["G₄ Traitor"]
    G5["G₅ Loyal"]
    G6["G₆ Loyal"]

    G0 -->|A| G1
    G0 -->|A| G2
    G0 -->|A| G3
    G0 -->|A| G4
    G0 -->|A| G5
    G0 -->|A| G6

    style G0 fill:#8f8,stroke:#333,color:#000
    style G1 fill:#f88,stroke:#333,color:#000
    style G2 fill:#8f8,stroke:#333,color:#000
    style G3 fill:#8f8,stroke:#333,color:#000
    style G4 fill:#f88,stroke:#333,color:#000
    style G5 fill:#8f8,stroke:#333,color:#000
    style G6 fill:#8f8,stroke:#333,color:#000

Figure 4: Round 0 - Loyal Commander $G_0$ sends consistent Attack (A) to all lieutenants. Red = Traitor, Green = Loyal.

Because the commander is loyal, every lieutenant, including the traitors $G_1$ and $G_4$, receives the same Attack command.

Table 8: Initial values received by each lieutenant from the loyal commander. Off-diagonal cells are empty, to be filled by messages exchanged in the next rounds.

Round 1

In Round 1, each lieutenant acts as the commander and relays the message they received from $G_0$ to all other lieutenants. This is where the traitors make their move.

Let's consider the iteration where traitor $G_1$ is the acting commander. Although $G_1$ received an Attack command, it will lie and tell every other lieutenant that it received a Retreat command.

flowchart TB
    G0["G₀ Loyal Commander"]
    G1["G₁ Traitor - Acting Commander"]

    G2["G₂"]
    G3["G₃"]
    G4["G₄"]
    G5["G₅"]
    G6["G₆"]

    G0 -->|A| G1
    G1 -->|"R ✗"| G2
    G1 -->|"R ✗"| G3
    G1 -->|"R ✗"| G4
    G1 -->|"R ✗"| G5
    G1 -->|"R ✗"| G6

    style G0 fill:#8f8,stroke:#333,color:#000
    style G1 fill:#f88,stroke:#333,color:#000
    style G2 fill:#8f8,stroke:#333,color:#000
    style G3 fill:#8f8,stroke:#333,color:#000
    style G4 fill:#f88,stroke:#333,color:#000
    style G5 fill:#8f8,stroke:#333,color:#000
    style G6 fill:#8f8,stroke:#333,color:#000

Figure 5: Traitor $G_1$ lies - reports R (Retreat) to everyone despite receiving A (Attack) from $G_0$.

Round 2

Now, the other lieutenants ($G_2$, $G_3$, $G_4$, $G_5$, $G_6$) enter Round 2. They gossip about the command they just received from the acting commander, $G_1$. Loyal lieutenants honestly relay the Retreat message they received from $G_1$. The other traitor, $G_4$, also relays Retreat, collaborating with $G_1$. Each lieutenant then takes the majority of the messages in their column. Since $G_1$ sent a consistent lie, every other lieutenant's majority decision for this iteration is Retreat.

Table 9: Round 2 gossip when $G_1$ is commander. All lieutenants report receiving Retreat, leading to a unanimous (but false) majority.

The majority of the messages obtained from Round 2 for the iteration is then used by the lieutenants for that iteration:

Table 10: Majority from Round 2 (when $G_1$ is acting commander) is incorporated into the knowledge table for Round 1.

Round 1, Again

Next, let's see what happens when a loyal lieutenant, $G_2$, is the acting commander. $G_2$ honestly reports the Attack command it received from $G_0$ to all other lieutenants.

flowchart TB
    G0["G₀ Loyal Commander"]
    G2["G₂ Loyal - Acting Commander"]

    G1["G₁"]
    G3["G₃"]
    G4["G₄"]
    G5["G₅"]
    G6["G₆"]

    G0 -->|A| G2
    G2 -->|A| G1
    G2 -->|A| G3
    G2 -->|A| G4
    G2 -->|A| G5
    G2 -->|A| G6

    style G0 fill:#8f8,stroke:#333,color:#000
    style G1 fill:#f88,stroke:#333,color:#000
    style G2 fill:#8f8,stroke:#333,color:#000
    style G3 fill:#8f8,stroke:#333,color:#000
    style G4 fill:#f88,stroke:#333,color:#000
    style G5 fill:#8f8,stroke:#333,color:#000
    style G6 fill:#8f8,stroke:#333,color:#000

Figure 6: Loyal $G_2$ honestly reports A (Attack) to all lieutenants.

Round 2, Again

In the corresponding Round 2, the lieutenants gossip about the message they received from $G_2$. This time, the traitors $G_1$ and $G_4$ lie, claiming they received Retreat from $G_2$, while loyal lieutenants report truthfully. Each loyal lieutenant receives two false Retreat messages (from $G_1$ and $G_4$) but three honest Attack messages from the loyal lieutenants. The majority for all loyal lieutenants is therefore Attack.

Table 11: Round 2 gossip when $G_2$ is commander. Traitors $G_1$ and $G_4$ send false reports, but loyal lieutenants form a majority for Attack.

The Round 1 knowledge table, after the completion of Round 2 where $G_2$ acts as the commander:

Table 12: Majority from Round 2 (when $G_2$ is acting commander) is incorporated into the knowledge table for Round 1.

Concluding the Example

This process repeats for every lieutenant acting as commander in Round 1. Traitors $G_1$ and $G_4$ will always report receiving Retreat. Loyal lieutenants $G_2, G_3, G_5, G_6$ will always honestly report receiving Attack. After all iterations are complete, the final state of knowledge is shown below. Each row represents the majority value determined from the corresponding Round 2 iteration.

Table 13: Final Round 1 knowledge table for all lieutenants after OM(2) completes. Each cell shows the majority value from the corresponding Round 2, and the diagonal shows the direct message from the commander.

Finally, each loyal lieutenant ($G_2$, $G_3$, $G_5$, and $G_6$) takes a majority vote of the values in its column from Table 13. The majority of messages for each loyal lieutenant is the same as the original command Attack that the loyal commander $G_0$ sent in Round 0. Although it is irrelevant what the traitor lieutenants ($G_1$ & $G_4$) end up doing, the majority of the messages for them is consistent with the loyal lieutenants.

This demonstrates that when the commander is loyal, OM(2) ensures all loyal lieutenants follow the commander's order.

Conclusion

The Byzantine Generals' Problem represents one of the fundamental challenges in distributed computing. Through our examination of the Oral Message algorithm (OM), we've seen how it's possible to achieve consensus even in the presence of malicious actors.

Key insights from our exploration:

• With $n$ generals and at most $t$ traitors, consensus requires $n \geq 3t+1$ and $m \geq t$ rounds of communication.
• The recursive nature of the algorithm allows loyal generals to filter out inconsistent information.
• Even with a traitor commander sending contradictory commands, loyal generals can still reach agreement.
• The solution works without requiring any form of message authentication or signatures.

This algorithm laid the foundation for many fault-tolerant distributed systems we rely on today, from cloud databases to blockchain networks. Modern consensus protocols like Practical Byzantine Fault Tolerance (PBFT) and those used in blockchain systems are direct descendants of Lamport's original solution.

Understanding these principles not only helps in designing robust distributed systems but also provides insight into the fundamental limits of what's achievable in the presence of Byzantine failures.