Amnesiac Flooding: Easy to Break, Hard to Escape

The dissemination of information to disparate participants is a fundamental problem in both the construction and theory of distributed systems. A common strategy for solving this problem is to “broadcast”, i.e. to transmit a piece of information initially held by one agent to all other agents in the system [1, 18, 21, 24, 25]. In fact, broadcast is not merely a fundamental communication primitive in many models, but also underlies solutions to other fundamental problems such as leader election and wake-up. Given this essential role in the operation of distributed computer systems and the potential volume of broadcasts, an important consideration is simplifying the algorithms and minimizing the overhead required for each broadcast.

Within a synchronous setting, Amnesiac Flooding as introduced by Hussak and Trehan in 2019 [13, 14] eliminates the need of the standard flooding algorithm to store historical messages. The algorithm terminates in asymptotically optimal $O(D)$ time (for $D$ the diameter of the network) and is stateless as agents are not required to hold any information between communication rounds. The algorithm in the fault-free synchronous message passing model is defined as follows:

These rules imply several other desirable properties. Firstly, the algorithm only requires the ability to forward the messages, but does not read the content (or even the header information) of any message to make routing decisions. Secondly, the algorithm only makes use of local information and does not require knowledge of a unique identifier. Thirdly, once the broadcast has begun, the initial broadcaster may immediately forget that they started it.

However, extending Amnesiac Flooding and other stateless flooding algorithms (such as those proposed in [27, 29, 4]) beyond synchronous fault-free scenarios is challenging. This is due to the fragility of these algorithms and their inability to build in complex fault-tolerance due to the absence of state and longer term memory. It has subsequently been shown that no stateless flooding protocol can terminate under moderate asynchrony, unless it is allowed to perpetually modify a super-constant number (i.e. $\omega (1)$) of bits in each message [27]. Yet, given the fundamental role of broadcast in distributed computing, the resilience of these protocols is extremely important even on synchronous networks.

Outside of a partial robustness to crash failures, the fault sensitivity of Amnesiac Flooding under synchrony has not been explored in the literature. This omission is further compounded by the use of Amnesiac Flooding as an underlying subroutine for the construction of other broadcast protocols. In particular, multiple attempts have been made to extend Amnesiac Flooding to new settings (for example routing multiple concurrent broadcasts [4] or flooding networks without guaranteed edge availability [29]), while maintaining its desirable properties. However, none have been entirely successful, typically requiring some state-fulness. It has not in fact been established that any other protocol can retain all of Amnesiac Flooding’s remarkable properties even in its original setting. These gaps stem fundamentally from the currently limited knowledge of the dynamics of Amnesiac Flooding beyond the fact of its termination and its speed to do so. In particular, all of the existing techniques (e.g. parity arguments such as in [16] and auxiliary graph constructions such as in [28]) used to obtain termination results for Amnesiac Flooding are unable to consider faulty executions of the protocol and fail to capture the underlying structures driving terminating behaviour.

We address these gaps through the application of novel analysis and by considering the structural properties of Amnesiac Flooding directly. By considering the sequence of message configurations, we are able to identify the structures underlying Amnesiac Flooding’s termination and use these to reason about the algorithm in arbitrary configurations. The resulting dichotomy gives a comprehensive and structured understanding of termination in Amnesiac Flooding. For example, we apply this to investigate the sensitivity of Amnesiac Flooding with respect to several forms of fault and find it to be quite fragile. Furthermore, we show that under reasonable assumptions on the properties of a synchronous network, any strictly stateless deterministic terminating broadcast algorithm oblivious to the content of messages, must produce the exact same sequence of message configurations as Amnesiac Flooding on any network from any initiator. We therefore argue that Amnesiac Flooding is unique. However, we show that if any of these restrictions are relaxed, even slightly, distinct terminating broadcast algorithms can be obtained. As a result of this uniqueness and simplicity, we argue that Amnesiac Flooding represents a prototypical broadcast algorithm. This leaves open the natural question: do there exist fundamental stateless algorithms underlying solutions to other canonical distributed network problems? Though memory can be essential or naturally useful in certain scenarios [5, 7, 8, 10, 17, 20], understanding what we can do with statelessness can help us push fundamental boundaries.

The literature surrounding both the broadcast problem and fault sensitivity is vast, and a summary of even their intersection is well beyond the scope of this work. Instead, we shall focus on work specifically concerning stateless, or nearly stateless broadcast.

The termination of Amnesiac Flooding and its derivatives has been the focus of several works. In combination they provide the following result that Amnesiac Flooding terminates under any sequence of multi-casts, i.e.

Two independent proofs of the algorithm’s termination have been presented, using either parity arguments over message return times [16] or axillary graph constructions [28]. The latter technique has further been used to establish tight diameter independent bounds on the termination of multicast using Amnesiac Flooding, complementing the eccentricity based bounds of [16]. The techniques we develop in this work, however, are more closely aligned with those of [15], as we exploit a similar notion to their “even flooding cycles” in our message path argument. In contrast to that work we focus on arbitrary configurations of messages, rather than just those resulting purely from a correct broadcast which allows us to obtain a stronger characterisation. Combining our techniques with the dual “reverse” flood introduced by [15], we are able to show the complement of Theorem 7, that only those configurations reachable from a sequence of multi-casts lead to termination.

