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.