Replication and Consistency Models

Replication is the maintenance of multiple copies, called replicas, of the same logical data item on different physical machines (or failure domains). The purpose is threefold: durability (a replica surviving a crash preserves the data), availability (a client can be served by any live replica), and performance (reads can be spread across replicas, and clients can talk to a nearby copy). The central difficulty is that once there is more than one copy, an update to one copy must somehow be reflected — immediately or eventually — in the others, and concurrent operations from different clients can arrive at different replicas in different orders. A consistency model is a formal contract between the distributed system and the programs that use it. It specifies, given a set of operations issued by possibly many clients, which interleavings ("histories") of those operations are legal for the system to expose. The strongest useful model, linearizability, requires that every operation appear to take effect atomically at some point between its invocation and its response, consistent with a single global real-time order — as if there were only one copy of the data and no concurrency at all. Weaker models relax this: sequential consistency drops the real-time constraint but keeps a single total order that respects each client's own program order; causal consistency only orders operations that are causally related (a read that observed a write must see that write, and everyone must see causally dependent writes in the same order); eventual consistency guarantees only that, absent new writes, all replicas will eventually converge to the same state, with no ordering guarantee in the meantime. Replication strategies are the mechanisms that implement points on this spectrum. Primary-backup (primary-copy) replication designates one replica as primary; all writes go through it and it propagates updates to backups, either synchronously (strong consistency, lower availability) or asynchronously (weaker consistency, higher availability). Chain replication arranges replicas in a pipeline: writes enter at the head and flow to the tail, reads are served at the tail, giving strong consistency with better write throughput than a naive synchronous primary-backup scheme. Quorum-based replication requires a write to be acknowledged by `W` out of `N` replicas and a read to consult `R` replicas, tuning consistency and availability by adjusting `W` and `R`. State-machine replication (SMR), built directly on a consensus protocol such as Paxos or Raft, applies the same sequence of operations in the same order to every replica, which is the standard mechanism for achieving linearizability in production systems.

Primary-backup replication

The primary serializes all writes (giving them a total order for free) and ships them to backups. ``` // Primary node function handle_write(op): apply(op, local_state) log.append(op) for backup in backups: send(backup, REPLICATE, op, log.seq_no) if mode == SYNCHRONOUS: wait_for_acks(backups, quorum = len(backups)) // or majority respond_to_client(SUCCESS) // Backup node function on_replicate(op, seq_no): if seq_no == expected_seq_no: apply(op, local_state) expected_seq_no += 1 send(primary, ACK, seq_no) else: request_retransmission(expected_seq_no) // gap detected function handle_read(client, mode): if mode == "read-from-primary": return primary.local_state // strong else: return local_state // possibly stale ``` Synchronous replication (primary waits for all/majority acks before replying) gives strong consistency but blocks on the slowest backup and cannot make progress if too many backups are unreachable. Asynchronous replication (primary replies before backups ack) is fast and available but can lose acknowledged writes if the primary crashes before propagation — a classic durability/latency tradeoff.

Quorum replication (Dynamo-style)

Assign `N` replicas to each data item. A write must succeed at `W` replicas; a read must query `R` replicas and return the most recent (highest-version) value seen. ``` function quorum_write(key, value): version = new_version_number() acked = 0 for replica in preference_list(key)[0:N]: send_async(replica, PUT, key, value, version) while acked < W and not timed_out(): if receive_ack(): acked += 1 if acked >= W: return SUCCESS else: return FAILURE // client may retry or accept degraded write function quorum_read(key): responses = [] for replica in preference_list(key)[0:N]: send_async(replica, GET, key) while len(responses) < R and not timed_out(): responses.append(receive_response()) best = argmax(responses, key = lambda r: r.version) // read repair: push best value to stale replicas for r in responses: if r.version < best.version: send_async(r.replica, PUT, key, best.value, best.version) return best.value ``` The correctness of quorum systems rests on a single arithmetic fact, proved below: if `W + R > N`, every read quorum intersects every write quorum, so at least one replica in any read set has seen the most recent completed write.

