<p><em>Edit: The answer below was written assuming that the ring is <strong>synchronous</strong>.</em></p>

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

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

<p>[1] Greg N. Frederickson, Nancy A. Lynch: Electing a leader in a synchronous ring. J. ACM 34(1): 98-115 (1987)</p>

CC BY-SA 3.0
2012-10-11T07:21:58.463Z
I am sorry. Perhaps I should have mentioned that the ring is asynchronous.
AJed
CC BY-SA 3.0
2012-10-11T07:13:24.320Z
2012-10-11T07:40:27.940Z
2012-10-11T07:40:27.940Z
Peter
<p>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. </p>

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

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

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

CC BY-SA 3.0
2012-10-11T06:40:50.510Z
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
CC BY-SA 3.0
2012-10-11T07:24:45.870Z
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
<ds.algorithms><graph-algorithms><dc.distributed-comp>
Lower bound for orienting an asynchronous ring?
AJed
# Lower bound for orienting an asynchronous ring?

(Asked by: username_0 on 2012-10-11)

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 ?

**Tags:** ds.algorithms, graph-algorithms, dc.distributed-comp
> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2012-10-11. Score: 2

*Edit: The answer below was written assuming that the ring is **synchronous**.*

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.

[1] Greg N. Frederickson, Nancy A. Lynch: Electing a leader in a synchronous ring. J. ACM 34(1): 98-115 (1987)

> **Comments:**
> **username_0**: I am sorry. Perhaps I should have mentioned that the ring is asynchronous.  

---

