Flooding or Viral Spread on a Network – Part 2

Part -2: the answer to the questions of part-1: will amnesiac flooding or viral spread on a network stop and how soon?

I am back with part 2 of the discussion of termination of Amnesiac flooding. Part 1 is here: Flooding or Viral Spread on a Network – Part 1

To recap, we were discussing the process of amnesiac flooding which can be viewed as possibly the simplest algorithm that can be executed in a decentralised/distributed manner on a network.  Here it is described below, where M is a message/object/infection initiated by an origin node.

Let’s say, the flooding/infection happens in rounds. The amnesiac flooding process sends M to all its neighbours and then forgets about it (hence, the amnesia!). The nodes receiving M then clone copies of M and send to all the other nodes from which they have not most recently received M, and so on this process continue.

The main question we asked (and which we answered in our STACS2020 paper) was the following:

Does Amnesiac flooding terminate on every connected graph?

And here are the exercises from part 1 and their solutions:

Exercise 1:  Does Amnesiac Flooding terminate in the following graph (where it originates from the red node)? If it does, how many rounds does it take?

Screenshot 2020-03-22 at 03.14.05

Well, here is the execution of amnesiac flooding starting from the red node (and we can count the number of rounds):

..and that’s 10 rounds. Good on you if you got that! Just for future reference, the diameter of this graph is 5. (For reference, the diameter of a graph is the longest distance (i.e. shortest path) between any two nodes in the graph).

Exercise 2: Going back to the Triangle and Square examples, how many rounds did it take for termination?

The triangle and square examples were in the first post. Here, they are again:

Simple counting shows that it takes 3 rounds for termination in the triangle and just 2 rounds in the square. The intriguing thing is that the diameter of a triangle is 1 and that of a square is 2, but it takes longer for it to terminate in the triangle than in the square, Hmm, something odd here?

And here were the more difficult puzzles which are really research questions addressed in our paper:

Puzzle 1: A triangle has only 3 nodes and a square 4 but it still takes longer to terminate in the triangle. Any guesses why?

Puzzle 2: And the big question:

Does Amnesiac flooding terminate on every connected graph?

 

The answers are not at all obvious and there were no guesses in the comments section, so I have no idea what your first thoughts were, but here’s the answer 🙂 –

Yes!

i.e Yes, Amnesiac flooding surprsingly terminates on every connected graph i.e. wherever you may start on any graph, at some point, the messages cancel each other out.

Something even more interesting happens – the message (or, say, the infection) visits each node at most twice!! This immediately implies that the maximum time for the process to terminate is twice of the diameter (since if it was more then some node will be visited thrice).

Now, for the intriguing question of puzzle 1. Is there some relation between the diameter  of a graph and the termination time of AF on it? But, then why does it not seem to hold for puzzle 1?

The answer lies in one particular property of the graph topology: bipartiteness! A bipartite graph is a graph which can be split into two sets of vertices such that all the edges go across the two sets and none between nodes on the same side. Now, if you observe carefully, a square is a bipartite graph. You can take the nodes which sit diagonally opposite each other in the same set and you observe that all the edges go across the two sets. In fact, any graph which is an even sized cycle (e.g. a square, or a hexagon) is bipartite whereas an odd sized cycle (triangle, pentagon) is not.

So, we get the following: If a graph is bipartite, amnesiac flooding terminates in at most diameter time (technically, in eccentricity of the origin node) with each node getting visited at most once! If a graph in not bipartite, the termination time will be more than the eccentricity of the node and less than twice the diameter, with each node visited at most twice.

Technically, the result is as follows:

Amnesiac flooding (AF) originating from a single node on a synchronous network terminates in a finite number of rounds. If the graph is bipartite, AF terminates in at most D rounds, otherwise in at most 2D+1 rounds, where D is the diameter of the graph.

For the technical details, see the paper, or await part-3 of this post!

Flooding or Viral Spread on a Network – Part 1

At this moment, it is very difficut to write something without reference to the rapidly spreading Corona virus which has brought the world to its knees. As it happens, our recent paper (in STACS 2020) is about a network process which can be seen to resemble an extreme version of a viral spread. This process is network flooding for which we postulated an interesting natural question (Will this process ever stop by itself?). As a disclaimer, this is far from how a real virus may spread in a real network but it is a very useful algorithm for delivering something (messages or data in our case) to every node in a communication network.

