A SELF-STABILIZING DISTRIBUTED ALGORITHM TO CONSTRUCT BFS SPANNING TREES OF A SYMMETRIC GRAPH
S. Sur, Pradip K. Srimani · Parallel Processing Letters · 1992
We propose a simple and efficient self-stabilizing distributed algorithm to construct the breadth first search (BFS) spanning tree of an arbitrary connected symmetric graph. We develop a completely new direct approach of graph theoretical reasoning to prove the correctness of our algorithm. The approach seems to have potential to have applications in proving correctness of other self-stabilizing algorithms for graph theoretical problems.