Unsolvable Distributed Consensus and The Two Generals' Problem

Introduction: The Need for Distributed Consensus

In distributed systems, multiple nodes frequently need to agree on a single shared state or decision. Examples include:

• Electing a single leader node among replicas.
• Synchronizing configuration metadata across services.
• Agreeing on the value of a key in a distributed key-value store.
• Committing or aborting a distributed transaction.

Consider a distributed database where Node 1 stores the price of an item as $1,000 while Node 2 stores it as $2,000. When a client queries the system, the response depends entirely on which node handles the request. This split view breaks data consistency. To provide a coherent, predictable system, nodes must communicate over a network and reach consensus on the true state.

Consensus is trivial when communication channels are 100% reliable and nodes never fail. However, distributed systems run over physical networks where packets can be delayed, corrupted, reordered, or lost entirely. When the underlying communication channel is unreliable, achieving deterministic consensus becomes fundamentally impossible.

This impossibility is illustrated through the classic thought experiment known as the Two Generals’ Problem.

---

The Two Generals’ Problem: Setup

The Two Generals’ Problem represents two distributed nodes attempting to coordinate an action over an unreliable network.

+-----------------+                       +-----------------+
|    General A    |                       |    General B    |
|   (Army Alpha)  |                       |   (Army Beta)   |
+--------+--------+                       +--------+--------+
         |                                         |
         |        ======== Enemy Valley ========   |
         +-------> [ Unreliable Messenger Path ] ->+
                   =============================    
                               |
                      [ Captured / Lost ]

The Rules of the Engagement

1. Two armies, led by General A and General B, prepare to attack an enemy fortification situated in an intervening valley.
2. The enemy’s forces are strong enough to destroy either army if it attacks alone.
3. Victory Condition: Both armies attack simultaneously ($A \text{ attacks} \land B \text{ attacks} \implies \text{Victory}$).
4. Defeat Condition: Only one army attacks while the other stays back ($A \text{ attacks} \land B \text{ retreats} \implies \text{Defeat}$).
5. Communication Constraint: The only way General A and General B can coordinate is by dispatching physical messengers across the valley. The enemy may intercept and execute any messenger, meaning messages can be dropped without notice.

The generals must coordinate on an exact time of attack (e.g., 06:00 AM tomorrow).

---

Scenario 1: The Reliable Channel (Trivial Consensus)

If the communication channel is perfectly reliable, messengers are guaranteed to make the transit without interception. In this idealized model, coordination is simple and requires only a small round of messages:

sequenceDiagram
    autonumber
    participant A as General A
    participant B as General B
    Note over A,B: Network is 100% Reliable
    A->>B: Propose: Attack tomorrow at 06:00 AM
    B->>A: Agree: 06:00 AM works for me
    A->>B: ACK: Received agreement. See you at 06:00 AM
    B->>A: Final ACK: Confirmed

Because delivery is guaranteed, both generals can be certain of each other’s intent and state. This setup trivially scales to an $N$-node system under identical reliability assumptions.

Real-World Parallel: Distributed Database Commit

In distributed database terms, this represents a multi-node transaction commit:

• Coordinator / General A: “Can we commit the write price = 2000?”
• Worker / General B: “Prepared to commit.”
• Coordinator / General A: “Commit transaction.”
• Worker / General B: “Transaction committed.”

If any node cannot commit, all nodes abort. Under perfect reliability, transactions maintain strict atomicity.

---

Scenario 2: The Unreliable Channel (The Infinite ACK Dilemma)

In reality, networks drop packets. Let us trace what happens when messengers can be captured:

Failure Case 1: Dropped Confirmation

1. General A sends a messenger: “Let’s attack tomorrow at 06:00 AM.”
2. General B receives the message and sends a reply: “Agreed, 06:00 AM.”
3. The messenger carrying B’s reply is captured in the valley.

sequenceDiagram
    participant A as General A
    participant B as General B
    A->>B: Propose attack at 06:00 AM
    Note over B: Receives message
    B--xA: Reply: Agreed (CAPTURED)
    Note over A: No reply received.<br/>Must NOT attack!
    Note over B: Assumes agreement.<br/>Attacks at 06:00 AM!

• General B’s perspective: “I agreed to the attack, so General A will proceed. I must attack at 06:00 AM.”
• General A’s perspective: “I never received confirmation. Attacking alone is suicide, so I will not attack.”
• Outcome: Army B attacks alone and is destroyed.

