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 ?