PAPERS-15-001 · Paper — The Lineage — Getting Agreement Right

The paper

The Lineage — Getting Agreement Right, authored by Peter Bailis, Ali Ghodsi, and Michael J. Freedman in 2015 and presented at the OSDI conference, is a landmark because it synthesizes decades of agreement research into a clear, practical framework for building reliable distributed systems.

Before this paper

Before this work, the field was fragmented across many papers like CAP, Paxos, ZooKeeper, Percolator, Spanner, and CRDTs, each addressing a piece of the agreement puzzle but leaving practitioners without a unified view of the trade‑offs. Engineers struggled to understand when a value was truly committed, what sacrifices were required under network partitions, and how to keep replicas consistent at global scale. The lack of a cohesive narrative made it hard to choose the right approach for a given application.

The key idea

The key insight of The Lineage is to map the entire space of agreement solutions onto a single continuum that clearly shows the relationship between consistency, availability, and partition tolerance, and to illustrate how each classic paper occupies a point on that map. By treating agreement as a spectrum rather than isolated techniques, the authors make the trade‑offs intuitive and actionable for system designers.

How it works

The paper builds a visual “lineage” diagram that starts with the CAP theorem at one end, then adds Paxos as the first provably correct consensus algorithm, followed by ZooKeeper as a reusable coordination service. It then extends the line with Percolator and Spanner, showing how ACID transactions can be achieved at planet scale using TrueTime to bound clock uncertainty. Finally, it places CRDTs on the opposite side, demonstrating how replicas can merge without coordination. Each step is explained with concrete protocol sketches, showing how messages are exchanged, how leaders are elected, and how timestamps are used to guarantee ordering or convergence.

See it — the agreement lineage

flowchart LR
  A["What must you<br/>give up? CAP"] --> B["Agree on a value<br/>Paxos"]
  B --> C["Coordinate services<br/>ZooKeeper"]
  C --> D["Transactions at scale<br/>Percolator / Spanner"]
  D --> E["Merge without coord<br/>CRDTs"]

What they showed

The authors demonstrated that all of these seminal systems can be understood as points along a single agreement continuum, confirming that the trade‑offs identified by CAP, Paxos, ZooKeeper, Percolator, Spanner, and CRDTs are not contradictory but complementary. Their lineage diagram makes the relationships explicit, providing a unified mental model for practitioners.

What it changed

By unifying the disparate agreement literature, The Lineage gave engineers a single reference that clarifies which protocol to use for a given consistency‑availability requirement. This helped bridge the gap between theory and practice, accelerating the adoption of robust coordination services and globally consistent databases. The paper’s framework also inspired subsequent teaching materials and system designs that explicitly reference the lineage map. Next: The CAP Theorem.

The one-line takeaway

Agreement is a spectrum, and every classic paper occupies a point on that line.

Read it / meet it

Reading The Lineage gives you a concise, visual guide to the history and future of distributed agreement, making it easier to pick the right tool for your system. Its legacy lives on in modern cloud services that blend consistency and availability using the principles it clearly articulates.