Distributed Systems

Failure detection

A subsystem that guesses whether a remote process has stopped, producing a suspicion rather than a measurement.

Heartbeats arrive on a schedule. Missing one increments suspicion; a threshold triggers a failure declaration.

A crashed process and a slow network both produce silence. No timeout can distinguish them in an asynchronous model, so the detector chooses an error rate.

The big idea

Any system that must evict a failed member. Short timeouts favor completeness; long ones favor accuracy. Fencing is required to handle false positives.

A peer that stops answering creates an ambiguity every operator has met in some form: the service may be dead, or the network may be slow. Failure detection is the machinery that turns silence into suspicion. In a network with no fixed bound on delay, that suspicion cannot be a measurement. Tuning a detector is a choice between suspecting healthy processes too quickly and waiting too long to remove failed ones.

Fundamental ambiguity

A process that has crashed sends nothing. A process that is merely slow, or whose replies are delayed by a congested network, also sends nothing for a while. From the outside these produce an identical observation. No amount of waiting resolves the ambiguity because the asynchronous model places no bound on message delay.

Every failure detector is therefore a guess with a tunable error rate rather than a measurement.

Heartbeats and phi accrual

Approach	How it works	Strength/Weakness
Heartbeats	Process periodically announces alive; peer declares failed after timeout	Simple; binary verdict doesn’t suit varying network conditions
Phi accrual	Continuous suspicion level computed from distribution of arrival intervals	Different subsystems can act at different thresholds; adapts automatically

Completeness versus accuracy

Designers judge a failure detector on two properties that pull against each other.

Property	Meaning	Favored by
Completeness	Every genuinely failed process eventually suspected	Short timeouts
Accuracy	No living process wrongly suspected	Long timeouts

Practical detectors favor completeness because the recovery path for a wrongly evicted node can be made cheap.

Fencing tokens

A wrongly suspected node eventually comes back believing it still holds whatever it held.

The classic failure:

• Node acquires a lock
• Pauses for long garbage collection
• Is declared dead; lock granted to second node
• First node resumes and writes (believing it is still owner)
• Both nodes write; data is corrupted

Monotonic token fix

The fix: the lock service issues a monotonically increasing token with each grant, and storage rejects any write carrying a token lower than the highest seen. Any system that grants exclusive access without fencing has this bug latent.

Consistency models

A contract specifying which histories of reads and writes a storage system permits.

The system enforces ordering constraints: linearizability requires real-time order; causal consistency tracks happens-before; eventual consistency promises only convergence.

Stronger guarantees cost coordination latency. Weaker ones allow local decisions but expose stale or reordered data.

The big idea

Any replicated store. The choice is made per operation or per data type, and session guarantees can restore sanity atop weak models.

After data is replicated, a familiar question becomes slippery: if one client writes and another reads elsewhere, what result is allowed? Consistency models give that question an exact contract. They specify which histories of reads and writes the storage system permits, from strict real-time behavior to eventual convergence. Choosing a model trades easier reasoning for clients against the coordination cost needed to enforce stronger ordering.

Linearizability

Linearizability is the strongest single-object guarantee. Every operation appears to take effect atomically at some instant between issue and response, and those instants respect real time.

Once a write returns, every subsequent read anywhere in the system observes it or something newer, and no reader ever goes backward.

Coordination cost

Achieving this requires coordination on writes (at least one round trip to a quorum), so the guarantee costs latency proportional to distance between replicas. Reads can sometimes escape the round trip: a leader holding a time-bounded lease can answer them locally without violating the guarantee, provided clock drift between servers is bounded. That is why the read and write paths of a linearizable store often have very different latency profiles.

That latency has a floor set by physics: a round trip between two replicas cannot beat the time light needs to cross the distance between them, so a linearizable store spread across regions pays tens of milliseconds on every operation regardless of how fast the machines are. Teams that need the guarantee usually place the replicas close together, trading the fault independence of separate regions for the lower latency of one, or they restrict linearizable operations to the few keys that genuinely require them and serve everything else under a weaker model. Routing every write through a single leader to fix the order turns that leader into both a throughput bottleneck and a failure point, so part of the cost lands on availability rather than latency.

Sequential consistency

Sequential consistency drops the real-time requirement while keeping a single global order. All processes agree on one order of operations, and each process’s own operations appear in that order.

Linearizable	Sequential
Order matches wall-clock time	Order need not match wall-clock time
Write completes → all readers see it	Write completed a minute ago may be ordered after a read that started now

Two users looking at the same data can disagree, and the system is still correct by its own contract.

Causal consistency

Causal consistency is the strongest model achievable without coordination, under conditions worth stating: Attiya, Ellen and Morrison proved in 2015 that a store which stays available under partition and converges cannot guarantee anything strictly stronger than observable causal consistency. That is a theorem about that setting rather than an engineering limitation, and it stops applying the moment a system is allowed to refuse a write.

Operations	Ordering guarantee
Related by causality	Seen in the same order by everyone
Concurrent (no causal path between them)	May be seen in different orders

