Amitabh Trehan is an Associate Professor at Durham University Computer Science.  Amitabh’s research focuses on Computer Science theory and algorithms specially aligned towards networks and distributed computing. At Durham, he heads the NESTiD (Network Engineering, Science, and Theory in Durham) research group. 

He is a recipient of fellowships such as the the Royal Society International Exchange (with Michael Elkin, Ben Gurion University), DUO-India Professor fellowship (with Sushanta Karmarkar, IIT Guhawati), the Royal Society Newton Incoming fellowship, the I-CORE (Israeli-Centers of Research Excellence) fellowship, the UNM Dean’s Doctoral fellowship etc.

He has also been a PI/Co-PI/CO-I on various grants inclduing the EPSRC First Grant, EPSRC Standard grant(s),  EU H2020 FET grant, Newton fund and London Maths Society starting grants (for visiting UNAM, Mexico and Koc University, Turkey respectively). He has won various other awards and honours (including best paper awards).

Previously, he was an Assistant Professor (i.e. Lecturer  in the UK system) at Loughborough University and at Queen’s University Belfast.

Research Areas and Projects

Amitabh’s main research interests center around designing efficient algorithms and reasoning about multi-agent dynamic scenarios. This has led to work on distributed algorithms in static scenarios (e.g. Leader Election), but particularly on dynamic scenarios for a line of work called Self-Healing algorithms. His general field of interest is Theoretical Computer Science. Amitabh also works in algorithmic game theory and actively explores the interconnections between distributed computing, game theory and also other computation models in Theoretical Computer Science. Though his tools are theoretical and mathematical, he often seeks inspiration from and applications in the exciting worlds of, for example, Internet of Things, Peer-to-Peer Networks, Social Networks and their implications, Security and Resilience, Software Defined Networking,  and Large Scale Networks.

Some current or recent research topics:

  • Compact (Low-Memory) resilience (COSHER) and distributed computing: This is an exciting area of research where we consider enhancing networks of low memory devices with resilience during distributed computation. For example, this may be useful for Internet of Things. Working with Prof. Danny Dolev (HUJI) and Dr. Armando Castaneda (UNAM, Mexico), we have devised the first Compact Self-Healing Routing solutions. Supported by The Newton Fund, Amitabh visited Mexico in the summer of 2016 to further pursue this project. Subsequently, the COSHER project is supported by an EPSRC first grant (with Dr. Jonas Lefevre as a postdoc).

  [Collaborators: Danny Dolev (HUJI), Armando Castaneda (UNAM, Mexico), Jonas Lefevre (Postdoc @ COSHER Project, Loughborough]

  • Peer to Peer Topology construction and maintenance: A large part of Amitabh’s research deals with this area. He is developing P2P maintenance algorithms to converge any arbitrary topology to a good topology in the CONGEST model (i.e. realistic message sizes) making the algorithms practical to implement hopefully.
  • Self-Healing:Self-healing is a specific resilience/fault-tolerant methodology we have investigated mainly for P2P topology maintenance (as mentioned before) but it need not be restricted to that. During Amitabh’s PhD,  a formal model of self-healing was developed which briefly described can be stated as follows:

An omniscient adaptive adversary attacks a network by deleting or adding a single node and the neighbours of the deleted node react by adding new connections in a distributed manner managing to maintain certain global properties over the whole run of attacks and repairs.

Over the years, Amitabh has been fortunate to work with a number of brilliant people on this topic.

 [Collaborators (along with previously listed):  Jared Saia(UNM), Tom Hayes(UNM), Navin Rustagi (UNM, now Baylor College of Medicine),  Gopal Pandurangan (Houston), Seth Gilbert (NUS), Peter Robinson (RHUL), Atish Das Sarma (Ebay Resarch)]

  • Leader Election: A simple problem to state with fascinating results, Leader Election is one of the most fundamental problems in distributed computing with immediate practical applications (being used in many industry protocols and systems). During Amitabh’s postdoc at Technion, working with collaborators, we revisited this classic problem and came up with two very interesting papers exploring the limits of randomized and deterministic, implicit and explicit leader elections. These papers proposed fundamental lower bounds and close to matching upper bounds.

  [Collaborators: Shay Kutten (Technion), David Peleg (Weizmann), Gopal Pandurangan(Houston), and Peter Robinson(RHUL)]

  • Byzantine Agreement: Resilience and Fault Tolerance can be thought of in terms of the power of the adversary the algorithm can handle. A byzantine adversary is one of the strongest which involve a set of nodes in the network which consciously aim to foil a distributed computation on the network. Byzantine agreement is the classic problem in this setting and a critical component for Blockchains and Cryptocurrency.

 [Collaborators: Valerie King(Victoria), Steven Lonargan(Victoria), Jared Saia(UNM)]

  • Edge-dynamic resilient ‘Self-Aware’ Distributed Estimation: How do nodes do distributed computing while there is dynamism/faults in the system? In the ‘edge-dynamic’ models, the edges of the graph change, the rate of which is the ‘churn’ of the system. We devised an algorithm for nodes to discover approximately the densest subgraph of the network and bieing `self-aware’ if they are part of that subgraph.

 [Collaborators: Danupon Nanangkoi (KTH), Atish Das-Sarma(Ebay Research), Ashwin Lall(Denison)]

  • Resilient Exascale Systems: As part of the EU H2020 project AllScale (https://www.researchgate.net/project/AllScale-Project),  Amitabh worked with colleagues at Queen’s University Belfast, towards designing futuristic resilient exascale high performance systems. Exascale systems are supposed to function at nearly the speed of the human brain and maybe contenders for ‘artificial intelligence’ in the future.

 [Collaborators: Dimitris Nikolopoulos (QUB), Charles Gillan (QUB) and Kiril Dichev (QUB)]

  • Resiiient (Self-healing) Software Defined Networks: Software Defined Networks is probably the most exciting concept in Networking at the moment (along with Internet of Things and Big data computation?). Amitabh’s proposal for Self-Healing Software Defined Networks won the prestigious Newton Incoming Fellowship to work at  Royal Holloway to further develop this idea. Amitabh has also been working with collaborators and students at QUB exploring facets of this idea.

 [Collaborators: Gregory Chockler (RHUL), Sandra Scott-Hayward (QUB)]

  • (Distributed) Algorithms Behind Biological Cell Communication: Here is my blog post on this.

 [Collaborators: Fred Currel (QUB)]


 Amitabh did his PhD in Computer Science with distinction from University of New Mexico with Prof. Jared Saia while also working closely with Prof. Tom Hayes.

Subsequently, he decided to increase his international frequent flyer miles doing postdocs (as is well known, these are the most fun times in an academic’s life):

Before going to the US, he did a M.Tech in Computer Applications from Indian institute of Technology Delhi, where he investigated natural languages and typesetting (LaTeX) with Prof. Wagish Shukla and Prof. Sanjiva Prasad (https://www.youtube.com/watch?v=PgZ9KaTCEPQ).

In Delhi, he also worked at Mahatma Gandhi International Hindi University, Sarai and NIIT.

He has a MCA from Indira Gandhi National Open University and a BSc Medical/Biology from DAV College, Punjab University. How and why he did all that and how he circumnavigated the Indian education system is probably the subject of a book in the future….