Accession Number:

ADA083268

Title:

An Algorithm for Mutual Exclusion in Computer Networks.

Descriptive Note:

Interim technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1980-02-01

Pagination or Media Count:

36.0

Abstract:

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

Subject Categories:

  • Computer Hardware
  • Computer Systems
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE