Implement Distributed Mutual Exclusion with Lamport Clocks - The Timekeeper

                      TASK
                    

Implementation

Lamport's mutual exclusion algorithm uses Lamport clocks to totally order lock requests. Each node maintains a request queue sorted by (timestamp, node_id).

Protocol:

To request the lock: broadcast a REQUEST(ts, node_id) to all other nodes, add to local queue
On receiving REQUEST: add to queue, send REPLY
To enter critical section: your request must be at the head of the queue AND you must have received REPLY from every other node
To release: remove from queue, broadcast RELEASE

Implement:

Request:  {"type": "request_lock", "msg_id": 1}
Response: {"type": "request_lock_ok", "in_reply_to": 1, "position": 1, "ts": 1}

Request:  {"type": "lock_status", "msg_id": 2}
Response: {"type": "lock_status_ok", "in_reply_to": 2, "holding": false, "queue_size": 1, "queue": [{"ts": 1, "node": "n1"}]}

Sample Test Cases

Request lock adds to queueTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"request_lock","msg_id":2}}
{"src":"c1","dest":"n1","body":{"type":"lock_status","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": "request_lock_ok", "in_reply_to": 2, "position": 1, "ts": 1, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "lock_status_ok", "in_reply_to": 3, "holding": true, "queue_size": 1, "queue": [{"ts": 1, "node": "n1"}], "msg_id": 2}}

Lock status with empty queueTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"lock_status","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": "lock_status_ok", "in_reply_to": 2, "holding": false, "queue_size": 0, "queue": [], "msg_id": 1}}

Hints

Hint 1▾

Each node maintains a priority queue of lock requests sorted by Lamport timestamp

Hint 2▾

To request: broadcast REQUEST to all nodes, add self to queue

Hint 3▾

To release: broadcast RELEASE to all nodes, remove self from queue

Hint 4▾

A node can enter CS when: its request is at the head AND it has received replies from all others

Hint 5▾

Use (timestamp, node_id) pairs for total ordering to break ties

Resources

Distributed Mutual Exclusion Algorithms

Overview of distributed mutex algorithms including Lamport

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

distributed mutexLamport mutexrequest queuetotal ordering

main.py

python