I try to solve an exercise in Distributed Algorithm described as follow.

Let's define a label assignment problem as follow. There is a anonymous network (vertices don't have unique ID's , nodes don't have any clue about $n$ - number of vertices nor about network topology ). The labels assigned to vertices must be distinct and there is no limitation on the length of the label. The initiator is given. Show the algorithm for solving the problem in asynchronous model with time complexity $\text{O}(D)$ and using $\text{O}(m)$ messages (where $D$ is the diameter of graph and $m$ number of edges), prove that the labels are indeed distinct. Show the changes in complexities if the algorithm is executed on the synchronous network.

Let's say that the initiator is the node A, wlog assign it $A_{id} = 1$, broadcast $A_{id} = 1$ to all children of $A$ by flooding algorithm, any node $B$ by receiving message from it's parent for the first time will assign $B_{id} = PARENT_{id}+1$ and send $B_{id}$ to it's children, if $B_{id}$ is already defined, drop the message. $T=\text{O}(D)$ - time complexity, $M=\text{O}(m)$ - message complexity for broadcast.

It seems like on synchronous network the complexities will be the same, just becasue broadcast and convergecast on synchronous and asynchronous network run in $T=\text{O(D)}$ and $M=\text{O}(m)$.

If there are any change in complexities on the synchronous network? Does the above algorithm look good?

  • $\begingroup$ Are you sure that the exercise does not assume a single initiator ? given that this is a book exercise as you say, i think it should be simple. $\endgroup$
    – AJed
    Dec 27, 2012 at 0:51
  • $\begingroup$ @AJed, you are right, let's assume we have an initiator (I've edited the question correspondingly), is the algorithm right, and what can we say about synchronous version? $\endgroup$
    – com
    Dec 27, 2012 at 7:24
  • $\begingroup$ That will asign the identity 2 to all neighbors of $A$... $\endgroup$
    – vonbrand
    Feb 25, 2013 at 12:43

1 Answer 1


I dont know the solution of your problem: especially as we dont have a limit on the ID's. My "guessing" is that you cannot solve this problem with complexities you listed.

I will only answer your following question:

Does the usage of randomized leader election is eligible in the case of graph as described above?

I dont suggest using leader election. Its lower bound does not meet your requirement (it is still an open problem to solve the election problem with $O(D)$ time and $O(m + n \log n)$ message, Peleg 199*). The known randomized election algorithms so far do not work on arbitrary graphs. There is a new algorithm that runs in arbitrary graphs (but requires knowledge of $n$). This algorithm is not yet officially published (due to Peleg et al. 2012).

I will list the references later.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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