Picking up the Pieces: Self-Healing in reconfigurable networks

Jared Saia, Amitabh Trehan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationParallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1-12
Number of pages12
ISBN (Electronic)978-1-4244-1694-3
ISBN (Print)978-1-4244-1693-6
DOIs
Publication statusPublished - 2008
EventIPDPS 2008. IEEE International Symposium on Parallel and Distributed Processing, 2008. - Miami, FL, United States
Duration: 14 Apr 200818 Apr 2008

Conference

ConferenceIPDPS 2008. IEEE International Symposium on Parallel and Distributed Processing, 2008.
CountryUnited States
CityMiami, FL
Period14/04/200818/04/2008

Keywords

  • degree based self-healing
  • network attack
  • network connectivity
  • network topology
  • reconfigurable network
  • power-law graph

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Picking up the Pieces: Self-Healing in reconfigurable networks'. Together they form a unique fingerprint.

Cite this