CHAPTER 04

Distributed Consistency, Consensus Protocols & Logical Clocks

Scaling beyond a single server machine introduces distributed network partitions, unpredictable message latency, clock drift, and split-brain risks. Achieving reliable state across clusters requires formal mathematical consensus primitives.

1. The CAP Theorem & PACELC Refinement

Consistency (C) Every read receives the most recent write or an error.

Availability (A) Every non-failing node returns a non-error response (without guarantee of latest write).

Partition Tolerance (P) System continues operating despite dropped or delayed messages between nodes.

PACELC Theorem Extension: If there is a Partition (P), trade off Availability (A) vs Consistency (C); Else (E), trade off Latency (L) vs Consistency (C).

• PC/EC (e.g. Spanner, HBase): Chooses Consistency under both partition and normal operation.
• PA/EL (e.g. Cassandra, DynamoDB): Chooses Availability during partitions, low Latency during normal operations.

2. Leaderless Quorum Replication (\(R + W > N\))

Dynamo-style databases (Cassandra, Amazon Dynamo) use leaderless replication configured by three parameters:

N
Replication Factor (e.g. 3 copies)

W
Write Quorum ACK count

R
Read Quorum Node count

Strong Consistency Guarantee: \(R + W > N\)

If \(N=3, W=2, R=2\), the read set and write set must overlap by at least one node containing the newest version. Read Repair and Anti-Entropy (using Merkle Trees) synchronize out-of-date nodes in the background.

3. Consistent Hashing with Virtual Nodes

Maps keys and server nodes to a circular hash ring (\(2^{32}-1\)). When a server node is added or removed, only \(\frac{K}{N}\) keys need remapping, eliminating total cache flush.

Virtual Nodes (V-Nodes): Each physical server is assigned 100-250 virtual positions on the ring. This balances key variance across machines with non-uniform hardware capacity.

4. The Raft Consensus Protocol

Raft enforces state machine replication across a cluster by decomposing consensus into three distinct sub-problems:

1. Leader Election Randomized election timeouts (150ms - 300ms) prevent split-vote deadlocks. Candidates request votes via RequestVote RPCs. A leader requires majority votes (\(\lfloor N/2 \rfloor + 1\)).

2. Log Replication Leader accepts client writes, appends entries to its log, and issues AppendEntries RPCs. Once entries are replicated on majority nodes, the leader commits and notifies followers.

3. Safety Requirement If a log entry is committed at a given index and term, it will be present in the logs of the leaders for all higher-numbered terms (Leader Completeness Property).

5. Logical Clocks & Google Spanner TrueTime

NTP (Network Time Protocol) clock drift across servers makes wall-clock timestamps unsafe for transaction ordering.

Lamport & Vector Clocks

Monotonically increasing logical counters. Vector clocks track causality across nodes: \(V_i[j]\) represents Node \(i\)'s knowledge of Node \(j\)'s clock.

Google Spanner TrueTime API

Uses GPS receivers and atomic clocks in datacenters to bound physical clock uncertainty: \(\text{TT.now}() \implies [t_{earliest}, t_{latest}]\) with \(\epsilon \le 7\text{ms}\). Enables external consistency without inter-datacenter communication locking.