Replication and quorums
To survive machine failures, distributed systems keep several copies, called replicas, of the same data. Replication brings consistency problems: if a write reaches only some replicas, readers may see stale data. A quorum system controls this by requiring a write to be acknowledged by W of the N replicas and a read to consult R replicas.
Python
from itertools import combinations
N = 3
replicas = [{"version": 0, "value": None} for _ in range(N)]
def write(value, version, targets):
for i in targets:
replicas[i] = {"version": version, "value": value}
def read(targets):
return max((replicas[i] for i in targets), key=lambda r: r["version"])["value"]
write("v1", 1, [0, 1])
print(read([1, 2]))
print(read([2]))
def always_overlap(w, r):
return all(set(ws) & set(rs) for ws in combinations(range(N), w) for rs in combinations(range(N), r))
print(always_overlap(2, 2))
print(always_overlap(2, 1))