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

<p>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)$ </p>

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

CC BY-SA 3.0
2012-10-24T16:31:42.407Z
I have a copy of the chapter, but I dont know how to attach it !
AJed
CC BY-SA 3.0
2012-10-24T03:52:01.060Z
2012-10-24T03:52:01.060Z
AJed
<p>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.</p>

<p>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?</p>

<p>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).</p>

CC BY-SA 3.0
2012-01-20T08:44:23.243Z
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.
Jukka Suomela
CC BY-SA 3.0
2012-01-20T08:52:22.200Z
@JukkaSuomela Clarified
Šimon Tóth
CC BY-SA 3.0
2012-01-20T09:20:07.263Z
Oh, I see, the challenge is to do it with $O(n)$ *messages*, not in $O(n)$ time?
Jukka Suomela
CC BY-SA 3.0
2012-01-20T09:21:46.833Z
@JukkaSuomela Yeah
Šimon Tóth
CC BY-SA 3.0
2012-01-20T10:46:18.690Z
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?
Jukka Suomela
CC BY-SA 3.0
2012-01-20T12:09:12.673Z
Edited for clarity (I hope).
Jeffε
CC BY-SA 3.0
2012-01-20T12:48:38.463Z
(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)](http://doi.acm.org/10.1145/1634.1889).
Peter
CC BY-SA 3.0
2012-01-20T16:45:39.247Z
@JukkaSuomela If you search google, you will get hits, but I haven't found any real description of the algorithm, only references, that it is well known.
Šimon Tóth
<cc.complexity-theory><complexity-classes><dc.distributed-comp>
O(N) leader election on torus with orientation and non-positional identity
Šimon Tóth
# O(N) leader election on torus with orientation and non-positional identity

(Asked by: username_0 on 2012-01-20)

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).

**Tags:** cc.complexity-theory, complexity-classes, dc.distributed-comp
> **Comments:**
> **username_1**: 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.  
> **username_0**: @JukkaSuomela Clarified  
> **username_1**: Oh, I see, the challenge is to do it with $O(n)$ *messages*, not in $O(n)$ time?  
> **username_0**: @JukkaSuomela Yeah  
> **username_1**: 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?  
> **username_2**: Edited for clarity (I hope).  
> **username_3**: (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)](http://doi.acm.org/10.1145/1634.1889).  
> **username_0**: @JukkaSuomela If you search google, you will get hits, but I haven't found any real description of the algorithm, only references, that it is well known.  

---

## 1 answers

### Answer by username_4 on 2012-10-24. Score: 3 | Accepted answer

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)

> **Comments:**
> **username_4**: I have a copy of the chapter, but I dont know how to attach it !  

---

