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 ?

  • $\begingroup$ 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. $\endgroup$ – AJed Oct 11 '12 at 6:40
  • $\begingroup$ 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. $\endgroup$ – AJed Oct 11 '12 at 7:24

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)

  • $\begingroup$ I am sorry. Perhaps I should have mentioned that the ring is asynchronous. $\endgroup$ – AJed Oct 11 '12 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.