Understanding the Paxos Consensus Algorithm Through a Three Kingdoms Analogy

Preface

Distributed systems are everywhere in daily life. The author first learned about distributed systems from a well‑written technical essay that won a competition, and provides a link to that article.

The first two lectures cover distributed theory, including the four major theories, with links to articles about the Byzantine Generals problem and the BASE, CAP, ACID concepts.

This article focuses on the Paxos consensus algorithm, one of the eight major distributed protocols.

Paxos Algorithm

Paxos is the classic algorithm for distributed consensus; many modern consensus algorithms (e.g., Raft) are built on it, so learning Paxos is essential.

Paxos consists of two parts:

Basic Paxos : how multiple nodes reach consensus on a single value ( Proposal Value ).

Multi‑Paxos : running multiple Basic Paxos instances to reach consensus on a sequence of values.

Basic Paxos is the core of Multi‑Paxos, so it receives special attention.

Three Kingdoms Paxos

In the Liu Bei group there are two strategists (Zhuge Liang and Pang Tong) who act as proposers, three generals (Guan Yu, Zhang Fei, Zhao Yun) who act as acceptors, and two civil officials (Fa Zheng and Ma Liang) who act as learners.

Roles

Proposer: proposes a value for voting.

Acceptor: votes on each proposal and stores the accepted value.

Learner: learns the final decided value without participating in voting.

Proposer or Acceptor?

A node can act as both proposer and acceptor, similar to the coordinator in a two‑phase commit protocol.

As an acceptor, it receives client requests (e.g., Zhuge Liang receives Liu Bei’s plan).

As a proposer, it initiates the two‑phase commit after gathering responses.

Diagram: Node 1 is both proposer and acceptor; Nodes 2 and 3 are acceptors.

Zhuge Liang vs. Pang Tong

Both propose plans: Zhuge Liang attacks from the north, Pang Tong from the south. The conflict between the two plans illustrates the consensus problem, which Paxos resolves in two phases: Prepare and Accept.

Prepare Phase

Proposers send a Prepare Request containing only the proposal number (no value) to all acceptors.

Sending Prepare Requests

Zhuge Liang sends proposal number 1.

Pang Tong sends proposal number 2.

Acceptors receive these requests at different times (e.g., Guan Yu at 8 o’clock, Zhang Fei at 9 o’clock, Zhao Yun at 12 o’clock).

First Round of Responses

Acceptors that have not seen any prior proposal reply with “No Proposal”. This tells the proposer that any request with a number ≤ 1 will be ignored.

Second Round of Responses

When a higher‑numbered prepare request arrives, acceptors again reply “No Proposal” because they have not yet accepted any value.

Diagram shows the timing of these messages.

Accept Phase

Sending Accept Requests

After receiving a majority of prepare responses, each proposer selects the value associated with the highest numbered proposal it learned (if any). Since both Zhuge Liang and Pang Tong received only “No Proposal” responses, they each send an accept request with their own values: proposal 1 with value “North” and proposal 2 with value “South”.

Receiving Accept Requests

Acceptors compare the incoming proposal number with the highest number they have promised to accept. If the incoming number is lower, they reject it. Thus, Guan Yu, Zhang Fei, and Zhao Yun reject Zhuge Liang’s proposal 1 (because they have promised to consider number 2) and accept Pang Tong’s proposal 2, achieving consensus on “South”.

Learners Join In

When acceptors accept a proposal, they notify learners. Learners (Fa Zheng and Ma Liang) also adopt the decided value “South”.

Summary

Basic Paxos achieves consensus via a two‑phase commit: Prepare and Accept.

It provides fault tolerance; the system continues to operate as long as a majority of nodes are alive.

Proposal numbers act as priorities, ensuring three guarantees about prepare and accept handling.

Bonus Question

If two acceptors have already accepted proposal [2, South] and a new proposer submits proposal [8, East], what will be the final plan for the three generals? (Readers are invited to comment.)

Book Giveaway

The author is giving away three copies of “Real‑World Algorithms: A Beginner’s Guide”. Readers can reply “Trial” to the public account to request a sample.

Participation ends on January 14 at 9 p.m.; the three comments with the most likes win.

Recommended description: The first technical book for learning algorithms, focusing on simple, real‑world problems and requiring only basic math and computer knowledge.

Click “Read Original” for more details.

- END -

Join the study group by scanning the QR code and remarking “[Study]”.