#!/usr/bin/env python3
"""
W3 — Split-brain, and the one inequality that prevents it.  (~60 min)

Miniature of P05. A deterministic, replayable simulator of leader election under
partition. Run it with a majority rule and with a plurality rule, and watch exactly
one of them elect two leaders in the same term.
"""
import random
from itertools import combinations

class Node:
    def __init__(self, nid): self.id=nid; self.term=0; self.voted={}; self.leader=False

def election(nodes, candidate, reachable, quorum):
    """candidate stands for election in a new term; only `reachable` peers hear it."""
    c = nodes[candidate]
    c.term += 1
    votes = 1                                  # a candidate votes for itself
    c.voted[c.term] = candidate
    for n in nodes:
        if n.id == candidate or n.id not in reachable: continue
        if n.term < c.term: n.term = c.term
        if n.voted.get(n.term) is None:        # one vote per term, first come first served
            n.voted[n.term] = candidate
            votes += 1
    won = votes >= quorum
    c.leader = won
    return won, votes

def trial(N, quorum, partition, seed):
    """partition: list of mutually unreachable groups. Returns leaders per term."""
    nodes = [Node(i) for i in range(N)]
    rng = random.Random(seed)
    leaders = {}
    # one candidate stands in each partition, in a deterministic order
    for group in partition:
        cand = min(group)
        won, votes = election(nodes, cand, set(group), quorum)
        if won:
            leaders.setdefault(nodes[cand].term, []).append((cand, votes))
    return leaders

N = 5
print(f"N = {N} replicas, partitioned into a 3-group and a 2-group\n")
partition = [[0, 1, 2], [3, 4]]

for quorum, label in ((3, "majority  (Q=3, 2Q=6 > 5)  CORRECT"),
                      (2, "plurality (Q=2, 2Q=4 <= 5) BROKEN ")):
    leaders = trial(N, quorum, partition, seed=0)
    total = sum(len(v) for v in leaders.values())
    dup = {t: v for t, v in leaders.items() if len(v) > 1}
    print(f"quorum={quorum}  {label}")
    for t, v in sorted(leaders.items()):
        for cand, votes in v:
            print(f"    term {t}: node {cand} elected with {votes} votes")
    print(f"    -> {total} leader(s);  SPLIT-BRAIN: {bool(dup) or total > 1}\n")

print("=" * 66)
print("Both partitions elect in term 1. With Q=2 the 2-group can also reach quorum,")
print("so two nodes believe they lead the same term and both accept writes. With")
print("Q=3 the 2-group cannot, and correctly refuses service.\n")

print("Exhaustive check of the inequality (the proof, brute-forced):")
print(f"{'N':>3} {'Q':>3} {'2Q>N':>6} {'disjoint quorums exist?':>24}")
print("-" * 40)
for N in range(2, 8):
    for Q in range(1, N + 1):
        nodes = range(N)
        disjoint = any(not (set(a) & set(b))
                       for a in combinations(nodes, Q) for b in combinations(nodes, Q))
        flag = "" if (not disjoint) == (2 * Q > N) else "  <-- MISMATCH"
        if Q in (N // 2, N // 2 + 1):          # only print the interesting boundary
            print(f"{N:>3} {Q:>3} {str(2*Q>N):>6} {str(disjoint):>24}{flag}")
print("\nThe boundary is exactly floor(N/2)+1. For N=6 that is 4, not 3 --")
print("even replica counts are where operators get this wrong.")