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