# An Algorithm for Mutual Exclusion in Computer Networks.

Title | An Algorithm for Mutual Exclusion in Computer Networks. |

Publication Type | Reports |

Year of Publication | 1980 |

Authors | Agrawala AK, Ricart G |

Date Published | 1980/// |

Institution | Department of Computer Science, University of Maryland, College Park |

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 2*(N-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 Lamport's '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. |