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

[Franco Raimondi]

Dear All,
this is in 15 minutes.

Franco


> 
> 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
>