Because causality is tracked with metadata rather than established by agreement, replicas can serve reads and accept writes during a partition.

Eventual consistency

Eventual consistency promises only that replicas converge if writes stop. The useful questions:

• How long does convergence take in practice? (Reported as replication lag distribution)
• What can a reader observe before convergence?

Without further guarantees a reader can see a value, then see an older value, then see the newer one again. Code that assumes monotonic progress breaks.

DNS authority and cache expiry

The Domain Name System (DNS) makes eventual consistency visible when a name still resolves to an old address after an update. A zone is the portion of the name tree managed by an authority; a resolver looks up records for clients and may cache the answers. RFC 1034 defines a record’s time to live (TTL) as a cache reuse interval in seconds. A zero TTL prohibits caching beyond the current lookup. TTL governs cached answers; authoritative zone copies follow separate refresh policies.

Expiry is not an unconditional cutoff for old answers. RFC 8767 permits serve-stale, reuse of expired records when a resolver cannot refresh them. An authority can be reachable but too slow for the resolver’s response deadline, so stale answers do not imply an unreachable server. Such answers must carry a positive TTL, with 30 seconds recommended. Lowering a record’s TTL alone therefore does not bound how long every client might see an old value.

Session guarantees

Guarantee	What it prevents	Implementation
Read-your-writes	Saving a change and seeing the old value	Route session to replica known to have caught up
Monotonic reads	Value appearing, disappearing, reappearing	Carry version token; require replica to have reached it

Neither requires global coordination; together they remove most user-visible strangeness of eventual consistency.

CAP theorem

A theorem stating that a system cannot provide linearizability and total availability while the network is partitioned.

If nodes cannot communicate, they must either refuse some requests (sacrifice availability) or accept divergent writes (sacrifice linearizability).

A single consistent order requires agreement, and agreement requires communication. Partitions block communication.

The big idea

Distributed stores during a partition. The choice is forced only while the partition lasts; most systems choose latency over consistency on ordinary days.

When a network split prevents replicas from talking, two sides cannot coordinate a single order for new operations. CAP theorem names the constraint in that moment. The system must either refuse some requests to preserve one order or answer everywhere and risk histories that cannot be made linearizable. The consequence is a forced choice during a partition, not a general license to treat consistency, availability, and partition tolerance as a permanent menu.

Precise claim

Each term is narrower than its plain-English sense:

Term	In CAP	Not
Consistency	Linearizability specifically	The C in ACID; any weaker model
Availability	Every request to every non-failed node returns a non-error response	Staying up on most nodes
Partition tolerance	System continues to function while network drops arbitrary messages	(Not optional)

The theorem says no system provides linearizability and total availability while a partition is in progress.

Choice is forced only during a partition

When the network is healthy, a system can be both linearizable and available. The design decision is what to do in the window when a partition is active:

• Refuse writes on the minority side (preserve single order)
• Accept writes on both sides (reconcile afterward)

Since partitions are rare and brief in a well-run datacenter and common across regions, the same reasoning yields different answers at different scales.

PACELC

PACELC extends CAP to cover the case that dominates in practice:

If there is a partition, choose availability or consistency. Else choose latency or consistency. Most systems described as choosing availability are in fact choosing latency, on ordinary Tuesdays rather than during an outage.

Common misreadings

Misreading	Why it’s wrong
CAP is a menu: pick any 2 of 3	Partition tolerance is not a choice; partitions happen
Must abandon linearizability for good availability	Session guarantees and causal consistency sit between the extremes

Quorums

A rule requiring reads and writes to contact overlapping subsets of replicas so that every read sees the latest write.

If R replicas are read and W are written and R + W exceeds N, at least one replica in the read set saw the write.

Overlap guarantees that the reader finds the newest value without contacting every replica.

The big idea

Replicated key-value stores, consensus systems. Sloppy quorums break the overlap and the guarantee.

Replicating data helps availability, but waiting for every replica makes one slow or failed machine slow the whole operation. Quorums are the rule that lets reads and writes contact only subsets while preserving an overlap. If the write set and read set must share a replica, the read has a place to discover the latest written version. Reads stay correct without every request depending on every copy being reachable.

$$R + W > N$$

If the replicas read and the replicas written total more than the replicas that exist, the two sets must share at least one member.

symbol	meaning
$R$	the number of replicas contacted on a read
$W$	the number of replicas that must acknowledge a write
$N$	the total number of replicas

Counting argument

Any set of $R$ replicas and any set of $W$ replicas drawn from $N$ must share a member when $R + W$ exceeds $N$ (pigeonhole principle). That shared member holds the newest completed write, so a reader that collects responses and takes the highest version sees it. Overlap alone does not make reads linearizable when a read races a write still in progress; the ABD protocol adds a write-back phase to reads for that.

No node needs to know which other nodes participated. Any $N - W$ replicas may be down and writes still succeed.

Majority quorums

