Paxos Intuition — consensus problem-এর প্রথম উত্তর

লক্ষ্য: experiment-এর ৩-acceptor duel-কে বড় cluster-এ, তিনজন প্রতিযোগী proposer-সহ generalize করা — দেখানো যে প্রতিটা নতুন, উঁচু-ballot proposer বারবার একই আগের value discover করে সেটাই পুনরায় adopt করে, কখনো ভিন্ন কিছুতে decide হয় না।

# paxos_cluster.py -- PaxosCluster: N=5 acceptors, 3 competing proposers
class Acceptor:
    def __init__(self, name):
        self.name = name
        self.promised = 0
        self.accepted_n = 0
        self.accepted_v = None

    def prepare(self, n):
        if n > self.promised:
            self.promised = n
            return True, self.accepted_n, self.accepted_v
        return False, self.accepted_n, self.accepted_v

    def accept(self, n, v):
        if n >= self.promised:
            self.promised = n
            self.accepted_n = n
            self.accepted_v = v
            return True
        return False


class Proposer:
    def __init__(self, pid, acceptors, majority):
        self.pid = pid
        self.acceptors = acceptors
        self.majority = majority

    def propose(self, n, value, phase1_targets, phase2_targets):
        print(f"--- proposer P{self.pid}: ballot n={n}, own value={value!r} ---")
        promises = []
        for a in phase1_targets:
            ok, an, av = a.prepare(n)
            print(f"  Prepare({n}) -> {a.name}: PROMISE (had accepted n={an}, v={av!r})")
            promises.append((an, av))
        if len(promises) < self.majority:
            print(f"  only {len(promises)}/{self.majority} promises -> no majority, retry later")
            return None
        best_n, best_v = max(promises)
        if best_n > 0:
            chosen = best_v
            print(f"  {len(promises)} promises, majority reached; highest prior accepted "
                  f"n={best_n} v={best_v!r} -> MUST adopt {chosen!r} (own {value!r} discarded)")
        else:
            chosen = value
            print(f"  {len(promises)} promises, majority reached; no prior accepted value "
                  f"anywhere -> free to propose own {chosen!r}")
        accepted_by = 0
        for a in phase2_targets:
            ok = a.accept(n, chosen)
            print(f"  Accept({n},{chosen!r}) -> {a.name}: {'ACCEPTED' if ok else 'REJECTED'}")
            if ok:
                accepted_by += 1
        if accepted_by >= self.majority:
            print(f"  {accepted_by}/{len(phase2_targets)} accepted -> "
                  f"** DECIDED value={chosen!r} at n={n} **")
            return chosen
        print(f"  only {accepted_by}/{len(phase2_targets)} accepted -> no decision this round")
        return None


B = [Acceptor(f"B{i}") for i in range(5)]
MAJORITY = len(B) // 2 + 1
print(f"acceptors={[b.name for b in B]}  majority-size={MAJORITY}")
print()

p1 = Proposer(1, B, MAJORITY)
p2 = Proposer(2, B, MAJORITY)
p3 = Proposer(3, B, MAJORITY)

# Round 1: P1 phase1 reaches all 5, phase2 only reaches B0 (rest in-flight)
p1.propose(11, "X", phase1_targets=B, phase2_targets=[B[0]])
print()

# P2 races in with a higher ballot before P1's remaining Accept messages land
p2.propose(12, "Y", phase1_targets=B, phase2_targets=B)
print()

# P3 arrives even later, still tries its own value
p3.propose(13, "Z", phase1_targets=B, phase2_targets=B)
print()

print("--- P1's delayed Accept(11,'X') finally arrives at B1..B4 ---")
for a in B[1:]:
    ok = a.accept(11, "X")
    print(f"  Accept(11,'X') -> {a.name}: {'ACCEPTED' if ok else 'REJECTED'} (promised={a.promised})")

print()
print("final state: " + ", ".join(f"{a.name}(n={a.accepted_n},v={a.accepted_v!r})" for a in B))
values = {a.accepted_v for a in B}
print(f"single decided value across cluster: {values == {'X'}}")

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

acceptors=['B0', 'B1', 'B2', 'B3', 'B4']  majority-size=3

