<p>I found the answer. The <a href="http://en.wikipedia.org/wiki/Synchronizer_%28algorithm%29" rel="nofollow">alpha synchronizer</a> will do it. </p>

<p>Here is the full paper: <a href="http://www.cs.uiowa.edu/~ghosh/synchronizer.pdf" rel="nofollow">Baruch Awerbuch (1985). Complexity of Network Synchronization</a></p>

CC BY-SA 3.0
2013-09-25T14:24:44.960Z
2013-09-25T14:24:44.960Z
pkacprzak
<p>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.</p>

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

<p>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. </p>

<p>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?</p>

CC BY-SA 3.0
2013-09-26T13:46:28.100Z
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
CC BY-SA 3.0
2013-09-26T14:17:19.383Z
@VolkerTurau yes
pkacprzak
<ds.algorithms><graph-algorithms><dc.distributed-comp>
Termination of the Bellman-Ford algorithm in asynchronous distributed model
pkacprzak
# Termination of the Bellman-Ford algorithm in asynchronous distributed model

(Asked by: username_0 on 2013-08-21)

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?

**Tags:** ds.algorithms, graph-algorithms, dc.distributed-comp
> **Comments:**
> **username_1**: 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?  
> **username_0**: @VolkerTurau yes  

---

## 1 answers

### Answer by username_0 on 2013-09-25. Score: 1

I found the answer. The [alpha synchronizer](http://en.wikipedia.org/wiki/Synchronizer_%28algorithm%29) will do it.

Here is the full paper: [Baruch Awerbuch (1985). Complexity of Network Synchronization](http://www.cs.uiowa.edu/~ghosh/synchronizer.pdf)


---

