On the complexity of universal leader election
On the complexity of universal leader election
复制标题
论普遍领导人选举的复杂性
DOI：
10.1145/2484239.2484274
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Amitabh Trehan
中科院分区：
文献类型：
--
作者：
S. Kutten;Gopal Pandurangan;D. Peleg;Peter Robinson;Amitabh Trehan
选举领导者是分布式计算的基本任务对于随机算法，大多数“明显”的复杂性界限尚未证明。 ω（d）时间（d是网络直径）是不平整的，用于随机（Monte Carlo）算法（最近的结果表明甚至是网络中的节点的数量）据我们所知，在完整网络中的较低限制使上述界限也不太明显。也是要求某些节点可能不会自发醒来，而D和N尚不清楚）。
我们在本文的一般情况下建立了这些基本的下限，M和N，即使已知D，M和N，所有节点都会同时唤醒，并且算法可以使任何节点的身份都表明这些界限很紧。 O（M）消息算法。
一个有趣的基本问题是，是否可以在所有图表的随机设置中达到上限（消息和时间）。在某些情况下，这两种复杂性都与确定性算法的第一步相比（某些情况下）。通用领导者选举算法具有折衷消息与时间的界限。
Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. The "obvious" lower bounds of Ω(m) messages (m is the number of edges in the network) and Ω(D) time (D is the network diameter) are non-trivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even Ω(n) (n is the number of nodes in the network) is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms (except for the limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that D and n were not known).
We establish these fundamental lower bounds in this paper for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (such algorithms should work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make anyuse of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω(m) message lower bound for randomized broadcast algorithms.
An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. (The answer is known to be negative in the deterministic setting). We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that trade-off messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.