# Termination of the Bellman-Ford algorithm in asynchronous distributed model

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?

• 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? – Volker Turau Sep 26 '13 at 13:46
• @VolkerTurau yes – pkacprzak Sep 26 '13 at 14:17