Fault-tolerant distributed match-making with weights

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