Date: 03/02/05 (Algorithms)    Keywords: no keywords

I was reading my Distributed algorithms book (by Nancy Lynch) last night and I got stuck in the 3rd chapter on the leader election problem in a synchronous network. I noticed that the LCR algorithm's communication-complexity is O(n^2) and the time-complexity is O(n). The time-complexity makes sense because you go through the ring and each node in the ring gets a chance to send out it UID to it's clockwise neighbor and wait for a reply from it's counter-clockwise neighbor and you do this for every node in the ring, since every node has a Unique Id, then there must be a largest value and the algorithm is O(n) to elect the leader. I am having trouble understanding why the algorithm has each node send out its UID (one at a time of course) until a leader is elected; making the communication complexity be O(n^2). Can't you just start in an arbitrary location in the ring and send out your uid, then when you receive a message (which should be the largest uid in the ring), record it and send out a "who's is this?" message around the ring and halt when the node with that uid annouces herself as leader? And if you want every node to know who the leader was so that each nodal process halts, the leader can send a "I am you leader" message around the ring. Now, this is O(3n) which is still O(n) and that's better than O(n^2) and also better than the O(n log n) algorithm (when n is large) they present in that chapter as well. Maybe someone can explain to me why LCR works the way it does? Am i missing something?

Source: http://www.livejournal.com/community/algorithms/48518.html