Ways to achieve distributed mutex

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.