Mastering Distributed Consistency: Paxos, NWR Model, and CAP Trade‑offs

Distributed systems must balance data completeness, consistency, and performance. This article systematically introduces techniques for handling distributed data consistency, such as Master‑Slave, Master‑Master, 2PC/3PC, the classic Byzantine Generals problem, Paxos, and Dynamo’s N‑R‑W and Vector Clock models.

Paxos Algorithm

Wikipedia provides detailed descriptions of various Paxos algorithms.

Paxos solves the problem of reaching agreement on a value in a distributed system that may experience failures, ensuring that all nodes eventually converge to a consistent state even when operations are applied in different orders.

Leslie Lamport proposed Paxos in 1990; after initial obscurity it was republished in 1998 and later clarified in 2001, gaining widespread adoption. Google’s Chubby lock service and Amazon’s internal services both rely on Paxos for consistency.

In simple terms, Paxos aims to make a cluster of nodes agree on changes to a value through a democratic voting process where a majority decides the outcome.

The algorithm proceeds in two phases assuming three nodes A, B, C:

Phase 1: Prepare – Node A sends a Prepare request with a unique, monotonically increasing proposal number to all nodes. Nodes reject proposals with numbers lower than the highest they have seen and promise not to accept lower numbers.

Phase 2: Accept – If A receives a majority of “Yes” responses, it sends an Accept request with the same proposal number. Nodes accept the value only if the proposal number is the highest they have seen.

This two‑stage process can be seen as an optimized version of two‑phase commit; 2PC/3PC are considered weaker alternatives, while Paxos is regarded as the definitive consensus algorithm.

Summary

The diagram from Ryan Barrett’s 2009 Google I/O talk illustrates that achieving high availability requires data replication, which introduces consistency challenges and performance trade‑offs, embodying the CAP theorem: a system can guarantee at most two of consistency, availability, and partition tolerance.

NWR Model

Amazon Dynamo’s N‑R‑W model lets users choose which two CAP properties to prioritize by configuring the number of replicas (N), the minimum number of successful writes (W), and the minimum number of reads (R) such that W+R > N.

When W=1 and N=3, a write succeeds after a single node acknowledges, but a read must query all three nodes, ensuring the latest version is returned. Conversely, setting W=N and R=1 favors write consistency over read latency.

Because N‑R‑W does not enforce strong consistency like Paxos, version conflicts can arise. Dynamo mitigates this by using vector clocks, where each node records its own version information, allowing applications to detect and resolve conflicts similarly to source‑code version control.

Example operation sequence:

A write to node A creates version D1(A,1); a subsequent write creates D2(A,2), overwriting D1.

D2 propagates to nodes B and C, so all three hold D2(A,2).

A new write to node B generates D3(A,2; B,1) with a global version of 3.

Before D3 reaches C, C processes another write, producing D4(A,2; C,1).

A read request with W=1 and R=3 reads all three nodes, observing versions D2(A,2), D3(A,2; B,1), and D4(A,2; C,1). The system can discard the stale D2 and must let the client resolve the conflict between D3 and D4.

Node A: D2(A,2)

Node B: D3(A,2; B,1)

Node C: D4(A,2; C,1)

This configuration emphasizes availability and partition tolerance (the A and P of CAP).