Amnesiac Flooding and the curious case of a Unique Algorithm by Amitabh Trehan

Venue: Bharti501

Abstract: In the field of distributed algorithm design, it is often standard to abstract the network as an undirected graph with the nodes as vertices and connections as edges. About the simplest process one can imagine on a network/graph is flooding: A node is in possession of a message M which has to be  eventually sent to every node on the graph (this is called achieving broadcast)- the node sends M immediately to all its neighbours and they send to all their neighbours they did not just receive the message from and so on. Clearly, this achieves broadcast. But, how to achieve termination? i.e. the copies of the message should not circulate indefinitely.

At the advent of distributed computing, more than 50 years ago, a simple solution was devised – keep a copy of M, and if M is received again, simply discard this M. However, this requires memory/state and a stack of earlier received messages. Surprisingly, we discovered [PODC2019,STACS2020,DC2023] that state is unnecessary to achieve terminating broadcast – the same process without any state or memory beyond the immediate receipt (hence, called Amnesiac Flooding (AF)), due to some still slightly mysterious properties of simple undirected graphs, terminates in asymptotically optimal time on every graph.  Intriguingly, we have recently discovered [DISC2025] that AF is Unique! i.e. under certain reasonable conditions, AF is the one and only algorithm that achieves terminating broadcast. Are there other examples of Unique algorithms in literature, and is counting the number of algorithms for solving a problem a concept we can reasonably postulate?

AF on Wikipedia: https://en.wikipedia.org/wiki/Amnesiac_flooding