Improving the availability of mutual exclusion systems on incomplete networks

摘要

We model a distributed system by a graph G=(V, E), where V represents the set of processes and E the set of bidirectional communication links between two processes. G may not be complete. A popular (distributed) mutual exclusion algorithm on G uses a coterie C(/spl sube/2/sup V/), which is a nonempty set of nonempty subsets of V (called quorums) such that, for any two quorums P, Q/spl isin/C, 1) P/spl cup/Q/spl ne/0 and 2) P/spl nsub/Q hold. The availability is the probability that the algorithm tolerates process and/or link failures, given the probabilities that a process and a link, respectively, are operational. The availability depends on the coterie used in the algorithm. This paper proposes a method to improve the availability by transforming a given coterie.