State-machine replication via consensus

To get linearizability without a fixed primary bottleneck (or to survive primary failure without losing acknowledged writes), replicate a deterministic state machine and use a consensus protocol to agree on the order of operations. ``` function client_request(op): seq = consensus.propose(op) // Paxos/Raft agree on log position + value wait_until(applied_upto >= seq) return apply_log_entry(seq) // deterministic apply, same on every replica // On every replica, driven by the consensus layer's committed log: function on_commit(seq, op): assert seq == applied_upto + 1 // apply in strict log order result = state_machine.apply(op) applied_upto = seq if is_leader(): respond_to_client(result) ``` Because consensus guarantees all replicas commit the same sequence of operations in the same order, and each replica applies them deterministically, all replicas pass through the identical sequence of states — this is exactly what makes the composite system behave like one machine, hence "state machine replication."

Latency. Synchronous replication to `k` backups (or a quorum of size `k`) has write latency bounded below by the round-trip time to the slowest of the `k` acknowledging replicas, i.e. `O(RTT_max)` for one network round trip, versus `O(RTT_local)` for a single unreplicated write. Asynchronous replication keeps client-visible write latency at `O(RTT_local)` but defers propagation, which is exactly the source of weaker consistency. State-machine replication via Paxos costs at least one full round trip to a majority of replicas per committed operation — the same lower bound as Paxos itself, since SMR literally is repeated instances (or a single multi-Paxos log) of consensus.

Message complexity. A single quorum write sends `O(N)` messages and waits for `W` responses; a quorum read symmetrically sends `O(N)` and waits for `R`. State-machine replication using Paxos costs `O(N)` messages per proposal in the steady state (one leader broadcasting to `N-1` acceptors) plus `O(N)` for the collection of acks, matching the bounds established for Paxos itself.

Storage. Replication factor `N` multiplies storage cost by `N` compared to an unreplicated system; this is the explicit price of fault tolerance, and it is what allows the system to survive `f = N - 1` replica failures in a crash-only model (any 1 surviving replica retains the data) or, more usefully, allows availability to survive `⌊(N-1)/2⌋` failures under quorum/consensus schemes that require a majority to remain reachable.

Correctness of the quorum intersection argument. Claim: if `W + R > N`, then any read quorum and any write quorum share at least one replica. Proof. Suppose for contradiction that a write quorum `A` (`|A| = W`) and a read quorum `B` (`|B| = R`) are disjoint. Then `|A| + |B| = |A ∪ B| ≤ N` (since `A` and `B` are both subsets of the `N` replicas and disjoint unions cannot exceed the universe size). But `|A| + |B| = W + R > N` by hypothesis, a contradiction. Hence `A ∩ B ≠ ∅`. ∎ This guarantees that a read quorum always includes at least one replica holding the most recently committed write — but by itself it does not guarantee linearizability. Two subtleties matter: 1. Write ordering across replicas. If two writes are concurrent and are applied in different orders at different replicas (no total order is enforced), the intersecting replica might hold either value, and different readers overlapping different subsets could observe non-monotonic version histories. Real quorum systems (e.g., Dynamo) attach version vectors/timestamps and use "last write wins" or explicit conflict resolution to cope, trading a clean total order for availability during concurrent writes. 2. Partial writes. If a write reaches only some of its `W` targets before a client observes a response (or before the coordinator crashes), a subsequent read might see an in-progress write. Read-repair and hinted handoff are engineering patches for this gap, not proofs of linearizability. So quorum replication alone typically achieves a model between eventual and causal consistency, unless combined with strict versioning and synchronous conflict resolution — it takes full consensus (state-machine replication) to get linearizability with certainty.

Correctness of state-machine replication. SMR's correctness follows directly from two properties inherited from the underlying consensus protocol and one property of the application layer:

