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?

Weapons of Math Destruction and the hippocratic oath

Don’t mess with the maths – it can shoot you in the foot! -‘You talking to me, you talking to me…’

Here is a very interesting article on the dangers of the big data hype: http://spectrum.ieee.org/tech-talk/computing/software/are-you-making-a-weapon-of-math-destruction.

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.

WeaponsMath r4-6-06.jpg

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.

Belfast to Mexico City via Self-healing Compact Routing!

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!

Screen Shot 2016-07-11 at 23.50.38.png
Basics of Routing: To send a letter in an envelope- what is needed is an address (packet header) and a database at each post office (routing tables)!

 

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 (Arxivwas 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!

 

 

 

 

Driving BCTCS 2016

The 32nd British Colloquium of Theoretical Computer Science (BCTCS 2016) was held in Belfast from March 22nd to 24th at Belfast (QUB). Here are some insights, pictures and links to some talks.

The  32nd British Colloquium of Theoretical Computer Science (BCTCS 2016)  was held in Belfast from March 22nd to 24th at the pictueresque setting of Queen’s University Belfast and the newly remodelled Graduate School. It was a good amount of work – a bit like a 200 mts race where you accelerate rapidly and take a while to stop! This was more so because my colleague Alan Stewart who brought the conference here promptly retired leaving me in-charge! (Though he still did much of the work even post-retirement 🙂

I did my PhD in the USA in the area of algorithms and I discover that the areas of focus in theoretical Computer Science differ markedly in the US and UK. The UK has traditional strength in Languages and Logic whereas in the US there seems to be more strength in Algorithms based theory (this is something that the EPSRC readily admit!). BCTCS had good representation across the themes particularly since some of our speakers were from across the pond(s) (including Iceland!).

Slides from some of the talks are available at http://www.amitabhtrehan.net/bctcs.html

 

 

Hope you have a look and find them interesting!

Halg!

Highlights of Algorithms, supermarine Paris, June 6th to 8th, 2016.

Halg! Here comes the Algorithms. Halg! .. and the algorithmicians.

Highlights of Algorithms  is taking place in Paris right now (June 6th to 8th). Surprisingly, all of Paris I have seen seems above water (contrary to what I expected seeing the news!). I think it’s a great idea- getting (hopefully) the best papers on algorithms in the past year at one venue (no formal proceedings). The atmosphere is lively and relaxed with probably more participants than the organisers expected (overflowing room!).

In true (and increasingly rare?) ode to ‘Theory’, Stephen Alstrup’s talk on labelling schemes used paper and OHP, as seen below:

IMG_20160606_151933

 

The talk schedule is given at http://highlightsofalgorithms.org/program/. The talks today have ranged across topics from dynamic algorithms, mechanism design to distributed graph algorithms. Each talk, of course, deserves a post on itself to do justice. Tomorrow afternoon, I will present my paper Compact Routing Messages in Self-Healing Trees in one of the short paper sessions.

On a lighter node, google searching halg reveals this ‘urban dictionary’ entry: http://www.urbandictionary.com/define.php?term=Halg:

On a basic level, a “halg” is a break in a conversation that is being held over MSN. The length of a “halg” depends on circumstances, time of day and the people involved in the conversation.

Hugh! Hold on, I need a halg before my next post.