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!

Funded PhD studentship in Graph Algorithms/Distributed Algorithms/Dynamic graphs

This slideshow requires JavaScript.

 

I am on the look out for an outstanding PhD student. Here is the advert! I will also be advertising soon for a postdoc position as I seek to grow my algorithms/distributed algorithms research group. The student will have the chance to work in the dynamic and fast growing Loughborough CS and one of the best campuses to be a student in the UK. For more on Lufbra, see my previous post.

In brief, you may create the next cutting edge graph algorithm for resilient networks or solve an open problem in graph theory! (..and add a figure from your research to those above!)

Here’s a more formal description of what I envisage the student could undertake (with guidance from me and my outstanding colleagues at Loughborough CS):

This project seeks to design and mathematically analyse distributed graph algorithms with an emphasis on resilience and dynamic scenarios and, in general, to explore decentralisation. Networks are pervasive and diverse and, with the upcoming Internet of Things, likely to be deeply integrated into our society. Networks often rely upon distributed protocols for their functioning. Failure of components and security also makes resilience a critical issue. Distributed graph algorithms allow us to model, explore and design solutions for all kinds of networks.

We seek candidates who have strong interest in and are willing to explore topics in this domain from, but not limited to the following: i) Self-healing, byzantine and other forms of resilient algorithms, ii) Compact routing and memory limited algorithms, iii) Static and dynamic Leader election and consensus, iv) Techniques such as topology, spectral and algebraic tools and communication complexity, v) Game theory applied to distributed algorithms and decision making, vi) Modelling and application to modern networks such as IOT and SDN.

Please apply via jobs.ac.uk at the link: http://www.jobs.ac.uk/job/AYE112/phd-studentship-distributed-and-resilient-graph-algorithms/  – the opening is fully funded for UK/EU students with a comfortable stipend, and is open for international (Non-EU) but the stipend will unfortunately be adjusted towards the higher international fees to begin with!

I have moved to Lufbra!

In February, I moved to the department of Computer Science at Loughborough University (called Lufbra or Lboro or other variants, in short) after spending more than three years at Queen’s University Belfast. I am pretty excited about the move and got a really nice welcome with the news of  the award of an EPSRC first grant in my first week here (more on that later). The department has a good mixture of systems and theory and, heartingly, sits in the School of Science (along with Maths and Physics, the right place I feel for CS – Djikstra would have it rather called Computing Science). I will work most closely with the Theory and Networks groups but, in fact, with anybody who’s willing to go to lunch or coffee with me (speaking of which, we have a nice communal and very active Nespresso machine)!

This slideshow requires JavaScript.

Though recent years and, let’s say, world events, have made me wary about news and rankings, this is the right time to brag about Lufbra – top 5  in the Guardian league tables, top 10 in complete University Guide and other rankings (more here), and #1 in student satisfaction rankings.  But what Lufbra is really legendary for is its sports (with alumni like Sebastian Coe and Paula Radcliffe) with it recently been crowned the best sports university in the world. Sports is everywhere on one of the largest closed campuses in the UK with many national and olympic facilities based here. Even more exciting for me is that the  English and Wales Cricket board national cricket performance centre is outside my window and also one of the two international standard cricket grounds on campus! We, at Computer Science have even graduated some test cricketers like Monty Panesar (nice article here on Monty’s story). There will be lot of nice cricket to watch from work over summer 😉

When I was a kid, I  wanted to be a Scientist and a Cricketer (let’s say, I have had moderate success in both ventures) – now, in my office, I’ll be a scientist and watch cricketers!

From 2016: My lectures on TOC (Maths Background)

In the last quarter of 2016, I was co-teaching Theory of Computation to year 2 Undergrads – to a large class of about 150 students. This was challenge in itself but strongly compounded by the fact that not all CS students at QUB come with A level maths background!

I spent the first five weeks giving a ‘fun’ (hopefully) intoduction to the maths background needed for TOC while intoducing many interesting and thought provoking challenges this subject provokes. The slides are at my website:

 http://www.amitabhtrehan.net/teaching.html

For All. Happy new year 2017! Surely There Exists better things next year!

My report on BCTCS 2016

My report on BCTCS 2016 held in Belfast from March 22nd to 24th at Belfast (QUB) is available at the bulletin of EATCS.

The 32nd British Colloquium of Theoretical Computer Science was held at Queen’s University Belfast from March 22nd to 24th, 2016. Here is my earlier blog post on the event.

I just noticed that my official report on the event was publised in the  June  issue of BEATCS (Bulletin of the European Association for Theoretical Computer Science). Here is the report (click the PDF link on the page).

Here are some nice mug shots of the crazies 🙂 involved in BCTCS : Organising Committee

If you get the clues from the previous page: On to University of St. Andrews in 2017, and Royal Holloway University of London in 2018!

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!).

tdy_alexander_debate_160927-nbcnews-ux-1080-600
Clinton and Trump try to win using hand mudras? (from https://goo.gl/gRMsQt)

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!):

Questions:

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?