Cluster size	Tolerates failures	Why this size
3	1	Common default
5	2	Node may be down for maintenance while another fails unexpectedly
7	3	Rare; write path waits for 4 acknowledgments

An odd $N$ is standard because an even one buys nothing (5 and 6 replicas both tolerate 2 failures).

Tuning R and W

Setting	Read cost	Write cost	Use case
$W = N$, $R = 1$	One replica	All replicas must be up	Data written once, read constantly
$W = 1$, $R = N$	All replicas	One replica	High-volume ingestion, rare reads
Balanced majority	Symmetric	Symmetric	Default; survives most failures on both paths

Sloppy quorums and hinted handoff

Under a sloppy quorum, a write may reach any $W$ reachable nodes, including nodes that do not normally hold that key. Those nodes store the data temporarily and forward it once the partition heals (hinted handoff).

The system stays writable when a majority of the proper replicas is unreachable, but a subsequent read of the proper replicas may miss the write entirely, because the overlap that made the guarantee true no longer holds.

Anti-entropy with Merkle trees

Replica repair must cover writes that hinted handoff never delivers. Dynamo uses anti-entropy, a protocol for synchronizing replicas, to handle cases such as a hinted copy becoming unavailable before it can be returned. Each node keeps a Merkle tree for each key range it hosts. A Merkle tree is a tree of hashes: leaves hash individual keys’ values, and each parent hashes its children. Replicas compare root hashes and descend through mismatching branches to find differing keys, without downloading the entire tree or dataset.

The paper reports that several Dynamo deployments used $(N,R,W) = (3,2,2)$: three replicas, with two responses required for a read or write. Those thresholds decide when an operation can finish; anti-entropy repairs copies that remain out of sync afterward. Repair does not retroactively restore the overlap that a sloppy quorum lacked.

Consensus

A protocol by which a set of processes agrees on a single value despite failures.

Processes propose and vote in rounds. A value is decided once a quorum commits to it, and safety rules prevent a different value from being decided later.

Overlapping quorums guarantee that any two decisions share a voter who remembers what was committed.

The big idea

Leader election, replicated logs, configuration changes. For deterministic protocols, liveness requires partial synchrony; safety holds even in an asynchronous network.

Distributed systems often need several processes to make one decision, such as which value won or which node leads. If different healthy processes decide differently, the rest of the design can split around that disagreement. Consensus names the problem of reaching a single decision despite failures. Coordination tasks build on it wherever safety depends on preventing two incompatible decisions from both becoming final.

Three properties

Property	Type	Meaning
Agreement	Safety	No two correct processes decide differently
Validity	Safety	The decided value was proposed by some process
Termination	Liveness	Every correct process eventually decides

Almost every real failure in a consensus system is a liveness failure (cluster is safe and stuck) because implementations sacrifice progress rather than correctness.

FLP result

FLP proves that no deterministic protocol achieves all three properties in an asynchronous network if even one process may crash. In a model with no bound on message delay, a protocol cannot tell a crashed process from a slow one, and an adversary controlling scheduling can always keep the system undecided.

The practical reading of FLP: the impossibility is routed around by giving up guaranteed termination, so a cluster that cannot reach a quorum stops serving rather than splitting.

Partial synchrony

Real systems assume partial synchrony: the network behaves badly for unbounded but finite periods and eventually delivers messages within some bound. Under that assumption a protocol can use timeouts to make progress whenever the network is behaving; when it is not, the protocol stalls without deciding two different values.

Paxos

Paxos was one of the earliest solutions and was hard enough to teach that its difficulty became the motivation for a replacement. The core protocol decides a single value through a two-phase exchange, and its safety argument resists intuition. The gap that caused the most trouble is that single-decree Paxos is not what anyone builds; systems need a replicated log, and every implementation made its own decisions in the undescribed regions.

Raft

A consensus protocol for managing a replicated log, structured for understandability.

One node is elected leader. It appends entries, replicates them, and commits once a majority acknowledges. Terms act as a logical clock to detect stale leaders.

Routing all writes through a leader serializes them without the complexity of multi-proposer protocols.

The big idea

Coordination services, metadata stores. Membership changes require a joint-consensus or single-node-change protocol to avoid split brain.

A replicated log has to keep one ordered story even as machines time out, recover, and rejoin. Raft is a consensus protocol organized around a leader that appends entries and commits them after a majority acknowledges. Its structure makes the moving parts easier to audit than a more opaque agreement protocol. It makes a practical coordination core, as long as elections and membership changes preserve the log’s safety rules.

Three parts

Component	Purpose
Leader election	Chooses one node to serve as single point through which all changes flow
Log replication	Has leader append entries and push them to followers
Safety	Adds constraints that prevent the first two from producing incorrect results

The key safety rule: a node may only vote for a candidate whose log is at least as up to date as its own.

Terms as a logical clock

Mechanism	Effect
Time divided into numbered terms, each beginning with an election	All messages carry sender’s term
Node receives message with higher term	Immediately updates, reverts to follower
Node receives message with lower term	Rejects it

