Chennai Mathematical Institute

Seminars




10:30 a.m.
Self-healing distributed networks and data structures: Forgiving Graph and Xheal

Amitabh Trehan
Industrial Engineering at Technion, Haifa, Israel.
13-03-12


Abstract

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. He has earlier worked with Prof. Valerie King (at UVIC, Canada) on Byzantine Agreement, and his Ph.D. Advisor, Prof. Jared Saia (UNM, USA) on algorithms for self-healing networks.

His broad research interests are in theory and algorithms with specic 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).

Abstract
========

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.