Why two majorities always intersect, and why a lock with a TTL is not enough

# /// script
# requires-python = ">=3.10"
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Why two majorities always intersect, and a stale lock holder.

(a) Every pair of quorums of size q out of N, checked for a shared node.
(b) A lock with a TTL, a client that pauses past it, and a storage that
accepts any write, then one that checks a fencing token.
"""
import argparse, itertools, json, threading, time

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--ttl", type=float, default=5.0, help="Lock TTL, seconds.")
p.add_argument("--pause", type=float, default=8.0, help="Seconds client A pauses after taking the lock.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

# (a) quorum intersection
quorums = []
for n, q in ((5, 3), (6, 3), (6, 4)):
    pairs = list(itertools.combinations(itertools.combinations(range(n), q), 2))
    disjoint = sum(1 for a, b in pairs if not set(a) & set(b))
    quorums.append({"N": n, "quorum": q, "pairs": len(pairs), "disjoint_pairs": disjoint})
    print(f"N = {n}, quorums of {q}: {len(pairs):,} pairs, {disjoint} with no shared node")

# (b) a lock service with a TTL and a fencing token
class LockService:
    def __init__(self): self.holder, self.expires, self.token = None, 0.0, 0
    def acquire(self, who):
        now = time.monotonic()
        if self.holder is None or now >= self.expires:
            self.token += 1; self.holder, self.expires = who, now + args.ttl
            return self.token
        return None

def run(fenced):
    lock, store, log = LockService(), {"value": None, "highest": 0}, []
    def write(who, token):
        if fenced and token < store["highest"]:
            log.append(f"{who} rejected (token {token} < {store['highest']})"); return
        store["highest"] = max(store["highest"], token); store["value"] = who
        log.append(f"{who} wrote (token {token})")
    def client_a():
        tok = lock.acquire("A"); time.sleep(args.pause); write("A", tok)       # paused past the TTL
    def client_b():
        while (tok := lock.acquire("B")) is None: time.sleep(0.1)
        write("B", tok)
    ta = threading.Thread(target=client_a); ta.start(); time.sleep(0.05)
    tb = threading.Thread(target=client_b); tb.start(); ta.join(); tb.join()
    return store["value"], log

rows = []
for fenced in (False, True):
    final, log = run(fenced)
    rows.append({"storage": "checks the fencing token" if fenced else "accepts any write", "events": "; ".join(log), "final": final})
    print(f"{rows[-1]['storage']:<26} {'; '.join(log):<60} final value: {final}")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"quorums": quorums, "locks": rows}}, f)