---
title: "Ways to achieve distributed mutex"
subject: "Distributed System"
chapter: 6
key: "semester_7/distributed_system:mutex-methods"
source: https://www.bctengineer.com/q/semester_7/distributed_system/mutex-methods
site: BCT Engineering
---

# Ways to achieve distributed mutex

Distributed System · Chapter 6: Coordination and Agreement

- Asked in: Model question
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/mutex-methods
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6

## Question

Define distributed mutual exclusion. In how many ways can the mutual exclusion be achieved in distributed system? (see all mutual exclusion algorithms)

## Short answer

Distributed mutual exclusion ensures only one process accesses a critical section at a time via message passing. It can be achieved by permission-based algorithms (centralized, Lamport, Ricart-Agrawala, Maekawa quorum) and token-based algorithms (token ring, Suzuki-Kasami, Raymond's tree).

## Answer

**Distributed mutual exclusion** guarantees that only one process at a time accesses a shared resource or critical section (CS) in a distributed system where processes only communicate by messages and share neither memory nor a clock. The requirements are safety (one process in CS), liveness (no deadlock) and fairness (no starvation).

Mutual exclusion can be achieved in the following ways.

#### A. Non-token-based (permission-based) algorithms
A process asks others for permission before entering the CS.
1. **Centralized algorithm**: one coordinator grants permission. 3 messages per entry; coordinator is a bottleneck and single point of failure.
2. **Lamport's algorithm**: timestamped requests kept in queues at all nodes; 3(N−1) messages.
3. **Ricart-Agrawala algorithm**: request to all, deferred replies; 2(N−1) messages.
4. **Maekawa's algorithm** (quorum/voting): permission from a subset of about √N processes; about 3√N messages.

#### B. Token-based algorithms
A unique token represents the right to enter the CS; only its holder may enter.
1. **Token ring algorithm**: the token circulates in a logical ring; 1 to N−1 messages per entry, but circulates continually.
2. **Suzuki-Kasami broadcast algorithm**: a requester broadcasts a request for the token; N messages per entry.
3. **Raymond's tree-based algorithm**: processes form a tree; the request moves toward the token holder; O(log N) messages.

#### C. Others
Mutual exclusion can also be achieved by a **hierarchical or hybrid** approach and by fault-tolerant versions with election of a new coordinator or token regeneration.

| Class | Representative | Messages per entry |
|---|---|---|
| Centralized | Coordinator | 3 |
| Non-token | Lamport / Ricart-Agrawala | 3(N−1) / 2(N−1) |
| Quorum | Maekawa | ~3√N |
| Token | Ring / Suzuki-Kasami | 1..N−1 / N |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Distributed mutual exclusion algorithms are mainly classified as
   A. Synchronous and asynchronous only
   B. Centralized and replicated databases
   C. Symmetric and asymmetric encryption
   D. Non-token (permission-based) and token-based
   Answer: D. Permission-based algorithms ask for permission; token-based ones use a unique token. (Key point: Classes of algorithms)

2. Which algorithm uses permission from a subset of about sqrt(N) processes?
   A. Maekawa's
   B. Ricart-Agrawala
   C. Token ring
   D. Suzuki-Kasami
   Answer: A. Maekawa's quorum voting needs about 3 sqrt(N) messages. (Key point: Quorum algorithm)

3. Match: Suzuki-Kasami and Raymond's message costs per entry.
   A. 3 and 3(N-1)
   B. N and O(log N)
   C. 2(N-1) and 3
   D. 1 to N-1 and N
   Answer: B. Suzuki-Kasami broadcasts a request (N messages); Raymond's tree moves requests along the tree. (Key point: Message costs)

## Related in Distributed System

- [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3×
- [Ricart-Agrawala mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aricart-agrawala) — Distributed System, chapter 6, asked 2×
- [Lamport algorithm for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-mutex) — Distributed System, chapter 6
- [Mutex requirements; token vs non-token](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-requirements-compare) — Distributed System, chapter 6
- [Autonomous vs distributed system](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aautonomous-vs-distributed) — Distributed System, chapter 1
- [Models of distributed system](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amodels-of-ds) — Distributed System, chapter 1

## Related in other subjects

- [Critical section; mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acritical-section-mutual-exclusion-pc) — Operating System, chapter 3
- [Race condition; mutual exclusion requirements](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-mutual-exclusion-requirements) — Operating System, chapter 3
- [Semaphore for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Asemaphore-enforce-mutual-exclusion) — Operating System, chapter 3
- [Mutual exclusion via sleep and wake](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Amutual-exclusion-sleep-wake) — Embedded System, chapter 6