Distributed Systems Theory
Quorum Systems
A quorum is the minimum number of replicas that must agree for a read or write to count — tuning the read quorum R and write quorum W against replication factor N trades consistency for availability and latency, one knob at a time.
- The core guarantee: if R + W > N, every read quorum overlaps every write quorum in at least one replica, so a read always sees the latest write
- W = N (write to every replica) maximizes read speed but any single replica being down blocks writes entirely
- R = 1, W = N or R = N, W = 1 push all the cost onto one side of the read/write ratio — tune to the workload
- R + W ≤ N is a valid, faster configuration — it just gives up the "read always sees latest write" guarantee (eventual consistency)
- Overlapping replicas can still disagree on which write is newest — quorum reads are typically paired with version vectors or timestamps to pick a winner
Quorums are the same majority-overlap idea behind Consensus Algorithms, applied directly to reads and writes on replicated data instead of to electing a leader: with N replicas, a write to any W of them and a read from any R of them are guaranteed to intersect in at least one replica as long as R + W > N — so at least one replica in the read set has seen the latest committed write.
| N | W | R | Property |
|---|---|---|---|
| 3 | 3 | 1 | Fast, simple reads; any replica down blocks all writes |
| 3 | 1 | 3 | Fast, simple writes; any replica down blocks all reads |
| 3 | 2 | 2 | Balanced — tolerates one replica being down for either |
| 3 | 1 | 1 | R+W ≤ N: fastest, but reads can return stale data (eventual consistency) |
CompletableFuture<Void> quorumWrite(List<Replica> replicas, Object value, int w) {
List<CompletableFuture<Void>> writes = replicas.stream()
.map(r -> r.writeAsync(value))
.toList();
// Succeed as soon as w of them complete; a straggler replica just catches up later.
return CompletableFuture.allOf(
writes.stream().limit(w).toArray(CompletableFuture[]::new)
);
}