Fault-tolerant distributed match-making with weights
Akira Nakajima · 2002
Protocols to solve several distributed issues, such as name service, mutual exclusion, and creation of an atomic shared register, require two types of subsets 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 regarding node failures, and in which weights of subsets are different. The paper first 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 extends it for other cases. The extended method is practical. It creates a cyclic communication structure, and is valid for any degree of fault-tolerance and weights.