Picking Up the Pieces: Self-Healing in Reconfigurable Networks

The authors consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Their goal is to maintain connectivity in these networks, even in the presence of repeated adversarial node deletion, by carefully adding edges after each attack. They present a new algorithm, DASH, that provably ensures that: the network stays connected even if an adversary deletes up to all nodes in the network; and no node ever increases its degree by more than 2 log n, where n is the number of nodes initially in the network.