LADC 2021 - Tutorials

The LADC Tutorial program is a forum for leading work on all aspects of dependability, security and resilience of systems and networks, covering both theory and experimental themes.

Tutorial: Self-healing Distributed Algorithms

Dr. Amitabh Trehan - Associate Professor at Durham University, U.K.

Monday November, 22nd 13:30-17:00 BRT


Abstract: Resilience and fault-tolerance are highly desirable properties for networks and often distributed algorithms are designed with this purpose in mind. Self-healing is one such fault-tolerance paradigm which seeks to maintain a desirable state of the system despite attack accepting only a short disruption. The concept of self-healing appears in various forms ranging from autonomic networks to practical networks to distributed algorithms. We look at the later setting formalising self-healing as a game on graphs where a powerful adversary deletes/inserts nodes and the network responds by adding/dropping edges locally in a distributed manner while seeking to maintain global invariants. This requires the network to be reconfigurable e.g. in the P2P-CONGEST model (with limited message sizes). We look at various results in this setting building up self-healing resilience by adding topological properties such as connectivity, diameter, stretch, expansion, and routing in a simultaneous manner.

Speaker Bio: Dr. Amitabh Trehan is Associate Professor at Durham University, UK. His broad research interests are in CS theory and algorithms, especially those arising from or applicable to real world and human engineered systems. He has specific interests in distributed algorithms, complexity, networks, graph theory, and game theory. Current work includes designing efficient distributed algorithms for robustness/self-healing/self-* properties in systems under attack from a computationally unbounded adversary, questions about algorithms in distributed and biological systems, and game theoretic and other mechanisms for evolving and dynamic networks, such as Peer-to-peer and social networks. He is a fellow of the UK Higher Education Academy (FHEA) and fulfill various teaching and administration roles including undergraduate final year project coordinator.

Tutorial Chairs

Armando Castañeda (UNAM, Mexico) armando.castaneda@im.unam.mx
Leonardo Montecchi (UNICAMP, Brazil) leonardo@ic.unicamp.br