Chapter 8 catalogued everything that goes wrong in a distributed system: lost packets, paused processes, unreliable clocks. Chapter 9 is the constructive answer. Instead of handling every fault at every call site, we build a few general-purpose abstractions with precisely stated guarantees and let applications rely on them the way they rely on transactions on a single node.

The central abstraction is consensus: getting nodes to agree on a value despite failures. The chapter's main result is that several problems which look different on the surface, such as linearizable registers, total order broadcast, atomic commit, leader election, locks and uniqueness constraints, are all equivalent to consensus. Knowing that equivalence is what separates a candidate who can name Raft from one who can explain why a system needs it.

In one minute

• Linearizability is a recency guarantee on single objects: the system behaves as if there were one copy of the data and each operation took effect atomically at some instant between its call and its response. It is not serializability, which is a transaction isolation property about multi-object operations.
• Linearizability is needed for distributed locks and leader election, uniqueness constraints, and wherever two communication channels can race (a database write followed by a queue message).
• Single-leader replication can be linearizable if reads go to the leader or synchronously updated followers; multi-leader and Dynamo-style quorums are not, even with w + r > n.
• The cost of linearizability is availability during partitions and latency always. CAP is one narrow statement about partitions, not a design framework.
• Causal consistency is the strongest model that stays available under partitions. Causality is a partial order; linearizability imposes a total order.
• Lamport timestamps give a total order consistent with causality, but only in hindsight; they cannot decide a uniqueness constraint at request time because the order is never known to be final.
• Total order broadcast (reliable, totally ordered message delivery) is equivalent to consensus; a linearizable compare-and-set register can be built from it and vice versa.
• Two-phase commit gives atomic commit across nodes but blocks, holding locks, when the coordinator fails. 2PC is not fault-tolerant consensus and is unrelated to 2PL.
• Fault-tolerant consensus (Paxos, Raft, Zab, Viewstamped Replication) uses epochs and two overlapping majority quorums so only one leader per epoch can decide; it tolerates a minority of crashes.
• ZooKeeper and etcd package consensus as a linearizable key-value store with watches and ephemeral nodes so applications can outsource leader election, locks and membership.

Consistency guarantees

Most replicated databases offer at least eventual consistency: stop writing and wait, and all replicas converge. This says nothing about when, and it allows a client to read a value and then read an older one from another replica a moment later. Code written against eventual consistency works in tests and breaks under faults, because the anomalies appear only when the network is slow or a node is down.

Stronger models cost performance and availability but are far easier to program against. The chapter examines the strongest single-object model (linearizability), then the ordering guarantees underneath it (causality, total order), then how to implement them with consensus.

Linearizability

What it means

Linearizability (also called atomic consistency or strong consistency) is the illusion that there is one copy of each object and every read and write happens atomically at a single point in time. Formally, each operation has an invocation and a response; a history is linearizable if you can place each operation at one instant between those two moments so that the resulting sequence is a valid serial execution of the object.

Two consequences are worth stating precisely. First, once any client has read a new value, every later read by any client returns that value or a newer one; a read may not flip back to the old value because it hit a different replica. Second, operations that overlap in time may be ordered either way, but the chosen order has to be the same for everyone.

A practical test: record every operation's invocation and response and search for a serial order respecting both real time and register semantics; Jepsen's Knossos checker does this against real databases. Linearizability concerns single objects and says nothing about multi-object transactions.

Linearizability versus serializability

	Linearizability	Serializability
Kind of guarantee	Recency of reads and writes on one object	Isolation of multi-object transactions
Ordering	Consistent with real time	Equals some serial order, not necessarily real time
Violated by	Stale replica reads	Write skew, phantoms, lost updates
Implemented by	Single leader with synchronous replication, consensus	2PL, serial execution, serializable snapshot isolation (SSI)

A system can provide both; the combination is strict serializability. Two-phase locking and actual serial execution are typically linearizable as well. SSI is deliberately not linearizable: it reads from a consistent snapshot and may not see writes that committed after the snapshot, even if they completed before the read in real time. Readers never block writers, which is the point, but an SSI database is not a linearizable store.

Where linearizability is needed

Locking and leader election. Single-leader replication requires everyone to agree on who the leader is. Two nodes both believing they are leader (split brain) accept conflicting writes. Election is usually built on a distributed lock, and that lock must be linearizable, or two nodes can both read "free" from stale replicas and both acquire it. ZooKeeper and etcd exist mainly to provide this lock.