• Agreement/Total order (from Paxos/Raft): all correct replicas commit the identical sequence of log entries.
• Determinism (application requirement): applying the same operation to the same starting state always produces the same resulting state and the same output, on every replica.

By induction on log position `i`: if all replicas have identical state after applying entries `1..i-1` (base case `i=0`, all replicas start in the same initial state), and entry `i` is identical across replicas (by Agreement) and applied deterministically (by Determinism), then all replicas have identical state after applying entry `i`. Hence all replicas remain in lock-step forever, and any client reading from any replica after it has applied entry `i` observes a state consistent with a single serial execution of the first `i` operations — precisely a linearizable history when combined with proper read handling (reading only after confirming the read is ordered after all causally-prior writes, typically by routing reads through the leader or via a read-index/lease protocol).

Tradeoffs, honestly. Stronger consistency models are not "better" in an absolute sense — they are more expensive. Linearizability requires a majority round trip on every write and complicates reads (a stale-replica read is a correctness bug, not just a performance quirk). Weaker models let the system stay available and fast during partitions and slow links, at the cost of pushing conflict resolution and staleness reasoning onto the application. This exact tension is what the CAP Theorem formalizes and what Eventual Consistency exploits deliberately.

Consider a key-value store with `N = 5` replicas, `R1..R5`, storing the key `"cart:42"`, configured for quorum replication with `W = 3, R = 3`.

Initial state: all replicas hold `value = {}, version = 0`.

Why it worked: B's read quorum `{R2, R4, R5}` and A's write quorum `{R1, R2, R3}` intersect at `R2` — guaranteed because `W + R = 3 + 3 = 6 > N = 5`, exactly the arithmetic proved above. Even though two of the five replicas were stale at read time, the overlap replica carried the correct version number, letting the coordinator detect and surface the freshest value.

Now the interesting failure case: suppose instead `W = 2, R = 2` (so `W + R = 4 = N - 1`, violating the intersection condition). If A's write quorum happens to be `{R4, R5}` (the two slow replicas from before) and B's read quorum happens to be `{R1, R2}`, the two quorums are disjoint. B's read returns `{}`, version 0 — a stale read with no way to even detect staleness, since the coordinator has no signal that a newer version exists elsewhere. This single misconfigured parameter silently downgrades the system from "read of latest write guaranteed" to "read of latest write not guaranteed," with no error raised anywhere — illustrating exactly why the quorum arithmetic is not optional bookkeeping but the entire correctness argument.

Replication and consistency theory grew out of database transaction processing and then merged with distributed systems and consensus research as networks became unreliable and geographically spread.

Primary-backup replication with synchronous commit underlies traditional relational databases' high-availability configurations, such as PostgreSQL synchronous streaming replication and MySQL semi-synchronous replication, where a standby must acknowledge before a transaction commits. Chain replication and its variants appear in systems like Microsoft's storage stacks and CRAQ, valued for high write throughput with strong consistency. Quorum-based replication with tunable `W`/`R` is the design of Amazon Dynamo and its many descendants (Cassandra, Riak, Voldemort), which deliberately favor availability and let applications choose their consistency level per operation. State-machine replication via Paxos or Raft is the backbone of etcd, ZooKeeper, CockroachDB, Spanner, and the Raft-based consensus layers inside most modern distributed databases and container-orchestration control planes (Kubernetes stores all cluster state in an etcd Raft-replicated log). Content-delivery networks and multi-region caches lean on weaker, eventually consistent replication because global synchronous consistency would make every write pay cross-continental latency. Understanding this spectrum is the prerequisite for reasoning precisely about Linearizability as an exact correctness criterion, about Eventual Consistency as a deliberate availability-first design, and about the fundamental tradeoff captured by the CAP Theorem.

Ask the tutor: How would you redesign the quorum parameters and repair strategy if the system needed to tolerate not just crash failures but Byzantine replicas?