Xheal: A localized self-healing algorithm using expanders

Gopal Pandurangan, Amitabh Trehan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


We consider the problem of self-healing in reconfigurable networks e.g., peer-to-peer and wireless mesh networks. For such networks under repeated attack by an omniscient adversary, we propose a fully distributed algorithm, Xheal, that maintains good expansion and spectral properties of the network, while keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. The algorithm heals global properties like expansion and stretch while only doing local changes and using only local information. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Xheal has low amortized latency and bandwidth requirements. Our work improves over the self-healing algorithms Forgiving tree [PODC 2008] andForgiving graph [PODC 2009] in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network.
Original languageEnglish
Pages (from-to)39-54
Number of pages16
JournalDistributed Computing
Issue number1
Early online date16 Jun 2013
Publication statusPublished - 01 Feb 2014


  • Distributed algorithm
  • Expansion
  • Local versus global
  • Peer-to-peer
  • Randomized algorithm
  • Reconfigurable networks
  • Self-healing
  • Spectral properties

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Theoretical Computer Science


Dive into the research topics of 'Xheal: A localized self-healing algorithm using expanders'. Together they form a unique fingerprint.

Cite this