3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Sep 26, 2013 at 13:46
  • $\begingroup$ @VolkerTurau yes $\endgroup$
    – pkacprzak
    Commented Sep 26, 2013 at 14:17

1 Answer 1

Reset to default
1
$\begingroup$

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

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

Improve this answer
$\endgroup$

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.