TASK
Implementation
Run your ID generator through Maelstrom verification to prove uniqueness. Maelstrom collects all generated IDs across all nodes and checks for duplicates.
Your implementation must pass with:
- Multiple nodes generating concurrently
- High throughput (thousands of IDs per second)
- Network partitions separating nodes
Think about why your scheme guarantees uniqueness. What assumptions does it make? What could cause collisions?
Sample Test Cases
Generate two IDs with proper formatTimeout: 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}}
{"src":"c2","dest":"n1","body":{"type":"generate","msg_id":3}}
Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c1","body":{"type":"generate_ok","in_reply_to":2,"msg_id":1,"id":"n1-0"}}
{"src":"n1","dest":"c2","body":{"type":"generate_ok","in_reply_to":3,"msg_id":2,"id":"n1-1"}}
Hints
Hint 1▾
Maelstrom will verify uniqueness automatically
Hint 2▾
Consider mathematical proof of your ID uniqueness
Hint 3▾
Document your uniqueness guarantees
OVERVIEW
Theoretical Hub
Proving Uniqueness
A strong ID scheme should have a provable uniqueness guarantee.
The Proof Structure
If IDs combine:
node_id- unique per nodetimestamp- monotonicsequence- unique per timestamp
Then uniqueness is guaranteed as long as:
- Node IDs are unique
- Clocks do not go backwards more than a tolerable amount
- Sequence does not overflow
Failure Modes
| Failure | Cause | Mitigation |
|---|---|---|
| Clock sync issue | NTP adjustment | Wait or use previous timestamp |
| Node ID reuse | Node restart with same ID | Persist counter or use epoch |
| Sequence overflow | >4096 IDs/ms | Wait for next millisecond |
Key Concepts
testingverificationglobal uniqueness
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
import threading
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.last_timestamp = 0
self.sequence = 0
self.lock = threading.Lock()
def send(self, dest, body):
body["msg_id"] = self.next_msg_id
self.next_msg_id += 1
message = {"src": self.node_id, "dest": dest, "body": body}
print(json.dumps(message), flush=True)
def reply(self, request, body):
body["in_reply_to"] = request["body"]["msg_id"]
self.send(request["src"], body)
def generate_id(self):
# TODO: Implement a provably unique ID scheme
pass
def main():
node = Node()
for line in sys.stdin:
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"]