Computer Science

News and events

17 March 2017

COSHER: Compact Self-Healing Routing Algorithms

Presented By Dr Amitabh Trehan, Lecturer, Department of Computer Science, Loughborough University
  • 1.30pm
  • N.1.12, Haslegrave Building

About this event

Abstract: 

The world is getting connected, and fast. Networks are blooming and the near future will see not just computer boxes but almost any thing you may come across in your day connected and ‘talking’ to each other. For example, the Internet of Things will see billions of connected devices of low memory.  Moreover,  more and more critical computations will be performed on large scale distributed networks and clouds. Reliability and resilience to failures is going to be ever more important in such scenarios. Our work on self-healing topologies that can be maintained despite node failures and node insertions provide one such set of solutions. 

Modelling networks as graphs and mathematically analysing distributed algorithms, in recent work [ICDCN 2016], we address the question of maintaining ‘computations’ over self-healing networks of low memory nodes. In particular, we show how to do compact (i.e. low memory) routing despite node failures. Moreover, our self-healing algorithm itself  is  ’compact’ and yields, to the best of our knowledge, the first self-healing compact routing scheme.  Previous compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013] had no means to tolerate failures, once the system has been setup and started. 

In this talk, I will briefly discuss our results on self-healing topology maintenance and compact self-healing routing. This research also forms the basis of a recently awarded EPSRC first grant.