Picking up the Pieces: Self-Healing in Reconfigurable Networks

Details Picking up the Pieces: Self-Healing in Reconfigurable Networks Picking up the Pieces: Self-Healing in Reconfigurable Networks

2008-01-24

arxiv.org/abs/0801.3710v1

Computer Science

Data Structures and Algorithms

To be presented at IPDPS (IEEE International Parallel & Distributed Processing Symposium) 2008

Scientific paper

We consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Our goal is to maintain connectivity in these networks, even in the presence of repeated adversarial node deletion, by carefully adding edges after each attack. We present a new algorithm, DASH, that provably ensures that: 1) the network stays connected even if an adversary deletes up to all nodes in the network; and 2) no node ever increases its degree by more than 2 log n, where n is the number of nodes initially in the network. DASH is fully distributed; adds new edges only among neighbors of deleted nodes; and has average latency and bandwidth costs that are at most logarithmic in n. DASH has these properties irrespective of the topology of the initial network, and is thus orthogonal and complementary to traditional topology-based approaches to defending against attack. We also prove lower-bounds showing that DASH is asymptotically optimal in terms of minimizing maximum degree increase over multiple attacks. Finally, we present empirical results on power-law graphs that show that DASH performs well in practice, and that it significantly outperforms naive algorithms in reducing maximum degree increase. We also present empirical results on performance of our algorithms and a new heuristic with regard to stretch (increase in shortest path lengths).

Affiliated with

Also associated with

No associations

Rating

Picking up the Pieces: Self-Healing in Reconfigurable Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Picking up the Pieces: Self-Healing in Reconfigurable Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Picking up the Pieces: Self-Healing in Reconfigurable Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-282985