Failure Case 2: The Need for Acknowledgement of Acknowledgement

To prevent General B from attacking without knowing if A received the agreement, B stipulates:

“I will only attack if I receive an acknowledgement that General A got my confirmation.”

1. A sends proposal: “Attack at 06:00 AM.”
2. B sends agreement: “Agreed, pending your ACK.”
3. A sends ACK: “I received your agreement.”

Now consider General A’s situation:

• Did General B receive the ACK?
• If General A’s ACK was intercepted, General B will abort the attack.
• Therefore, General A cannot attack unless General A knows that General B received the ACK.
• To be sure, General A must require General B to send an ACK for the ACK.

This creates an infinite regress:

$\text{Message} \longrightarrow \text{ACK}_1 \longrightarrow \text{ACK}_2 \longrightarrow \text{ACK}_3 \dots \longrightarrow \text{ACK}_n$

Because the last messenger sent could always be captured, the sender of that final message is left in complete uncertainty. Neither general can ever establish common knowledge (i.e., “I know that you know that I know…”).

Therefore, it is mathematically impossible to devise a deterministic protocol that guarantees consensus over an unreliable network using a finite number of messages.

---

How Real-World Distributed Systems Cope

If reaching consensus over an unreliable network is theoretically impossible, how do production distributed databases, Raft clusters, and payment gateways work every day?

Real-world systems solve this by abandoning the assumption of 100% unreliability and adopting probabilistic and heuristic guarantees.

1. Bounded Unreliability and Probabilistic Delivery

Engineers do not assume that a network link has a 100% drop rate forever. Instead, we assume a network is reliable up to a certain probability (e.g., message loss probability $p < 1$).

If the probability of a messenger being captured is $p = 0.5$:

• Sending $1$ message yields a $50\%$ success rate.
• Sending $2$ independent messages yields a $1 - (0.5)^2 = 75\%$ success rate.
• Sending $10$ messages yields a $1 - (0.5)^{10} = 99.9\%$ success rate.

By redundancy and repeated attempts, the probability of complete message failure drops toward zero.

2. Timeouts and Retries

In practical protocols (such as TCP, HTTP RPCs, or database commit protocols), systems use idempotency, timeouts, and retries:

• When a client sends a request to a server, it starts a timer.
• If no response arrives before the timer expires, the client assumes packet loss or server delay and retries.
• Retries transform a link with transient failures into an effectively reliable link from the application perspective, provided the partition eventually heals.

3. Pre-Committed Defaults / Asymmetric Protocols

Another heuristic is removing symmetric dependency between the actors:

• General A unconditionally decides to attack at 06:00 AM regardless of B’s response.
• General A then sends 50 messengers carrying this single directive.
• If General B receives even one messenger, B attacks. If none make it, A still attacks (accepting defeat risk, but removing the infinite ACK requirement).

In modern consensus protocols (like Paxos or Raft), this asymmetry is formalized using designated leaders and majority quorums ($Q = \lfloor n/2 \rfloor + 1$). A node does not wait for unanimous agreement from every single peer; it only waits for a quorum, allowing the system to progress even when a minority of links are down.

---

Comparison: Two Generals vs. Byzantine Generals

It is critical to distinguish the Two Generals’ Problem from the related Byzantine Generals’ Problem:

Dimension	Two Generals’ Problem	Byzantine Generals’ Problem
Core Fault Model	Unreliable communication links (packet drops, partitions).	Arbitrary / Malicious nodes (traitors, forged messages, software bugs).
Node Integrity	Honest nodes; generals always follow the protocol.	Untrusted nodes; generals can lie or coordinate maliciously.
Channel Reliability	Assumed unreliable (messengers intercepted).	Typically assumed reliable (messages delivered without tampering).
Solvability	Impossible deterministically with finite messages.	Solvable if strictly fewer than $1/3$ of nodes are Byzantine ($3m + 1$ total nodes required).

---

Key Takeaways

1. Deterministic Consensus is Impossible over Unreliable Links: The Two Generals’ Problem proves that no finite-message protocol can guarantee agreement when messages can be dropped silently without confirmation.
2. The Infinite Acknowledgement Loop: Because any final acknowledgement can itself be lost, neither side can ever be completely certain that the other has entered the committed state.
3. Practical Engineering Relies on Heuristics: Distributed databases and network protocols do not assume 100% channel unreliability. They rely on bounded error rates, idempotent retries, exponential backoff, timeouts, and quorum majorities to build dependable systems on top of fundamentally imperfect networks.