Fault-Tolerant Distributed Match-Making with Any Resiliency
Akira Nakajima · 1991
Protocols to solve several distributed issues, such as name service, mutual exclusion, and creation of an atomic shared register, require two types of sub-sets with intersection property. Distributed match-making provides a method of creating the subsets, and the lower bound of the number of messages to solve the issues. This paper discusses the fault-tolerant and weighted case, in which a protocol is fault-tolerant re-garding node failures, and in which weights of subsets are different. The paper jrst provides the lower bound of the number of messages required for a protocol in a general form. Then, it concentrates a symmetric case and shows the lower bound in a simpler form. The paper also provides a method of constructing the two types of subsets, which realize the lower bound. It first shows a method for a fully symmetric case, and ex-tends it for other cases. The extended method is prac-tical. It creates a cyclic communication structure; and is valid for any degree of fault-tolerance and wezghts. 1