Compare Mutex Algorithms: Lamport vs Token Ring vs Centralized - The Timekeeper

Implementation

Different distributed mutex algorithms have different tradeoffs. Compare three approaches:

Lamport's algorithm: 3(N-1) messages per CS entry, fully distributed, fair
Token ring: 0 to N-1 messages, no starvation, but token can be lost
Centralized: 3 messages, simple, but coordinator is a single point of failure

Implement a compare_mutex handler:

Request:  {"type": "compare_mutex", "msg_id": 1, "nodes": 5}
Response: {"type": "compare_mutex_ok", "in_reply_to": 1, "comparison": [
    {"algorithm": "lamport", "messages_per_cs": 12, "fault_tolerant": true, "fair": true},
    {"algorithm": "token_ring", "messages_per_cs_avg": 2.5, "fault_tolerant": false, "fair": true},
    {"algorithm": "centralized", "messages_per_cs": 3, "fault_tolerant": false, "fair": true}
]}

Also implement a simulate_token_ring handler:

Request:  {"type": "simulate_token_ring", "msg_id": 2, "nodes": 5, "requests": ["n3", "n1"]}
Response: {"type": "simulate_token_ring_ok", "in_reply_to": 2, "total_messages": 5, "grant_order": ["n3", "n1"]}

Sample Test Cases

Compare mutex for 5 nodesTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"compare_mutex","msg_id":2,"nodes":5}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Compare mutex for 10 nodesTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"compare_mutex","msg_id":2,"nodes":10}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

Lamport mutex: 3(N-1) messages per critical section entry (request + reply + release)

Hint 2▾

Token ring: 0 to N-1 messages per entry (depends on token position)

Hint 3▾

Centralized: 3 messages per entry (request + grant + release) but single point of failure

Hint 4▾

Compare on: message count, fault tolerance, fairness, and latency

Hint 5▾

Build a comparison table with all metrics

Implementation

Sample Test Cases

Hints

Resources

Theoretical Hub

Key Concepts