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).
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:
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!
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?
- 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.
Hunt for the towel 