[ont.events] CS Seminar, Mr. Piquer on "A Facult-Tolerant Mutual Exclusion .."

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.