Time and message bounds for election in synchronous and asynchronous complete networks
Time and message bounds for election in synchronous and asynchronous complete networks
复制标题
同步和异步完整网络中选举的时间和消息范围
DOI：
10.1145/323596.323613
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
E. Gafni
中科院分区：
文献类型：
--
作者：
Y. Afek;E. Gafni
本文探讨了在同步和异步完全网络中分布式选举领导者的问题。给出了消息复杂度为O(n log n)的同步和异步算法。同步算法的时间复杂度为O(log n)，而异步算法的时间复杂度为O(n)。在同步情况下，证明了消息复杂度的下限为Ω(n log n)。还证明了任何消息最优的同步算法需要Ω(log n)的时间。在证明这些界限时，对节点执行的操作类型没有限制。因此，这些界限适用于一般算法，而不仅仅是基于比较的算法。领导者要从一组最初仅在其标识符（ids）上不同的节点中选出，且没有节点知道任何其他标识符。任意节点子集在任意时间自发唤醒，并通过网络发送消息来启动算法。当消息交换终止时，一个领导者从所有其他节点中区分出来。本文专门研究在完全网络中选举领导者的问题。在这样的网络中，每对节点都由双向通信链路连接。在算法开始之前，没有节点拥有关于任何其他节点的任何信息。因此，一个节点的入射链路（其上没有发送或接收消息）是无法区分的。我们考虑同步和异步两种模式。
This paper addresses the problem of distributively electing a leader in both syn- chronous and asynchronous complete networks. O(n log n) messages synchronous and asynchronous algorithms are presented. The time complexity of the synchronous algorithm is O(log n), while that of the asynchronous algorithm is O(n). In the synchronous case, a lower bound of 12(nlogn) on the message complexity is proven. It is also proven that any message-optimal synchronous algo- rithm requires 12(log n) time. In proving these bounds, the type of operations performed by nodes are not restricted. The bounds thus apply to general algorithms and not just to comparison-based algorithms. to be selected from a set of nodes which initially differ only in their identifiers (ids), with no node being aware of any other id. An arbitrary subset of nodes wakes up spontaneously at arbitrary times and starts the algorithm by sending messages over the network. When the message exchange terminates, a leader is distinguished from all other nodes. This paper specializes in the problem of electing a leader in a complete network. In such a network, each pair of nodes is connected by a bidirectional communication link. Before the algorithm starts, no node has any information on any of the other nodes. Hence, the incident links of a node, on which no message was sent or received, are indistinguishable. We consider both synchronous and asynchronous modes of