Seminar by Amitabh Trehan
Networks that fix themselves aka Selfhealing networks
Amitabh Trehan
Technion, Haifa, Israel
Date: Friday, November 9th, 2012
Time: 5PM
Venue: CS101.Abstract:
Given a connected graph, two players play a turn-based game: First. the red guy removes a node (and therefore, its adjoining edges too), now the blue guy adds edges between the remaining nodes. What edges should the blue guy add so that over a whole run of the game, the network remains connected, no node gets too many new edges and the distance between any pair of nodes (i.e. the network stretch) does not blow up by much? Now, imagine that the nodes in the graph are computers and the graph is a distributed network; the nodes themselves are the blue guys but they do not know anybody beyond the nodes they share an edge with. Solving such problems is the essence of self-healing distributed networks.
We shall present the distributed self-healing model which is especially applicable to reconfigurable networks such as peer-to-peer and wireless mesh networks and present fully distributed algorithms that can 'heal' certain global and topological properties using only local information. Forgiving Graph [PODC 2009; DC 2012] uses a 'virtual graphs' approach maintaining connectivity, low degree increase and closeness of nodes (i.e. stretch). Xheal [PODC 2011; Xheal : localized self-healing using expanders] further maintains expansion and spectral properties of the network. We present a full distributed implementation in the LOCAL message passing model. However, we are working on ideas to allow even more efficient implementations and stronger guarantees.