leader election in complete networks
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 &Ohgr;( 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.
completeness network paper message optimality timing time complexity asynchronicity direct log lower bound families spanning tree computation global functional