Distributed Calculation of Edge-Disjoint Spanning Trees for Robustifying Distributed Algorithms Against Man-in-the-Middle Attacks

In this paper, we provide a distributed methodology to allow a network of agents, tasked to execute a distributed algorithm, to overcome Man-in-the-Middle (MITM) attacks that aim at steering the result of the algorithm toward inconsistent values or dangerous configurations. We want the agents to be able to restore the correct result of the algorithm despite the attacks. To this end, we provide a distributed algorithm to let the set of agents, interconnected by an undirected network topology, construct several edge-disjoint spanning trees by assigning labels to their incident edges. The ultimate objective is to use these spanning trees to run multiple instances of the same distributed algorithm in parallel, in order to detect MITM attacks or other faulty or malicious link behavior (e.g., when the instances yield different results) and to restore the correct result (when the majority of instances is unaffected). The proposed algorithm is lightweight and asynchronous, and is based on iterated depth-first visits on the graph. We complement this paper with a thorough analysis of the performance of the proposed algorithms.