This work is devoted to the problem of spanning trees maintenance in the presence of crash failures in a distributed environment using only local knowledge. Using a pre-constructed spanning tree of a k-connected graph, we present a protocol to maintain a spanning tree in the presence of k-1 consecutive failures. The contribution of this paper is threefold. First, the problem is formalized as an occurrence of Menger's theorem in a distributed setting. The second result shows an implementation of the protocol which is composed of a set of modules encoded using a graph relabeling systems model. The last contribution is the implementation of this protocol in the asynchronous message passing model. For a given graph G =(V,E), where M is the number of its edges, N is the number of its nodes, and Δ is its degree; After each failure occurrence, our algorithms need the following requirements: The first one uses O(Δ × N) steps and O(Δ) bits per node. The second one uses O(N+M) messages and O(N) time and O(Δ) bits per node. In addition, we investigate the possible specification and verification of the presented algorithm using Alloy as a tooled formal language.

Additional Metadata
Keywords Distributed computing, Failure detectors, Fault tolerance, Graph relabeling systems, Local computations, Maintenance, Spanning tree, Vertex connectivity
Persistent URL dx.doi.org/10.1109/PRDC47002.2019.00052
Conference 24th IEEE Pacific Rim International Symposium on Dependable Computing, PRDC 2019
Citation
Hamid, B. (Brahim), Rouland, Q. (Quentin), & Jaskolka, J. (2019). Distributed maintenance of a spanning tree of k-connected graphs. In Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC (pp. 217–226). doi:10.1109/PRDC47002.2019.00052