Distributed Mutual Exclusion and Leader Election

Mutual exclusion and leader election are classical coordination problems: ensuring that at most one process accesses a critical resource, and selecting a single distinguished coordinator among peers.

Definition

Distributed mutual exclusion guarantees that at most one process at a time holds a shared resource while ensuring eventual access for all requesters; leader election deterministically selects exactly one process as coordinator, with all processes agreeing on the outcome.

Scope

This topic covers permission-based mutual-exclusion algorithms (Lamport's timestamp algorithm, Ricart-Agrawala, Maekawa's quorum approach) and token-based algorithms, together with their message complexity and fairness properties; and leader-election algorithms for rings (Chang-Roberts) and general networks (the bully algorithm), including their assumptions about identifiers and synchrony. These primitives recur throughout coordination services and replicated systems.

Core questions

• How can processes serialize access to a shared resource using only messages?
• What are the message-complexity and fairness trade-offs among permission-based and token-based schemes?
• How is a unique leader chosen, and how is election re-triggered after the leader fails?

Key theories

Permission-based mutual exclusion

Algorithms such as Ricart-Agrawala order requests by logical timestamps and grant entry once a requester has received permission from all (or a quorum of) peers, achieving fairness with bounded message cost per critical-section entry.

Token-based mutual exclusion

A unique token circulates or is requested on demand, and only its holder may enter the critical section, reducing message traffic but requiring mechanisms to regenerate a lost token after failures.

Leader election

Election algorithms such as Chang-Roberts for rings and the bully algorithm for general networks use process identifiers to converge on a single highest-priority coordinator that all correct processes recognize.

Clinical relevance

Leader election is invoked whenever a replicated system must pick a primary or coordinator, and distributed locking generalizes mutual exclusion; both are exposed as core services by coordination systems used throughout cloud infrastructure.

History

Lamport's 1978 logical-clock paper introduced a timestamp-based mutual-exclusion algorithm; Ricart and Agrawala optimized it in 1981, Maekawa introduced quorums shortly after, and Garcia-Molina's 1982 bully algorithm formalized leader election, giving the field its canonical coordination algorithms.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

How does distributed mutual exclusion differ from a lock on a single machine?

There is no shared memory or central lock manager to rely on, so processes must coordinate purely by exchanging messages and must explicitly handle message delay and failures, which a single-machine lock can take for granted.