Distributed & Decentralized Systems Curriculum
Distributed Transactions Coordination · Distributed Mutual Exclusion

Key Question

How do the simplest distributed mutual exclusion algorithms work?

Deep Dive

Centralized Algorithm

One node is elected as the coordinator (lock manager). All other nodes send requests to it.

Protocol:
                         ┌──────────┐
              Request ──→│          │
              Grant  ←───│Coordinator│
                         │          │
                    ┌────┤(queue)   │
                    │    └──────────┘
                    │
               Request Queue: [P3, P7]
                          
Node P1 wants CS:     P1 ──REQUEST──→ C
                      P1 ←──GRANT──── C
                      (enter CS)
                      P1 ──RELEASE──→ C
                      C grants next in queue

Messages per entry: 3 (REQUEST, GRANT, RELEASE)

Problems:

  • Single point of failure: Coordinator crashes → system deadlock
  • Performance bottleneck: Coordinator handles all requests
  • No fairness guarantees: Starvation possible if coordinator is biased
Failure scenario:
  ┌──────────┐     ┌───┐
  │Coordinator│─────│ X │  (crash)
  └──────────┘     └───┘
  All nodes waiting forever...

Token Ring Algorithm

Nodes form a logical ring (not necessarily matching physical topology). A single token circulates. Only the token holder enters the critical section.

Token Ring (logical ring of 4 nodes):

          P1 ───→ P2
          ↑       ↓
          P4 ←─── P3

Token path: P1 → P2 → P3 → P4 → P1 → ...

When P3 wants CS:
  P3 receives token → enters CS → holds token → releases → passes to P4
  
When P3 does NOT want CS:
  P3 receives token → immediately passes to P4

Messages per entry: 1 (receiving the token in the best case — you happen to be the next node)

Problems:

  • Token loss: Token can be lost due to network failure or node crash. Requires a recovery protocol.
  • Token delay: If P1 wants CS but the token is at P3, P1 must wait for 2 hops.
  • Ring management: Adding/removing nodes requires reconfiguring the ring.
Token loss recovery:
  1. Nodes detect token absence via timeout
  2. Run election protocol to regenerate token
  3. Risk: two tokens could be generated (duplicate token = violation!)

Comparison

Property            Centralized        Token Ring
────────────────────────────────────────────────────
Messages/entry     3                  1 (best case)
Delay              Request + grant    0 to N hops
Fault tolerance    Low (coordinator)  Low (token loss)
Fairness           Depends             Round-robin
Complexity         Simple              Moderate
Load balancing     Coordinator is     Token circulates
                   bottleneck         evenly

Check Your Understanding

  1. In the centralized algorithm, what happens if the coordinator crashes while a node holds the lock?
  2. How many messages per critical section entry does the centralized algorithm require?
  3. In a token ring of 5 nodes, what’s the maximum number of hops a requesting node might wait before receiving the token?

The “So What?”

These algorithms are the “Hello World” of distributed mutual exclusion — simple enough to understand, but with flaws that motivate more sophisticated approaches. The token ring’s circular-passing pattern appears in real systems like the Token Bus (IEEE 802.4) and some lock managers. The centralized approach’s SPOF problem is why production systems use replicated coordinators (etcd, ZooKeeper) rather than a single lock server.

✏️ 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 section

c) 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.