TASK
Implementation
Integrate HLC-based IDs into the Maelstrom generate workload. Each generated ID must be globally unique across all nodes and should preserve causal ordering.
ID format: "{pt}_{lc}_{node_id}" (e.g., "1704067200001_0_n1")
Implement the standard Maelstrom generate handler:
Request: {"type": "generate", "msg_id": 1}
Response: {"type": "generate_ok", "in_reply_to": 1, "id": "1704067200001_0_n1"}Also implement parse_hlc_id to decompose an HLC ID:
Request: {"type": "parse_hlc_id", "msg_id": 2, "id": "1704067200001_3_n2"}
Response: {"type": "parse_hlc_id_ok", "in_reply_to": 2, "pt": 1704067200001, "lc": 3, "node": "n2"}Sample Test Cases
Generate produces HLC-formatted IDTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"generate","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Parse HLC ID extracts componentsTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"parse_hlc_id","msg_id":2,"id":"1704067200001_3_n2"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "parse_hlc_id_ok", "pt": 1704067200001, "lc": 3, "node": "n2", "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
Combine HLC timestamp with node_id for globally unique IDs
Hint 2▾
Format: pt_lc_nodeId ensures uniqueness across nodes
Hint 3▾
HLC guarantees monotonicity even with clock skew
Hint 4▾
The Maelstrom generate workload requires globally unique IDs
Hint 5▾
Verify uniqueness by collecting IDs from all nodes
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
unique ID generationMaelstrom workloadlinearizabilityHLC integration
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
import time
class HLC:
def __init__(self, node_id):
self.node_id = node_id
self.pt = 0
self.lc = 0
def tick(self):
now = int(time.time() * 1000)
if now > self.pt:
self.pt = now
self.lc = 0
else:
self.lc += 1
def generate_id(self):
# TODO: Tick and return formatted HLC ID
pass
@staticmethod
def parse_id(hlc_id):
# TODO: Parse "pt_lc_node" format
pass
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.hlc = None
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)