Space efficient and time optimal distributed BFS tree construction

In this paper, we give a simple distributed algorithm for constructing a BFS spanning tree in an almost anonymous, asynchronous, rooted network. The proposed algorithm is an improved version of an algorithm by Aspnes. The time complexity of the algorithm is optimal for this problem, i.e., O(diam), where diam is the diameter of the network, and the space complexity of each process is O(δP) for each process P, where δP is the degree of P. The message complexity is O(diam⋅|E|), where E is the set of links, and the size of each message is O(1).