June 20, Wednesday 14:15, Room 303, Jacobs Building
Title: Distributed Algorithms for Self-healing Networks
Lecturer:
Amitabh Trehan
Lecturer homepage
: http://www.cs.unm.edu/~amitabh/
Affiliation : Technion
In this presentation, 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.