Shadow Banning in Directed Graphs for Fault-Tolerant Averaging

We consider the problem of average consensus in a distributed system wherein a subset of the nodes comprising the system becomes faulty. To address this problem, we rely on a class of averaging algorithms whereby each node maintains a collection of variables, which it iteratively updates as a linear combination of other variables received by the node from its in-neighbors, i.e., nodes from which it receives information directly. Algorithms within this class exhibit, throughout their execution, certain invariance properties that are local to each node and reflect the conservation of certain quantities capturing an aggregate of all the values received by a node from its in-neighbors and all the values sent by said node to its out-neighbors, i.e., nodes that receive its information directly. In this paper, we exploit one such invariance property to enable each node to check whether or not any of its in-neighbors becomes faulty during the execution of the algorithm. In addition, we provide a shadow-banning mechanism to remove faulty nodes from the execution, and nullify the information they have broadcast up to the time when they were declared faulty.