Distributed Mutual Exclusion
Stub. Message-passing solutions (Lamport, Ricart-Agrawala, Maekawa), token-passing algorithms (Suzuki-Kasami, Raymond), shared-memory solutions (Peterson, test-and-set, load-linked/store-conditional), and the group mutual exclusion generalization.
How to guarantee only one process is in a critical section at a time when there’s no shared memory to arbitrate with. Three families of solution: message-passing permission-based algorithms (Lamport’s totally-ordered requests, Ricart-Agrawala’s optimization, Maekawa’s quorum-based approach trading messages for a more complex correctness argument), token-passing algorithms (a single token circulates and possession grants access — Suzuki-Kasami, Raymond’s tree-based variant), and, when shared memory is available, classical solutions (Peterson’s algorithm, hardware test-and-set, load-linked/store-conditional). Group mutual exclusion generalizes the problem to let same-group processes share the section simultaneously.
Outline (TODO — flesh out each)
- Message-passing solutions: Lamport’s, Ricart-Agrawala’s, Maekawa’s
- Token-passing algorithms: Suzuki-Kasami, Raymond’s
- Shared-memory solutions: Peterson’s algorithm
- Solutions using special instructions: test-and-set, LL/SC
- The group mutual exclusion problem — centralized and decentralized solutions