Demonstrate Lamport Clock Causality Limitation - The Identifier

                      TASK
                    

Implementation

Lamport clocks guarantee: if A happens-before B, then L(A) < L(B). But the converse is not true: L(A) < L(B) does NOT mean A happened before B. Two concurrent events on different nodes can have any relative clock values.

Your task is to build an event tracker that demonstrates this limitation:

Track events on the local node with their Lamport timestamps
Accept events from remote nodes with their timestamps
Implement a check_causality handler that, given two event IDs, reports whether causality can be determined from Lamport clocks alone

Request:  {"type": "record_event", "msg_id": 1, "event_id": "e1", "data": "write x=1"}
Response: {"type": "record_event_ok", "in_reply_to": 1, "event_id": "e1", "clock": 1, "node": "n1"}

Request:  {"type": "check_causality", "msg_id": 3, "event_a": "e1", "event_b": "e2"}
Response: {"type": "check_causality_ok", "in_reply_to": 3,
           "clock_a": 1, "clock_b": 2,
           "lamport_says": "a_before_b",
           "actual": "unknown"}

The lamport_says field reports what Lamport ordering suggests. The actual field is always "unknown" for events on different nodes (since Lamport clocks cannot determine true causality in that case).

Sample Test Cases

Record event returns clock and nodeTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"record_event","msg_id":2,"event_id":"e1","data":"write x"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "record_event_ok", "event_id": "e1", "clock": 1, "node": "n1", "in_reply_to": 2, "msg_id": 1}}

Check causality between two local eventsTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"record_event","msg_id":2,"event_id":"e1","data":"a"}}
{"src":"c1","dest":"n1","body":{"type":"record_event","msg_id":3,"event_id":"e2","data":"b"}}
{"src":"c1","dest":"n1","body":{"type":"check_causality","msg_id":4,"event_a":"e1","event_b":"e2"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "record_event_ok", "event_id": "e1", "clock": 1, "node": "n1", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "record_event_ok", "event_id": "e2", "clock": 2, "node": "n1", "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "check_causality_ok", "clock_a": 1, "clock_b": 2, "lamport_says": "a_before_b", "actual": "causal", "in_reply_to": 4, "msg_id": 3}}

Hints

Hint 1▾

L(A) < L(B) does NOT imply A happened before B

Hint 2▾

Two independent events on different nodes can have any clock ordering

Hint 3▾

Construct a scenario where two events have ordered clocks but are concurrent

Hint 4▾

The converse of the Lamport property fails: ordered clocks do not imply causality

Hint 5▾

This limitation motivates vector clocks

Resources

Logical Clocks - Martin Kleppmann

Kleppmann on clock systems and distributed ordering

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

causalityconcurrent eventspartial orderhappens-before relation

main.py

python

#!/usr/bin/env python3
import sys
import json
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
        self.lamport = 0
        self.events = {}  # event_id -> {clock, node, data}
    def send(self, dest, body):
        body["msg_id"] = self.next_msg_id
        self.next_msg_id += 1
        msg = {"src": self.node_id, "dest": dest, "body": body}
        print(json.dumps(msg), flush=True)
    def reply(self, request, body):
        body["in_reply_to"] = request["body"]["msg_id"]
        self.send(request["src"], body)
    def tick(self):
        self.lamport += 1
        return self.lamport
def main():
    node = Node()
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        message = json.loads(line)
        body = message["body"]
        msg_type = body["type"]
        if msg_type == "init":
            node.node_id = body["node_id"]
            node.node_ids = body["node_ids"]
            node.reply(message, {"type": "init_ok"})