Implement Quorum Writes (N/W)

Quorum Writes in Dynamo

In a replicated system, every write must propagate to multiple nodes. The write quorum W defines the minimum number of nodes that must confirm receipt before the coordinator considers the write durable and responds to the client. This single parameter controls the entire availability-vs-consistency trade-off for writes.

The NWR Model

Dynamo exposes three tunable parameters that together define the replication contract for every operation:

• N — the total number of replicas maintained for each key (typically 3 in production Dynamo).
• W — the write quorum: the minimum number of replica acknowledgements required before a write is declared successful.
• R — the read quorum: the minimum number of responses required before a read is returned to the client.

The critical consistency condition is: W + R > N. When this holds, the set of nodes that participated in a write and the set that participates in a read must overlap by at least one node. That overlap guarantees at least one read response has seen the most recent write.

With Dynamo's defaults of N=3, W=2, R=2: the quorum sets each have size 2 out of 3, so they must share at least one member. Any read after a successful write is guaranteed to return the latest value.

Availability vs Consistency Trade-off

W	Fault tolerance	Consistency guarantee	Use case
1	N-1 failures tolerated	None (fire-and-forget)	Logging, metrics
2 (of 3)	1 failure tolerated	Strong (W+R=4>3)	Dynamo default
N	0 failures tolerated	Linearizable	Rarely used

What Happens to the Other N-W Replicas?

Dynamo still attempts to write to all N replicas asynchronously — it just does not wait for all of them. The coordinator fires writes to all N nodes simultaneously and returns OK as soon as W acknowledgements arrive. The remaining N-W replicas will either catch up via background anti-entropy (Merkle tree sync) or via read-repair the next time that key is read. This is the fundamental mechanism behind eventual consistency: the system converges to the latest value without requiring all replicas to be synchronously in agreement.

Coordinator Role

def write(key, value, replicas, W):
    acks = 0
    for replica in replicas:
        if replica.is_up():
            replica.write(key, value)
            acks += 1
    return 'OK' if acks >= W else 'FAIL'

Why It Matters

Amazon's shopping cart service uses W=1 for maximum availability — it is more important that the cart never fails to accept an item than that the item is immediately durable on multiple replicas. Other Dynamo use cases, such as billing records, use higher W values. The NWR model lets each application choose its own trade-off without changing the underlying storage engine.

Common Pitfalls

• W+R <= N gives no consistency guarantee: with W=1, R=1, N=3, a read can easily miss the latest write because neither quorum overlaps reliably.
• W=N is not truly atomic: even with all N replicas acknowledging, two concurrent writes can still interleave. Use vector clocks (Track 3) to detect and reconcile concurrent writes.
• Node count vs quorum size: if the number of available nodes drops below W, the write must fail or be buffered. Sloppy quorums (next task) address this with hinted handoff.