Distributed Algorithms for Leader Election on Partially Ordered Keys (特集マルチメディア通信プロトコル)

概要

論文の詳細を見る
The leader election problem is a fundamental problem in distributed computing. the classical leader election problem can be considered as finding the processor with the maximum key in a distributed network in which each processor has one key and a total order is defined on the keys. In this paper, we define a generalized leader election problem that finds all the processors with the maximal keys on the basis of a partial order on the keys. We propose two distributed algorithms for the generalized leader election problem. The first algorithm solves the problem on a network by using a spanning tree of the network. The message complexity of the algorithm is O(mn), where m is the number of different keys and n is the number of processors. The time complexity of the algorithm is O(n). The second algorithm solves the problem using a coterie of the n processors. The number of messages exchanged on the coterie is O(max{rn, n^<1.5>}), where r is the number of the maximal keys. When the physical network for connecting the n processors is considered, the message and time complexities of the second algorithm are O(max{drn, dn^<1.5>}) and O(d), respectively, where d is the diameter of the network.
一般社団法人情報処理学会の論文
2000-02-15