Construction of optimal communication structures for weighted distributed match-making

Abstract

Several distributed issues such as name service and replicated data management need a communication structure with an intersection property. This paper discusses the efficiency of communication structures for cases in which the issues are weighted. We first provide a lower bound of communication complexity, using a distribution vector, and then give a method for constructing an efficient and symmetric communication structure. Our method achieves the lower bound 2 √abn in the symmetric case, where √an/b and √bn/a are integers, a and b are weights, and n is the number of nodes. © 1993.