Improving the availability of mutual exclusion systems on incomplete networks

Takashi Harada, Masafumi Yamashita

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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(⊆ 2V), which is a nonempty set of nonempty subsets of V (called quorums) such that, for any two quorums P, Q ∈ C, 1) P ∩ Q ≠ ∅ and 2) P ⊄ 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.

Original languageEnglish
Pages (from-to)744-747
Number of pages4
JournalIEEE Transactions on Computers
Issue number7
Publication statusPublished - Jul 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Improving the availability of mutual exclusion systems on incomplete networks'. Together they form a unique fingerprint.

Cite this