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

Advertisements

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!

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

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.

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.

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.

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!

Author Cathy O’Neil (The mathbabe!) in her book Weapons of Math Destruction (What a name!) states that we should remember that predictive models and algorithms are really just “opinions embedded in math.” Well said, indeed. After all, maths is annother language – a very powerful one for emotionless, ‘logical’ calculus though.

Maybe time for all to take the Modeler’s Hippocratic Oath (Derman and Wilmott):

–I will remember that I didn’t make the world, and it doesn’t satisfy my equations.

∼ Though I will use models boldly to estimate value, I will not be overly impressed by mathematics.

∼ I will never sacrifice reality for elegance without explaining why I have done so.

∼ Nor will I give the people who use my model false comfort about its accuracy. Instead, I will make explicit its assumptions and oversights.

∼ I understand that my work may have enormous effects on society and the economy, many of them beyond my comprehension.

Thanks to the Newton Fund and the Mexican Academy of Science (AMS) I get to spend six weeks in Mexico city visiting my colleague at UNAM, researching, what else but Compact Self-Healing Routing… and authentic Mexican food 😉

The first part of this post is by way of thanks to the Newton Fund , the UK academies (say, The Royal Society) and the Mexican Academy of Sciences (AMC) for a Newton mobility grant which will allow me to visit my colleague Armando Castaneda at UNAM for six weeks in August and September this year. The call funds upto three months of ‘foreign activity’ so I could have possibly asked for more time but I was unsure of being able to get away for so long. Armando managed to visit me at Belfast some time ago so this can be even thought of as a return visit! He even managed to time his visit to coincide with the Belfast Marathon (while he’s training for a marathon) – `curiosier and curioser’, as Alice would say!

So, what’s this resilient compact routing? About three years ago, I was fortunate to be an I-CORE postdoc with Danny Dolev and Armando was a postdoc at Technion. We started discussing ideas around routing and possibly due to my long line of work with self-healing algorithms (on which many blog posts may follow!) we started to gravitate towards the question: Can we route messages despite failures in the network? At about the same time, Shiri Chechik bested our Leader Election paper (On the complexity of universal leader election) with her paper Compact routing schemes with improved stretch for the best paper award at PODC 2013. With many life-changing events in-between (such as getting faculty positions and moving to many degrees drop in average temperature and many degrees more of precipitation!), the first paper in this line has just managed to struggle over in early 2016. Compact Routing messages in self-healing trees (Arxiv) was a finalist for the best paper award in ICDCN 2016.

So, what’s this resilient compact routing (take 2)? Routing is a very important `primitive’ for networks – the ability of the network to take a message from a source node and deliver it to a target. We encounter it every time we get onto a network- as soon as we connect to a router, to a website, send an email, make a skype/voip call etc.. In practice, the most used protocols for routing are based on well known standard graph distance finding algorithms such as Djikstra’s and Bellman-Ford, which itself is a testament to the longevity of these algorithms and to the power of graph algorithms, in general. If a node x gets a packet which started at node a and needs to end at node b, node x will refer to it’s routing table – a table which tells it which of its neighbours to send its packet to.

Often, a routing table will contain an entry for every node in the network telling where to forward a message addressed to that node. Now, this means the table can be really really huge depending on the size of the network. In practice, there are ways around this. One way, which makes for some nice theory is to do some preprocessing on the network e.g. build spanning trees, do DFS traversal, maybe some renaming and port changes, to reduce the size of the routing tables and the packet header. The crux of many of these schemes seems to be (the now seemingly simple) idea of interval routing (which by itself may not be compact)introduced by Santaro and Khatib in 1982. The idea may be summarised as follows:

Starting from a particular node, do a Depth First Search (DFS) traversal and construct the corresponding DFS tree. Also, give each node a label that is that node’s DFS number (ID) (say, the time step at which that node was first encountered in the DFS traversal).

Now, at each node, if you store the ‘largest’ ID of its subtree and the IDs of its children, you can now get intervals – which tell you which neighbour in the tree a node should send a packet addressed to another node. Hence, the name Interval Routing.

This spawned an active and productive field of research for the last few decades particularly in the effort of reducing both the size of the labels and tables while reducing the necessary tradeoff to be paid in terms of the distance. It is well known that if you reduce the space you use for routing, you cannot use the shortest paths and must pay in some measure by using a longer path (this measure is called stretch).

Looking at the above description, one will notice that developing these data structures seem to rely heavily on the initial DFS traversal. This implies that one may need to do a lot of recomputation if the network changes. In this spirit, there are some (but not many) works on `resilient’ compact routing i.e. compact routing that can handle changes to the network. Ours is one such attempt – in which we show how to do the well know Thorup-Zwick routing (over trees for now) in the self-healing model. In brief, the self-healing model is a responsive model of resilience where an adversary chooses a node/processor to take down or even insert (presumably to do the most damage in either case) and the neighbours of the attacked node/processor react by adding some edges/connections to the graph/network. We show how to both the compact routing and self-healing in low-memory (O(log^n) at most, where n is the number of nodes in the network).

I will defer the technical details of both self-healing and our compact self-healing routing to another post but needless to say, I am quite excited about continuing this work!