proomt

Search

Search posts, papers, and topics

Hall of Fame

Hall of FameLeslie Lamport200120 min readpaperadvanced

Paxos Made Simple

Read on azurewebsites.netHN 65·7 comments

Summary

Lamport’s “Paxos Made Simple” formalizes the classic Paxos consensus algorithm, detailing its two‑phase prepare/accept protocol and the invariants that guarantee safety under an asynchronous crash‑failure model. It shows how majority quorums, monotonically increasing proposal numbers, and persistent acceptor state ensure a single value is chosen and learned.

  • Paxos uses a two‑phase protocol: a prepare phase to gather promises and the highest accepted value, followed by an accept phase to commit a proposal.
  • Safety relies on majority quorum intersection and the invariant that any higher‑numbered proposal must adopt the value of the highest accepted proposal in the quorum.
  • Acceptors must persist the highest prepare number and the highest accepted proposal to survive crashes and restarts.
  • Proposers must generate unique, monotonically increasing proposal numbers and may adopt the value from the highest numbered accepted proposal they learn.

Any engineer building fault‑tolerant distributed services needs to understand Paxos fundamentals to design or reason about consensus mechanisms.

9/10
distributed systemsalgorithmsfault toleranceconsensuspaxos

Related reading

  1. In Search of an Understandable Consensus Algorithm (Raft)

    Raft is a consensus algorithm for managing replicated logs, designed to be significantly more understandable than Paxos. It achieves this by separating leader election, log replication, and safety, and includes a novel mechanism for cluster membership changes. User studies confirm Raft's improved learnability over Paxos.

    Hall of Famegithub.io63 minpaperHN8126

  2. Impossibility of Distributed Consensus with One Faulty Process

    The FLP paper proves that in an asynchronous distributed system, it's impossible to reach consensus if even one process can crash, assuming no synchronized clocks or reliable failure detection. This fundamental impossibility result means any practical consensus protocol must relax one of these assumptions.

    Hall of Famemit.edu20 minpaperHN164

  4. Simple Made Easy

    Rich Hickey argues that simplicity, not easiness, is the foundation of reliable software. He outlines how to choose simple constructs and design abstractions to keep systems understandable and changeable.

    Hall of Fameinfoq.com9 mintalkHN16836

  5. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging

    ARIES is a transaction recovery method using write-ahead logging (WAL) that supports fine-granularity locking and partial rollbacks. It introduces the "repeating history" paradigm to redo all missing updates before performing rollbacks of loser transactions during system restart, using Log Sequence Numbers (LSNs) on pages.

    Hall of Famestanford.edu155 minpaper

  6. How Uber Protects Against Retry Storms

    Uber developed a context-aware mechanism to prevent retry storms in deep microservice dependency chains. It introduces "error ownership" where services claim errors they originate and unclaim errors they propagate, allowing upstream callers to make informed retry decisions and avoid amplifying load on already struggling services.

    Hacker News front pageuber.com12 minHN11949