Generate Unique IDs Using Node ID and Timestamp - The Identifier

                      TASK
                    

Implementation

Distributed systems need unique identifiers for entities, events, and messages. Without a central authority, each node must generate IDs independently while avoiding collisions.

Implement a generate workload handler that responds to generate requests with unique IDs:

{
  "type": "generate",
  "msg_id": 1
}

Your response should be:

{
  "type": "generate_ok",
  "msg_id": 1,
  "in_reply_to": 1,
  "id": "unique-id-here"
}

For this first implementation, combine your node_id with a timestamp to create IDs. This provides uniqueness across nodes (different node_ids) and over time (different timestamps).

Sample Test Cases

Generate single ID with initTimeout: 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}}
{"src":"n1","dest":"c1","body":{"type":"generate_ok","in_reply_to":2,"msg_id":1,"id":"n1-0"}}

Hints

Hint 1▾

Combine node_id with a timestamp for basic uniqueness

Hint 2▾

Consider using millisecond precision

Hint 3▾

Format: node_id-timestamp-sequence

Resources

Unique ID Generation Challenge

Fly.io Gossip Glomers unique ID generation walkthrough

                      OVERVIEW
                    

Theoretical Hub

Why Unique IDs Matter

Every database record, every log entry, every message needs an identifier. In a distributed system, you cannot simply increment a counter because multiple nodes might generate the same number simultaneously.

The Collision Problem

Consider a simple counter-based approach:

Node A: counter = 1 → generates ID 1
Node B: counter = 1 → generates ID 1  // COLLISION!

Both nodes generate the same ID because they have no coordination.

Timestamp-Based IDs

Timestamps provide a natural ordering and uniqueness over time, but two nodes might generate the same timestamp. By including the node_id, we guarantee uniqueness across nodes:

ID = "{node_id}-{timestamp}"

Node A: "n1-1704067200000"
Node B: "n2-1704067200000"  // Different node_id = unique

Remaining Challenge

However, a single node might still generate duplicate IDs within the same millisecond. We'll address this in the next task.

Key Concepts

unique IDstimestampsnode identity

main.py

python

#!/usr/bin/env python3
import sys
import json
import time
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
    
    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: Generate a unique ID using node_id and timestamp
        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"]
            node.reply(message, {"type": "init_ok"})
        elif msg_type == "generate":
            # TODO: Generate and return unique ID
            pass