Key Question
How do processes across different machines ensure only one enters a critical section at a time?
Deep Dive
On a single machine, mutual exclusion is straightforward: semaphores, monitors, test-and-set instructions, all sharing memory. The OS guarantees that only one thread holds the lock at a time because the lock variable lives in RAM that every thread can see.
In a distributed system, there is no shared memory. Process A on machine X and process B on machine Y cannot atomically read and write the same memory location. So how do you solve mutual exclusion?
Single Machine Distributed System
┌─────────────────────┐ ┌─────┐ ┌─────┐ ┌─────┐
│ Thread A Thread B │ │ A │ │ B │ │ C │
│ ↕ ↕ │ │ │ │ │ │ │ │ │ │
│ Lock Variable │ │ └──┼────┼──┘ │ │ └──┤
│ (shared memory) │ │ │ │ │ │ │
└─────────────────────┘ └─────┘ └─────┘ └─────┘
No shared lock variable
Must coordinate via messagesThree fundamental approaches:
Approach Messages/Entry SPOF? Best For
──────────────────────────────────────────────────────────
Centralized (1) 3 Yes Small, simple systems
One coordinator
grants/denies access
Distributed (2) 2(N-1) No Fault-tolerant systems
All peers coordinate
(Ricart-Agrawala)
Token-based (3) 1 (best) Partial High throughput,
Token circulates (token loss) predictable loadCentralized: One node acts as the lock manager. Simple to reason about, 3 messages per critical section entry. But the coordinator is a single point of failure — if it crashes, no one can enter.
Distributed (Ricart-Agrawala): Every node participates in granting access. No single point of failure, but requires 2(N-1) messages per entry. More complex but more robust.
Token-based: A single token (like a baton) circulates among nodes. Only the token holder can enter. Most efficient (1 message in best case) but the token can be lost, requiring recovery.
All three must handle concurrent requests: if two nodes both want the critical section at the same time, the algorithm must ensure exactly one enters. The difference is how they coordinate.
Check Your Understanding
- Why can’t you simply use a semaphore for mutual exclusion across a network?
- What are the three categories of distributed mutual exclusion algorithms?
- What’s the fundamental tradeoff between the centralized and distributed approaches?
The “So What?”
Distributed mutual exclusion is the foundation for distributed locks, leases, and coordination services like ZooKeeper and etcd. Every time a microservice acquires a distributed lock or a Kubernetes controller does a leader election, it’s solving this same critical section problem — just on a network instead of shared memory.
✏️ Exercises
Distributed Mutual Exclusion: Exercises
Exercise 1: Counting Messages
Consider a 10-node cluster using three different mutual exclusion algorithms. For each, calculate the number of messages needed for one critical section entry.
a) Centralized algorithm b) Token ring (best case — the requesting node holds the token) c) Token ring (worst case — the token is N-1 hops away and not currently held by a node that wants CS) d) Ricart-Agrawala e) Maekawa’s voting set algorithm
Exercise 2: Ricart-Agrawala Race Condition Analysis
Three processes P1, P2, P3 are running Ricart-Agrawala. P1 and P2 want to enter the critical section.
- P1 sends REQUEST(5) to P2 and P3 at time T=0
- P2 sends REQUEST(3) to P1 and P3 at time T=0 (same time, different logical clock speeds)
- P3 is not interested in the critical section
a) Who enters the critical section first? Why? b) Trace the sequence of messages. At each step, note whether a REPLY is sent or DEFERRED. c) When does the second process enter the critical section?
Exercise 3: The Delayed Grant Problem
Suppose a 4-node token ring uses a single token that circulates in the order P1 → P2 → P3 → P4 → P1.
Currently, P1 holds the token. P1 passes the token to P2, but the message is delayed due to network congestion. After a 500ms timeout, P1 assumes the token is lost and generates a new one, sending it to P2 again.
a) What goes wrong when P2 receives both tokens? b) How would you fix this using sequence numbers? c) If P1 used fencing tokens, how would a storage system distinguish the “real” token holder from the stale one?
👁️ View Solutions
Distributed Mutual Exclusion: Solutions
Solution 1: Counting Messages
For a 10-node cluster:
a) Centralized: 3 messages per entry (REQUEST → coordinator, GRANT ← coordinator, RELEASE → coordinator).
b) Token ring (best case): 1 message — the requesting node already holds the token or receives it as the immediate next in the ring.
c) Token ring (worst case): The token is N-1 hops away = 9 hops. But each hop is 1 message, and the requesting node doesn’t send any messages to request it — the token just arrives after visiting all other nodes. So 0 messages sent, up to 9 message arrivals before the token arrives. In terms of messages sent by the requesting node, it’s 0. In terms of total messages in the system per entry, it’s 1 (the token pass from whoever holds it).
d) Ricart-Agrawala: 2(N-1) = 2(9) = 18 messages — 9 REQUESTs sent, 9 REPLYs received.
e) Maekawa’s voting sets: 3√N ≈ 3√10 ≈ 3(3.16) ≈ 9 or 10 messages per entry. (Actually √N ≈ 3.16, so 3 × 3.16 = 9.48 ≈ 10 messages in practice.)
Solution 2: Ricart-Agrawala Race Condition Analysis
a) P2 enters first. P2’s REQUEST has timestamp 3, which is earlier (smaller number = higher priority) than P1’s timestamp 5.
b) Message sequence:
T=0: P1 sends REQUEST(5) to P2, P3
P2 sends REQUEST(3) to P1, P3
P3 receives both REQUESTs, is not interested → sends REPLY to both immediately
P1 receives REQUEST(3) from P2:
- P1 is interested, has sent REQUEST(5)
- 3 < 5 (P2's timestamp is older)
- P1 sends REPLY to P2 immediately
P2 receives REQUEST(5) from P1:
- P2 is interested, has sent REQUEST(3)
- 5 > 3 (P1's timestamp is newer)
- P2 DEFERS reply to P1
T=1: P2 has all replies (from P1 and P3)
P2 enters critical section
T=2: P2 exits critical section
P2 sends deferred REPLY to P1
T=3: P1 has all replies (from P2 and P3)
P1 enters critical sectionc) P2 enters at T=1. P1 enters at T=3 (after P2 exits and sends the deferred reply).
Solution 3: The Delayed Grant Problem
a) Two tokens exist simultaneously: P2 receives one token (the original delayed one) and then another (the regenerated one). If P2 enters the critical section with one token, and then another node (e.g., P3) receives the second token, both P2 and P3 could be in the critical section simultaneously — violating mutual exclusion.
b) Sequence number fix:
- Each token carries a monotonically increasing sequence number (e.g., token #1, token #2, etc.)
- When P1 regenerates the token, it increments the sequence number to token #2
- Nodes track the highest sequence number they’ve seen
- When P2 receives the delayed token #1 followed by token #2, it recognizes #1 as stale and discards it
P1 generates token#1 → P2 receives token#1 (but message delayed)
P1 times out → generates token#2 → P2 receives token#2
P2 updates highest_seq = 2
P2 later receives token#1 → discards (seq 1 < 2)c) Fencing tokens work differently from token ring sequence numbers. A fencing token is issued by a lock service (like ZooKeeper) and monotonically increases each time a lock is granted:
Grant #1: fencing token = 1 for P1
Grant #2: fencing token = 2 for P2 (after P1's lock expired)
P1 writes to storage: "write X, fence_token=1"
(storage remembers last fence token = 2)
P2 writes to storage: "write Y, fence_token=2"
(storage accepts: 2 >= 2)
P1's delayed write arrives: "write X, fence_token=1"
(storage rejects: 1 < 2 → stale grant)This provides idempotency and freshness guarantees even when messages are delayed. This is why production distributed locks (etcd, ZooKeeper, Redis Redlock) all recommend fencing tokens for correctness-critical operations.