ভেক্টর ক্লক ও কজালিটি ট্র্যাকিং

১ · সমস্যা — গ্লোবাল ক্লক ছাড়া ক্রম নির্ধারণ

একটি একক মেশিনে ইভেন্টের ক্রম নির্ধারণ সহজ — একটি ঘড়ি, একটি টাইমলাইন। কিন্তু ডিস্ট্রিবিউটেড সিস্টেমে প্রতিটি নোডের নিজস্ব ফিজিক্যাল ঘড়ি আছে, এবং সেগুলো কখনোই নিখুঁতভাবে সিঙ্ক্রোনাইজড নয় (clock skew)। তাই নোড A-এর timestamp ১০০ ও নোড B-এর timestamp ১০১ থেকে এটা বলা যায় না যে A-এর ইভেন্টটি সত্যিই B-এর আগে ঘটেছিল — B-এর ঘড়ি হয়তো এগিয়ে আছে। আমাদের এমন একটি পদ্ধতি দরকার যা প্রকৃত কজালিটি (causality) — কোন ইভেন্ট কোনটির কারণ — ট্র্যাক করে, ফিজিক্যাল সময়ের ওপর নির্ভর না করে।

২ · Vector Clock — প্রতিটি নোডের নিজস্ব গণনা

Vector ClockVector Clockপ্রতিটি নোড একটি ভেক্টর (প্রতি নোডের জন্য একটি কাউন্টার) রাখে; লোকাল ইভেন্টে নিজের এন্ট্রি বাড়ে, মেসেজ পাঠালে পুরো ভেক্টর সংযুক্ত হয়, রিসিভ করলে elementwise-max নিয়ে নিজের এন্ট্রি বাড়ানো হয় — এভাবে দুটি ইভেন্টের মধ্যে প্রকৃত কার্যকারণ সম্পর্ক ট্র্যাক করা যায়। -এ প্রতিটি নোড $N$-দৈর্ঘ্যের একটি কাউন্টার-ভেক্টর রাখে (একটি এন্ট্রি প্রতি নোডের জন্য)। তিনটি নিয়ম:

৩ · Worked Example — ধাপে ধাপে

দুটি নোড A ও B কল্পনা করুন (index 0 = A, index 1 = B), উভয়ে [0, 0] দিয়ে শুরু করে।

• ধাপ ১: A একটি লোকাল ইভেন্ট করে — A-এর ক্লক হয় [1, 0]।
• ধাপ ২: B (স্বাধীনভাবে, A-এর থেকে সম্পূর্ণ বিচ্ছিন্নভাবে) একটি লোকাল ইভেন্ট করে — B-এর ক্লক হয় [0, 1]।
• তুলনা ১: [1,0] বনাম [0,1] — কেউ কাউকে dominate করে না (১>০ কিন্তু ০<১) → CONCURRENT।
• ধাপ ৩: A এখন B-কে একটি মেসেজ পাঠায়, নিজের ক্লক [1,0] সংযুক্ত করে।
• ধাপ ৪: B মেসেজটি receive করে — নতুন ক্লক = elementwise-max([0,1], [1,0]) = [1,1], তারপর B নিজের এন্ট্রি (index ১) বাড়ায় → [1,2]।
• তুলনা ২: A-এর ক্লক [1,0] বনাম B-এর receive-পরবর্তী ক্লক [1,2] — ১≤১ এবং ০≤২, এবং অন্তত একটি কঠোরভাবে ছোট (০<২) → A-এর ইভেন্ট B-এর receive-পরবর্তী স্টেটের happened-before।

৪ · Python দিয়ে যাচাই করা

নিচের কোডে local_event, receive, ও compare ফাংশন দিয়ে উপরের ধাপে-ধাপে উদাহরণটি হুবহু পুনর্গঠন করা হয়েছে।

def local_event(vc, idx):
    new_vc = vc[:]
    new_vc[idx] += 1
    return new_vc

def receive(vc, idx, other_vc):
    merged = [max(a, b) for a, b in zip(vc, other_vc)]
    merged[idx] += 1
    return merged

def compare(vc1, vc2):
    if vc1 == vc2:
        return "equal"
    le = all(a <= b for a, b in zip(vc1, vc2))   # vc1 এর প্রতিটি এলিমেন্ট <= vc2
    ge = all(a >= b for a, b in zip(vc1, vc2))   # vc1 এর প্রতিটি এলিমেন্ট >= vc2
    if le:
        return "before"       # vc1 happened-before vc2
    if ge:
        return "after"        # vc1 happened-after vc2
    return "concurrent"


# index 0 = A, index 1 = B
A = [0, 0]
B = [0, 0]

A = local_event(A, 0)   # A করে একটি local event -> [1,0]
B = local_event(B, 1)   # B (স্বাধীনভাবে) করে একটি local event -> [0,1]

print("A:", A)
print("B:", B)

result1 = compare(A, B)
print("compare(A, B) ->", result1)

# A এখন B-কে মেসেজ পাঠায়, নিজের ক্লক [1,0] সংযুক্ত করে
message_from_A = A[:]
B_after_receive = receive(B, 1, message_from_A)   # max([0,1],[1,0])=[1,1] তারপর index1 +1 -> [1,2]

print()
print("A-এর পাঠানো মেসেজের ক্লক:", message_from_A)
print("B receive করার পর ক্লক:  ", B_after_receive)

result2 = compare(A, B_after_receive)
print("compare(A, B_after_receive) ->", result2)

print()
print("প্রত্যাশিত সিকোয়েন্স মিলছে কি:",
      result1 == "concurrent" and result2 == "before")