[Nets-seminars] SSE Seminar: The Forgiving Tree: towards self-healing networks

[Franco Raimondi]

Dear All,
the following seminar may be of interest to people outside the SSE group.

Monday, 15th of December, 12-1pm in Room 6.12
Speaker: Amitabh Trehan (University of New Mexico, Albuquerque, USA)
Title: The Forgiving Tree: towards self-healing networks

Abstract:
Can systems continue when their components fail? Can nodes in a
network reorganize themselves to offset the damage caused by a malicious
adversary? Will your skype work after the next windows update? In this
talk, I will try to address these profound questions (in a rather
specific context).
Consider the problem of self-healing in peer-to-peer networks that are
under repeated attack by an omniscient adversary, where  the following
process continues for up to n rounds where n is the total number of
nodes initially in the network: the adversary deletes an arbitrary node
from the network, then the network responds by quickly adding a small
number of new edges.

I will present a distributed data structure that ensures two key
properties.  First, the diameter of the network is never more than O(log
Delta) times its original diameter, where Delta is the maximum degree of
the network initially.  Note that for many peer-to-peer systems, Delta
is polylogarithmic, so the diameter increase would be a O(log log n)
multiplicative factor.  Second,
the degree of any node never increases by more than 3 over its original
degree.  The data structure is fully distributed, has O(1) latency per
round and requires each node to send and receive O(1) messages per
round.  The data structure requires an initial setup phase that has
latency equal to the diameter of the original network, and requires,
with high probability, each node v to send O(log n) messages along every
edge incident to v.  This approach is orthogonal
and complementary to traditional topology-based approaches to defending
against attack.

References:
  - The Forgiving Tree: A Self-Healing Distributed Data Structure by Tom
Hayes, Navin Rustagi, Jared Saia and Amitabh Trehan. PODC (Principles of
Distributed Computing), 2008 (http://arxiv.org/abs/0802.3267,
http://portal.acm.org/citation.cfm?id=1400751.1400779)
- Picking up the Pieces: Self-Healing in Reconfigurable Networks, by
Jared Saia and Amitabh Trehan. / IEEE International Parallel and
Distributed Processing Symposium, 2008. (http://arxiv.org/abs/0801.3710,
/http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4536326)

Short Bio:
  Amitabh Trehan is a PhD candidate in the department of Computer Science
at the University of New Mexico, Albuquerque, USA. He is advised by Prof
Jared Saia.  They have been working on developing distributed algorithms
for self-healing in computer networks. More recently, they have  been
dabbling in game theory, and working in Europe!
  http://www.cs.unm.edu/~amitabh