It is also a simple process to understand and a nice puzzle to attempt solving. So, let me postulate the puzzle and ask from you, the reader, a solution. To explain the flooding algorithm (which we technically call amnesiac flooding, as I’ll explain later) imagine the graph as given below. This is a simple line graph. The red node in the middle (node b) is the node originally having the message M (or the virus, if you wish).

Screenshot 2020-03-22 at 01.30.57

Let’s say, the flooding/infection happens in rounds. The amnesiac flooding process sends M to all its neighbours and then forgets about it (hence, the amnesia!). The nodes receiving M then clone copies of M and send to all the other nodes from which they have not most recently received M, and so on this process continue.

To illustrate on our line graph, this is how the process progresses:

 

Screenshot 2020-03-22 at 01.46.42
Node b transmitting M to neighbours a and c
Screenshot 2020-03-22 at 01.46.57
Node a has M but nobody to transmit to. Node c transmits to node d.
Screenshot 2020-03-22 at 01.47.06
Node d has M but nobody to transmit to. Flooding terminates.

The illustration shows that starting from the single node b with the message/infection M, it sends M to nodes a and c. Since a has just received the message from b and it has no other neighbours, the transmission stops at that end. On the other end, c can still transmit to neighbour d, which it does. However, in the next round, d is the only one with M, but since it has just received the message from c, it has no neighbour to forward the message to. At this point, the process simply stops.

In the line graph it is easy to see that the process will stop (and quickly) but as soon as a graph has cycles, this is not obvious any more. In reality, a graph can be much more complicated with possibly many cyclic and acyclic components. So, the question we are interested in is as follows:

For any possible connected graph, will the flooding process (Amnesiac Flooding) terminate on that graph?

Note that, as mentioned, nodes do not retain a memory of having received M beyond the immediately last round. This is ike the character Leonard in the movie Memento, who has only short term memory but still has to accomplish his task. If the graph has cycles, it is quite possible that a node will receive M again and transmit it further again, and then again and again!

Amnesiac Flooding like the character in the movie Memento has only short term memory.
Amnesiac Flooding like the character in the movie Memento has only short term memory.

However, if the nodes had long term memory (like long term innoculation against a virus), all it needs to do to stop the message transmitting is to check the incoming message – if it is M, it just stops the tranmission. In fact, this is exactly how network flooding (which is probably the oldest and simplest algorithm for a network) has been usually implemented on real communication networks. However, this has a memory overhead over a longer series of floodings (nodes will retain these messages). Also, it is illustrative to study the memory/state-less variant which seems a natural propagation process.

Let us look at some simple cyclic examples and leave you with a puzzle for the part 1 of this blog post.

Consider the graph which is a square. From the above figiure, we can see that the process terminates for the Square graph.

What about the Triangle?

Again, the figure shows that it terminates in the Triangle. However, notice an interesting phenomena – the messages crossed over and were received multiple times.

So, here are the exercises and puzzles:

  • Exercise 1:  Does Amnesiac Flooding terminate in the following graph (where it originates from the red node)? If it does, how many rounds does it take?Screenshot 2020-03-22 at 03.14.05
  • Exercise 2: Going back to the Triangle and Square examples, how many rounds did it take for termination?
  • Puzzle 1: A triangle has only 3 nodes and a square 4 but it still takes longer to terminate in the triangle. Any guesses why?
  • Puzzle 2: And the big question:

Does Amnesiac flooding terminate on every connected graph?

It will be great to see your answers/guesses in the comments below. I will come back with the solutions in part-2 of this post.

If you just cannot wait, you can look at our recently published paper (Spoiler alert) at STACS 2020 – On the Termination of Flooding.

Winning the ASEM DUO-India Fellowship

Recently, I received the good news that I am one of the recepients of the ASEM DUO-INDIA  professors fellowship 2020, in partnership with Prof. Sushanta Karmarkar of IIT Guhawati. This is an innovative fellowship under the auspices of ASEM – Asia-Europe Meeting. The fellowship will allow Sushanta to spend one month with me in Loughborough and I one month visiting Sushanta at Guhawati, with the idea of developing our research!!

