Distributed mutual exclusion on a ring of processes

DOI10.1016/0167-6423(85)90015-2MaRDI QIDQ1060005zbMATH OpenOpenAlexFDO

Authors Alain J. Martin

Publication date 1985

Published in Science of Computer Programming (Search for Journal in Brave)

Full work available at URL https://resolver.caltech.edu/CaltechCSTR:1984.5080-tr-83

zbMATH Keywords

communication networkconcurrent computationcorrectness proofsCSPcyclic processesdistributed mutual exclusion

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Review text

A set of processes called 'masters' are sharing a critical section on a mutual exclusion basis. A master communicates only with its private 'server'. The servers communicate with each other in a ring. Three solutions for solving the mutual exclusion problem are presented. They all rely on the presence of a unique privilege in the ring. The notation used extends CSP input and output commands with a Boolean primitive, the 'probe', which makes it possible to determine whether a communication action is pending on a channel. In the correctness proofs, the concept of 'trace' is introduced, i.e. a total ordering of actions corresponding to a possible interleaving of the atomic actions of a concurrent computation.

Recommendations

• Symmetric and economical solutions to the mutual exclusion problem in a distributed system
• The mutual exclusion problem
• The mutual exclusion problem: part II---Statement and solutions
• The mutual exclusion problem
• The mutual exclusion problem. I: A theory of interprocess communication

Cited in

(4)

• On the complexity of deadlock-free programs on a ring of processors
• Fair Petri nets and structural induction for rings of processes
• Adaptive distributed mutual exclusion by dynamic topology switching
• Automatic verification of parameterized networks of processes

This page was built for publication: Distributed mutual exclusion on a ring of processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060005)