COSHER: journal paper published


The final version of the paper Compact Routing Messages in Self-Healing Trees has now been published in the journal Theoretical Computer Science. The paper is now available at the following link: till February 07, 2018 without any registration or fees ūüôā (Thanks, Elsevier!).


A week in Bergen!

…to try to fix a marriage between distributed computing and parametrised complexity!

uib H√łyteknologisenteret: Unfortunately it is not at all as sunny in the picture (rain, rain everywhere!) ūüėČ


This is ‘working day’ 2 of my week in Bergen! I was delighted to be invited by the incredible Saket Saurabh to visit their world leading research department. The aim of this week is for me to give a series of lectures (one per day (1.5 hrs)! – I am hoping that my new postdoc Jonas Lefevre will take one for me ūüėČ on distributed computing with the aim to find intersections and possible¬† influences between distributed algorithms and parametrized complexity. I hope I have only a fraction of the energy that Saket has in managing his 12+ PhD students and postdocs ūüôā

It’s exciting being here and looking forward to a really productive week!




PhD studentship in algorithms/theory available again!

Funded PhD studentship in algorithms/theory at

A PhD studentship similar in description to the one advertised earlier is available. The application deadline is rather short: July 3rd! Details and an application link are available at

We seek candidates with strong interest in and willing to explore topics from, but not restricted to the following:  i) Graph algorithms and theory, ii) Self-healing, byzantine and other forms of resilient algorithms, iii) Compact routing and memory limited algorithms, iv) Static and dynamic Leader election and consensus, v) Connections between distributed algorithms and research areas such as parameterised complexity, topology, combinatorics, communication complexity, spectral, algebraic tools, vi) Algorithmic game theory and decision making, vi) Modelling and application to modern networks such as IOT and SDN.

The successful candidate will work closely with active research groups centred around both CS theory and networks. In particular, the candidate can benefit from interaction with upcoming research on compact self-healing routing algorithms supported by EPSRC (EPSRC research grant EP/P021247/1).

Postdoc position: now accepting applications

Advertisement for postdoc position for working on distributed algorithms under the EPSRC project COSHER is now live at

Below is the message I have sent out to a few mailing lists!

Here are some related blog posts on this same blog related to the opening and the research:

Postdoc in distributed algorithms required

My exciting EPSRC first grant!

Belfast to Mexico City via Self-healing Compact Routing!


Applications are invited for a postdoctoral research associate position in the area of distributed algorithms in the research group of Dr. Amitabh Trehan at Loughborough University Computer Science.

The position is funded by an EPSRC first grant to work on an exciting new project called COSHER:  Compact Self-healing Routing (COSHER) (RCUK link) that aims to combine research on compact routing with resilience (self-healing) using the standard message-passing modelling of networks (as graphs) and mathematical analysis of proposed algorithms. The position is for a one-year fixed term in the present instance providing a competitive 12 month salary with standard benefits.  The expected start date is Fall 2017 (Available to begin as early as July 1, 2017).

The successful candidate should have a PhD in Computer Science, mathematics or related disciplines with knowledge and understanding of algorithms and CS theory and/or networks. Experience in designing distributed/network algorithms is highly desirable.


More details and a link to the application is available at

The application deadline is June 1st, 2017.

The (online) application should include (1) Education details, (2) Supporting information in the form of a brief cover letter and research interest statement, (3) Names and contact information of three referees, (4) CV and publications list.

Informal enquiries should be made to Dr. Amitabh Trehan by email at or by telephone on +44 (0)1509 222564.

Please also refer to the blog for more pointers on the research.

Dr. Amitabh Trehan
Computer Sciece
Loughborough University
Loughborough, England.

My exciting EPSRC first grant!

COSHER: Compact Self-Healing Routing at the RCUK portal:

When I moved to Loughborough in February, I got one of the best gifts possible. In my first week here, I got the news that I had been awarded an EPSRC first grant. I had applied the grant while I was at Queen’s University Belfast – in fact, physically, I was in an AirBnB rental in Coycocan, Mexico city (as a visitor to UNAM for a Newton fund grant) when I had sent in the application. It was a stressful process, a stressful about three years procrastinating and agonising over the content and language. The primary reason being that you have only one shot at the ‘first grant’.

Anyways, it came through (hurrah!). Once you have been through one of these submissions, you discover this amazing maze of systems that bestow upon you the resources to help you conduct research!! You get to add a number of new keywords to your dictionary.

In brief, what happens is that you submit your application on the Je-S system with a number of documents after you have agonised, procrastinated, discussed, debated, tried to get industry support (or decide not to get, as in my case), written, re-written, accidentally deleted the whole application (as in my case on the eve of submission), got the application re-instated by calling somebody in charge etc etc… Then, the documents (and by extension, your career) passes through the hands of expert reviewers whose advice goes before a panel (which meet a few times a year). One fine (or horrible) day all is revealed – as in my case in the EPSRC ICT Prioritastion panel Jan 2017. As one can see, there are a number of different grants considered – the first grant seems to have a better chance being of relatively smaller value and of lower expectations than, say, the standard grants. In my panel, it seems 6 out of the 7 first grant applicants made it while only 4 out of 12 standard grants did. Sometimes, it can be far worse!