A partitioned leader discovers the truth on first contact with the majority side, because that side has moved to a higher term. The old leader’s uncommitted requests never committed because commitment requires acknowledgment from a majority the old leader could not reach.

Election timeouts

Randomized election timeouts make simultaneous candidacies less likely. Ongaro and Ousterhout’s Raft paper gives 150–300 ms as an example range, so one server will usually time out and gather votes before the others start. Each candidate starts a new randomized timeout for each election attempt, which also reduces repeated split votes.

Timing affects availability; Raft’s safety must hold even when delays exceed expectations. The paper defines broadcast time as the average round trip for remote procedure calls sent in parallel to every server, and MTBF as the mean time between failures of one server. A stable leader requires $\text{broadcastTime} \ll \text{electionTimeout} \ll \text{MTBF}$. Its estimates are 0.5–20 ms for broadcast time, depending on stable-storage writes, roughly 10–500 ms for election timeouts, and months or more for server MTBF. Choose the timeout against the cluster’s measured broadcast time: too short causes unnecessary elections; too long extends the outage after a leader fails.

Commit rule

An entry is committed once replicated to a majority, with one restriction: a new leader may not commit an entry from a previous term merely by observing it is present on a majority. Instead the leader commits an entry from its own current term, which implicitly commits everything before it.

The restriction exists because counting replicas alone is not sufficient evidence that an entry is permanent. The scenario that violates it requires a specific interleaving of failures across three terms; it is the part of the protocol most often omitted from summaries.

Membership changes

The naive approach (switching every node directly from old to new configuration) can elect two leaders, because nodes apply the change at different times.

Approach	How it works
Joint consensus	Intermediate configuration requires majorities of both old and new sets
Single-node changes	Add or remove one node at a time; old and new majorities always overlap

Either approach works; skipping both produces a split brain that appears only when reconfiguration coincides with a failure.

Byzantine generals problem

The problem of reaching agreement when faulty participants may lie, forge messages, or behave arbitrarily.

Protocols require more than three times as many participants as faulty ones, and multiple rounds of all-to-all confirmation.

A faulty node can send conflicting messages to different peers. Corroboration from an honest supermajority is the only way to distinguish truth from lies.

The big idea

Systems spanning trust boundaries: permissioned blockchains, cross-organization settlement. Rarely justified inside a single datacenter.

A crashed process merely stops contributing information. A malicious or arbitrary process can contribute false information, including different messages to different peers. The Byzantine generals problem is agreement under that stronger fault model. Because any single message may be a lie, protocols need corroboration from enough participants that at least one honest process overlaps between decisions. The price is higher replica counts and more communication than ordinary crash-tolerant agreement.

Crash versus Byzantine faults

Fault type	Behavior	What it contributes
Crash	Process stops	No information
Byzantine	Process does anything (sends conflicting messages, forges votes, replays old messages)	False information

Protocols cannot treat a received message as evidence unless it is corroborated. Every majority argument that worked for crash tolerance must be redone assuming some of the majority is lying.

Bound: $n > 3f$

Tolerating $f$ Byzantine processes requires more than $3f$ total, in the asynchronous and partially synchronous settings these protocols target. With $n = 3f + 1$, any two quorums of size $2f + 1$ intersect in at least $f + 1$ processes, guaranteeing at least one correct process in the overlap. The bound is a property of that setting rather than of Byzantine fault tolerance as such: given synchrony and digital signatures, agreement is reachable with far weaker ratios.

Faults (f)	Minimum nodes (Byzantine)	Minimum nodes (crash)
1	4	3
2	7	5

Practical Byzantine fault tolerance (PBFT)

The protocol runs three phases, and because a node must confirm that other nodes received the same message it did, the agreement phases broadcast among all participants, producing $O(n^2)$ messages per decision. At a handful of nodes this is unremarkable; at a hundred it dominates everything else.

Classical Byzantine protocols are deployed in small committees rather than large open networks. The quadratic pattern of all-to-all confirmation is what the earlier designs pay, and it is a worst-case floor for deterministic agreement rather than a per-message necessity: threshold signatures let one node aggregate a quorum’s votes into a single certificate, which brings the common case down to linear; HotStuff extends that to view changes, so the quadratic cost returns only across a run of faulty leaders.

When Byzantine tolerance earns its cost

The model applies across trust boundaries rather than inside one administrative domain. Within a single datacenter, nodes are not adversaries: misbehavior comes from hardware error, memory corruption, or software bugs, and the standard defenses are checksums, canaries, and staged rollouts. Byzantine tolerance earns its cost when participants are operated by parties with conflicting incentives (permissioned blockchains, cross-organization settlement systems). Open networks push the problem further, replacing the known committee with an incentive that makes attack unprofitable; cryptocurrency treats that construction and its failure modes.

Two-phase commit

An atomic commitment protocol that makes a transaction across several systems succeed or fail as a unit.

A coordinator asks each participant to prepare, waits for all votes, decides commit or abort, and broadcasts the decision.

Requiring unanimous yes votes before commit ensures that every participant can honor the decision.

