mwang_pay (06/28/82)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
SYSTEMS SEMINAR - Tuesday, July 6, 1982.
Mr. Alfredo R. Piquer, a graduate student of this depart-
ment, will speak on "A Fault-Tolerant Mutual Exclusion Al-
gorithm for a Distributed System."
TIME: 3:30 PM
ROOM: M&C 5158
ABSTRACT
We present a mutual exclusion algorithm for a distributed
system that is correct (i.e. achieves exclusion and avoids
deadlock), even if some processors fail. The algorithm is
simple and it has minimal overhead when there is only one
processor trying to enter the critical section: in this
case it requires only one message to every other proces-
sor. The algorithm does not require each processor to
keep global information about the system, so the algorithm
can be executed by a processor after a loss of memory
(e.g. due to a failure) without extra overhead.
The algorithm is first presented in an abstract form,
without specifying how information is exchanged among pro-
cessors. It is then shown that LeLann's algorithm for to-
ken regeneration in a virtual ring is one possible imple-
mentation of our algorithm. Finally, we discuss an imple-
mentation using a set of processes in each processor, com-
municating with simple message passing primitives.