There have, further, been multiple variants of Amnesiac Flooding introduced. It was observed by [27] in a result reminiscent of the BASIC protocol proposed by [12], that sending a second wave of messages from a subset of the initial nodes reduces the worst case $2D+1$ termination time to the optimal $D+1$ in all but a specific subset of bipartite graphs. We note that our fault sensitivity results extend naturally to this algorithm as well, as the same invariants apply to this setting. Beyond this, there have been several approaches to deal with the flooding of multiple messages simultaneously. In [15], the original authors of [13] show that under certain conditions termination can be retained, even when conflicting floods occur. Since then, two partially stateless algorithms have been proposed, both making use of message buffers and a small amount of local memory [29, 4]. We will not be directly concerned with these approaches, however, as we assume a single concurrent broadcast throughout. However, the mechanism employed in [29] should be highlighted as it rather cleverly exploits the underlying parity properties we identify as driving termination. Furthermore, as reduction to Amnesiac Flooding is used as a technique for proofs in many of these works, the comprehensive understanding of its termination we present here could prove a powerful tool for future work in these areas.

While the robustness of Amnesiac flooding and its variants have been previously studied, this has been focused on two forms of fault. The first is the disappearance and reappearance of nodes and links. The termination of Amnesiac Flooding is robust to disappearance and vulnerable to reappearance [16]. We will observe that this is a necessary consequence of the invariants driving termination and their relation to cyclicity. In particular, the disappearance of nodes and links cannot form new cycles violating the invariant, whereas their reappearance can. A pseudo-stateless extension to Amnesiac Flooding has been proposed to circumvent this [29], implicitly exploiting the parity conditions of [16]. The second are faults that violate synchrony. Under a strong form of asynchrony, truly stateless and terminating broadcast is impossible [27]. However, the landscape under a weaker form of asynchrony (namely, the case of fixed delays on communication links) is more fine-grained. Although termination results have been obtained for cycles, as well as the case of single delayed edges in bipartite graphs [16], there is no clear understanding of the impact of fixed channel delays. While we do not directly address this, we believe that techniques mirroring our invariant characterizations may prove fruitful in this area. To our knowledge, this work is the first to consider both the uniqueness of Amnesiac Flooding, as well as its fault sensitivity beyond node/link unavailability in a synchronous setting.

Beyond Amnesiac Flooding and its extensions, the role of memory in information dissemination is well studied in a variety of contexts. Frequently, stateful methods obtain faster termination time, such as in the phone-call model where the ability to remember one’s communication partners and prevent re-communication dramatically improves termination time and message efficiency [10, 5, 8]. Similarly, for bit dissemination in the passive communication model the addition of only $\log \log n$ bits of memory is sufficient to break the near linear time convergence lower bound of [7] and achieve polylogarithmic time [17]. Even more strongly, a recent work [20] has shown that in the context of synchronous anonymous dynamic networks, stabilizing broadcast from an idle start is impossible with $O(1)$ memory and even with $o(\log n)$ memory if termination detection is required. Despite this, low memory and even stateless broadcasts remain desirable [12]. The possibility of solving other canonical distributed computing problems beyond broadcast, in a stateless manner, remains intriguing. In this direction, various low memory stateful models have been proposed to handle more complex distributed problems e.g. the compact local streaming (CLS) model in [6] with deterministic solutions (routing, self-healing fault-tolerance etc.) and randomised solutions for distributed colouring in a similar model [11].

Stateless broadcast schemes have been studied in a variety of contexts. To give an example, they are used in mobile ad hoc networks, which, due to the lower power and rapid movement of devices, see diminishing returns from maintaining information about the network [19]. However, given a lack of synchronisation as well as the wish to avoid so-called broadcast storms [26], these techniques typically rely on either some form of global knowledge (such as the direction or distance to the initiator) or the ability to sample network properties by eavesdropping on communications over time [3, 23]. It should be noted however, that in contrast to many models, such as anonymous dynamic networks, radio networks and many mobile ad hoc networks, the typical framework for studying stateless flooding (“true statelessness” as defined by [27] restricting the model of [9]) permits the knowledge and distinguishing of neighbours in both broadcasting and receiving.

Throughout this work we consider only finite, connected graphs on at least two nodes. We denote the set $\{1,\mathrm{\dots },x\}$ by $[x]$ and $R(r,s)$ the Ramsey number such that any graph on $R(r,s)$ vertices contains either a clique on $r$ vertices or an independent set on $s$ vertices. In this work, we make use of a generic synchronous message passing model (as described in definition 1) with several additional assumptions based on the truly stateless model of [27]. Our agents are the nodes of a network and are able to communicate via messages of arbitrary size sent over the edges of this network. Computation occurs in synchronous rounds, consisting of three phases: (i) nodes receive messages sent in the previous round, (ii) nodes perform computation and (iii) nodes send messages to be delivered in the next round. Unless stated otherwise, agents do not suffer faults and no messages are lost. In addition to these standard assumptions, we enforce that the model is stateless, i.e. nodes cannot maintain any additional information between rounds (such as routing information, previous participation in the flood or even a clock value), cannot hold onto messages and can only forward, not modify the messages.

