O(N) leader election on torus with orientation and non-positional identity 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).
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)