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

Key Question

How does Ricart-Agrawala achieve mutual exclusion without a coordinator or token?

Deep Dive

Ricart-Agrawala is the most influential distributed mutual exclusion algorithm. It’s fully decentralized: every node participates in granting access. No coordinator, no circulating token β€” just timestamped messages and logical clocks.

The Protocol

When node Pα΅’ wants to enter the critical section:

1. Send REQUEST(timestamp, Pα΅’) to ALL other N-1 nodes
2. Wait until all N-1 have replied
3. Enter critical section
4. On exit, send deferred replies

When node Pβ±Ό receives REQUEST(t, Pα΅’):

  IF Pβ±Ό is NOT interested in CS:
      ──→ REPLY immediately

  IF Pβ±Ό IS interested in CS and hasn't sent its own REQUEST yet:
      ──→ REPLY immediately (Pα΅’'s request is earlier)

  IF Pβ±Ό IS interested in CS and HAS sent its own REQUEST(tβ±Ό, Pβ±Ό):
      IF t < tβ±Ό (Pα΅’'s timestamp is older/higher priority):
          ──→ REPLY immediately
      ELSE (t > tβ±Ό, Pα΅’'s request is newer/lower priority):
          ──→ Defer reply (queue it)

3-Node Timeline

P1 wants CS at T=10:          P2 wants CS at T=15:      P3 (not interested):
     β”‚                              β”‚                         β”‚
     │──REQUEST(10,P1)────→ P2 ────│─────────────────────────→│ P3
     β”‚                              β”‚                         β”‚
     β”‚                              β”‚ P2 is interested, has   β”‚
     β”‚                              β”‚ newer timestamp (15>10) β”‚
     β”‚                              β”‚ so P2 DEFERS reply      β”‚
     β”‚                              β”‚                         β”‚
     │←─── REPLY ───────────── P2   β”‚ P2 sees t=10 < t=15,    β”‚
     β”‚                              β”‚ so P2 REPLIES           β”‚
     │←─── REPLY ───────────────────── P3 (not interested)    β”‚
     β”‚                              β”‚                         β”‚
     β”‚  *** P1 enters CS ***        β”‚                         β”‚
     β”‚  (has all N-1 replies)       β”‚                         β”‚
     β”‚                              β”‚                         β”‚
     │─── RELEASE ────────────→ P2  β”‚ Deferred replies sent   β”‚
     β”‚                              β”‚ P2 now has all replies  β”‚
     β”‚                              β”‚ *** P2 enters CS ***    β”‚

Key Properties

Safety: Only one node enters CS at a time. Proof: if two nodes both entered, they’d each need replies from all others, including each other β€” but the later requester defers its reply to the earlier one.

Liveness: The request with the smallest timestamp gets replies from everyone. No deadlock because timestamps provide a total ordering.

Fairness: Requests are granted in timestamp order (FCFS).

Message complexity: 2(N-1) messages per entry β€” (N-1) REQUESTs + (N-1) REPLYs.

Why timestamps matter:

Without timestamps, concurrent requests could deadlock:
  P1: "I want CS"
  P2: "I want CS"
  Both wait forever for each other's reply.

With timestamps (logical clocks):
  P1: REQUEST(10)   P2: REQUEST(15)
  P2 sees 10 < 15 β†’ P2 replies to P1 (defers its own)
  P1 enters, exits, sends deferred reply to P2
  P2 enters (all replies received)

Optimization: Maekawa’s Voting Sets

Maekawa reduced messages to ~3√N by having nodes request a voting set (subset of nodes) instead of all nodes. Each pair of voting sets must intersect. This reduces message complexity but introduces the possibility of deadlock.

Check Your Understanding

  1. How many messages does Ricart-Agrawala use per critical section entry?
  2. In Ricart-Agrawala, why do we compare timestamps when deciding whether to defer a reply?
  3. If P1 sends REQUEST(5) and P2 sends REQUEST(3), who enters the critical section first? Why?

The β€œSo What?”

Ricart-Agrawala is the canonical example of a decentralized coordination algorithm. Its timestamp-based approach is the ancestor of many modern protocols, including the way ZooKeeper orders requests via ZXID timestamps and how distributed databases sequence transactions with hybrid logical clocks.

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