TASK
Implementation
Leslie Lamport showed that in a distributed system, you don't need physical clocks to order events. A Lamport clock is a simple counter that provides a partial order: if event A causally precedes event B, then L(A) < L(B).
Rules:
- Before any send, increment then stamp the message
- On receive, set counter = max(local_counter, message_counter) + 1
- On any local event, increment the counter
Your task is to implement a Lamport clock in your Maelstrom node:
Request: {"type": "tick", "msg_id": 1}
Response: {"type": "tick_ok", "in_reply_to": 1, "clock": 1}The tick handler triggers a local event (increment). Also handle send_stamped which sends a message with the current Lamport timestamp to another node:
Request: {"type": "send_stamped", "msg_id": 1, "target": "n2", "data": "hello"}
Response: {"type": "send_stamped_ok", "in_reply_to": 1, "clock": 2}And a get_clock handler that returns the current clock value:
Response: {"type": "get_clock_ok", "in_reply_to": 1, "clock": 5}Sample Test Cases
Tick increments clockTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"tick","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "tick_ok", "clock": 1, "in_reply_to": 2, "msg_id": 1}}
Multiple ticks increment sequentiallyTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"tick","msg_id":2}}
{"src":"c1","dest":"n1","body":{"type":"tick","msg_id":3}}
{"src":"c1","dest":"n1","body":{"type":"tick","msg_id":4}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "tick_ok", "clock": 1, "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "tick_ok", "clock": 2, "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "tick_ok", "clock": 3, "in_reply_to": 4, "msg_id": 3}}
Hints
Hint 1▾
A Lamport clock is a single integer counter per node
Hint 2▾
On every local event or send: increment the counter
Hint 3▾
On receive: counter = max(local, received) + 1
Hint 4▾
Lamport clocks give a partial order, not a total order
Hint 5▾
If L(A) < L(B), it does NOT mean A happened before B
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
Lamport clocklogical timepartial orderhappens-before
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
class LamportClock:
def __init__(self):
self.counter = 0
def tick(self):
# TODO: Increment on local event, return new value
pass
def send_tick(self):
# TODO: Increment before send, return value to stamp message
pass
def receive_tick(self, received_counter):
# TODO: max(local, received) + 1
pass
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.clock = LamportClock()
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 main():
node = Node()
for line in sys.stdin: