Fault-Tolerant Distributed Match-Making with Any Resiliency

Amane NAKAJIMA

Summary :

Distributed match-making is a paradigm that deals with the match-making property of distributed issues such as name service, mutual exclusion, and replicated data management. In order to realize distributed match-making, two kinds of subsets with certain properties must be constructed for each process. We call a set of the subsets defined for all processes an arrangement." In this paper, we discuss arrangements for symmetric and fault-tolerant distributed match-making. First, it is shown that a combinatorial design called a symmetric balanced incomplete block design (SBIBD) can be applied to fault-tolerant distributed match-making. However, an SBIBD does not realize symmetry. We therefore focus on ways of achieving this. A completely symmetric arrangement for fault-tolerant distributed match-making does not always exist. We show that a completely symmetric arrangement called a symmetric resilient arrangement (SRA) exists when n/m is an integer, where n is the number of processes and m-1 is the resiliency of an algorithm. We present a method of constructing an SRA and generalize the method to allow construction of a generalized SRA (GSRA), which is almost symmetric and can be constructed with any combination of n and m. The communication complexity of fault-tolerant distributed match-making is also discussed. We show that the communication complexity of our SRA is 2mn and that the communication complexity of our GSRA is equal to or less than 2 min (mn/m, n). We also show that a lower bound of the communication complexity of an SBIBD is 2mn.

• Publication: IEICE TRANSACTIONS on Information Vol.E74-D No.2 pp.427-434
• Publication Date: 1991/02/25
• Type of Manuscript: PAPER
• Category: Fault Tolerant Computing

Authors

Amane NAKAJIMA

Keyword