Elections are in the air!! – Oh well, that’s not much fun any more sadly so let’s do more mundane things like Computing!
Leader Election is one of the foundational problems of distributed computing – starting with a 1977 paper by Le Lann. The idea is for the nodes in the network to elect a leader among their own – no mean task even for computers!
Here, the drosophila of distributed computing comes into form – the Ring topology! We discuss some examples and algorithms on rings. Then we visit some of our own results – sublinear probablistic Leader elections on topologies like good expanders and the most simultaneously time and message efficient Leader Election!
We also visit verification and proof labelling – an attempt to understand complexity in distributed computing in similar terms to P vs NP centralised computing.
This lecture looks at the most basic of distributed algorithms: flooding (with a rather interesting question that arose accidentally!). We also see how it can be used to build spanning trees – Breadth First Search (BFS), Depth First Search (DFS) Trees, Broadcast and Convergecast (reverse broadcast)!
We look at the message passing model in a more formal manner including the timing model – synchronous or asynchronous! Thus, we fill up more of the empty slots of the huge matrix of possibilities of models in this multi-agent world of distributed computing!
Jan 28th, 2019 was a historic day at Loughborough University – well, at least, for distributed algorithms, since the first Distributed Algorithms @ Loughborough workshop was held there. Even though I am biased as the organiser, my feeling is that the day went well and the attendees enjoyed the workshop and all that was on offer – the high quality talks, the hospitality at Burleigh court – the large lunch and dinner, the drinks and even the foosball!
Somebody at Burleigh court kept trying hard to convince us (by putting up signposts) that our workshop was on Distribution Algorithms (rather than on Distributed Algorithms) but still the speakers pushed on with the high quality talks on distributed algorithms, the slides and abstracts of which are now available on the conference site www.cosher.org/dal or linked right below (in order of presentation). Many thanks again to all the attendees and to EPSRC for making this possible.
The first in a short series of lectures attempting the impossible task of covering distributed computing in 4 lectures to a group at the University of Bergen!
The Zoo of distributed computing where you’ll find many kind of creatures – regular or strange, benign or dangerous, dumb or rational and cunning, healthy or weak, quick or slow, boring or interesting. Centralised vs Distributed – Message passing (flooding etc) with a hint of Shared memory and PRAM etc.
My EPSRC first grant COSHER (Compact Self-Healing Routing) is coming to it’s final stages. Maybe I should have shouted about it earlier but we do have a website at www.cosher.org. My wonderful postoc Jonas Lefevre has recently moved on to his new mission after his year here. We have a number of interesting results, I believe, and more than that, a number of interesting ideas in the pipeline. In particular, we have some interesting ideas on algorithms for low memory large networks which I shall discuss here at some point in the future. We also have work on variants of leader election and fully dynamic self-healing routing in the pipeline. The time was almost too short – for this, it is good that EPSRC has now removed the funding cap of £125K from the first grant (besides renaming it to NIA – New Investigator Award) making it practically possible to support a postdoc for more than a year. Merci beacoup Jonas and thank you, EPSRC.
Finally, I am planning to organise a workshop centered around the themes of the grant – Reliability, Routing and Memory constraints on January 28th at Loughborough. I already have some exciting ‘Ayes’ to participation. The idea is to have some practitioners tell us what they really need and some theorists like me to feel happy that our dreamy ideas will be transformative in reality! I plan to call it DA@L – Distributed Algorithms @ Loughborough. I know, I know, it probably reminds a few of you of Lentil soup (daal), which doesn’t seem as exciting as butter chicken but, hey, climate change is real and maybe we have to do our bit eating low carbon usage foods! 🙂 – If you have some ideas and/or plan to participate, please drop me a message!
A random walk through my maze of thousands of unread/less-read mails on my gmail account landed me on a mail with the picture above. This brought back thoughts from the summer on what research is all about – escaping from a few good days of `intellectual’ activity to possibly even more satisfying evenings of Beer and Indian food!
In particular, on the last day of the conference (-1 days before the final workshop day), as workshops chair and one of the localhosts (192.168.1.1), I was cornered by a Nitin Vaidya in desperate yearning of very spicy Indian food. This was fortuitious – the conference being in London, which apparently boasts of more Indian restaurants than Bombay and Delhi combined! Anyways, a proposal was floated for the best Punjabi food outside Punjab (this being in SouthAll) – a few other afficiniados gathered, program scrapped due to heavy traffic, resurrected after the beer above (not at Southall but by the river Thames) and finally culminated in glory and delicious (and spicy on request) food at the Roxy restaurant in SouthAll. The menu was Sarson Saag, Makki Roti, Makki Methi Roti, Daal Makhani, Madras Chicken et etc..ending with Faluda dessert! Needless to say, we were too busy with the food to take pictures!
Here’s a fascinating read about the fascinating `Little Punjab’. and a sampler of eating out in SouthAll. Being a Punjabi, I can assert to the authenticity of the experience but I would say I was less better off with the spices the next day than the brave quartet of Nitin, Maurice, Antonio and Gadi!