News Archives

  • UNM
  • >Home
  • >News
  • >2012
  • >April
  • >[Colloquium] How should computers fix themselves? or Self-healing distributed networks

[Colloquium] How should computers fix themselves? or Self-healing distributed networks

April 3, 2012

Watch Colloquium: 

M4V file (640 MB)

  • Date: Tuesday, April 3, 2012 
  • Time: 11:00 am — 12:15 pm 
  • Place: Mechanical Engineering 218

Amitabh Trehan
Technion, Haifa, Israel

Consider a simple turn based game between an attacker and a defender (you) playing on a large connected graph: In her turn, the attacker deletes a node and in your turn you are supposed to connect all the neighbors of the deleted node so that somehow at any point in the game, no node has increased its degree by more than a constant nor has the diameter of the network blown up. Now, consider that the nodes themselves are smart computers or agents and do not know anything about their network other than their ‘nearby’ nodes and have no centralized help; In essence they have to maintain certain local and global properties by only local actions while under attack from a powerful adversary.

The above game captures the essence of distributed self-healing in reconfigurable networks (e.g. peer-to-peer, ad-hoc and wireless mesh networks etc). Many such challenging and interesting scenarios arise in this context. We will look at some of these scenarios and at our small but rich and evolving body of work. Our algorithms simultaneously maintain a subset of network properties such as connectivity, degree, diameter, stretch, subgraph density, expansion and spectral properties. Some of our work uses the idea of virtual graphs – graphs consisting of ‘virtual’ nodes simulated by the real nodes, an idea that we will look at in more detail.

 

Bio: Amitabh Trehan is a postdoc at Technion, Haifa, Israel. There, he works with Profs. Shay Kutten and Ron Lavi on distributed algorithms and game theory. He has earlier also worked as a postdoc with Prof. Valerie King (at UVIC, Canada). He did his Ph.D. with Prof. Jared Saia at UNM 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).