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.

Distributed computing, Failure detectors, Fault tolerance, Graph relabeling systems, Local computations, Maintenance, Spanning tree, Vertex connectivity
24th IEEE Pacific Rim International Symposium on Dependable Computing, PRDC 2019
Department of Systems and Computer Engineering

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