Edge-preserving self-healing: Keeping network backbones densely connected

A. Das Sarma, A. Trehan

Research output: Chapter in Book/Report/Conference proceedingChapter

10 Citations (Scopus)


Healing algorithms play a crucial part in distributed peer-to-peer networks where failures occur continuously and frequently. Whereas there are approaches for robustness that rely largely on built-in redundancy, we adopt a responsive approach that is more akin to that of biological networks e.g. the brain. The general goal of self-healing distributed graphs is to maintain certain network properties while recovering from failure quickly and making bounded alterations locally. Several self-healing algorithms have been suggested in the recent literature [IPDPS'08, PODC'08, PODC'09, PODC'11]; they heal various network properties while fulfilling competing requirements such as having low degree increase while maintaining connectivity, expansion and low stretch of the network. In this work, we augment the previous algorithms by adding the notion of edge-preserving self-healing which requires the healing algorithm to not delete any edges originally present or adversarialy inserted. This reflects the cost of adding additional edges but more importantly it immediately follows that edge preservation helps maintain any subgraph induced property that is monotonic, in particular important properties such as graph and subgraph densities. Density is an important network property and in certain distributed networks, maintaining it preserves high connectivity among certain subgraphs and backbones. We introduce a general model of self-healing, and introduce xheal+, an edge-preserving version of xheal[PODC'11].
Original languageEnglish
Title of host publicationProceedings - IEEE INFOCOM
Number of pages6
Publication statusPublished - 01 Jan 2012
EventNetSCiCom 2012, IEEE Infocomm 2012: Workshop on Network Science for Communication Networks. - Orlando, FL, United States
Duration: 30 Mar 201230 Mar 2012


ConferenceNetSCiCom 2012, IEEE Infocomm 2012: Workshop on Network Science for Communication Networks.
Country/TerritoryUnited States
CityOrlando, FL


Dive into the research topics of 'Edge-preserving self-healing: Keeping network backbones densely connected'. Together they form a unique fingerprint.

Cite this