[Colloquium] Tom Hayes (TTI-C) Talk

[Julia MacGlashan]

When:    Friday, May 9 @ 10:00am

Where:   TTI-C Conference Room, 1427 E. 60th St.

Who:     Tom Hayes, TTI-C

Topic:   The Forgiving Tree: A Distributed Algorithm for Self-Healing in
Reconfigurable Networks


We will study an abstract model for cascading node failures in enormous
graphs, motivated by examples such as the Skype network failure for two days
last August, or the California "electricity crisis" of 2000-2001.  In this
model, our algorithm will repeatedly respond to adversarial node deletions
by quickly adding a few new edges with the following goals:
  (1) maintain connectivity of the network
  (2) avoid large increases in node degrees (which might cause further
failures)
  (3) prevent large increases in the diameter of the network.
Here, by "quickly," (4) we allow the response time to depend on the degree
of the deleted node, but not on the size of the network.

I will describe a new algorithm, called the Forgiving Tree, which achieves
these goals.  Over the course of any sequence of node
deletions:
 (1) the network stays connected,
 (2) no node degree increases by more than a total of 3,
 (3) the diameter doesn't increase by more than log(max degree), and (4) the
responses require O(1) messages of size O(1) to be sent and received by each
neighbor of the deleted node (these nodes and their neighbors are the only
ones involved in the self-healing step).

Our result has several advantages over more traditional approaches.
 (1) rather than *designing* a network which is robust to node failures,
which typically requires a lot more edges, in our setting, we start out with
any network topology, and preserve it as well as we can.
 (2) since there is no centralized control of the healing process, it can
proceed much faster.
 (3) our bounds apply to adversarial sequences of node failures, rather
than, e.g., random node failures.

Joint work with Navin Rustagi, Jared Saia and Amitabh Trehan


Contact:     Tom Hayes, TTI-C     hayest at tti-c.org     834-3485