I'm looking for an algorithm to compute the BFS tree of a graph rooted in the leader processor $r$ in the asynchronous distributed model.

The only requirement is $O(D)$ time complexity, where $D$ denotes the diameter of the graph (message complexity isn't relevant).

Currently, I'm using Bellman-Ford algorithm, but I don't know how to guarantee the global termination of this method in $O(D)$ time. I was trying to use the convergecast technique, but with no success.

Is it possible to guarantee a termination of Bellman-Ford in $O(D)$ time or is there any other algorithm for computing the BFS tree in $O(D)$ time?

  • $\begingroup$ A proof that the algorithm terminates in time O(Diam(G)) is contained in Peleg's book (p. 53). Do you want the root to detect the termination in this time? $\endgroup$ – Volker Turau Sep 26 '13 at 13:46
  • $\begingroup$ @VolkerTurau yes $\endgroup$ – pkacprzak Sep 26 '13 at 14:17

I found the answer. The alpha synchronizer will do it.

Here is the full paper: Baruch Awerbuch (1985). Complexity of Network Synchronization


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.