Leader Election — একজনকে দায়িত্ব দেওয়ার protocol

লক্ষ্য: দুই protocol-এর message anatomy চোখের সামনে trace করা — কে কাকে কী পাঠাল, কত message খরচ হলো, winner কে।

# election_ring.py — ElectionRing: ring election vs majority-vote, hop-by-hop trace
N = 5
LEADER = N - 1                      # node 4 starts as leader, then dies


class ElectionRing:
    def __init__(self, mode="ring"):
        self.mode = mode
        self.alive = [True] * N
        self.log = []               # (tick, from, to, msg)
        self.tick = 0
        self.msgs = 0

    def next_alive(self, i):
        j = (i + 1) % N
        while not self.alive[j]:
            j = (j + 1) % N
        return j

    def send(self, frm, to, msg):
        self.msgs += 1
        self.log.append((self.tick, frm, to, msg))

    def kill(self, i):
        self.alive[i] = False

    # ---- ring protocol: ELECTION token carries highest id seen ----
    def elect_ring(self):
        origin = self.next_alive(LEADER)
        hi, cur = origin, origin
        while True:                                  # forward hop-by-hop
            nxt = self.next_alive(cur)
            if cur != origin:
                hi = max(hi, cur)
            self.send(cur, nxt, f"ELECTION(max={hi})")
            if nxt == origin:                        # token completed circle
                break
            cur = nxt
        cur = origin                                 # announce phase
        while True:
            nxt = self.next_alive(cur)
            self.send(cur, nxt, f"COORDINATOR(leader={hi})")
            if nxt == origin:
                break
            cur = nxt
        return hi

    # ---- majority variant: unicast votes, declare only with > N/2 ----
    def elect_majority(self):
        origin = self.next_alive(LEADER)
        votes = 1                                    # own vote
        for v in range(N):
            if v != origin and self.alive[v]:
                self.send(origin, v, "VOTE-REQUEST")
                votes += 1
                self.send(v, origin, f"VOTE-YES(for={origin})")
        if votes > N // 2:
            for v in range(N):
                if v != origin and self.alive[v]:
                    self.send(origin, v, f"COORDINATOR(leader={origin})")
            return origin
        return None

    def run(self):
        self.kill(LEADER)
        self.tick = 1
        return (self.elect_ring() if self.mode == "ring"
                else self.elect_majority())


for mode in ("ring", "majority"):
    r = ElectionRing(mode)
    w = r.run()
    print(f"=== mode={mode}: leader=node{w}, messages={r.msgs}")
    for t, f, to, m in r.log[:6]:
        print(f"  t{t:>2}  node{f} -> node{to}  {m}")
    if len(r.log) > 6:
        print(f"  ... (+{len(r.log) - 6} more)")

প্রত্যাশিত output (deterministic):

=== mode=ring: leader=node3, messages=8
  t 1  node0 -> node1  ELECTION(max=0)
  t 1  node1 -> node2  ELECTION(max=1)
  t 1  node2 -> node3  ELECTION(max=2)
  t 1  node3 -> node0  ELECTION(max=3)
  t 1  node0 -> node1  COORDINATOR(leader=3)
  t 1  node1 -> node2  COORDINATOR(leader=3)
  ... (+2 more)
=== mode=majority: leader=node0, messages=9
  t 1  node0 -> node1  VOTE-REQUEST
  t 1  node1 -> node0  VOTE-YES(for=0)
  t 1  node0 -> node2  VOTE-REQUEST
  t 1  node2 -> node0  VOTE-YES(for=0)
  t 1  node0 -> node3  VOTE-REQUEST
  t 1  node3 -> node0  VOTE-YES(for=0)
  ... (+3 more)

পড়ার সময়: ring-mode winner node3 (max-id invariant), majority-mode winner node0 (initiator) — একই cluster, ভিন্ন চুক্তি। Message-count প্রায় সমান (৮ বনাম ৯), কিন্তু majority-mode-র প্রতিটা vote আলাদা round-trip — WAN-এ ring-এর sequential hops আরও ব্যথা দেয়।

নিজে বাড়ান: node4-কে flapping করান (kill→revive লুপ) আর দেখুন bully-invariant কতবার re-election ট্রিগার করে; majority-mode-এ candidate নিজের বদলে lowest-id পেলে কী হয়?