Unless stated otherwise we do not assume that nodes have access to unique identifiers, however they have locally labelled ports that are distinguishable and totally orderable for both receiving and sending messages. When we do work with identifiers these identifiers are assumed to be unique, drawn from $[|V|+\kappa ]$ for $\kappa >0$ a constant and assigned adversarially. We refer to such an assignment of IDs to a network as a labelling of the network and we identify the port label of a link leading to a node with the ID of that node. We further assume that individual nodes have access to arbitrarily powerful computation on information they do have.

We are principally interested in the problem of broadcast, although we will occasionally consider the related multicast problem i.e. there are multiple initiators who may potentially wake up in different rounds with the same message to be broadcast. For a graph $G=(V,E)$ and an initiator set $I\subseteq V$ we say that a node is informed if it has ever received a message from a previously informed node (where initiators are assumed to begin informed). An algorithm correctly solves broadcast (resp. multicast) on $G$ if for all singleton (resp. non-empty) initiator sets there exists a finite number of rounds after which all nodes will be informed. Unless specified otherwise, we assume that initiator nodes remain aware of their membership for only a single round. We say that an algorithm terminates on $G=(V,E)$ if, for all valid initiator sets, there exists a finite round after which no further messages are sent (i.e. the communication network quiesces).
Formally, for the message $M$, we denote a configuration of Amnesiac Flooding as follows:

Further, for $H$ a subgraph of $G$, we denote by $S_H$, $S$ restricted to $H$. Below, we define the operator $A_{I,G}:2^{V^2}\to 2^{V^2}$ to implement one round of Amnesiac Flooding on the given configuration where agents in $I$ receive the message from outside the network:

We will drop the subscript when $G$ is obvious from context and $I=\mathrm{\varnothing }$. Further, we adopt the standard convention of using $A_{I,G}^k$ to mean $A_{I,G}$ applied $k$ times. Theorem 7 in this notation can be expressed as follows:

In this section, we investigate broadcast protocols similar to Amnesiac Flooding and establish four desirable properties that Amnesiac Flooding uniquely satisfies in combination. On the other hand, we show that this result is sharp and that by relaxing any of these conditions one can obtain similar terminating broadcast protocols.

With the uniqueness of Amnesiac Flooding established, a greater understanding of its properties is warranted. In this section, we study the configuration space of Amnesiac Flooding and obtain an exact characterisation of terminating configurations. We then apply this to investigate the algorithm’s fault sensitivity.

In this paper, we prove a uniqueness result: Under standard synchronous message passing assumptions, any strictly stateless deterministic algorithm oblivious to the message content which solves terminating broadcast is indistinguishable from Amnesiac Flooding. We therefore argue due to both its uniqueness and simplicity, that Amnesiac Flooding is a fundamental or prototypical broadcast algorithm. We formalise the four properties required for this uniqueness to hold, and show that by relaxing each individually one can obtain other correct and terminating broadcast algorithms, of which we present several. These present the following natural questions: To what extent does Amnesiac Flooding represent a “minimal” broadcast algorithm? Are there identifiable families of algorithms solving terminating broadcast with a subset of these restrictions? Are any of these independent of (i.e. not derivatives of) Amnesiac Flooding? Lastly, we are not aware of any similar uniqueness results in algorithms literature, restricting the number of successful algorithms to just one (or even to small finite numbers) - can this result stimulate a study into enumerating distinct algorithms for solutions to interesting problems? Note that our model of true statelessness rules out trivial extensions to algorithms such as delaying algorithm start or holding messages for a certain count. Are there reasonable ways to define distinctiveness i.e. discard “trivial” extensions to algorithms in less restrictive models than ours?

We also obtain an understanding of the structural properties of Amnesiac Flooding. In particular, we study its sensitivity to single message drops, uni-directional link failures, and weak byzantine collusion, showing it can easily become non-terminating or non-broadcasting under such conditions. This is perhaps surprising, as statelessness is frequently associated with fault tolerance, such as in the self stabilizing setting. A reasonable interpretation of Theorem 15, however, is that Amnesiac Flooding, while locally stateless, depends heavily on a distributed “meta-state” contained in the configuration of sent messages. This suggests it is unlikely that any minor modification of Amnesiac Flooding will resolve its fragility without depending on an entirely different mechanism for termination. In support of this, we note that of the four alternatives presented in the proof of Theorem 3, only Random-Flooding is meaningfully more robust (and will in fact terminate from any configuration in finite time almost surely). Nevertheless, we contend that further exploration of stateless algorithms such as Amnesiac Flooding, their properties and related models are important for both theory and practice of distributed networks.