Understanding Paxos and Consensus Algorithms in Distributed Systems

This article introduces distributed consistency and consensus algorithms, focusing on Paxos, which solves crash fault tolerance (CFT) but not Byzantine fault tolerance (BFT). It explains why achieving full consistency in a distributed system requires sequential consistency across all nodes.

The text classifies consensus algorithms into crash fault tolerance (e.g., Paxos, Raft, ZAB) and Byzantine fault tolerance (e.g., FBFT, PoW). It also describes the Byzantine Generals Problem as an illustration of malicious nodes interfering with consensus.

Section "Paxos" covers its background, history, and the basic two‑phase protocol (Prepare and Accept). It details the roles of Proposer, Acceptor, and Learner, and walks through a simple proposal where a client writes an address value (e.g., "Shenzhen") that must be agreed upon by a majority of acceptors.

The article then discusses handling concurrent proposals, the need for proposal numbering, and how acceptors reject lower‑numbered proposals. It explains how the protocol resolves conflicts, avoids deadlock, and deals with edge cases such as proposer failures, livelocks, and changing cluster size.

To improve performance, the text introduces Multi‑Paxos, which elects a single leader (Proposer) to eliminate the Prepare phase for subsequent proposals. It compares Multi‑Paxos with other consensus algorithms like ZAB and Raft, highlighting differences in leader election, log handling, and implementation complexity.

Finally, the article summarizes the two core challenges of consensus algorithms—proposing a value and achieving agreement among nodes—and notes that the choice of algorithm depends on the specific scenario and requirements.