Skip to main content
[N|S]nosqlsummer
All papers
2001classic paperspaper #14 / 29

Paxos Made Simple

by Leslie Lamport

Paxos Made Simple
Paxos Made Simple by Leslie Lamport The Paxos algorithm, when presented in plain English, is very simple.

Why this paper matters

Leslie Lamport’s Paxos Made Simple (2001) demystifies distributed consensus by stripping the problem to its core and presenting a protocol that is both mathematically rigorous and conceptually accessible. The paper arrives at a pivotal moment in distributed systems history: the late 1990s and early 2000s, when monolithic databases struggled to scale across geographies and failures, and the internet began demanding fault-tolerant, self-healing infrastructure. Prior to Paxos, consensus algorithms were shrouded in cryptic formalisms or buried under impractical assumptions. Lamport’s genius was to reframe the problem not as a puzzle, but as a clear interaction between proposers, acceptors, and learners, governed by a handful of rules that guarantee safety under asynchrony and partial failure. This simplification didn’t just make Paxos teachable-it made it adoptable. The paper’s influence extends far beyond theory: it seeded the architectural blueprint for modern strongly consistent distributed databases, enabling systems that could survive network partitions, node crashes, and clock skew without sacrificing correctness.

In 2026, Paxos remains the canonical foundation for consensus in distributed databases and cloud-native storage engines. While newer protocols like Raft have gained popularity for their operational simplicity, Paxos provides the deeper semantic guarantees that modern systems rely on when correctness is non-negotiable. Its enduring relevance stems from the fact that consensus is not a solved problem: even in the AI era, where systems are increasingly adaptive and self-optimizing, the need to agree on a single value across unreliable nodes persists-whether for metadata, leader election, or transaction sequencing. Paxos, in its simplicity and generality, provides the intellectual scaffolding that allows engineers to reason about correctness in systems that operate at planetary scale. Without Lamport’s distillation, today’s databases would be far more fragile, less predictable, and harder to debug.

Paxos also introduced a critical mindset shift: from viewing distributed systems as collections of nodes to modeling them as protocols governed by strict invariants. This perspective permeates modern engineering culture, from database design to microservices orchestration. Engineers now routinely ask, “What invariants does this system preserve?” and “What happens if two nodes believe different things?”-questions that Paxos made central to distributed systems discourse. The paper’s legacy is not just in the systems it inspired, but in the way it reshaped how we think about distributed correctness.

Key contributions

  • Formalizes the consensus problem in a minimalist model: proposers, acceptors, learners, and a set of rules ensuring safety despite asynchrony and message loss.
  • Introduces the Paxos algorithm as a two-phase protocol: prepare/promise and accept/accepted, with a clear safety proof based on ballot numbers and accepted values.
  • Demonstrates that consensus can be achieved without synchronized clocks or bounded message delays, relying only on message ordering and majority agreement.
  • Presents the “Synod” problem as a special case of consensus, showing how it generalizes to real-world systems like replication and leader election.
  • Clarifies the relationship between safety and liveness, proving that safety is achievable in asynchronous systems while liveness requires partial synchrony assumptions.
  • Provides a human-readable derivation that exposes the algorithm’s intuition, making it accessible to engineers without sacrificing formal guarantees.

Impact on modern systems

Paxos’s direct lineage is visible in many of today’s most influential distributed databases and storage systems, each inheriting specific design choices from its core model. Google’s Spanner (2012), the first globally distributed database to offer external consistency and SQL semantics, uses a variant of Paxos for its TrueTime-based consensus layer. Spanner’s implementation replaces Lamport’s simple ballot numbers with hybrid logical clocks and GPS/atomic-clock-derived timestamps to bound uncertainty, but the underlying two-phase exchange of proposals and promises is unmistakably Paxos. This allows Spanner to achieve linearizability across data centers while tolerating clock skew and network partitions-something no earlier system could guarantee at global scale.

Similarly, CockroachDB (2014-present), an open-source, geo-distributed SQL database, adopts a Raft-inspired variant of Paxos for its consensus module. While Raft simplifies leader election and log replication for human operators, its consensus core is structurally equivalent to Paxos’s Synod algorithm. CockroachDB leverages this to provide ACID transactions across regions with latency budgets under 100ms in many deployments. The system maps Paxos acceptors to Raft nodes, and proposers to client-driven transaction coordinators, thereby preserving the safety guarantees Lamport formalized. This design choice underpins CockroachDB’s ability to scale writes across continents without sacrificing serializability-a direct consequence of Paxos’s clarity.

YugabyteDB (2017-present), another PostgreSQL-compatible distributed SQL system, takes an even more explicit approach: it implements Raft for consensus but credits Paxos as the theoretical backbone of leader-based replication. Yugabyte’s engineers emphasize that Raft’s safety proof is built on the same invariants Lamport established-majority quorums, ballot progression, and value acceptance rules. The system also inherits Paxos’s robustness to message reordering and duplication, using idempotent client requests and deterministic conflict resolution to prevent split-brain scenarios.

Beyond relational systems, the influence of Paxos extends to key-value stores like FoundationDB (2013, acquired by Apple), which uses a layered consensus architecture where Paxos-like protocols coordinate storage servers. FoundationDB’s durability guarantees-surviving simultaneous node failures-derive directly from the quorum intersection properties Lamport proved. Even in systems like Amazon Dynamo (2007), which is often cited for its eventual consistency model, the underlying conflict resolution mechanisms implicitly rely on consensus principles similar to Paxos when strong consistency is required during conflict scenarios.

