Brief Announcement: Self-healing Algorithms for Reconfigurable Networks

摘要

We present an algorithm to self-heal reconfigurable networks. This algorithm reconfigures the network during an attack to protect two critical invariants. First, it insures that the network remains connected. Second, it insures that no node increases its degree by more than O(log n). We prove that our algorithm can successfully maintain these invariants even for large networks under massive attack by a computationally unbounded adversary.