Xheal: Localized Self-Healing Using Expanders

The authors consider the problem of self-healing in reconfigurable networks (e.g. peer-to-peer and wireless mesh networks) that are under repeated attack by an omniscient adversary and propose a fully distributed algorithm, Xheal that maintains good expansion and spectral properties of the network, also 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. They use a model similar to that used in recent work on self-healing. In their model, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network.

Provided by: Brown University Topic: Mobility Date Added: Apr 2011 Format: PDF

Find By Topic