S071 · Replication — Leader/Follower, Multi-Leader, Leaderless

"""s071_quorum_sim.py — leaderless replication with W/R tunable per request.
 
Demonstrates:
  * W + R > N guarantees at least one read sees the latest write.
  * W + R <= N allows stale reads.
"""
from __future__ import annotations
from dataclasses import dataclass, field
import random, time
 
 
@dataclass
class Replica:
    name: str
    store: dict[str, tuple[str, int]] = field(default_factory=dict)  # value, version(ts)
 
 
class Cluster:
    def __init__(self, n: int = 3):
        self.replicas = [Replica(f"r{i}") for i in range(n)]
 
    def _rand(self, k: int):  # pick k replicas at random
        return random.sample(self.replicas, k)
 
    def write(self, key: str, value: str, w: int) -> bool:
        ts = time.time_ns()
        acks = 0
        for r in self._rand(len(self.replicas)):
            # simulate 30% of replicas being slow / dropping this write
            if random.random() < 0.3:
                continue
            r.store[key] = (value, ts)
            acks += 1
            if acks >= w:
                return True
        return False
 
    def read(self, key: str, r: int) -> str | None:
        results = []
        for rep in self._rand(len(self.replicas)):
            if key in rep.store and len(results) < r:
                results.append(rep.store[key])
        if not results:
            return None
        # Take the highest version (LWW)
        return max(results, key=lambda vt: vt[1])[0]
 
 
if __name__ == "__main__":
    random.seed(42)
    N = 3
 
    print(f"N={N} replicas")
    for W, R in [(1, 1), (2, 2), (3, 1), (1, 3), (2, 1)]:
        cluster = Cluster(N)
        # write ‘v1’, then ‘v2’ — both with same W
        cluster.write("k", "v1", w=W)
        cluster.write("k", "v2", w=W)
        # read
        val = cluster.read("k", r=R)
        guarantee = "GUARANTEED latest" if W + R > N else "MAY be stale"
        print(f"  W={W} R={R}  W+R={W+R}  read={val!r}   ({guarantee})")