Overall, the ASEM DUO fellowship program fosters collaboration between European and Asian nations. Besides the professors fellowship, the DUO program also runs a similar exchange fellowship for students.

Looking forward to it – thanks ASEM.

Short Lectures on Distributed Computing 4: Self-Healing and Compact Routing

Disttibued algorithms and networks differ from their centralised counterparts in that failure is part of their DNA! i.e. they can continue despite failures and need to be designed to handle such failures. Failures can come in many forms – from crash failures (a component is knocked out and refuses to get up), transient failures (a component gets punched hard, falls down, recovers on wobbly feet!), Byzantine (a component (our fictitious boxer, as you have no doubt figured out by now) has taken money from bookies to fix the match and is trying to lose ruining the whole fight).

An adversary – the other boxer is a good way to model attacks – i.e. I seek to make a statement such that my boxer does well against the best boxer known; my boxer can stand forever against a boxer that does not use an undercut; my boxer does well against a boxer that throws random punches but may do poorly against one who knows that I didn’t have breakfast today;my referee does well against a bookie who’s paid my boxer to get the match fixed!

The paradigm which looks at keeping the distributed system running despite failures in some acceptable form (maybe degraded from the original) is called fault-tolerance. Self-healing is a fault-tolerance paradigm for reconfigurable networks, in a broad sense. Reconfigurable networks are networks which permit changes to be made quickly , say, in contrast with hard-wired networks where to change the network topology, you would have to physically disconnect and change wires. One example is overlay networks e.g the Internet which can be thought of as virtual connrections made over an underlay – a network of wirings which permit any two computers (say, with IP addresses) to connect to each other.

Self-healing can now be thought of as a game where an adverary removes/deletes/adds a node from the network/graph and the neighbours of the deleted node respond locally by creating new connections in the reconfigurable network with the objective maintaining global properties such as connectivity, distances, expansion etc while allowing only minimal increase in degree of individual nodes. Formalising and designing self-healing algorithms was the subject of my PhD thesis and this lecture should give some flavour of it.

The other topic this lecture deals with is compact routing – a very interesting topic that generated a lot of interest in the distributed graph algorithms community. Those with basic familiarity with routing will remember that to route messages in a network, two data structures are used: the routing table which is available at every node, and routing labels which are the address and related information that each packet contains. These can be thought of as corresponding to post-offices and addresses on letters to be delivered to individuals.

Now, the simplest way to biuld a routing table would be to run something like a Djikstra algorithm all pairs shortest path algorithm and at every node store which neighbour to forward a packet to for every destination. For example, if a node has three neighbours a,b, and c, and it gets a packet destined for node x, the node can see in its routing table that node b is on the shortest path from itself to x, and it can thus forward the packet to node b. This is called shortest path routing and is most desirable since it follows the quickest route to get packets across (ignoring other real world constraints such as bad weather, lazy porters etc etc..). However, the cost is that each node now stores an O(n) sized table where n is the number of nodes in the network. This is considered too much!

Thus, the research area of compact routing is obsessed with keeping the tables (and also the labels) to  smaller (than n) size at the expense of approximating shortest paths – some thought on the matter leads to conclusion that this is an unavoidable tradeoff.

At the same time, what about the six degrees of seperation? – that idea states that not only do you know everybody in the world through a chain of six people, if these people were willing enough – they could even route a postcard from you to them! – thus, this is a really compact routing protocol. This effect was discovered by the Milgram experiment in the 1930s USA.

The difference is that this efffect relies a lot on geographical information i.e. Chicago is closer to New York than Albuquerque, thus, if I have a choice between a friend in New York and another in Albuquerque, I will send the packet to my friend in New York (i.e. I will do greedy routing) if my objective is to send the packet to a Barack Obama, resident of Chicago! In general, compact routing on networks has very little global information, thus, the challenge is higher. This information is gathered and a protocol built. This, however, creates a new challenge – what happens to the routing if the network changes. Compact self-healing routing is a research area that seeks to provide continuing compact routing when the network is changing, at least in the self-healing paradigm.

Lecture Slides are available here (in pdf).

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.

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!