Consensus and Consistency §

Why FLP matters: it shows that consensus requires either (1) synchrony (bounded message delays), (2) randomization (probabilistic termination), or (3) a failure detector (a mechanism that detects crashes). In practice, systems use a combination: timeouts (approximate synchrony) + leader election (randomization via random timeouts).

Byzantine faults (malicious nodes) require $n \geq 3f + 1$ nodes; see Adversarial-failure for the full treatment.

Consistency (C): all nodes see the same data at the same time. A read after a write returns the written value. This is the strongest guarantee (linearizability).

Availability (A): every request gets a response, even if the response is stale. The system does not block or return errors during a partition.

Partition tolerance (P): the system tolerates network partitions. Since real networks partition, P is non-negotiable for any distributed system. The choice is C vs. A.

Examples:

• CP (choose consistency): Raft, ZooKeeper, etcd. During a partition, the minority side returns errors.
• AP (choose availability): Dynamo, Cassandra, CouchDB. During a partition, both sides accept writes; conflicts are resolved later.

The CAP theorem is the organizing principle for the consistency models below: linearizability is the C extreme, eventual consistency is the A extreme.

Quorum: $2f + 1$ nodes tolerate $f$ crash failures. For 3 nodes: quorum = 2. For 5 nodes: quorum = 3. For 7 nodes: quorum = 4. See Fault-Tolerance for replication strategies and quorum-based read/write policies.

Quorum intersection property: any two quorums of $n$ nodes (size $> n/2$) must share at least one node. This is the safety argument: if a value is committed (accepted by a quorum), any future leader (elected by a quorum) must have heard of it.

Leader election (Raft): each node has a random election timeout (150–300 ms). If no heartbeat is received within the timeout, the node becomes a candidate and increments its term. It votes for itself and requests votes from peers. The first candidate to get a quorum becomes the leader.

Raft state machine:

Log compaction: the log grows unbounded. Snapshots: periodically, a node saves its state and truncates the log. A new follower that is too far behind receives a snapshot instead of the full log.

2PC details: 2PC is blocking: if the coordinator crashes after participants have voted “yes” but before sending the commit, participants are stuck in the “prepared” state. This is why 2PC is used for short-lived transactions, not for long-running consensus. Paxos and Raft solve this by making the log the source of truth.

Linearizability vs. serializability: linearizability adds a real-time constraint. If client X writes value 5 at time t₁ and client Y reads at time t₂ > t₁, a linearizable system must return 5 to Y. A serializable system might return an older value if the serial order places Y’s read before X’s write.

MVCC (Multi-Version Concurrency Control): readers see a snapshot; writers create new versions. Provides snapshot isolation (a weaker form of serializability). Used in PostgreSQL, Oracle, and many NoSQL stores.

Causal consistency in practice: implemented with vector clocks or hybrid logical clocks. DynamoDB’s “strong” consistency is linearizable; its “eventual” mode is eventual consistency.

Choosing a model:

• Linearizability: financial transactions, leader election, distributed locks.
• Causal consistency: collaborative editing, social media feeds.
• Eventual consistency: DNS, CDN caches, analytics.

The single-machine analog of consensus is the mutex: a lock ensures mutual exclusion among threads, just as a quorum ensures agreement among nodes. Message delivery semantics (at-least-once, exactly-once) and message queues are covered in Message-Passing.

1. Detection: B, C, D, E stop receiving heartbeats from A. After their election timeouts (150–300 ms, random), they become candidates.

2. Election: Suppose B’s timeout fires first. B increments its term to 2, votes for itself, and sends RequestVote to C, D, E. C, D, E have not voted in term 2, so they grant their votes. B has 4 votes (itself + C, D, E) > quorum (3). B becomes the leader.

3. Safety: B’s log is at least as up-to-date as any other node’s log (Raft’s election restriction: a candidate must have a log at least as up-to-date as a quorum of peers). B cannot commit entries from a previous term that were not committed. Any entry that was committed before A’s crash is in B’s log.

   Quorum intersection guarantee: the committed entry was written to a quorum (3 of 5 nodes). B was elected by a quorum (3 of 5 nodes). By the pigeonhole principle, these two quorums share at least one node, so B (or a node that voted for B) has the committed entry.

4. Recovery: B sends heartbeats to C, D, E. They switch to follower mode and accept B’s term. If D’s log is behind B’s, B sends the missing entries via AppendEntry. D applies them and catches up.

Guarantee: no committed entry is lost. The new leader’s log contains all committed entries. The system continues to make progress as long as a quorum (3 of 5) is alive.