Replication, Consistency and Consensus
Open in the Padhaiko app4.1 Replication: Motivation, Passive, Active, Multi-Leader, and Leaderless Replication
Data Replication
Replication is the maintenance of multiple copies (replicas) of the same data object across multiple independent nodes or geographic regions in a distributed system.
Motivation for Replication
- Reliability and Fault Tolerance: If one replica crashes or a disk fails, surviving replicas continue serving requests without data loss.
- Performance and Low Latency: Placing replicas geographically closer to clients shortens round-trip time (RTT).
- Read Scalability: Read requests can be distributed across many replicas instead of overloading a single node.
- Core Trade-Off: Replication makes reads fast and resilient, but updates must propagate to all replicas, creating a fundamental tension between consistency, availability, and latency.
4.1.1 Passive (Primary-Backup) vs. Active Replication
| Aspect | Passive (Primary-Backup) Replication | Active (State-Machine) Replication |
|---|---|---|
| Where Execution Happens | Only the primary (leader) processes each write and sends resulting state updates to backups | Every replica independently receives and executes the same sequence of operations |
| Ordering Requirement | Primary determines the total order of writes | Requires Total-Order (Atomic) Multicast so all replicas execute in identical order |
| Determinism | Operations can be non-deterministic (primary computes the new value/timestamp once) | Operations must be deterministic (no unseeded random numbers or local clocks) |
| Failover Behavior | Backup must be promoted on primary crash (brief pause/election) | Seamless—remaining replicas already hold identical state |
4.1.2 Single-Leader, Multi-Leader, and Leaderless Replication
- Single-Leader Replication: One designated leader accepts all writes and ships a replication log synchronously or asynchronously to follower replicas (e.g., PostgreSQL, MySQL primary-replica). Simple conflict avoidance, but writes scale only to one leader and cross-region writes pay WAN latency.
- Multi-Leader Replication: Multiple nodes (e.g., one leader per data center) accept writes locally and replicate asynchronously to other leaders. Improves local write latency and survives single-datacenter outages, but concurrent writes to the same key create write conflicts requiring resolution (Last-Write-Wins, CRDTs, or custom merge logic).
- Leaderless Replication (Dynamo-Style): Clients send writes and reads directly to multiple replicas in parallel using quorums (), read repair, and anti-entropy (Merkle trees) with version vectors to reconcile divergent siblings.
4.2 Data-Centric Consistency Models: Linearizability, Sequential, and Causal Consistency
A consistency model is a contract between the distributed data store and its processes specifying what values a read operation may return when concurrent reads and writes occur.
4.2.1 Linearizability (Strict / Atomic Consistency)
Linearizability
An execution is linearizable if:
- All operations appear to execute atomically at a single point in real physical time between each operation's invocation and its completion response.
- Every read returns the value written by the most recent write in that global real-time order.
Linearizability provides the strongest single-object guarantee (as if there were only one physical copy), but requires cross-node coordination on every read/write, sacrificing availability during network partitions (CAP Theorem: under a Partition, a system must choose between Consistency/Linearizability and Availability).
4.2.2 Sequential Consistency
Introduced by Lamport (1979), sequential consistency drops real-time bounds while preserving a single global order:
- The result of any execution is the same as if the operations of all processes were executed in some single total sequential order, and
- The operations of each individual process appear in this global sequence in the exact order specified by its own program (program order).
- Key Difference from Linearizability: Two concurrent processes may observe a write take effect slightly later than wall-clock time, as long as all processes agree on the exact same global sequence.
4.2.3 Causal Consistency
Causal consistency weakens sequential consistency by ordering only causally related writes (, e.g., via Lamport/vector clocks or read-from dependencies):
- All processes must observe causally related writes in the same causal order.
- Concurrent writes () may be observed in different orders by different processes.
- Example: In a forum thread, a reply must never appear before the question it answers (causal order), whereas two unrelated comments posted concurrently can appear in either order on different replicas.
| Model | Global Total Order? | Respects Real-Time Order? | Respects Program Order? | Respects Causality? |
|---|---|---|---|---|
| Linearizability | Yes | Yes | Yes | Yes |
| Sequential Consistency | Yes | No | Yes | Yes |
| Causal Consistency | Only on causal chains | No | Per-process causal chains | Yes |
| Eventual Consistency | Only after quiescence | No | No | Not guaranteed |
4.3 Client-Centric Consistency Models: Eventual Consistency, Read-Your-Writes, Monotonic Reads
When data stores use eventual consistency (if no new updates occur, all replicas eventually converge to the same value), a mobile or multi-session client switching between replicas can experience jarring anomalies unless client-centric guarantees are enforced.
- Eventual Consistency: Weakest convergence guarantee—replicas may temporarily disagree after writes, but converge once updates stop and anti-entropy completes.
- Read-Your-Writes (Read-Your-Own-Writes) Consistency: A client that writes a value is guaranteed that its own subsequent reads will return (or a newer write), never an older value—even if routed to a different replica. Implementation: Route the user's reads to the leader for a short window after a write, or pass the client's last write timestamp to replicas so stale replicas wait before serving.
- Monotonic Reads Consistency: If a client has seen value of key at time , any later read by that same client at will never return an older value from before (no "moving backward in time"). Implementation: Pin each client session to a fixed replica (sticky sessions) or require the replica's version vector to dominate the client's last-seen version.
- Monotonic Writes & Writes-Follow-Reads: A client's writes are serialized in the order issued, and a write performed after reading is ordered after the write that produced .
4.4 Quorum-Based Protocols and Replica Management
In quorum-based replication (Gifford, 1979), a data item is replicated across nodes, and operations do not require contacting all replicas. Instead, every read contacts a read quorum of replicas and every write contacts a write quorum of replicas.
Quorum Intersection Rules
To guarantee strong consistency (preventing stale reads and concurrent write conflicts) across replicas:
- Read-Write Overlap: Every read quorum must intersect every write quorum at least at one up-to-date replica:
- Write-Write Overlap: Every two write quorums must intersect so two concurrent writes cannot proceed independently:
Weighted Voting and Dynamic Replica Management
- Weighted Voting: Each replica can be assigned a weight totaling ; then and allow prioritizing fast/local replicas with higher vote weights.
- Sloppy Quorums & Hinted Handoff: Under network partitions (e.g., Amazon Dynamo), if home replicas are unreachable, writes temporarily succeed on reachable fallback nodes with a hint to hand the data back once home nodes recover—trading strict consistency ( overlap no longer guaranteed on home nodes) for high write availability.
- Anti-Entropy & Read Repair: Replicas synchronize background differences using Merkle trees (hash trees of key ranges) and fix stale replicas lazily when a read detects an outdated version.
4.5 Distributed Transactions: Two-Phase Commit and Three-Phase Commit
When a transaction updates data across multiple independent shards or resource managers (participants), it must satisfy atomicity (all commit or all abort).
4.5.1 Two-Phase Commit (2PC)
A coordinator orchestrates commit across participants in two phases:
- Phase 1 — Voting (Prepare) Phase:
- Coordinator logs
START_2PClocally and sendsPREPAREto all participants. - Each participant checks constraints, acquires locks, writes an undo/redo log stably to disk, and replies
VOTE_COMMIT(Yes) orVOTE_ABORT(No).
- Coordinator logs
- Phase 2 — Decision (Commit/Abort) Phase:
- If all participants voted
VOTE_COMMIT, coordinator stably logsGLOBAL_COMMITand sendsCOMMITto all; otherwise it logsGLOBAL_ABORTand sendsABORT. - Participants release locks, apply or roll back changes, and reply
ACK.
- If all participants voted
- Blocking Problem of 2PC: If a participant votes
VOTE_COMMIT(entering the UNCERTAIN state) and the coordinator crashes before broadcastingCOMMITorABORT, that participant cannot decide unilaterally (another participant might have votedABORT, or the coordinator might have already told another participantCOMMIT), so it must block and hold locks until the coordinator recovers!
4.5.2 Three-Phase Commit (3PC)
3PC eliminates 2PC's coordinator-crash blocking (assuming a synchronous network with bounded timeouts and crash-stop failures—no arbitrary network partitions) by splitting Phase 2 to insert an intermediate PRE_COMMIT phase:
- Phase 1 (
CAN_COMMIT/ Voting): Coordinator asksCAN_COMMIT?; participants replyYESorNO. - Phase 2 (
PRE_COMMIT): If all repliedYES, coordinator sendsPRE_COMMITand participants acknowledgeACK(now every surviving participant knows all votedYESand no abort occurred, though changes are not yet committed). - Phase 3 (
DO_COMMIT): Coordinator sendsDO_COMMIT; participants commit and release locks.
- Why 3PC Is Non-Blocking Under Synchronous Assumptions: If the coordinator crashes, a newly elected coordinator inspects any surviving participant's state: if any node is in
PRE_COMMIT, it is safe to commit; if no node reachedPRE_COMMIT, it is safe to abort. (In asynchronous WANs with partitions, 3PC can still split-brain, so real systems use consensus protocols like Paxos/Raft instead.)
| Aspect | Two-Phase Commit (2PC) | Three-Phase Commit (3PC) |
|---|---|---|
| Message Rounds | rounds ( messages normal case) | rounds ( messages normal case) |
| Coordinator Crash in Uncertain State | Blocking (participants hold locks until coordinator recovers) | Non-blocking (under synchronous timeout model without partitions) |
| Network Partition Tolerance | Blocks safely (preserves consistency) | Unsafe under asynchronous network partitions (split-brain risk) |
| Practical Usage | Widely used (XA transactions, SQL clusters) | Rarely used in practice (superseded by Paxos/Raft) |
4.7 Consensus Problem and Paxos
The Consensus Problem
In a distributed system of processes where each process proposes an initial value , a consensus protocol must satisfy three properties despite up to crash failures:
- Agreement: Every non-faulty process decides the exact same value.
- Validity: The decided value must be one of the values actually proposed by some process.
- Termination: Every non-faulty process eventually reaches a decision.
FLP Impossibility Result (Fischer, Lynch, Paterson, 1985)
In a purely asynchronous distributed system, no deterministic consensus protocol can guarantee all three properties (Safety + Liveness/Termination) if even a single process can fail by crashing. Practical consensus algorithms (Paxos, Raft) therefore guarantee safety (Agreement & Validity) always, and guarantee termination (liveness) once the network becomes eventually synchronous (long enough without leader failures/timeouts).
Single-Decree Paxos (Lamport)
Paxos defines three logical roles (often co-located on the same nodes): Proposers, Acceptors (fault-tolerant quorum storage), and Learners. Assume acceptors; any majority quorum has size so any two quorums share at least one acceptor.
Paxos runs in two phases with monotonically increasing proposal numbers (unique per proposer, e.g. (round, node_id)):
- Phase 1 — Prepare / Promise:
- Phase 1a (
Prepare(n)): A proposer picks a unique proposal number and sendsPrepare(n)to a majority of acceptors. - Phase 1b (
Promise(n, n_a, v_a)): If (the highest proposal number this acceptor has seen so far), the acceptor updates , promises never to accept any proposal numbered , and replies with the highest-numbered proposal it has already accepted (ornullif none).
- Phase 1a (
- Phase 2 — Accept / Accepted:
- Phase 2a (
Accept(n, v)): If the proposer receivesPromisefrom a majority quorum, it selects value :- If any acceptor returned an already-accepted value, the proposer must adopt the value corresponding to the highest returned!
- Otherwise (all returned
null), the proposer is free to propose its own value . It then sendsAccept(n, v)to the quorum.
- Phase 2b (
Accepted(n, v)): An acceptor accepts(n, v)if and only if (it has not promised to a higher proposal number in the meantime), persists(n_a = n, v_a = v), and notifies the proposer and learners. Once a majority accepts(n, v), the value is chosen.
- Phase 2a (
Worked Out Examples
4.1
A distributed key-value store replicates each key across nodes using quorum replication.
- Evaluate whether the following pairs satisfy both strong consistency () and write-write serialization (): (a) , (b) , (c) .
- Suppose nodes span two data centers, and the operator wants the fastest possible read that still guarantees strong consistency without allowing conflicting concurrent writes. Find the minimum valid and .
Part 1 — Checking Each Pair for ():
- (a) : (read-write overlap holds) and (write-write overlap holds). Valid strong quorum. Tolerates up to node failures for both reads and writes.
- (b) : and . Valid strong quorum (ultra-fast local reads from any node, but writes fail if even of the nodes is down).
- (c) : , HOWEVER ! Two concurrent writes can hit disjoint pairs of nodes and , creating silent write conflicts. Does NOT satisfy write-write serialization.
Part 2 — Minimizing Read Quorum for (): To prevent concurrent write conflicts, we require . With , to minimize subject to :
(Note: If were desired instead, would have to be so that , sacrificing write fault tolerance.)
- (a) and (b) satisfy both quorum rules; (c) fails write-write overlap ().
- For with minimal and , (or if reads must touch only node at zero write fault tolerance).
4.2
Consider a shared register initially accessed by three processes:
- :
W(x, 1)starting at real time and finishing at . - :
R(x) -> 0starting at and finishing at , followed byR(x) -> 1starting at and finishing at . - :
W(x, 2)starting at and finishing at , followed byR(x) -> 1starting at and finishing at .
Determine whether this history is (a) Linearizable and (b) Sequentially Consistent.
Checking Linearizability (Real-Time Order): In real time, W(x, 1) by finishes at , strictly before 's first read R(x) -> 0 starts at . Under linearizability, any read starting after W(x, 1) finishes must return (or a newer write ), never the initial value . Therefore, the history is NOT linearizable.
Checking Sequential Consistency (Global Order Preserving Program Order): Can we arrange all operations into a single global sequence respecting each process's own program order? Try the sequence:
Check each process's program order:
- :
W(x,1)(only 1 op). - :
R(x)->0beforeR(x)->1(preserved!). - :
W(x,2)beforeR(x)->1(preserved!). - Read validity: First read sees initial ;
W(x,2)overwrites ;W(x,1)overwrites ; both final reads see .
All rules hold! Therefore, the history IS sequentially consistent.
(a) Not Linearizable ( reads after 's write to already completed in real time). (b) Sequentially Consistent (valid total order: ).
4.3
Five Paxos acceptors start with no accepted proposals.
- What is the minimum quorum size ?
- Proposer runs Phase 1 with proposal number on , gets
Promise(1, null), and runs Phase 2Accept(1, "X"). Only and receive and accept(1, "X")before pauses. - Proposer now wants to propose
"Y"using proposal number and contacts quorum . Trace what receives in Phase 1b and what value must propose in Phase 2a!
1. Minimum Paxos Quorum Size:
2–3. Tracing Proposer () on Quorum :
- : Previously promised and accepted
(n_a = 1, v_a = "X"). Since , updates and repliesPromise(2, 1, "X"). - : Previously promised , never received
Accept. RepliesPromise(2, null). - : Never contacted before. Replies
Promise(2, null). - Phase 2a Value Selection by : Because returned an already-accepted proposal
(1, "X")(and no higher was returned), Paxos safety forbids from proposing"Y". must adopt"X"and sendAccept(2, "X")to the quorum.
- Quorum size .
- returns
(1, "X")while returnnull; by Paxos safety, must abandon"Y"and proposeAccept(2, "X")so"X"remains consistent.
Exercises
Practice Exercises — Replication, Consistency and Consensus
Compare Passive (Primary-Backup), Active, Multi-Leader, and Leaderless replication strategies, highlighting how each handles ordering, write conflicts, and non-deterministic operations.
Passive vs. Active Replication:
- Passive: Only the primary executes writes and ships state updates to backups; supports non-deterministic operations and avoids total-order multicast, at the cost of failover delay.
- Active: Every replica executes every operation in total-order multicast; requires deterministic execution, provides seamless failover.
Multi-Leader vs. Leaderless:
- Multi-Leader: Multiple datacenters accept writes locally and replicate asynchronously; fast local writes, but concurrent updates require conflict resolution (LWW, CRDTs).
- Leaderless: Clients write/read directly across quorum replicas using version vectors, read repair, and anti-entropy Merkle trees.
Passive serializes writes on one primary (allowing non-determinism); Active runs deterministic operations on all replicas via total-order multicast; Multi-Leader allows concurrent local writes with conflict resolution; Leaderless relies on client quorums, version vectors, and read repair.
Define Linearizability, Sequential Consistency, and Causal Consistency. Also distinguish between Read-Your-Writes and Monotonic Reads client-centric consistency models.
Data-Centric Models:
- Linearizability: Global total order respecting real physical time (every read sees the latest completed write).
- Sequential Consistency: Global total order respecting each process's program order, without strict real-time bounds.
- Causal Consistency: Only causally related operations are ordered identically everywhere; concurrent writes may appear in different orders.
Client-Centric Models:
- Read-Your-Writes: After a client writes , that client's subsequent reads always reflect (or a newer write).
- Monotonic Reads: Once a client reads version , later reads by the same client never return an older version than .
Linearizability enforces real-time global order; Sequential enforces one global order consistent with program order; Causal orders only causally dependent operations. Client-centric Read-Your-Writes ensures a writer sees its own updates, while Monotonic Reads prevents a reader from moving backward to stale versions.
A distributed database maintains replicas.
- If the write quorum is set to (minimum for write-write exclusion), what is the minimum read quorum required for strong consistency?
- If the system workload is reads and the operator sets for ultra-fast reads, what minimum write quorum is required? How many node failures can writes tolerate in that configuration?
1. Minimum when (): To satisfy :
(Also holds.)
2. Minimum when ():
(Note automatically holds.) Since a write requires of replicas to respond, writes can tolerate node failure.
- (symmetric majority quorum ).
- , tolerating node failure during writes.
Explain the blocking problem in Two-Phase Commit (2PC) and how Three-Phase Commit (3PC) attempts to overcome it. Why do modern cloud databases still prefer Paxos/Raft over 3PC?
2PC Blocking and 3PC Non-Blocking:
- 2PC Blocking: If the coordinator crashes after a participant votes
VOTE_COMMIT(entering the uncertain state), surviving participants cannot tell whether the decision wasCOMMITorABORT, so they must hold locks until the coordinator recovers. - 3PC: Inserts a
PRE_COMMITround between voting andDO_COMMIT. Under bounded synchronous timeouts (no partitions), a new coordinator commits if any survivor reachedPRE_COMMITand aborts otherwise.
Why Paxos/Raft Replace 3PC: Over real asynchronous networks, partitions can split nodes into two groups that time out simultaneously, causing split-brain (one side commits while the other aborts) in 3PC. Majority-quorum consensus (Paxos/Raft) guarantees safety under arbitrary network partitions and tolerates minority crashes without blocking.
2PC blocks when the coordinator crashes while participants are in the uncertain VOTE_COMMIT state. 3PC adds a PRE_COMMIT phase to unblock under synchronous assumptions, but fails safety under asynchronous network partitions—making Paxos/Raft standard in production.
State the three requirements of consensus, the FLP Impossibility Theorem, and trace the two phases (Prepare/Promise and Accept/Accepted) of Single-Decree Paxos.
Consensus Properties and FLP:
- Properties: Agreement (all correct nodes decide the same value), Validity (decided value was proposed by some node), Termination (all correct nodes eventually decide).
- FLP Theorem: In an asynchronous network, no deterministic consensus algorithm can guarantee both safety and termination if even one crash failure can occur.
Single-Decree Paxos Phases:
- Phase 1 (Prepare/Promise): Proposer sends
Prepare(n); acceptors promise not to accept proposals and return any highest already-accepted(n_a, v_a). - Phase 2 (Accept/Accepted): Once a majority promises, proposer picks the value with the highest (or its own if all
null) and sendsAccept(n, v); acceptors accept iff .
Consensus requires Agreement, Validity, and Termination; FLP proves no deterministic asynchronous algorithm achieves all three with crash faults. Paxos preserves safety via Prepare/Promise (blocking older proposals and adopting prior accepted values) followed by Accept/Accepted across majority quorums.