Time and message bounds for election in synchronous and asynchronous complete networks

摘要: This paper addresses the problem of distributively electing a leader in both syn- chronous and asynchronous complete networks. O(n log n) messages synchronous algorithms are presented. The time complexity algorithm is O(log n), while that O(n). In case, lower bound 12(nlogn) on message proven. It also proven any message-optimal algo- rithm requires 12(log time. proving these bounds, type operations performed by nodes not restricted. bounds thus apply to general just comparison-based algorithms. be selected from set which initially differ only their identifiers (ids), with no node being aware other id. An arbitrary subset wakes up spontaneously at times starts sending over network. When exchange terminates, distinguished all nodes. specializes such network, each pair connected bidirectional communication link. Before starts, has information Hence, incident links node, was sent or received, indistinguishable. We consider modes