Understanding Paxos: A Beginner’s 30‑Minute Guide with Real‑World Analogy

Paxos algorithm was proposed by Leslie Lamport in 1990 as a message‑passing, highly fault‑tolerant consensus algorithm. It is used in Google’s Chubby, MegaStore, Spanner, and Hadoop’s ZooKeeper, though implementations differ from the original description.

The article aims to help a beginner understand Paxos in half an hour, avoiding heavy mathematics and complex theory by using everyday analogies.

Imagine 25 travelers scattered across the country who need to agree on a destination for a Mid‑Autumn trip. Instead of a simple group chat (shared memory), Paxos assumes communication can fail, so the travelers can only send SMS messages, and the system must reach agreement even if some participants become unreachable.

Five additional people act as “team leaders.” Each traveler (proposer) sends a request to any of the leaders. Leaders only communicate with the most recent request they have received, based on timestamp, ensuring fairness.

In the first (proposal) phase, a traveler must obtain affirmative responses from a majority of leaders (more than half) before proceeding. Only then can the traveler enter the second (acceptance) phase.

During the acceptance phase, the traveler who secured communication receives the leaders’ chosen destinations. If a majority of leaders have already decided on a location, the traveler adopts that decision; otherwise, the traveler proposes a new destination, and leaders may update their choices based on the latest request.

This process mirrors Paxos: proposers correspond to travelers, acceptors to leaders, and timestamps to epoch numbers. Consensus is reached when a majority of acceptors agree on a value, providing strong fault tolerance because the system works as long as more than half of the nodes remain operational.

The article also touches on related concepts such as the need for majority agreement (2N+1 nodes, N+1 required), the distinction between Paxos consistency and ACID consistency in relational databases, and mentions other distributed systems like HDFS and Amazon Dynamo that solve similar problems with different approaches.

Finally, it notes that Paxos assumes reliable channels (messages are not altered) while allowing message loss, and that Byzantine fault tolerance is a separate challenge.

Source: https://www.cnblogs.com/esingchan/p/3917718.html