Leader election in complete networks
Gurdip Singh · 1992
This paper presents protocols for leader election in complete networks. The protocols are message optimal and their time complexities are a significant improvement over currently known protocols for this problem. For asynchronous complete networks with sense of direction, we propose a protocol which requires O(N) messages and O(log N) time. For asynchronous complete network without sense of direction, we show that Ω(N/log N) is a lower bound on the time complexity of any message optimal election protocol and we present a family of protocols which requires O(Nk) messages and O(N/k) time, log N ≤ k ≤ N. Our results also improve the time complexity of several other related problems such as spanning tree construction, computing a global function, etc.