# Lower bound for orienting an asynchronous ring?

We require a lower message complexity bound of an asynchronous distributed algorithm that do the following: Given a undirected ring, with $n$ vertices, we want to let each node direct its edges to form a directed cycle in the ring.

That is: if our ring is : a-b-c-d-a ---> then we want our result to be a->b->c->d->a

Note that the nodes in the ring do not have a common definition of left and right .. that is, the left of node a may be the right of node b etc .. (this is why the problem is difficult)

I think that the lower bound is $\Omega(n\log n)$ - similar to the election problem. But I cannot prove it until now. I was trying to prove it by contradiction with other known lower bounds. That is, if we can solve this problem, then we can solve problem A with a complexity lower than its known lower bound. I tried it with the election problem, it did not work obviously. Any suggestions ?

• Note that a simple solution to this problem (and perhaps the optimal) is to select a leader, and then the leader broadcast starting from one of its neighbors only.
– AJed
Commented Oct 11, 2012 at 6:40
• Actually, I guess I found the answer - which is nlogn as expected. The result is cited in [1] - I still need to get my hand on the original proof in [2]. \n [1] New lower bound techniques for distributed leader finding and other problems on rings of processors, Han L. Bodlaend [2] C. Attiya, M. Snir and M. Warmuth, Computing on anonymous rings, Technical Report 85-2, Computer Science Dept., The Hebrew University, March 1985.
– AJed
Commented Oct 11, 2012 at 7:24

Note that if node ids are chosen from some countable set and you don't care about time complexity, the $\Omega(n\log n)$ messages lower bound for electing a leader in a synchronous ring does not apply.
In that case, there's an $O(n)$ messages algorithm that solves your problem: First, elect a leader using the $O(n)$ time-slicing algorithm of [1], and then, as mentioned in your comment, use the leader to orient the ring. Moreover, $\Omega(n)$ seems to be a trivial lower bound: If $o(n)$ messages are being sent, then there is a segment of $2$ neighboring nodes that do not send/receive any messages throughout the run. By an indistinguishability argument, you can show that there is a run where you get conflicting orientations.