The big idea

Cross-resource transactions in one datacenter. Blocks if the coordinator or a prepared participant fails; avoid across regions.

A transaction that spans several systems can leave data inconsistent if one participant commits while another aborts. Two-phase commit is the protocol that makes those participants vote before any final decision is applied. Everyone first prepares, then the coordinator records and broadcasts commit or abort. The result is true all-or-nothing behavior when the protocol completes, but prepared participants can block if the decision is lost behind a failure.

Protocol

Phase	What happens
Prepare	Coordinator asks every participant if it can commit; each writes changes durably, takes locks, replies yes or no. A yes is a promise to be able to commit even after crash and restart.
Commit	Coordinator collects votes, decides commit (all yes) or abort (any no), records decision durably, broadcasts it. Participants apply the decision and release locks.

Blocking problem

When the coordinator fails after participants have prepared, a participant that voted yes is holding locks and cannot decide on its own.

Committing is wrong if some other participant voted no. Aborting is wrong if the coordinator already decided to commit. The locks stay held for the entire outage, so the failure of one component stalls every other participant.

Distinction from consensus

Consensus	Two-phase commit
Requires termination among correct processes	Requires unanimity
Majority can decide while minority is down	Single participant that cannot commit must abort the whole transaction

A participant that goes unreachable before voting can be treated as an abort. A participant that has already voted to commit is stuck until it learns the decision.

Where two-phase commit earns its place

Committing across a few tables in one database, or across a database and a message broker in the same datacenter, costs an extra round trip and gives genuine atomicity. It stops being worth paying for when participants span regions (tens of milliseconds per round trip, unbounded blocking during partition) or when the number of participants makes at least one being unavailable approach certainty.

Sagas

A long transaction split into local steps, each paired with a compensating action that undoes its effect.

Each step commits locally. If a later step fails, previously committed steps are compensated in reverse order.

Avoiding held locks across slow or unreliable services keeps the system available.

The big idea

Cross-service workflows where isolation can be relaxed. Intermediate states are visible; steps must be idempotent.

A workflow spread across services often cannot hold database-style locks while waiting on slow or unreliable calls. The alternative is to let each local step commit and define what should undo it if a later step fails. Sagas are that pattern of committed steps paired with compensating actions. The consequence is that the workflow stays available across service boundaries, while other code may observe intermediate states before the saga finishes.

Compensation is not rollback

Rollback	Compensation
Erases history: transaction never happened	New forward operation that offsets an earlier one
No observer saw partial state	Effects were already visible and may have been acted upon

Refunding a charge is not the same as never charging (customer saw the charge, statement records both entries, fee may have been assessed). Writing the compensation requires a decision about what the business wants to happen.

Choreography versus orchestration

Approach	How it works	Tradeoff
Choreography	Each service listens for events and emits its own	Loose coupling; flow invisible, debugging requires reconstructing from logs
Orchestration	Coordinator holds saga’s state and calls each step	Flow readable in one place, current position queryable; coordinator knows about every participant

For anything with more than a few steps, the observability difference dominates.

Intermediate states are visible

A saga provides atomicity in an eventual sense and no isolation at all. Between step three and step four, the world genuinely contains an order that is paid for and unshipped, and other processes will read it.

Countermeasures:

• Semantic locks that mark a record as in-flight
• Versioning that lets a reader detect the state changed underneath it
• Ordering steps so the most consequential and least reversible one runs last

Isolation is not restored

None of these restores isolation.

A semantic lock is a flag other code has to agree to honor, so it coordinates cooperating participants and does nothing about a reader that ignores it. Versioning lets a reader detect that the state changed underneath it but still exposes the intermediate state in the first place. Ordering the steps shrinks the window in which the most damaging one is visible without ever closing it. The safe design assumption is that any committed step can be read by another process before the saga finishes, so each step and each compensation has to stay correct in the presence of that reader. Code that instead assumes serializable isolation, a read and a later write with nothing able to intervene between them, is what corrupts data under a saga.

Idempotent steps

Any step whose response is lost will be retried, and the retry cannot distinguish a request that never arrived from one that succeeded and whose acknowledgment vanished. If charging a card twice produces two charges, the saga is wrong.

The standard implementation carries a client-supplied idempotency key with each step. The receiving service records the key alongside the result and returns that stored result for any repeat. Compensations need the same treatment.

Logical and vector clocks

Counters attached to events that capture causal order without a synchronized physical clock.

A Lamport clock is one counter incremented on each event and advanced on message receipt. A vector clock is one counter per process, compared elementwise.

Physical clocks disagree and can be adjusted backward. Logical clocks order events by their causal relationships, which are stable.

The big idea

Conflict detection, version ordering. Only vector clocks distinguish causally ordered events from concurrent ones.

Using wall-clock time to order distributed events feels natural until two machines disagree about the time or a clock moves backward. Logical and vector clocks replace physical time with counters advanced by local events and messages. They record causal order, the relation between events that could have influenced one another. The consequence is that a replica can tell when one version supersedes another, and with a counter per process it can also tell when two updates are genuinely concurrent.

