The first fully polynomial stabilizing algorithm for BFS tree construction (Q2272977)

The paper introduces a new class of distributed algorithms for constructing a spanning tree and characterized by a round complexity polynomial on the network diameter and a step complexity polynomial on the network size, namely fully polynomial algorithms. Moreover, an example of such algorithm is provided for constructing a BFS tree under a distributed daemon; the BFS tree construction is based on a snap-stabilizing algorithm. The new class of distributed algorithms is particularly suitable in the context of large scale networks, while the algorithms allow to have an execution with a high degree of parallelism, while the communication complexity is bounded.