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