The paper’s emphasis on majority quorums and ballot monotonicity has also shaped modern failure detection and leader election mechanisms. Systems like ScyllaDB and TiDB rely on these principles to avoid split-brain during node recovery, proving that Lamport’s simple rules scale from whiteboard proofs to production fleets running millions of IOPS. In Apache Cassandra (2008), while the default model is eventual consistency, operators can enable “hinted handoff” and “read repair” mechanisms that converge toward consensus-like behavior under specific configurations-illustrating how Paxos’s quorum principles permeate even systems not originally designed for strong consistency.

Paxos’s impact is also visible in modern cloud-native storage engines like Google Bigtable (2006), where consensus protocols are used to synchronize metadata across tablet servers. While Bigtable itself relies on a centralized Chubby lock service for coordination, the underlying need to agree on metadata versions across distributed components reflects the same problem Paxos was designed to solve. Similarly, systems like etcd and ZooKeeper, which underpin Kubernetes and distributed coordination services, implement variants of Paxos to maintain strongly consistent configuration state across clusters.

AI era: how LLMs and vector databases relate to this paper

The AI revolution has reintroduced distributed consensus at multiple layers-from model training coordination to inference routing, state management, and semantic indexing. Vector databases like Pinecone, Weaviate, Qdrant, and pgvector, which power retrieval-augmented generation (RAG), are not merely storage engines; they are consensus substrates for semantic state. Each vector embedding represents a distributed fact about meaning, and queries must agree on which embeddings are relevant across shards and replicas. Here, Paxos’s core insight-agreement on a single value across unreliable nodes-maps directly to agreement on the top-k nearest neighbors in high-dimensional space. Modern vector databases employ leader-based consensus (often Raft, but conceptually rooted in Paxos) to synchronize index updates and ensure that all replicas return consistent results despite network partitions or stale caches. When an LLM generates a response using a RAG pipeline, the quality of the answer depends on the system’s ability to reach consensus on the retrieved context-precisely the problem Lamport solved.

In large-scale LLM inference systems, consensus reappears in agent orchestration. Multi-agent AI systems, where agents delegate tasks across services or tools, require a shared notion of task state and outcome. Tools like LangChain and LlamaIndex implicitly rely on distributed state stores that must agree on whether an agent’s plan succeeded or failed. These stores often use consensus protocols inspired by Paxos to coordinate state transitions, especially in systems that span microservices or serverless functions. The latency of LLM inference-often dominated by retrieval and planning steps-is directly influenced by the consensus overhead required to validate state changes before proceeding. Systems that minimize this overhead (e.g., via speculative execution or leader caching) are essentially optimizing the liveness side of Paxos’s safety/liveness tradeoff.

Semantic indexes themselves are distributed artifacts that must be updated atomically. When a vector database refreshes its index after new documents are ingested, it must ensure that all replicas agree on the version of the index used for a query. This is a consensus problem: which version of the index is authoritative? Modern systems like Milvus and Vespa use Raft or similar protocols to synchronize index snapshots, with ballot numbers replaced by vector clock timestamps or epoch counters. The idea of progressing through numbered proposals (prepares and accepts) is echoed in the way these systems manage schema migrations and embedding updates.

Even LLM-driven query planning benefits from Paxos-like reasoning. When an LLM generates a complex SQL or NoSQL query plan across heterogeneous stores, the planner must ensure that the plan is executed consistently despite partial failures. Tools like LangChain’s SQL agent or Haystack use consensus-inspired mechanisms to validate intermediate results before proceeding-essentially performing a lightweight, application-level consensus on query correctness. This mirrors the learner role in Paxos: once a value is chosen, it must be observed consistently by all participants.

Beyond retrieval and orchestration, consensus plays a critical role in LLM serving infrastructure. Systems like vLLM and TensorRT-LLM use distributed inference to manage model shards and KV-cache synchronization across GPUs. While these systems prioritize throughput and latency, they still rely on consensus-like mechanisms to ensure that generated tokens are consistent across replicas, especially in speculative decoding or beam search scenarios. The need to agree on the “chosen” token sequence before proceeding to the next step is a direct application of Paxos’s core problem: agreeing on a single value in the presence of unreliable communication.

The rise of embedding serving platforms like NVIDIA’s NeMo Retriever and Cohere’s embedding services further underscores the relevance of consensus. These platforms must synchronize embeddings across multiple replicas to ensure that semantic search results are consistent and reproducible. In high-availability deployments, consensus protocols derived from Paxos are used to coordinate embedding updates and query routing, ensuring that users receive identical results regardless of which replica handles the request. This is particularly critical in applications like legal or medical RAG systems, where consistency is legally or clinically required.

In short, the AI era has not obsoleted Lamport’s protocol-it has repurposed it. Whether for synchronizing embeddings, coordinating agent state, or validating LLM outputs, distributed agreement remains a prerequisite for reliable intelligence at scale. The simplicity of Paxos allows engineers to reason clearly about correctness in systems where correctness is no longer just about data integrity, but about the integrity of thought itself. As AI systems grow more complex and interconnected, the need for robust consensus mechanisms will only intensify, ensuring that Paxos’s legacy endures for decades to come.

Further reading

Paxos Made Simple — architecture diagram