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

Advertisements