Optimal distributed leader election algorithm for synchronous complete network
Paul Francis, Sharad Saxena · 2002
We address the problem of electing a leader in a synchronous complete network consisting of n nodes, each node has a unique ID. We give a message-optimal algorithm which runs in O(k) time using O(kn/sup /spl alpha/(k)/) messages, where /spl alpha/(k)=1+(1/2/sup k/) and parameter k is a positive integer; in particular we get a constant time algorithm which uses O(n/sup 1+/spl epsiv//) messages.