Distributed Algorithms for Leader Election on Partially Ordered Keys

• Item type: Journal(1)
• 公開日: 2000-02-15
• タイトル: Distributed Algorithms for Leader Election on Partially Ordered Keys
• タイトル / 言語: en
• タイトル: Distributed Algorithms for Leader Election on Partially Ordered Keys
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：マルチメディア通信プロトコル
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 分散処理
• 著者所属: Department of Computer Software University of Aizu
• 著者所属: Department of Computer Software University of Aizu
• 著者所属(英): en
• 著者所属(英): Department of Computer Software, University of Aizu
• 著者所属(英): en
• 著者所属(英): Department of Computer Software, University of Aizu
• 著者名: Zixue, Cheng; Qian-PingGu
• 著者名(英): Zixue, Cheng; Qian-Ping, Gu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The leader election problem is a fundamental problem in distributed computing.The classical leader election problem can be considered as findingthe processor with the maximum key in a distributed networkin 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 findsall 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 ofthe second algorithm are $O(?max ?{drn dn^{1.5}?})$ and $O(d)$ respectively where $d$ is the diameter of the network.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The leader election problem is a fundamental problem in distributed computing.The classical leader election problem can be considered as findingthe processor with the maximum key in a distributed networkin 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 findsall 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 ofthe second algorithm are $O(\max \{drn,dn^{1.5}\})$ and $O(d)$, respectively,where $d$ is the diameter of the network.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 41, 号 2, p. 415-423, 発行日 2000-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764