Happens-before relation

Event $a$ happens before event $b$ if:

• They occur in the same process with $a$ first
• $a$ is the sending of a message and $b$ is its receipt
• By transitivity through a chain of such steps

Events with no such chain in either direction are concurrent (causally independent rather than simultaneous).

Why wall-clock time fails

Problem	Effect
Physical clocks disagree (skew of a few milliseconds is normal)	Network round trips inside a datacenter are tens of microseconds; ordering by timestamps is guessing
Clock adjusted backward by synchronization daemon	Later event carries earlier timestamp; systematic error

Lamport clocks

A Lamport clock is a single counter per process, incremented on each local event and advanced to exceed any timestamp seen on incoming messages.

Property	Implication
If $a$ happens before $b$ then $a$‘s timestamp is less than $b$‘s	Useful for imposing arbitrary but consistent total order
Converse does not hold	Smaller timestamp does not imply causal precedence; cannot detect concurrency

Vector clocks

Each process keeps a counter for every process. Comparing two vectors elementwise yields three outcomes:

Result	Meaning
One dominates in every position	First causally precedes second
Reverse	Second causally precedes first
Neither dominates	Events are concurrent

That third outcome is the one no scalar clock can produce, and it is the input every conflict resolution rule needs.

Version vectors and pruning

The cost is metadata that grows with the number of writers. Version vectors reduce this by counting per replica rather than per client. Entries for departed replicas must be pruned, usually by attaching a wall-clock timestamp and discarding entries untouched for longer than any plausible partition.

CRDTs

Data types whose merge operation is commutative, associative, and idempotent, so replicas converge without coordination.

Replicas apply local updates and periodically exchange state or operations. Merge produces the same result regardless of order or repetition.

The algebraic properties guarantee a unique least upper bound, so all replicas reach the same state without consensus.

The big idea

Collaborative editing, counters, sets across partitions. Metadata and tombstones grow; surprising semantics may not match user intent.

If two replicas accept writes while disconnected, a later merge needs an answer that does not depend on who receives which update first. CRDTs build that answer into the data type. Their merge rules are chosen so order and repetition do not change the final state. They converge without a leader or consensus round, and pay for it with metadata and sometimes surprising semantics.

State-based versus operation-based

Design	What travels	Network requirement	Tradeoff
State-based	Entire state	Only eventual delivery (out of order, duplicated, any path OK)	Bandwidth cost; delta encodings help
Operation-based	The operation itself	Exactly once, causal order	Cheaper on wire; requires delivery infrastructure

Standard catalog

Each standard CRDT pairs a data type with a merge rule fixed by its algebra.

Type	Merge rule	Note
Grow-only counter	Max of each entry; value is sum	Increments commute
PN-counter (allows decrements)	Two vectors: increments and decrements	Single counter merged by max cannot represent going down
Grow-only set	Union	Trivially commutative
Set with removal	Tag each addition with unique identifier; removal deletes only identifiers it observed	Naive remove lost when concurrent add arrives
Sequence (collaborative text)	Dense, immutable position identifiers from infinitely divisible space	Concurrent insertions at same position produce same order everywhere

Why convergence is guaranteed

If the merge operation is commutative, associative, and idempotent, then the set of states forms a join-semilattice and merging always moves upward toward a least upper bound. There is no leader, no quorum, no consensus round, and no window during which the system is unavailable.

Costs

Cost	Cause
Metadata growth	Entries for departed replicas
Tombstones	Every removed element needs identifier retained so replicas that never saw the addition don’t resurrect it
Surprising semantics	Merge rule is mathematically forced; add-wins and remove-wins variants give different answers to the same user action

Consistent hashing

A scheme for mapping keys to nodes so that adding or removing a node moves only a small share of keys.

Hash both keys and nodes onto a ring. Each key belongs to the first node encountered clockwise. Virtual nodes spread load.

Adding a node splits one arc; removing one merges one arc. Most keys stay in place because most arcs are unchanged.

The big idea

Caches, distributed key-value stores. Naive modulo hashing moves nearly all keys on any membership change.

A cache or key-value cluster should not have to move nearly every key whenever a node is added or removed. Simple placement based on the current node count has exactly that failure mode. Consistent hashing gives keys and nodes stable positions in a hash space so membership changes disturb only nearby assignments.

Ring

The hash space is treated as a circle, with both nodes and keys hashed into it. Each key is assigned to the first node encountered moving clockwise.

Operation	Effect
Adding a node	Splits one arc; takes over only keys between new position and predecessor
Removing a node	Hands its arc to clockwise successor

The expected fraction of keys that move is $1/n$ when growing from $n - 1$ to $n$ nodes.

Why naive modulo hashing fails

Approach	What happens when node count changes
Consistent hashing	~$1/n$ keys move
Modulo hashing (key hash % node count)	~$(n-1)/n$ keys move (nearly all)

