An Algorithm for Mutual Exclusion in Computer Networks.
Interim technical rept.,
MARYLAND UNIV COLLEGE PARK DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
An algorithm is proposed which creates mutual exclusion in a computer network whose nodes can communicate only by messages and do not share memory. The algorithm sends only 2N-1 Messages, where N is the number of nodes in the network, per critical section invocation. This number of messages is a minimum if parallel, distributed, symmetric control is used hence, the algorithm is optimal in this minimal under some general assumptions. Like Lamports bakery algorithm, unbounded sequence numbers are used to provide first-come first-served priority into the critical section. It is shown that the number can be contained in a fixed amount of memory by storing it as the residue of a modulus. The number of messages required to implement the exclusion can be reduced by using sequential node-by-node processing, by using broadcast message techniques or by sending information through timing channels. The readers and writers problem is solved by a simple modification of the algorithm. The modifications necessary to make the algorithm robust are described. Author
- Computer Hardware
- Computer Systems
- Non-Radio Communications