Implement ID Generation During Network Partition - The Identifier

                      TASK
                    

Implementation

Distributed systems must handle network partitions - times when nodes cannot communicate with each other. Your ID generator must continue working even when completely isolated from other nodes.

Test your implementation by verifying it works when:

The node cannot reach any other nodes
The network has high latency
Messages are being dropped

A good ID generation scheme is fully local and does not require coordination with other nodes.

Sample Test Cases

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

Hints

Hint 1▾

Your ID generation should work without network access

Hint 2▾

Do not depend on other nodes or external services

Hint 3▾

Consider what happens if clocks drift

Hint 4▾

Generated IDs must be globally unique - use timestamp + node_id + sequence to guarantee no collisions even under partition

Resources

CAP Theorem

Understanding the trade-offs in distributed systems

                      OVERVIEW
                    

Theoretical Hub

CAP Theorem and Availability

The CAP theorem states that during a network partition, you can have either Consistency or Availability, but not both.

ID generation should prioritize availability: even an isolated node should generate valid IDs.

Local-First Design

By embedding the node_id in our IDs, we achieve partition tolerance. Each node can independently generate IDs that are guaranteed unique across the cluster, without coordination.

The Trade-off

Approach	Consistency	Availability
Central ID server	Strong (sequential IDs)	Fails during partition
Node-embedded IDs	Weak (no ordering)	Always available

Clock Drift Handling

What if the clock goes backwards? This can happen with NTP adjustments. A robust implementation should:

Detect backward clock movement
Wait until timestamp advances, OR
Continue using the previous timestamp with incrementing sequence

Key Concepts

network partitionsavailabilityCAP theorem

main.py

python

#!/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: Generate IDs that work during network partitions
        # Should not require communication with other nodes
        with self.lock:
            timestamp = int(time.time() * 1000)
            
            if timestamp == self.last_timestamp:
                self.sequence += 1
            else:
                self.sequence = 0
                self.last_timestamp = timestamp
            
            return f"{self.node_id}-{timestamp}-{self.sequence}"
def main():