The Taub Faculty of Computer Science Events and Talks

In this talk, we 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 fully distributed algorithms that 'heal' certain global and local properties while doing only local changes and using only local information.

Our model assumes repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. We shall cover briefly, either one or both of the following algorithms, as time permits:

Forgiving Graph [PODC 2009; The forgiving graph: a distributed data structure for low stretch under adversarial attack] preserves closeness of nodes i.e. network stretch after adversarial deletions or insertions, without increasing node degrees by more than a constant factor. It also introduces a simple but interesting mergable data structure called half-full tree and shows how to use it to implement the algorithm in the distributed setting.

Xheal [PODC 2011; Xheal: localized self-healing using expanders] 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 central idea is to reconnect nodes that have lost a neighbor by k-regular expanders while not allowing degrees to blow up.