Understanding Basic Paxos Through the Three-Generals Problem Analogy

Background

In computer communication theory there is the famous Two Generals problem, which shows that two parties communicating via ACK can never reach consensus because there is always an in‑flight ACK that needs confirmation.

1) The parties need to reach consensus. 2) Only a single consensus is required. 3) The channel may lose, delay, or replay messages, but messages are not tampered with.

Basic Paxos is similar to the Two Generals problem. The original story uses the Greek parliament, which many find hard to understand, so this article replaces it with a more familiar three‑army scenario.

Assumed Three‑Army Problem

1) One Red army camps in a valley, surrounded by three Blue armies on the hills. 2) The Red army defeats any single Blue army; two or more Blue armies together defeat the Red army. 3) The Blue armies must synchronize their attack time, but the only communication method is a messenger walking into the valley, who may be captured or delayed. 4) Each army has one advisor who proposes an attack time and one commander who must approve it. An advisor’s proposal needs approval from at least two commanders to be valid. 5) Question: Is there a protocol that allows the Blue armies to synchronize their attack time?

Scenario: Two Proposers Sequential Proposals

1) Proposer 1 sends a prepare message with number 1 to the three commanders. 2) All three commanders, having no prior number, store number 1 and reply “ok”. 3) Proposer 1 receives at least two “ok” replies and sends a commit with (1, attack‑time 1). 4) All commanders store (1, attack‑time 1) and reply “Accepted”. 5) Proposer 1 receives at least two “Accepted” replies and knows the attack time is chosen. 6) Proposer 2 sends a prepare with number 2. 7) Commanders see number 2 > number 1, store number 2, and reply with the previously accepted (1, attack‑time 1). 8) Proposer 2 adopts the earlier accepted time, sends commit (2, attack‑time 1). 9) Commanders store (2, attack‑time 1) and reply “Accepted”. 10) Proposer 2 receives at least two “Accepted” replies and confirms the attack time.

Scenario: Two Proposers Interleaved Proposals

1) Proposer 1 sends prepare (1). 2) Commander 1 and Commander 2 record (1) and reply “ok”; the messenger to Commander 3 is captured, so Commander 3 receives nothing. 3) Proposer 2 simultaneously sends prepare (2). 4) Commander 2 and Commander 3 record (2) (Commander 2 because 2 > 1, Commander 3 because it had no prior proposal) and reply “ok”; the messenger to Commander 1 is captured. 5) Proposer 1, after receiving two “ok”, sends commit (1, attack‑time 1) to the two responders. 6) Commander 1 accepts and replies “Accepted”; Commander 2 rejects because it has a higher number (2) and replies “Rejected, 2”. 7) Proposer 2, after two “ok”, sends commit (2, attack‑time 2). 8) Commander 2 and Commander 3 accept and reply “Accepted”. 9) Proposer 2 receives at least two “Accepted” replies and confirms the attack time. 10) Proposer 1 receives one “Accepted” and one “Rejected, 2”, so it starts a new proposal with number 3. 11) Commanders react to proposal 3: Commander 1 and Commander 2 store number 3 (both higher than their previous numbers) and return their previously accepted times; Commander 3 receives nothing. 12) Proposer 1, after two replies, selects the higher number’s time and sends (3, attack‑time 2). 13) Commander 1 and Commander 2 accept (3, attack‑time 2) and reply “Accepted”. 14) Proposer 1 receives at least two “Accepted” replies and knows the majority has accepted the time.

Summary

1) Participants aim for cooperative consensus rather than adversarial competition; violating the protocol (e.g., a proposer forcing its own time) introduces Byzantine behavior. 2) Unlike typical request/response protocols that only return success or failure, Basic Paxos’s prepare and commit phases also return previously accepted values. 3) In the three‑army analogy, the proposer learns the accepted time, not the commanders; during interleaved proposals, a commander may hold an outdated time, showing that Paxos achieves consensus among the proposers, not necessarily a visible agreement for every participant. 4) The two scenarios illustrate different client behaviors in distributed systems: concurrent clients, sequential clients with a pause, and a single client retrying after a failure.

Postscript

The article draws on two references: “Paxos Algorithm Detailed Explanation (Part 1) – Using Real‑World Stories” and a discussion on why Paxos does not solve the original Two Generals problem, even when extended to three armies. The analogy helps illustrate Paxos’s mechanics while highlighting its limitations.