Constraints and uniqueness. A username must be unique, an account must not go negative, a seat cannot be sold twice. Enforcing such constraints at write time is the lock problem again: "claim username X" is a linearizable compare-and-set on X. Loosely enforced constraints (overbook and apologise) are a legitimate alternative, developed in Chapter 12, but hard constraints need linearizability.

Cross-channel timing dependencies. A web server writes a full-size image to a file store and separately enqueues "resize image 123". The worker gets the message and reads the store, which, if not linearizable, may return an old version or nothing. There are two channels (store replication and the queue) with no ordering between them. Linearizable storage closes the race; otherwise the data must travel through a single channel or carry explicit causal metadata.

Implementing linearizable systems

Replication method	Linearizable?	Why
Single-leader, reading from leader or sync followers	Potentially	One authoritative copy; but a node that wrongly believes it is leader serves stale data, and async failover loses writes
Consensus (Raft, Zab, Paxos-based)	Yes	Includes the measures that prevent split brain and stale replicas; how ZooKeeper and etcd get it
Multi-leader	No	Concurrent writes on different leaders must be reconciled; there is no single copy
Leaderless quorums	Not in practice	A reader can observe a write before a later reader does, even with strict quorums; LWW with wall clocks is definitely not

The quorum anomaly surprises people. With n = 3, w = 3, r = 2, a writer's messages reach replicas at different times. Reader A hits the replica that already has the new value and returns it; reader B starts later but hits two replicas that have not yet received it and returns the old value. Overlapping quorums do not impose a real-time order. Synchronous read repair and read-before-write narrow the gap at a performance cost, but a linearizable compare-and-set still needs consensus, which is why Cassandra's lightweight transactions use Paxos.

The cost

Replicate across two datacenters and cut the link. Multi-leader keeps serving in both (available, not linearizable). Single-leader clients on the wrong side must wait (unavailable) or read stale data (not linearizable). You cannot have both.

That is the real content of the CAP theorem, and the chapter is blunt about its limits. The accurate reading is "during a network partition, choose between linearizability and total availability." The "pick two of three" slogan misleads: partitions are not a choice, the proof's "availability" is not what operators mean, and the theorem ignores latency, crashed nodes and every other trade-off. State the actual trade-off instead of invoking CAP.

