Logical Clock — Lamport আর Vector Clock

লক্ষ্য: একই simulation দুই ঘড়ি দিয়ে চালিয়ে দেখানো — Lamport কোথায় কোথায় ভুল দিক নির্দেশ করে, vector clock সেই ভুল কীভাবে ধরে।

# clocks.py — LamportClock, VectorClock, 3-process simulation
class LamportClock:
    def __init__(self):
        self.L = 0
    def tick(self):
        self.L += 1
        return self.L
    def send(self):
        self.L += 1
        return self.L
    def receive(self, L_msg):
        self.L = max(self.L, L_msg) + 1
        return self.L

class VectorClock:
    def __init__(self, node_id, nodes):
        self.node_id = node_id
        self.V = {n: 0 for n in nodes}
    def tick(self):
        self.V[self.node_id] += 1
        return dict(self.V)
    def send(self):
        self.V[self.node_id] += 1
        return dict(self.V)
    def receive(self, V_msg):
        for k in self.V:
            self.V[k] = max(self.V[k], V_msg.get(k, 0))
        self.V[self.node_id] += 1
        return dict(self.V)
    @staticmethod
    def compare(Va, Vb):
        keys = set(Va) | set(Vb)
        le = all(Va.get(k, 0) <= Vb.get(k, 0) for k in keys)
        ge = all(Va.get(k, 0) >= Vb.get(k, 0) for k in keys)
        if le and ge: return "EQUAL"
        if le: return "BEFORE"
        if ge: return "AFTER"
        return "CONCURRENT"

NODES = ["P1", "P2", "P3"]
lam = {n: LamportClock() for n in NODES}
vec = {n: VectorClock(n, NODES) for n in NODES}
log = []  # (event_id, node, L, V)

def local(node, eid):
    L = lam[node].tick()
    V = vec[node].tick()
    log.append((eid, node, L, V))

def send(node, eid):
    L = lam[node].send()
    V = vec[node].send()
    log.append((eid, node, L, V))
    return (L, V)

def receive(node, eid, msg):
    L = lam[node].receive(msg[0])
    V = vec[node].receive(msg[1])
    log.append((eid, node, L, V))

# --- scenario: P1 -> P2 -> P3 -> P1 chain, প্লাস independent local events ---
local("P1", "a1")
m1 = send("P1", "a2")
local("P1", "a3")

local("P2", "b1")
receive("P2", "b2", m1)
m2 = send("P2", "b3")

local("P3", "c1")
receive("P3", "c2", m2)
m3 = send("P3", "c3")

receive("P1", "a4", m3)

print("event   node   L    V")
for eid, node, L, V in log:
    vstr = "{" + ", ".join(f"{k}:{V[k]}" for k in NODES) + "}"
    print(f"{eid:<7} {node:<6} {L:<4} {vstr}")

print()
print("pairs where Lamport-order disagrees with true causal relation:")
events = {eid: (node, L, V) for eid, node, L, V in log}
pairs = [("c1", "a2"), ("c1", "a3"), ("c1", "b2"), ("c1", "b3"),
         ("b1", "a2"), ("b1", "a3")]
for x, y in pairs:
    _, Lx, Vx = events[x]
    _, Ly, Vy = events[y]
    rel = VectorClock.compare(Vx, Vy)
    lamport_says = "x->y" if Lx < Ly else ("y->x" if Ly < Lx else "tie")
    print(f"  {x}(L={Lx}) vs {y}(L={Ly})  lamport suggests {lamport_says:<5}"
          f"  vector says {rel}")

প্রত্যাশিত output (deterministic — হুবহু এটাই আসবে):

event   node   L    V
a1      P1     1    {P1:1, P2:0, P3:0}
a2      P1     2    {P1:2, P2:0, P3:0}
a3      P1     3    {P1:3, P2:0, P3:0}
b1      P2     1    {P1:0, P2:1, P3:0}
b2      P2     3    {P1:2, P2:2, P3:0}
b3      P2     4    {P1:2, P2:3, P3:0}
c1      P3     1    {P1:0, P2:0, P3:1}
c2      P3     5    {P1:2, P2:3, P3:2}
c3      P3     6    {P1:2, P2:3, P3:3}
a4      P1     7    {P1:4, P2:3, P3:3}

pairs where Lamport-order disagrees with true causal relation:
  c1(L=1) vs a2(L=2)  lamport suggests x->y   vector says CONCURRENT
  c1(L=1) vs a3(L=3)  lamport suggests x->y   vector says CONCURRENT
  c1(L=1) vs b2(L=3)  lamport suggests x->y   vector says CONCURRENT
  c1(L=1) vs b3(L=4)  lamport suggests x->y   vector says CONCURRENT
  b1(L=1) vs a2(L=2)  lamport suggests x->y   vector says CONCURRENT
  b1(L=1) vs a3(L=3)  lamport suggests x->y   vector says CONCURRENT

তিন মুহূর্ত পড়ার সময় লক্ষ করুন: (১) মূল chain a2 → b2 → b3 → c2 → c3 → a4 — প্রতিটা ধাপে Lamport-ও বাড়ছে, vector-ও componentwise বড় হচ্ছে, দুই ঘড়ি একমত; (২) c1 আর b1 — process শুরুর independent local event — এদের সাথে অন্য process-এর পরের যেকোনো event তুলনা করলেই Lamport বিভ্রান্ত করে (৬টা pair-ই তালিকায়), কারণ c1, b1-এর ছোট সংখ্যা শুধু বোঝায় “কম কাজ করা প্রক্রিয়া”, causal আগে হওয়া না; (৩) vector compare প্রতিটাতেই সঠিক রায় দেয় — CONCURRENT, কোনো ব্যতিক্রম ছাড়া। এটাই সেই জায়গা যেখানে vector clock টাকা উশুল করে — ঠিক এই ৬টা pair-ই Lamport-only display বা delivery-logic-এ ভুল ক্রম হিসেবে বেরিয়ে আসত।

নিজে বাড়ান:

1. VectorClock.compare-এ EQUAL case-টা কখনো ট্রিগার হয় কি এই scenario-তে? না হলে, কী পরিবর্তন করলে হতো — চিন্তা করুন
2. Node-সংখ্যা 3 থেকে 6-এ বাড়িয়ে চালান — misleading-pair তালিকা কীভাবে বাড়ে বা কমে দেখুন
3. (L, node_id) tiebreak যোগ করে একটা total_order() function লিখুন — তারপর সেই order আর vector-compare-এর causal রায় পাশাপাশি রেখে কোথায় দ্বিমত হয় খুঁজুন