For a cache, this means a near-total miss storm the moment a node is added or lost. The resulting load on the backing store is a well-known way to turn one failed cache node into a full outage.

Virtual nodes

A small number of random positions distributes the ring badly. Giving each physical node many virtual positions averages the variance down.

Benefit	Why
Better load distribution	Node’s load is sum of many independent arcs
Better recovery	When node fails, lost load spreads across cluster instead of doubling one neighbor’s burden
Heterogeneous hardware	Machine with twice the capacity gets twice the positions

Rendezvous hashing

Rendezvous hashing achieves the same minimal-disruption property with less machinery. It computes a hash of the pair (key, node) for every candidate node and assigns the key to whichever node scores highest.

Property	Consistent hashing	Rendezvous hashing
Disruption bound	$1/n$	$1/n$
Virtual node bookkeeping	Required	None
Hash computations per lookup	1 (plus ring walk)	1 per node
Scale constraint	None	Becomes costly at thousands of nodes

Jump consistent hash

Jump consistent hash computes a shard assignment without storing a ring or virtual-node table. A bucket is a numbered shard; Lamping and Veach’s algorithm uses the key to generate repeatable jumps between bucket counts where that key changes placement. For $n$ buckets, the expected loop count is below $\ln n + 1$, where $\ln$ is the natural logarithm. Adding a bucket moves an expected $1/(n+1)$ share of keys to it. In the paper’s example, growing from 10 to 12 shards requires moving only one-sixth of the data.

The tradeoff is membership: every client must use the same consecutive bucket numbers, from 0 through $n-1$. The interface supports adding the next bucket or removing the last, rather than removing an arbitrary bucket while preserving the others’ identities. This suits stable logical shards in a replicated store; independently disappearing cache nodes are a better fit for ring or rendezvous hashing.

Keys reassigned when a node leaves

Outer dots: keys. Larger dots: moved keys. Inner ticks: virtual nodes. Hollow circles: removed positions.

The fixed key set is assigned to the first virtual node clockwise. Enable JavaScript to compare the assignments.

Physical nodes N

6

Virtual nodes per node

8

Restore last node

Illustrative inputs; 360 fixed keys. Hash: FNV-1a (32-bit) followed by an avalanche mix. Node IDs stay 0 through N - 2 when node N - 1 leaves. Ring benchmark: 1/N for uniform independent positions with equal virtual-node counts. Modulo benchmark: 1 - 1/N, because N - 1 of the N(N - 1) equally likely residue pairs preserve the node ID. The fixed ring and finite key set need not match these expectations.

Only the arc belonging to the departed node moves, while modulo hashing would move nearly everything. Computed from the expression on this page rather than measured.

Exactly-once semantics

The guarantee that a message takes effect exactly once, achieved in processing rather than in delivery.

Deliver at least once, then deduplicate or use idempotent writes keyed by message identifier.

Acknowledgments can be lost, so delivery cannot distinguish a truly lost message from a lost reply. Idempotent processing makes retries safe.

The big idea

Message queues, event processing. External side effects without idempotency keys may still occur twice.

A missing acknowledgment leaves the sender unable to distinguish a lost message from a lost reply. Retrying protects against loss but risks doing the work twice. Exactly-once semantics names the desired effect, but the enforceable version lives in processing rather than delivery. Messages may arrive at least once, while consumers deduplicate or make writes idempotent. Repeated delivery is then safe for the stored effect.

Delivery options

Option	Behavior	Tradeoff
At-most-once	Sender transmits, does not retry	Lost message is simply lost
At-least-once	Sender retries until acknowledged	Duplicates occur when acknowledgment goes missing
Exactly-once	(Not achievable)	Sender would need to know whether unacknowledged message was received (two generals problem)

Systems that advertise exactly-once are not solving delivery. Reading their documentation closely always reveals a claim about effects rather than about the wire.

Mechanism: at-least-once delivery + idempotent processing

Every message carries a stable identifier chosen by the producer. The consumer records processed identifiers and skips any it has already seen, or writes the effect in a way that is naturally idempotent (setting a value rather than incrementing one).

The deduplication table needs a retention window long enough to outlast any plausible retry.

Transactional writes

The classic bug: a consumer processes a message, crashes before recording its offset, restarts, and processes the message a second time.

The fix: write both the result and the consumed offset in a single atomic transaction to the same store. On restart the recorded offset always matches the work actually completed.

External side effects

The guarantee ends at the external side effect. A payment sent to a card network, an email handed to a delivery service, or a call to a third-party API is outside the transaction.

If external system accepts idempotency key	Problem moves there, is solved
If it does not	Record intent durably before acting and reconcile afterward, or accept that effect may happen twice

End-to-end checks and fate-sharing

The end-to-end argument places the final correctness check with the application that knows what success means. In Saltzer, Reed, and Clark’s file-transfer example, the receiver rereads the saved file from disk and sends its checksum, an error-detecting summary of the contents, back to the sender. The application declares the transfer committed only if that checksum matches the original. Their reported gateway bug swapped a byte pair about once per million bytes despite packet checksums on each network hop: corruption occurred in the gateway’s buffers between those checks. Checksums address integrity; duplicate suppression remains a separate obligation.

