#!/usr/bin/env python3
"""A majority quorum decides only on the majority side of a partition, DDIA 2e Ch. 10.

Single-decree consensus modelled as a quorum: a proposed value is DECIDED only
when a strict majority of the cluster's nodes acknowledge it. floor(n/2)+1 acks
are required -- nothing less counts, however many nodes are alive.

Three things fall out, and two of them surprise people:

  1. Partition a 5-node cluster 3-2. The 3-node side reaches majority (3 >= 3)
     and DECIDES. The 2-node side has only 2 < 3 acks: it cannot decide, and it
     cannot even tell whether the other side already did. Only the majority side
     makes progress.

  2. Adding nodes raises the number of failures tolerated: floor((n-1)/2) is
     1, 2, 3 for n = 3, 5, 7. More replicas = more availability.

  3. But every decision STILL needs a full majority round-trip, and the majority
     GROWS with n: 2, 3, 4 acks for n = 3, 5, 7. So a single decision does not
     get faster with more nodes -- there is strictly more work per decision. The
     "more replicas = more throughput / my minority partition keeps serving"
     intuition is wrong on both counts.

Pure standard library, deterministic -> reproducible.
"""


def majority(n):
    """Strict majority of an n-node cluster: the smallest set any two majorities
    must overlap in. floor(n/2)+1."""
    return n // 2 + 1


def failures_tolerated(n):
    """A cluster of n survives losing this many nodes and still forms a majority
    from the rest: n - majority(n) = floor((n-1)/2)."""
    return n - majority(n)


class Cluster:
    """A single-decree consensus cluster of n nodes. propose() decides a value
    only if a majority of the *reachable* nodes acknowledge -- a full quorum
    round-trip. A partition makes only some nodes reachable to a given proposer."""

    def __init__(self, n):
        self.n = n
        self.quorum = majority(n)
        self.decided = None  # the value the cluster has agreed on, once any side decides

    def propose(self, value, reachable):
        """Try to decide `value` by collecting acks from `reachable` nodes.
        Succeeds iff we can reach a strict majority of the whole cluster.
        Returns (decided: bool, acks: int)."""
        acks = len(reachable)  # each reachable node sends exactly one ack
        if acks >= self.quorum:
            if self.decided is None:
                self.decided = value
            return True, acks
        return False, acks


def scenario_partition():
    print("=== Scenario 1: a 5-node cluster, partitioned 3-2 ===")
    n = 5
    cluster = Cluster(n)
    print(f"    cluster size n = {n}, majority needed = {cluster.quorum} acks\n")

    big_side = ["n1", "n2", "n3"]
    small_side = ["n4", "n5"]

    ok_big, acks_big = cluster.propose("x=BIG", reachable=big_side)
    print(f"    3-side {big_side} proposes x=BIG:")
    print(f"        collected {acks_big} acks, need {cluster.quorum} -> "
          f"{'DECIDED' if ok_big else 'BLOCKED'}")

    ok_small, acks_small = cluster.propose("x=SMALL", reachable=small_side)
    print(f"    2-side {small_side} proposes x=SMALL:")
    print(f"        collected {acks_small} acks, need {cluster.quorum} -> "
          f"{'DECIDED' if ok_small else 'BLOCKED'}")

    print()
    print(f"    cluster decided value: {cluster.decided!r}")
    print("    the 2-side cannot decide, and cannot even tell whether the 3-side")
    print("    already did -- it just blocks. Only the majority side progresses.\n")


def scenario_fault_tolerance():
    print("=== Scenario 2: failures tolerated vs. cluster size ===")
    print(f"    {'n':>3}  {'majority':>9}  {'failures tolerated':>18}")
    for n in (1, 3, 5, 7):
        print(f"    {n:>3}  {majority(n):>9}  {failures_tolerated(n):>18}")
    print("    adding nodes raises the failures tolerated: floor((n-1)/2) = 1, 2, 3.")
    print("    (an even node adds NO tolerance over the odd below it: n=4 also")
    print(f"     tolerates {failures_tolerated(4)}, same as n=3 -- so clusters stay odd.)\n")


def scenario_throughput():
    print("=== Scenario 3: acks per decision vs. cluster size ===")
    print(f"    {'n':>3}  {'acks per decision (= majority)':>32}")
    for n in (3, 5, 7):
        print(f"    {n:>3}  {majority(n):>32}")
    print("    every decision needs a full majority round-trip, and the majority")
    print("    GROWS with n: 2, 3, 4 acks. A single decision does more work, not")
    print("    less, as the cluster grows -- consensus throughput is flat-to-")
    print("    declining in n, never rising. More nodes buy availability, not speed.\n")


def main():
    scenario_partition()
    scenario_fault_tolerance()
    scenario_throughput()


if __name__ == "__main__":
    main()