Responsive Algorithms for Defending Recon gurable Networks

We present algorithms to self-heal reconfigurable networks when they are under attack. These algorithms reconfigure the network during attack to protect two critical invariants. First, they insure that the network remains connected. Second, they insure that no node increases its degree by more than O(log n). We show both theoretically and empirically that our algorithms can successfully maintain these invariants even for large networks under massive attack by a computationally unbounded adversary