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.