At the end of it all, Research Council UK (RCUK)’s nice sounding Gateway to Research¬† gives you a listing as a Principal Investigator and your successful project gets its own page and its own life! – Well, the real life for my project begins from July 1st when the money comes in and the expectations begin.


Postdoc in distributed algorithms required

A postdoc position to work with me on an EPSRC research project at Loughborough University is available from July 2017.

I have a position for a 1 year (in the first instance) postdoctoral research associate to work with me at Loughborough University. The position, supported by the EPSRC first grant COSHER (Compact Self-Healing Routing), comes with a good salary (in the UK system) and other perks and trainings. The project is available here at the RCUK gateway. The related research question is described in my earlier post here.

The earliest (and expected) start date is July 1st, 2017, but a later start date may be possible. The formal advertisement will be out in the coming week but please get in touch with me for more details!

The best leader election in the world!

As the world watches with intense interest the quadrennial spectacle of the US presidential election and the endless sparring and debating, we discuss the most efficient way to elect a leader!

Television viewers are getting ready for another¬†Trumpillary debate. The media has been licking its lips at skyrocketing TRP ratings supported by all the sparring and salacious stories. Since I’ve now got you here like those media channels, possibly against your will, let me tell you that this post is about electing a leader in a distributed network and is in, all likelihood, going to be much more boring than the US presidential election. This is not surprising at all, since the candidates in the distributed network are all honest, non-malicious, ¬†rational, ‘think’ in exactly the same manner, and really and truly interested in electing the best candidate!

Moreover, their ¬†desirability/’fitness’ is immediately comparable (e.g. given by a unique ID such as a mac address). Unfortunately, for the Trump(H)illary contest ¬†this would be like ¬†looking at the following picture and assiming the hand mudras define the candidates telling who will win e.g. will¬†Trump’s Gyan mudra¬†(i.e. knowledge hand gesture, which looks like F in the one hand sign language) trump Hillary’s¬†Abhay mudra? (i.e. Fearlessness hand gesture, hmm, I hope you already see the contradictions!).

Clinton and Trump try to win using hand mudras? (from

OK, now to the technical part of this post. Leader Election is one of the most fundamental problems in distributed systems. The idea is simply to select one of the nodes in the network as a leader and let it solve the critical problem of the day and then just convey the solution to the rest of the network. Electing a leader can often be the first step in many systems and was formally introduced as a rigorous problem in the context of token ring networks by Le Lann (1977).

We were fortunate to derive some very interesting results for this classic problem in the past few years. This is in the form of the following two papers –

The first paper has some very interesting lower bounds (which were assumed to be folklore but never proven). One aim of the paper was to achieve algorithms which can meet the lower bounds- that is leader election algorithms for arbitrary topologies must need O(diameter) time and O(#edges) messages simulteneously. Algorithms which meet either O(diameter) time or O(#edges) messages ignoring the other parameter have been long known but achieving both simultaneously has been very challenging. The paper has randomised algorithms which (almost) achieve that. The paper also has what we consider the best determinisitic leader election algorithm in terms of achieiving both parameters simultaneously. The result is an O(D.logn) time and O(m.logn) messages algorithm called The Double-Win Growing Kingdom Algorithm (Here, D: diameter, n: #nodes, m:#edges). Yes, it is more bloody than Game of Thrones! (Imdb rating; 9/5/10, wow).

I tell the high level idea and show some (almost) cool animations by one of my students. Our algorithm turned out to be similiar to Abu-Amara and Kanevsky’s (ICCI 1993) algorithm which they erroneously thought to work in O(D) time and O(m + log n) messages. Here is an informal outline of the algorithm:

(Note that the network here is depicted as a graph with the computers/agents as nodes and interconnections between them as edges. The agents can only communicate by sending messages to their neighbours along these edges. So, we are designing a graph theoretical algorithm.)

Initially every node (each with a unique ID) in the network wants to be a leader i.e. is a candidate and begins with radius=1. Ultimately, the node with the highest ID will win. Each node tries to win over other nodes and expand their kingdom by conquering other nodes! The algorithm terminates when the sole candidate left cannot grow its kingdom anymore.

In each round, for each node:

  1. If candidate, double your radius of conquest and broadcast conquest messages over this radius (i.e. ask neighbours to forward the message)
  2. If you get a message from a higher ranked node than you, drop out and join that node’s kingdom!
  3. Collision: You get hit by messages from multiple candidates. Choose the highest rank one and join its kingdom. Do not further the winner messages!
  4. Inform the winners of their boundary of conquest by sending back acknowledegments of victory along the path the conquest messages came (actually, a broadcast tree)

… and so on…

The above idea is fairly straightforward but the main challenge is to keep the messages and time low РI am skipping the technical details except mentioning that each round in itself has four phases. This shows up in the following cool simulations done by my student Christopher (Thanks Christopher!):


The ideal algorithm will be O(D) time + O(m) messages – there is a substantial gap here:

  • Can a determistic algorithm achieve these bounds or get closer to it than the Double-Win Growing Kingdom¬†algorithm?
  • Is there a better lower bound than O(D) time + O(m) messages? i.e. Is the problem even more difficult than we think?