--- proposer P1: ballot n=11, own value='X' ---
  Prepare(11) -> B0: PROMISE (had accepted n=0, v=None)
  Prepare(11) -> B1: PROMISE (had accepted n=0, v=None)
  Prepare(11) -> B2: PROMISE (had accepted n=0, v=None)
  Prepare(11) -> B3: PROMISE (had accepted n=0, v=None)
  Prepare(11) -> B4: PROMISE (had accepted n=0, v=None)
  5 promises, majority reached; no prior accepted value anywhere -> free to propose own 'X'
  Accept(11,'X') -> B0: ACCEPTED
  only 1/1 accepted -> no decision this round

--- proposer P2: ballot n=12, own value='Y' ---
  Prepare(12) -> B0: PROMISE (had accepted n=11, v='X')
  Prepare(12) -> B1: PROMISE (had accepted n=0, v=None)
  Prepare(12) -> B2: PROMISE (had accepted n=0, v=None)
  Prepare(12) -> B3: PROMISE (had accepted n=0, v=None)
  Prepare(12) -> B4: PROMISE (had accepted n=0, v=None)
  5 promises, majority reached; highest prior accepted n=11 v='X' -> MUST adopt 'X' (own 'Y' discarded)
  Accept(12,'X') -> B0: ACCEPTED
  Accept(12,'X') -> B1: ACCEPTED
  Accept(12,'X') -> B2: ACCEPTED
  Accept(12,'X') -> B3: ACCEPTED
  Accept(12,'X') -> B4: ACCEPTED
  5/5 accepted -> ** DECIDED value='X' at n=12 **

--- proposer P3: ballot n=13, own value='Z' ---
  Prepare(13) -> B0: PROMISE (had accepted n=12, v='X')
  Prepare(13) -> B1: PROMISE (had accepted n=12, v='X')
  Prepare(13) -> B2: PROMISE (had accepted n=12, v='X')
  Prepare(13) -> B3: PROMISE (had accepted n=12, v='X')
  Prepare(13) -> B4: PROMISE (had accepted n=12, v='X')
  5 promises, majority reached; highest prior accepted n=12 v='X' -> MUST adopt 'X' (own 'Z' discarded)
  Accept(13,'X') -> B0: ACCEPTED
  Accept(13,'X') -> B1: ACCEPTED
  Accept(13,'X') -> B2: ACCEPTED
  Accept(13,'X') -> B3: ACCEPTED
  Accept(13,'X') -> B4: ACCEPTED
  5/5 accepted -> ** DECIDED value='X' at n=13 **

--- P1's delayed Accept(11,'X') finally arrives at B1..B4 ---
  Accept(11,'X') -> B1: REJECTED (promised=13)
  Accept(11,'X') -> B2: REJECTED (promised=13)
  Accept(11,'X') -> B3: REJECTED (promised=13)
  Accept(11,'X') -> B4: REJECTED (promised=13)

final state: B0(n=13,v='X'), B1(n=13,v='X'), B2(n=13,v='X'), B3(n=13,v='X'), B4(n=13,v='X')
single decided value across cluster: True

তিনটা পাঠ: P1-এর প্রথম round শুধু ১টা acceptor-এ পৌঁছে থেমে গেল — majority ছাড়া কোনো decision নেই, এমনকি প্রস্তাবকারী নিজেও জিতল না। P2 উঁচু ballot নিয়ে ঢুকে B0-এর মধ্য দিয়ে “X” discover করল, নিজের “Y” বাদ দিয়ে সেটাই পুরো cluster-এ ছড়িয়ে দিল — এবং সেটাই decided হলো। P3 আরও পরে, আরও উঁচু ballot নিয়ে এসেও নতুন কিছু চাপাতে পারল না — এতক্ষণে সবাই “X” accept করে বসে আছে, তাই P3-ও বাধ্য হয়ে “X”-ই আবার propose করল। তিনজন প্রতিযোগী, তিনটা আলাদা value-র ইচ্ছা, তবু cluster-জুড়ে একটাই সত্য টিকে থাকল।

নিজে বাড়ান:

1. একটা চতুর্থ proposer যোগ করুন যেটা সবার আগে শুরু করে কিন্তু phase-2 message সবচেয়ে দেরিতে পাঠায় — দেখুন race-এর ক্রম বদলালে decided value বদলায় কি না
2. Stale-ballot Prepare-এর জন্য explicit REJECT branch যোগ করুন — এখন কোড শুধু condition-fail হলে চুপ থাকে, বাস্তব system-এ NACK পাঠানো হয় (দ্রুত retry-র জন্য)
3. N=7 cluster-এ minority (৩টা) স্থায়ীভাবে বন্ধ করে দেখুন decision তবু হয় কি না; majority-র নিচে (৪-এর কম জীবিত) নামলে কী ঘটে