Happens-before ও Causality — কার আগে কার পরে

লক্ষ্য: network উল্টো করে জিনিস পাঠাক — engine এমন deliver করবে যে parent কখনো reply-র পরে আসবে না, আর একই sender-এর msg1 কখনো msg2-র পরে না। শেষের দুই assertion এটাই যাচাই করে।

# causal_buffer.py — CausalBuffer: holdback-queue সহ causal delivery
class CausalBuffer:
    def __init__(self):
        self.known = {}          # delivered-সমূহের merged vector clock
        self.holdback = []       # এসেছে, কিন্তু deliverable নয়
        self.order = []          # চূড়ান্ত delivery sequence

    def _deliverable(self, sender, V):
        # (১) নিজের slot: sender-এর ঠিক পরের message হতে হবে (FIFO)
        if V.get(sender, 0) != self.known.get(sender, 0) + 1:
            return False
        # (২) বাকি slot: অন্য কার কাজও কি আমি সব দেখে ফেলেছি?
        return all(V.get(k, 0) <= self.known.get(k, 0)
                   for k in V if k != sender)

    def receive(self, sender, V, payload):
        self.holdback.append((sender, V, payload))
        self._show(f"receive  {payload!r}")
        self._pump()
    def _pump(self):
        progressed = True
        while progressed:
            progressed = False
            for ev in list(self.holdback):
                s, V, p = ev
                if self._deliverable(s, V):
                    self.holdback.remove(ev)
                    for k, v in V.items():            # knowledge merge
                        self.known[k] = max(self.known.get(k, 0), v)
                    self.order.append(p)
                    self._show(f"DELIVER  {p!r}")
                    progressed = True
    def _show(self, tag):
        hb = [f"{s}:{p}" for s, _, p in self.holdback]
        print(f"    {tag:<24} holdback=[{', '.join(hb) or '-'}]")


buf = CausalBuffer()
print("— arrival order: ইচ্ছা করেই উল্টো ফেড —")
buf.receive("bob",   {"bob": 1, "alice": 1}, "reply(parent)")
buf.receive("carol", {"carol": 2},           "carol-msg2")
buf.receive("alice", {"alice": 1},           "parent")
buf.receive("carol", {"carol": 1},           "carol-msg1")

print("— চূড়ান্ত delivery order —")
for i, item in enumerate(buf.order, 1):
    print(f"  {i}. {item}")

assert buf.order.index("parent") < buf.order.index("reply(parent)")
assert buf.order.index("carol-msg1") < buf.order.index("carol-msg2")
print("OK: causality + per-sender FIFO দুই-ই রক্ষা")

প্রত্যাশিত output — holdback queue-র শ্বাস-প্রশ্বাসটাই মূল পাঠ:

— arrival order: ইচ্ছা করেই উল্টো ফেড —
    receive  'reply(parent)' holdback=[bob:reply(parent)]
    receive  'carol-msg2'    holdback=[bob:reply(parent), carol:carol-msg2]
    receive  'parent'        holdback=[bob:reply(parent), carol:carol-msg2, alice:parent]
    DELIVER  'parent'        holdback=[bob:reply(parent), carol:carol-msg2]
    DELIVER  'reply(parent)' holdback=[carol:carol-msg2]
    receive  'carol-msg1'    holdback=[carol:carol-msg2, carol:carol-msg1]
    DELIVER  'carol-msg1'    holdback=[carol:carol-msg2]
    DELIVER  'carol-msg2'    holdback=[-]
— চূড়ান্ত delivery order —
  1. parent
  2. reply(parent)
  3. carol-msg1
  4. carol-msg2
OK: causality + per-sender FIFO দুই-ই রক্ষা

তিন মুহূর্ত: reply সবার আগে এসেও parent-এর অপেক্ষায় holdback-এ জীবন কাটাল; parent-delivery-র সাথেই cascade হয়ে বেরিয়ে এলো; carol-msg2 ভাইয়ের জন্য FIFO-রক্ষায় অপেক্ষা করল।

নিজে বাড়ান:

1. Duplicate delivery inject করুন (একই (sender, seq) দুইবার) — idempotency guard যোগ করুন
2. এক sender চিরতরে মরলে holdback-এ কোনগুলো আটকে থাকবে — timeout/flush policy ডিজাইন করুন
3. Multi-key version — প্রতি key আলাদা buffer, কোন state share?