Networks That Fix Themselves Aka Self-healing Networks

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.

Brief bio:

Amitabh Trehan is a postdoc with the information systems group at the faculty of Industrial Engineering at Technion, Haifa, Israel. At Technion, he works with Profs. Shay Kutten and Ron Lavi on distributed systems and game theory. Before Technion, he was a postdoc with  Prof. Valerie King (at UVIC, Canada). His Ph.D. Advisor was Prof. Jared Saia (University of New Mexico, USA) with whom he worked on algorithms for self-healing networks. His broad research interests are in theory and algorithms with specific interests in distributed algorithms, networks, and game theory. His interest includes designing efficient distributed algorithms for robustness/self-healing/self-* properties in systems under adversarial attack, and studying game theoretic and other mechanisms for evolving networks, such as social networks or distributed systems (P2P networks etc).