The Complexity of Leader Election: A Chasm at Diameter Two
The Complexity of Leader Election: A Chasm at Diameter Two
复制标题
领导者选举的复杂性：直径二的鸿沟
DOI：
10.1145/3154273.3154308
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Robinson, Peter
中科院分区：
文献类型：
--
作者：
Chatterjee, Soumyottam;Pandurangan, Gopal;Robinson, Peter
领袖选举是分布式计算中的基本问题之一。在其含蓄的版本中，只有领导人必须知道谁是当选的领导人。本文主要研究了同步分布式网络，特别是直径为2的网络中领袖选举的消息复杂性问题。Kutten等人。[JACM2015]证明了Ω(M)(m是网络中的边数)关于(隐式)领导者选举的消息复杂性的一个基本下界，该下界也适用于具有恒定成功概率的蒙特卡罗随机算法；这个下界适用于直径至少为3的图。另一方面，对于完全图(即直径1)，Kutten等人。[TCS 2015]建立了随机领导选举消息复杂度的Θ(√n)1的一个紧界(n为网络中的节点数)。对于直径为2的图，其复杂性是未知的，本文通过证明Θ(N)对直径为2的网络中领导人选举的消息复杂性的一个紧界来解决这一复杂性。我们首先给出了一个简单的随机蒙特卡罗领袖选举算法，该算法以很高的概率(即，对于某个正数c，概率至少为1-n-c)成功并且使用O(Nlog3n)个消息，并且运行O(1)轮；该算法不需要n的知识(因此不需要全局知识)。然后，我们证明了任何算法(即使是具有足够大的恒定成功概率的蒙特卡罗随机算法)都需要Ω(N)消息(即使在n已知的情况下)，而与轮数无关。我们还给出了一个O(Nlogn)消息确定性算法，它需要O(Logn)轮(但需要n的知识)；我们证明了这种消息复杂性对于确定性算法来说是紧的.我们的结果表明，领袖选举可以在(本质上)线性(In N)消息复杂度的直径二图中求解，因此Ω(M)下界不适用于直径二图.结合Kutten等人的前两个结果，我们的结果充分刻画了领导人选举相对于图直径的消息复杂性。
Leader election is one of the fundamental problems in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message complexity of leader election in synchronous distributed networks, in particular, in networks of diameter two. Kutten et al. [JACM 2015] showed a fundamental lower bound of Ω(m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability; this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., diameter 1), Kutten et al. [TCS 2015] established a tight bound of Θ(√n)1 on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known.In this paper, we settle this complexity by showing a tight bound of Θ(n) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 -- n-c, for some positive constant c) succeeds and uses O (n log3 n) messages and runs in O (1) rounds; this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs Ω(n) messages (even when n is known), regardless of the number of rounds. We also present an O (n log n) messages deterministic algorithm that takes O (log n) rounds (but needs knowledge of n); we show that this message complexity is tight for deterministic algorithms.Our results show that leader election can be solved in diameter-two graphs in (essentially) linear (in n) message complexity and thus the Ω(m) lower bound does not apply to diameter-two graphs. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-à-vis the graph diameter.
登录
查看更多内容
影响因子：
1.3
作者：
Maleq Khan;F. Kuhn;D. Malkhi;Gopal Pandurangan;Kunal Talwar
通讯作者：
Kunal Talwar
完整处理器网络的某些分布式算法的严格下限和上限
DOI：
10.1145/800222.806747
发表时间：
1984
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
E. Korach;S. Moran;S. Zaks
通讯作者：
S. Zaks
完整处理器网络的某些分布式算法的最佳下界
DOI：
10.1016/0304-3975(89)90103-5
发表时间：
1989
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
E. Korach;S. Moran;S. Zaks
通讯作者：
S. Zaks
在 0(N log N) 条消息中选择派系中的领导者
DOI：
10.1109/cdc.1984.272191
发表时间：
1984
期刊：
The 23rd IEEE Conference on Decision and Control
影响因子：
--
作者：
P. Humblet
通讯作者：
P. Humblet
同步和异步完整网络中选举的时间和消息范围
DOI：
10.1145/323596.323613
发表时间：
1985
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Y. Afek;E. Gafni
通讯作者：
E. Gafni