Linearizability is also slow without partitions: Attiya and Welch showed that linearizable operation latency is at least proportional to the uncertainty in network delay. Even a multi-core CPU is not linearizable by default (cores see each other's writes late; memory barriers buy ordering at a cost). Weak models exist for latency, not only for fault tolerance.

Ordering guarantees

Ordering and causality

Ordering recurs throughout the book because it preserves causality: if B could have been influenced by A, the system should not present B as if A had not happened. Violations look like an answer appearing before its question, a row arriving at a follower before the row it references, or a read that shows a transaction's effect but not its cause. A system that respects causal ordering is causally consistent; snapshot isolation provides it inside one database because a snapshot that contains a write also contains everything the write depended on.

The key distinction is partial versus total order. Causality is a partial order: some pairs are ordered, others are concurrent and incomparable. Linearizability is a total order: every pair is ordered, as if run on one copy. So linearizability implies causal consistency, not the reverse.

Causal consistency is the strongest model that does not slow down under network delay and stays available under partitions. Much of what seems to require linearizability only requires causality. The implementation question is how the database learns which operation happened before which. Version vectors from Chapter 5 do it in general, by attaching the version a client read to its next write, but tracking everything a client has read is expensive.

Sequence numbers and Lamport timestamps

The cheaper tool is a sequence number: a counter that gives a total order consistent with causality, so that if A happened before B then A's number is lower. With a single leader this is free: the leader's replication log position is the number. Without one, naive schemes fail. Per-node counters (odd/even) are not causal because a busy node runs ahead; wall-clock timestamps suffer skew; preallocated blocks have the per-node problem.

Lamport timestamps (1978) fix this. Each node keeps a counter and a unique ID; the timestamp is (counter, node ID), compared by counter then ID, so timestamps are unique and totally ordered. Every node and client carries the maximum counter it has seen and includes it on each request; a recipient bumps its own counter to at least that value before incrementing. Because of the piggybacking, causal predecessors always get lower timestamps.

Lamport timestamps are compact and total, but they cannot tell concurrent operations from causally dependent ones; any two are comparable, so the information that two writes conflicted is lost. Use version vectors to detect conflicts, Lamport timestamps when you just need a consistent total order.

Why a total order in hindsight is not enough

Two users simultaneously create the same username. Give each create a Lamport timestamp, let the lower win, and the problem looks solved. It is solved only after the fact: once all operations are collected, sorting yields an unambiguous winner. But the node serving a request must answer now, and it cannot know whether another node is concurrently processing a lower-timestamped claim on the same name. Asking every node what it is doing stalls if any node is unreachable. What is missing is knowing when the order is finalised: no lower-numbered operation can still arrive. That is what total order broadcast provides.

Total order broadcast

Total order broadcast (atomic broadcast) delivers messages to all nodes with two safety properties that must hold even under faults: reliable delivery (if one node gets a message, all do) and totally ordered delivery (every node delivers in the same order). Single-leader replication is total order broadcast with the leader as sequencer; the hard part is surviving leader failure, which is what consensus algorithms do. Zab (ZooKeeper) and Raft (etcd) are total order broadcast implementations.

Delivering every write as a message keeps replicas identical, the state machine replication principle. Delivering every transaction as a deterministic stored procedure in the same order to every partition yields serializability (how Calvin and VoltDB work). Crucially, order is fixed at delivery: a message is an append to a log and nothing can be inserted retroactively. A lock service that hands out increasing fencing tokens is doing total order broadcast of lock acquisitions.

From total order broadcast to linearizability and back

The two differ: broadcast is asynchronous (delivery eventually, no recency), linearizability is a recency guarantee. Yet each builds the other.

Linearizable compare-and-set from broadcast. Append "claim username X" to the log, then read the log forward until your own message comes back. If the first claim for X you see is yours, commit; otherwise abort. Everyone sees the same order, so everyone agrees on the winner. Linearizable reads need one more step because a replica may be behind: append a dummy message and read when it returns (etcd quorum reads), fetch the latest log position linearizably and wait for it (ZooKeeper sync), or read from a synchronously updated replica.

Broadcast from a linearizable register. With a linearizable increment-and-get, increment to obtain a gap-free sequence number, attach it to the message, and have recipients deliver in sequence order, waiting for gaps. Unlike Lamport timestamps these numbers are contiguous, so a node that has 4 and 6 knows 5 is still coming.

The punchline: a linearizable compare-and-set register, total order broadcast and consensus are equivalent. Solve one fault-tolerantly and you have solved all. The FLP result shows none can be solved deterministically in a purely asynchronous system with even one crash, which is why real algorithms use timeouts or randomness to detect failures.

Distributed transactions and consensus

The consensus problem

Each node proposes a value; the algorithm decides one. Formally:

Property	Meaning	Type
Uniform agreement	No two nodes decide differently	Safety
Integrity	No node decides twice	Safety
Validity	A decided value was proposed by some node	Safety
Termination	Every non-crashed node eventually decides	Liveness

Termination requires that fewer than half the nodes have crashed; safety must hold regardless. Most algorithms assume no Byzantine (lying) nodes.

Atomic commit and two-phase commit

The motivating database problem is atomic commit across nodes: a transaction touching several partitions, or a secondary index on another node, must commit everywhere or nowhere. On one node atomicity is the order of writes to the WAL. Across nodes, independent decisions leave some committed and some aborted, and a commit cannot be undone once clients may have seen it.

Two-phase commit (2PC) uses a coordinator (often a library in the application process) and participants:

1. The application gets a globally unique transaction ID and performs reads and writes against each participant as ordinary single-node transactions tagged with it. Anything failing here aborts.
2. Prepare: the coordinator asks every participant to prepare. A participant answering yes has durably written all transaction data and its prepared state and promises to commit later no matter what, even after a crash. It surrenders the right to abort.
3. The coordinator decides commit only if all said yes, else abort, and writes the decision to its own log on disk. That write is the commit point.
4. Commit or abort: the coordinator sends the decision to all participants, retrying forever on failure. The decision is irreversible.

Two points of no return: a participant's yes and the coordinator's logged decision. Everything between is a promise.

Coordinator failure

A participant that fails before voting is simply aborted; one that fails after voting yes recovers and asks the coordinator. The bad case is the coordinator failing after collecting some yes votes but before delivering the decision. Those participants are in doubt: they cannot abort (they promised) and cannot commit (another may have voted no). They wait for the coordinator to recover and replay its log, holding row locks all the while and blocking other transactions on those rows. Hence 2PC is a blocking protocol. The emergency fallback is a heuristic decision, where an operator forces each in-doubt participant to commit or abort, breaking atomicity.

Three-phase commit

3PC adds a pre-commit phase so participants can decide on timeout, making the protocol non-blocking. It is correct only with bounded network delay and response times, which amounts to requiring a perfect failure detector. A timeout cannot distinguish a dead node from a slow one, so under partitions 3PC can violate atomicity. It is not used in production.

Distributed transactions in practice

Two different things share the name. Database-internal distributed transactions (VoltDB, MySQL Cluster NDB, Spanner's cross-shard commits) involve one system's nodes running one codebase, so the protocol can be optimised, and they work reasonably well. Heterogeneous distributed transactions span different technologies, for example consuming a message, updating a database and acknowledging the message atomically. That is attractive (exactly-once processing) and where the pain lives.

The standard is X/Open XA (1991), supported by PostgreSQL, MySQL, Oracle, SQL Server, ActiveMQ, IBM MQ and others; Java's JTA is the equivalent used by JDBC and JMS drivers. XA is a C API through which a coordinator, typically a library in the application process logging to local disk, drives participants via their drivers. Its problems explain why modern systems avoid it:

• The coordinator is a single point of failure, usually unreplicated, and it quietly makes a "stateless" application server stateful: its log is now critical data.
• In-doubt participants hold locks for the duration of any coordinator outage; a crashed coordinator can collapse a database's throughput.
• Orphaned in-doubt transactions outlive log corruption and need manual resolution.
• Lowest common denominator: no cross-system deadlock detection, no SSI, features of individual systems lost.
• It amplifies failures: any slow or down participant fails the whole transaction, the opposite of fault tolerance.

Fault-tolerant consensus

2PC funnels every decision through one coordinator; fault-tolerant consensus algorithms remove that single point. The main ones are Paxos and Multi-Paxos (Lamport), Viewstamped Replication (Oki and Liskov), Zab (ZooKeeper) and Raft (etcd, CockroachDB, TiKV, Consul, Kafka's KRaft). They share a structure and most are really total order broadcast: they decide a sequence of values, one per log position.

Epochs. Each uses a monotonically increasing epoch number (ballot in Paxos, view in VR, term in Raft) and guarantees at most one leader per epoch. A node that stops hearing heartbeats starts an election in a new epoch; a higher epoch always wins a conflict. This repairs the weakest part of the Chapter 5 single-leader story.

Two overlapping quorums. Before deciding, a leader must confirm no higher-epoch leader exists. It sends each proposal to a quorum (usually a majority), and a node accepts only if it knows of no higher epoch. The election quorum and each acceptance quorum must overlap, so at least one voter in any acceptance quorum also voted in the latest election; if none of them knows of a higher epoch, the leader is still current and holds the latest committed state.

That is Raft's node state machine. Raft adds the rule that a candidate must have a log at least as up to date as the voter's, so committed entries survive leader changes.

Relation to 2PC. Both have a leader collecting votes, but in 2PC the coordinator is fixed, unanimity is required and there is no recovery from coordinator failure. In consensus the leader is elected, a majority suffices and a dead leader is replaced. Those differences are the whole reason one is fault-tolerant and the other is not.

Limitations of consensus

• Synchronous replication. Every decision waits for a majority round trip, so throughput is network-bound and geo-distributed quorums are slow.
• Majority requirement. Three nodes tolerate one failure, five tolerate two; the minority side of a partition stalls.
• Fixed membership. Dynamic membership (Raft joint consensus, ZooKeeper reconfiguration) exists but is delicate.
• Timeout sensitivity. Failure detection is timeout-based. A flaky network triggers repeated elections and a cluster that is always electing does no work; Raft has a known pathology where one bad link bounces leadership indefinitely.
• Not a general transaction mechanism. Consensus decides small values in sequence. Spanner layers 2PC on top of per-shard Paxos groups, with the coordinator itself a Paxos group, so cross-shard commit is atomic and the coordinator is no longer a single point of failure.

Membership and coordination services

ZooKeeper (modelled on Google's Chubby) and etcd are small in-memory replicated key-value stores whose data is replicated by total order broadcast (Zab and Raft). Applications rarely use them for application data; they are embedded in other systems: HBase, YARN, Solr and pre-KRaft Kafka use ZooKeeper, and Kubernetes keeps its entire cluster state in etcd. Their job is small, slowly changing, critical coordination state.

Feature	What it gives you
Linearizable atomic operations	Compare-and-set to implement a lock: the first to create the key wins, correct under faults
Total ordering of operations	Monotonically increasing transaction IDs (zxid, revision) usable as fencing tokens, so a holder whose lease expired is rejected by downstream resources
Failure detection and ephemeral nodes	Clients keep a heartbeat session; when it expires, ephemeral keys the client created vanish, releasing its locks
Watches	Clients are notified of changes to a key or prefix and learn of a new leader or member without polling

Uses:

• Allocating work. Leader election for a database or scheduler, assigning partitions to nodes, rebalancing on join or leave. This data changes over minutes or hours, which suits the service. A fleet of thousands does not run consensus among itself; it runs a 3- or 5-node ensemble and coordinates through it. Apache Curator packages recipes (locks, leader latch, barriers) on top.
• Service discovery. Services register endpoints on start-up; clients look them up. Discovery tolerates slight staleness, so Consul and etcd also serve read-only DNS caches outside consensus; leader election still needs the linearizable path.
• Membership. Which nodes are alive is itself a coordination problem. Combining failure detection with consensus gives agreement on membership: a node declared dead may still be running, but everyone treats it consistently, and fencing tokens handle its return.

Design trade-offs

You need	Weakest sufficient model	Mechanism	Cost
Replicas eventually agree	Eventual consistency	Async replication, LWW or siblings	Stale and out-of-order reads under faults
No causal anomalies, available under partition	Causal consistency	Version vectors, dependency tracking, snapshot isolation	Metadata; conflicts still need resolving
A single agreed order, decided once	Total order broadcast	Consensus (Raft, Zab, Multi-Paxos)	Majority round trip per decision; minority stalls
Lock, leader election, uniqueness	Linearizable compare-and-set	Consensus-backed store (ZooKeeper, etcd, Spanner, Cassandra LWT)	Same, plus the service becomes critical infrastructure
Atomic commit across heterogeneous systems	2PC / XA	Coordinator and prepared participants	Blocking on coordinator failure; locks held; features lost
Atomic commit across shards of one system	2PC over consensus groups	Spanner style: Paxos per shard, 2PC across, replicated coordinator	Two protocols stacked; higher latency

Rules of thumb: pick the weakest model that keeps the application correct; use linearizability only where split brain or duplicate claims are unacceptable; never build your own consensus, use etcd or ZooKeeper; treat XA as a last resort and prefer idempotent, log-based integration (Chapters 11 and 12).

Interview angle

• Explain linearizability and contrast it with serializability. Linearizability is the illusion of a single copy: once any client reads a new value, all later reads see it; it is a recency guarantee on single objects. Serializability is an isolation property for multi-object transactions: the result equals some serial order, which need not match real time. A database can have either, both (strict serializability) or neither; SSI is serializable but not linearizable.

• Why aren't Dynamo-style quorums linearizable even with w + r > n? Replicas receive a write at different times, so one reader may see the new value while a later reader hitting two stale replicas sees the old one. Quorum overlap does not create a real-time order. Synchronous read repair narrows it; compare-and-set still requires consensus, which is why Cassandra's lightweight transactions use Paxos.

• What is wrong with "pick two of CAP"? Partitions are not optional, so the only choice is linearizability versus availability during a partition, and the theorem's "availability" is not the operational meaning. It ignores latency and node crashes. State the actual behaviour: "under partition, this component refuses writes rather than risk split brain."

• Why can't Lamport timestamps enforce a unique username? They order operations consistently with causality, but only once all operations are known. A node answering now cannot know whether another node is concurrently handling a lower-timestamped claim on the same name. You need the order to be final, which requires total order broadcast, that is, consensus.

• Walk through 2PC and the coordinator-crash case. Prepare: a yes vote means the participant has durably written the transaction and promises to commit. The coordinator logs its decision (the commit point), then sends commit or abort with retries. If it crashes between those steps, participants that voted yes are in doubt, cannot act unilaterally and hold locks until the coordinator recovers. The fix is to make the coordinator fault-tolerant through consensus, as Spanner does.

• How does fault-tolerant consensus differ from 2PC when both have a leader collecting votes? In 2PC the coordinator is fixed, votes must be unanimous and coordinator failure blocks everyone. In Raft or Paxos the leader is elected per epoch, a majority suffices, and the overlap between election and acceptance quorums guarantees a leader cannot decide while a higher epoch exists. Consensus tolerates a minority of failures; 2PC tolerates none at the coordinator.

• Design leader election for a 50-node service. Do not run consensus across 50 nodes; deploy a 3- or 5-node etcd or ZooKeeper ensemble. Each candidate tries to create the same ephemeral key; the creator is leader, and the key's revision is the fencing token attached to every downstream write, which resources reject if lower than the latest seen. Others watch the key; when the leader's session expires a new election runs. The fencing token, not the lock alone, protects against a paused ex-leader.

• When would you accept XA? Only when two heterogeneous legacy systems must be atomically consistent, the dataflow cannot be restructured and transient inconsistency is unacceptable. Otherwise prefer idempotent writes and a single ordered log (CDC, Kafka) that each system consumes, which can be retried and does not block on a coordinator.

Pitfalls and misconceptions

• "Strong consistency" without a definition. Vendors use it for anything from read-your-writes to linearizability. Name the model; linearizability has a precise test.
• Confusing 2PC with 2PL. Two-phase commit is atomic commit across nodes; two-phase locking is serializability within one database. They share a number and nothing else.
• Treating 2PC as consensus. 2PC reaches agreement but blocks on coordinator failure and needs unanimity. Fault-tolerant consensus needs elected leaders, epochs and majorities.
• Treating serializability as the strongest guarantee. An SSI database can show stale data. If a read after a completed write must see it, ask for linearizability or strict serializability.
• Assuming quorum reads are linearizable. Not without synchronous read repair, and compare-and-set is impossible without consensus.
• Locks without fencing tokens. A client can acquire a lock, pause, lose it to expiry, then wake and write as if it still held it. The resource must check a monotonically increasing token.
• Running consensus across the whole fleet. Cost grows with cluster size; the pattern is a small ensemble coordinating many nodes.

Key terms

Term	Meaning
Linearizability	Each operation appears to take effect atomically at one instant between call and response, as if on a single copy
Serializability	Transaction outcome equals some serial execution of the transactions
Strict serializability	Serializable and linearizable; the serial order matches real time
Eventual consistency	Replicas converge once writes stop; no bound on when
Causal consistency	Causally related operations are seen in causal order everywhere; concurrent ones in any order
Partial vs total order	Partial: some pairs incomparable (concurrent). Total: every pair ordered
Lamport timestamp	(counter, node ID) with counters piggybacked on messages; total order consistent with causality, cannot detect concurrency
Version vector	Per-replica counters capturing a value's causal history; detects concurrent writes
Total order broadcast	Reliable delivery of messages to all nodes in one agreed order; equivalent to consensus
Consensus	Agreement on one proposed value with uniform agreement, integrity, validity and termination
Atomic commit	A multi-node transaction commits everywhere or nowhere
Two-phase commit	Prepare, log the decision, then commit or abort; blocks on coordinator failure
XA / JTA	Standards for heterogeneous distributed transactions through a shared coordinator API
Epoch (term, ballot, view)	Monotonically increasing leadership period number; at most one leader per epoch
Quorum	Nodes (usually a majority) whose votes are required; election and acceptance quorums overlap
Fencing token	Increasing number issued with a lock or lease so stale holders are rejected
Ephemeral node	ZooKeeper key tied to a client session, deleted when the session expires
CAP theorem	Under partition, a system cannot be both linearizable and fully available

Further reading

• DDIA, Chapter 9: "Consistency and Consensus"; Kleppmann's reference list at https://github.com/ept/ddia-references
• Herlihy and Wing, "Linearizability: A Correctness Condition for Concurrent Objects," ACM TOPLAS, 1990
• Martin Kleppmann, "Please Stop Calling Databases CP or AP," 2015: https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
• Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," CACM, 1978
• Leslie Lamport, "Paxos Made Simple," 2001: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
• Ongaro and Ousterhout, "In Search of an Understandable Consensus Algorithm," USENIX ATC 2014: https://raft.github.io/raft.pdf
• Fischer, Lynch and Paterson, "Impossibility of Distributed Consensus with One Faulty Process," JACM, 1985
• Hunt et al., "ZooKeeper: Wait-free Coordination for Internet-scale Systems," USENIX ATC 2010
• Corbett et al., "Spanner: Google's Globally-Distributed Database," OSDI 2012