Simulate Concurrent Mutex Requests from Multiple Nodes - The Timekeeper

                      TASK
                    

Implementation

Simulate 5 nodes all requesting the mutex simultaneously. With Lamport's algorithm, only one can hold it at a time. The request with the lowest (timestamp, node_id) pair wins.

Your task is to process multiple lock requests and verify mutual exclusion:

Request:  {"type": "multi_request", "msg_id": 1, "requests": [
    {"node": "n1", "ts": 3}, {"node": "n2", "ts": 1}, {"node": "n3", "ts": 3},
    {"node": "n4", "ts": 2}, {"node": "n5", "ts": 1}
]}
Response: {"type": "multi_request_ok", "in_reply_to": 1, "grant_order": ["n2","n5","n4","n1","n3"],
           "violations": 0}

Also implement a release_lock handler:

Request:  {"type": "release_lock", "msg_id": 2, "node": "n2"}
Response: {"type": "release_lock_ok", "in_reply_to": 2, "next_holder": "n5"}

Sample Test Cases

Multi request orders by (ts, node_id)Timeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"multi_request","msg_id":2,"requests":[{"node":"n1","ts":3},{"node":"n2","ts":1},{"node":"n3","ts":3},{"node":"n4","ts":2},{"node":"n5","ts":1}]}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "multi_request_ok", "in_reply_to": 2, "grant_order": ["n2", "n5", "n4", "n1", "n3"], "violations": 0, "msg_id": 1}}

Single request gets immediate grantTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"multi_request","msg_id":2,"requests":[{"node":"n1","ts":1}]}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "multi_request_ok", "in_reply_to": 2, "grant_order": ["n1"], "violations": 0, "msg_id": 1}}

Hints

Hint 1▾

When multiple nodes request simultaneously, the one with the lowest (ts, node_id) wins

Hint 2▾

Track how long each node waits before acquiring the lock

Hint 3▾

Verify mutual exclusion: only one holder at a time

Hint 4▾

After release, the next node in the queue should be able to acquire

Hint 5▾

Report average and max wait times across all requests

Resources

Mutual Exclusion in Distributed Systems

Lecture on distributed mutual exclusion and contention handling

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

contentionfairnesswait timequeue ordering

main.py

python