Short Lectures on Distributed Computing 3: Let’s do some elections!

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.

Here are the lecture slides in pdf.

Advertisements

Short Lectures on Distributed Computing: Lecture 2 – Trees and formal message passing model

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!

Here are the lecture slides in pdf.

A report from DA@L – Distributed Algorithms @ Loughborough

A 180 degrees science from DA@L
A 180 degrees scene from DA@L – Distributed Algorithms @ Loughborough

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.

 

 

DA@L is cooking!

DA@L is ready.  We have an exciting line up for the Distributed Algorithms @ Loughborough workshop for this coming Monday, Jan 28th. The details of the workshop  are at www.cosher.org/dal – many thanks to EPSRC for funding the COSHER project.

  • Artur Czumaj, Warwick, UK. Round Compression for Parallel Approximate Matching Algorithms
  • Matthew Daggitt, Cambridge, UK. An algebraic approach to routing
  • Michael Elkin, Ben-Gurion University, Israel. Distributed Routing
  • Shay Kutten, Technion, Israel. Brief history of local checkability: from self stabilization to complexity theory
  • Iain Phillips, Loughborough University, UK. How to break the Internet in new and interesting ways
  • Thomas Sauerwald, Cambridge, UK. On coalescence time in graphs — When is coalescing as fast as meeting?
  • Paul Spirakis, Liverpool University, UK. Models for Programmable Matter
  • Amitabh Trehan, Loughborough University, UK. COSHER: Self-Healing Compact Routing and other problems in low memory
  • Posco Tso,  Loughborough University, UK. The Federated RaspberryPi µ-Infrastructure Testbed

 

Short Lectures on Distributed Computing: Lecture 1 – Introduction

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.

Here are the lecture slides in pdf.

COSHER, Jonas and DA@L

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 summer blast: from sidelines of PODC’18

Some very regular and well known or less known (like me) Beer drinking musketeers of PODCs!
Some very regular and well known or less known (like me) Beer drinking musketeers of PODCs!

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!

Roxy@SouthAll, London

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!