6
$\begingroup$

I'm really confused by this. Apparently there is a deterministic algorithm that does leader election on a torus with orientation and non-positional identity using only O(N) messages. I'm unable to find to find any description of this algorithm, and I still don't understand how it is even possible.

On a general graph with sense of direction you should be able to do leader election using O(N log N) messages. On complete graphs with sense of direction you do it with O(N) messages, because you have constant (1 message) communication with distant nodes. But how could you do that on a torus?

Here are some relevant details: The system is asynchronous. All processes start simultaneously. Each node has a "sense of direction"; that is, each node knows which of its neighbors are north, east, south, or west. Finally, each node has a unique ID (not related to its position in the torus).

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ You should define your terms ("non-positional identity", "sense of direction", etc.) as well as the model of computation. Anyhow, if you are interested in synchronous deterministic distributed algorithms, and you have unique $O(\log n)$-bit identifiers, then it is trivial to elect a leader in $O(n)$ synchronous communication rounds on any connected graph: just find the smallest identifier. And if you happen care about the size of messages, $O(\log n)$-bit messages are sufficient. $\endgroup$
    – Jukka Suomela
    Jan 20, 2012 at 8:44
  • $\begingroup$ @JukkaSuomela Clarified $\endgroup$
    – Šimon Tóth
    Jan 20, 2012 at 8:52
  • $\begingroup$ Oh, I see, the challenge is to do it with $O(n)$ messages, not in $O(n)$ time? $\endgroup$
    – Jukka Suomela
    Jan 20, 2012 at 9:20
  • 1
    $\begingroup$ Could you post a reference to the claim that such an algorithm exists? And do you already know how to solve the problem on a cycle? $\endgroup$
    – Jukka Suomela
    Jan 20, 2012 at 10:46
  • 2
    $\begingroup$ (not a real answer but I can't write comments yet) I would be surprised if it exists. In an asynchronous cycle there's an \Omega(n\log n) lower bound on the average message complexity see Jan K. Pachl, Ephraim Korach, Doron Rotem: Lower Bounds for Distributed Maximum-Finding Algorithms. J. ACM 31(4): 905-918 (1984). $\endgroup$
    – Peter
    Jan 20, 2012 at 12:48

1 Answer 1

Reset to default
3
$\begingroup$

The idea is growing territories. That is, a candidate broadcast to neighbors that are $\alpha^i$ away in iterations.

The trick is in the analysis! (so it s not really clear) -- by getting to know the worst case of candidates, and the number of messages they send + setting $\alpha$ to a certain constant - we get $O(n)$

The solution can be found in N. Santoro book in Chapter 3 (oriented torus)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have a copy of the chapter, but I dont know how to attach it ! $\endgroup$
    – AJed
    Oct 24, 2012 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.