Fate-sharing puts essential state with the entity that depends on it, so losing the state is acceptable only when that entity is also lost. Clark’s 1988 account places transport connection state at the end hosts rather than intermediate packet switches, so losing a switch need not erase a live connection. The same lifetime question applies to processing effects: a completed payment can outlive a worker, so keeping its deduplication record only in that worker’s memory leaves retries unsafe after a crash.

Tail latency

The slow end of the response time distribution, which dominates user experience when requests fan out.

If a request depends on n calls each with probability p of being slow, the probability that at least one is slow is 1 minus (1 minus p) to the n.

A request that waits for many backends finishes when the slowest one finishes. Rare slowness at the leaf is common at the root.

The big idea

Any service with fan-out. Hedged requests and tied requests mitigate; improving medians does almost nothing.

A user-facing request often waits on many backend calls, and the response cannot finish until the slowest required call returns. Tail latency is the slow end of that response-time distribution. Fan-out makes rare slowness at one dependency show up regularly at the root request, because any slow child can hold the whole operation open. The consequence is that median latency can improve while users still feel the slow cases.

$$1 - (1 - p)^{n}$$

The chance that at least one of the calls a request depends on is slow, when the calls are independent. At 1 percent and 100 calls this is about 63 percent, so a rare event at the leaf is the common case at the root. Correlation moves the number toward the single-call rate, since calls that stall together on one overloaded shard behave closer to one call than to a hundred.

symbol	meaning
$p$	the probability that a single call is slow
$n$	the number of calls one request fans out to

Why median is nearly useless

A user session issues many requests, and the probability that all of them land near the median falls quickly. The session’s felt speed is set by its slowest request rather than its typical one.

Metric	What it measures	Actionability
Median	Experience almost nobody has in full	Moves hardly at all when tail doubles
99th percentile	The slow user	Requires structural changes
Average	Value neither typical nor slow user experiences	Useless for diagnosis

Fan-out amplification

An event that an individual service owner reasonably calls rare is, at the root of the call tree, the normal case. The 99th percentile of a leaf service is the property that matters; improving its median buys the system almost nothing.

Hedged and tied requests

Technique	How it works	Tradeoff
Hedged request	Send to second replica after waiting ~95th percentile latency; take whichever answer arrives first	Small extra load (only slowest few percent trigger hedge); large improvement at tail
Tied request	Send a second copy after a short delay; each replica knows its counterpart; first to start cancels the queued twin	Removes most duplicated execution; requires cancellation message

Dean and Barroso suggest a delay of twice the average network message delay between tied copies, to reduce the chance that both start before cancellation arrives. They describe these techniques as most applicable to operations without critical changes to system state. Duplicated execution still needs to be safe because cancellation can arrive too late. Both techniques stop helping when slowness is caused by a shared resource both replicas depend on.

What the measurements show

A fast individual leaf does not imply a fast whole query. In Dean and Barroso’s The Tail at Scale, one real Google service had a 99th-percentile completion time of 10 ms for a randomly chosen leaf request, measured at the root, compared with 140 ms for all leaf requests to finish.

In a separate Bigtable benchmark reading 1,000 keys across 100 servers, a hedge issued after 10 ms cut the 99.9th-percentile completion time from 1,800 ms to 74 ms with 2% more requests. For small uncached Bigtable reads from the distributed file system, a tied copy sent 1 ms later cut that percentile by nearly 40% when the benchmark ran in isolation. Tied requests added less than 1% disk utilization in both the isolated test and a test with a concurrent sorting job.

Sources of tail latency

Source	Mechanism
Queueing	As utilization rises toward saturation, waiting time grows non-linearly
GC pauses	Multi-hundred-millisecond delays injected into otherwise healthy processes
Noisy neighbors	Shared hardware competing for memory bandwidth, cache, storage queues
Background activity	Compaction, index maintenance, log rotation invisible in application metrics
Head-of-line blocking	Single slow request blocks a connection
Retry storms	Arrive exactly when service is already struggling

TCP congestion feedback

Network loss recovery can hold up a response after the backend computation has finished. The Transmission Control Protocol (TCP) limits unacknowledged data through a sender-side congestion window, cwnd. In the baseline congestion-avoidance algorithm specified by RFC 5681, that window grows by roughly one full-sized segment, a TCP data packet, per round-trip time (RTT). Acknowledgments permit growth; loss signals that the sender should reduce traffic.

On the first retransmission timeout for a segment, the slow-start threshold, the window at which startup switches to congestion avoidance, is capped at half the bytes still in flight with a two-segment floor. With FlightSize for those unacknowledged bytes and SMSS for the sender’s maximum segment payload, the bound is ssthresh = max(FlightSize / 2, 2 * SMSS). The congestion window itself falls to at most one full-sized segment, the loss window, before slow start rebuilds it. That pause and recovery can extend the tail even if server execution time is unchanged.