Deterministic Synchronous Self-Stabilizing BFS Construction with Constant Space Complexity

This paper addresses the challenge of developing memory-efficient self-stabilizing algorithms for the Breadth-First Search (BFS) Spanning Tree Construction problem. Self-stabilization [3, 18, 20, 23] is a versatile technique that facilitates recovery after arbitrary transient faults impact the distributed system, affecting both the participating processes and the communication medium. Essentially, a self-stabilizing protocol can restore the system to a legitimate configuration (from which its behavior satisfies its specification), beginning from an arbitrary, potentially corrupted, initial global state, without the need of any human intervention. A BFS spanning tree construction involves (i) each node identifying a single neighbor as its parent, with the exception of the root node, which has no parent, and (ii) the set of parent-child relationships forming an acyclic connected structure, ensuring that following the parent nodes from any node results in the shortest path to the root node. Memory efficiency pertains to the amount of information transmitted to neighboring nodes to enable stabilization. A smaller space complexity results in reduced information transmission, which (i) decreases the overhead of self-stabilization in the absence of faults or after stabilization, and (ii) facilitates the integration of self-stabilization and replication [22, 24].

We adopt the classical state model introduced in [18]. In this model, a node can read its own memory and the memory of its neighbors, and execute its algorithm accordingly when needed. This means that a node’s memory is accessible to all its neighbors, ensuring they all obtain the same information. Consequently, if a node $v$ wants to communicate information exclusively to its neighbor $u$, $v$ must indicate in its memory that the information is intended only for $u$. This indication is typically made by adding node $u$’s identifier. This type of communication is inherent to wireless networks, where nodes exchange information by broadcasting messages over one or more carrier waves. In such networks, the notion of neighboring node of $v$ refers to any other node able to directly receiving messages emitted by $v$, typically without the aid of relays. Consequently, targeting a specific neighbor necessitates that the sender explicitly includes the recipient’s ID within the transmitted message. This identification requirement adds a significant overhead in memory space, specifically $O(\log n)$ bits in a network containing $n$ nodes. Within anonymous semi-uniform networks, nodes are devoid of identifiers, and only a single node assumes a role distinct from the rest. More precisely, the distinguished node operates under a dedicated protocol, whereas all other nodes execute an identical protocol. As a result of anonymity, it is not possible to rely on identifiers to interact with or refer to a specific node.

In [21], the authors introduce the notion of a silent algorithm (defined in a model slightly different from the state model [18]), a fundamental concept that significantly influences the space complexity of self-stabilizing algorithms. An algorithm is said to be silent if every execution eventually reaches a point beyond which the state of all nodes remains unchanged. They show that in networks of $n$ nodes, solving tasks such as leader election or spanning tree construction silently requires at least $\mathrm{\Omega }(\log n)$ bits of memory per node. However, in the state model, a self-stabilizing algorithm is not necessary silent, and talkative (i.e., non-silent) approaches were successful in reducing the memory cost of self-stabilizing algorithms [10, 11].

In general networks, such as those considered in this paper, self-stabilizing leader election is closely linked to self-stabilizing tree construction. On one hand, the presence of a leader enables efficient self-stabilizing tree construction [9, 13, 15, 16, 19, 25, 26, 27]. On the other hand, growing and merging trees is the primary technique for designing self-stabilizing leader election algorithms in networks, as the leader often serves as the root of an inward tree [1, 2, 4, 7, 10, 11].

From a memory perspective, the aforementioned works employ two algorithmic techniques for self-stabilization that negatively impact memory complexity. The first technique involves using a distance variable to store the distance of each node to the elected node in the network. This distance variable is employed in self-stabilizing spanning tree construction to break cycles resulting from arbitrary initial states, see for instance [1, 2, 4]. Clearly, storing distances in $n$-node networks may require $\mathrm{\Omega }(\log n)$ bits per node. Some works [6, 10, 11] distribute pieces of information about the distances to the leader among the nodes using different mechanisms, allowing for the storage of $o(\log n)$ bits per node. However, in general networks, the best result so far [11] uses $O(\log \log n+\log \mathrm{\Delta })$ bits per node, closely matched by the $\mathrm{\Omega }(\log \log n)$ bits per node lower bound obtained in [8].

The second technique involves using a pointer-to-neighbor variable to unambiguously designate a specific neighbor for each node (with the designated neighbor being aware of this). For tree construction, pointer-to-neighbor variables typically store the parent node in the constructed tree (with the parent being aware of its children). In a naive implementation, the parent of each node is designated by its identifier, requiring $\mathrm{\Omega }(\log n)$ bits for each pointer variable. However, it is possible to reduce the memory requirement to $O(\log \mathrm{\Delta })$ bits per pointer variable in networks with a maximum degree of $\mathrm{\Delta }$ by using node-coloring at distance 2 instead of identifiers to identify neighbors. The best available deterministic self-stabilizing distance-2 coloring protocol [11] achieves a memory footprint of $O(\log \log n+\log \mathrm{\Delta })$ bits per node, assuming unique identifiers. This implies that even self-stabilizing protocols solely relying on a constant number of pointer-to-neighbor variables per node [26, 16] actually use at best $O(\log \log n+\log \mathrm{\Delta })$ bits per node (assuming unique identifiers) in the classical state model, and that a lower bound of $\mathrm{\Omega }(\log \mathrm{\Delta })$ bits per node also holds for these solutions (regardless of the nodes being anonymous or not).

We now turn to the results of Itkis and Levin [25], which constitute one of the works most closely related to ours. their approach, the authors propose a randomized asynchronous self-stabilizing algorithm for leader election, based on a deterministic construction of a BFS tree. Their algorithms are designed under the same model as in this paper, namely the state model, but augmented with pointer-to-neighbor variables. As already mentioned above, using such additional assumption, each node $u$ can maintain a unique pointer to a neighbor $v\in N(u)$; more importantly, this neighbor $v$ is aware that it is being pointed to by $u$. Three deterministic BFS construction algorithms are presented by Itkis and Levin [25], proving successive improvements on their space complexity. Their first algorithm is a standard BFS construction based on the distance from each node to the root, and it is requiring $O(\log n)$ bits of memory per node. The other two algorithms are presented in natural language, and their formalization as a set of guarded rules is left undefined. The former is restricted to graphs of degree 2. It is based on a sophisticated and elegant cycle-detection mechanism based on the Thue-Morse sequence. Note that although no formal proof exist in the literature, the inherent properties of the Thue-Morse sequence and finite automata theory suggest that it is impossible to implement this sequence within finite memory. Nevertheless, the authors use a Thue-Morse-based certificate to obtain a constant space complexity per node. The second of the two algorithms generalizes the first to arbitrary graphs. This algorithm maintains a forest of pointers, and guarantees acyclicity of these pointers thanks to the use of the degree-2 algorithm. The latter is applied to each path from the root of the BFS tree to its leaves, where each path is identified thanks to a depth-first search (DFS) traversal of the BFS tree. These DFS traversals are benefiting from the pointer-to-neighbors variables. To keep the space complexity constant, the DFS traversals are performed successively. This requires to keep track of which DFS traversals have already been performed. This authors argue that this can be done using constant space complexity using the pointer-to-neighbor variables allowed by their model. However, in absence of such pointers, it is not clear how to implement this sequence of DFS traversals using less than $\mathrm{\Omega }(\log \mathrm{\Delta })$ bits of memory per node [15, 17].

Overall, up to this paper, there exists no deterministic self-stabilizing solution to the spanning tree construction problem that uses a constant number of bits of memory per process. Furthermore, the reuse of known techniques makes this goal unattainable.

In this section, we define the underlying distributed execution model considered in this paper, and state what it means for a protocol to be self-stabilizing.

A distributed system is an undirected connected graph, $G=(V,E)$, where $V$ is a set of vertices (or nodes) – $|V|=n,n\ge 2$ – and $E$ is the set of edges connecting those vertices. The distance between two nodes $u$ and $v$, denoted by $d_v^u$ is the length of the shortest path between $u$ and $v$ in $G$. Note that since $G$ is not oriented, $d_v^u=d_u^v$, and if $u=v$, then $d_v^u=0$. Then, the eccentricity of a node $v$ is the maximum distance from $v$ to any other node in the network.

Vertices represent processes, and edges represent bidirectional communication links (that is, the ability for two nodes to communicate directly). We assume that each node $v$ is able to distinguish each incident edge with a locally assigned unique label called port number. Port numbers are immutable and are not coordinated in any way: the edge $(u,v)$ may correspond to port number $k$ at $u$ and to port number $k^{\prime }\ne k$ at $v$. Let $N(v)$ be the set of port numbers, also called set of neighbors of $v$. The degree of $v$ denotes $|N(v)|$.

We consider the state model in the context of semi-uniform anonymous networks. In this model, the communication paradigm allows each node to read its own memory as well as the memories of its neighbors. Let $v$ be any node in $V$, and let $\{u_0,\mathrm{\dots },u_{|N(v)|}\}$ denote its set of neighbors. No neighbor $u_i,i\in \{0,\mathrm{\dots },|N(v)|\}$, can determine which port number in $N(v)$ corresponds to the edge $(v,u_i)$. Conversely, since nodes have no identifiers, $v$ cannot designate any particular $u_i$ to receive $v$’s information. Hence, a pointer-to-neighbor cannot be implemented solely by reading the neighbors’ variables.

A semi-uniform anonymous network is characterized by the absence of node identifiers and the presence of a unique distinguished node. This node serves as the root of the BFS tree and follows a distinct protocol, while all other nodes adhere to a uniform protocol. The protocol of a node consists of a set of variables and a set of (guarded) rules, of the following form:

Each node may write its own variables, and read its own variables and those of its neighboring nodes. The guard of a rule is a predicate on the variables of $v$ and its neighbors. The statement of a rule of $v$ updates one or more variables of $v$. A rule may be executed only if its guard evaluates to true. The rules are atomically executed, so the evaluation of a guard and the execution of the corresponding statement, if any, are done in one atomic step.

The state of a node is defined by the values of its variables. The configuration of a system is the product of the states of all nodes. Let $\mathrm{\Gamma }$ be the set of all possible configurations of the system. A distributed algorithm (or, protocol) $𝒜$ is a collection of binary transition relations, denoted by $\mapsto$, on $\mathrm{\Gamma }$ such that given two configurations ${\gamma }_1$ and ${\gamma }_2$, ${\gamma }_1\mapsto {\gamma }_2$ by the atomic execution of guarded action of one or more nodes. A protocol $𝒜$ induces an oriented graph ${\mathrm{\Gamma }}^{\mapsto }=(\mathrm{\Gamma },\mapsto )$, called the transition graph of $𝒜$. A sequence $e={\gamma }_0,{\gamma }_1,\mathrm{\dots },{\gamma }_i,{\gamma }_{i+1},\mathrm{\dots }$, $\forall i\ge 0,{\gamma }_i\in \mathrm{\Gamma }$, is called an execution of $𝒜$ if and only if $\forall i\ge 0,{\gamma }_i\mapsto {\gamma }_{i+1}$.

A node $v$ is said to be enabled in a configuration $\gamma \in \mathrm{\Gamma }$ if there exists a rule $R$ such that the guard of $R$ is true at $v$ in $\gamma$. In this paper, we assume that each transition of ${\mathrm{\Gamma }}^{\mapsto }$ is driven by a synchronous scheduler. This means that, given a pair of configurations ${\gamma }_1,{\gamma }_2\in \mathrm{\Gamma }$, then ${\gamma }_1\mapsto {\gamma }_2\in {\mathrm{\Gamma }}^{\mapsto }$ if and only if all enabled nodes in ${\gamma }_1$ execute an atomic rule during the transition ${\gamma }_1\mapsto {\gamma }_2$.

We now state our main technical result.

We presented the first constant space deterministic self-stabilizing BFS tree construction algorithm that operate in semi-uniform synchronous networks of arbitrary topology. Our solution $\mathrm{𝚃𝚘𝚔𝙱𝚒𝚗}$ is independent of any global network parameter (maximum degree, diameter, number of nodes, etc.). As classical techniques such as point-to-neighbor and distance-to-the-root cannot be used in such a constrained setting, we introduced a novel infinite token stream technique to break cycles and restore BFS construction that may be of independent interest for other tasks. We briefly mention how our BFS construction can be used to optimally color bipartite graphs (that is, with two colors Black and White). All nodes run $\mathrm{𝚃𝚘𝚔𝙱𝚒𝚗}$ so that eventually a $BF{S}^{\equiv 3}$ is constructed. With respect to colors, the root has color Black and retains it forever, while every other node take the opposite color of its parents whenever it executes $\mathrm{𝚃𝚘𝚔𝙱𝚒𝚗}$ (if it has parents). After stabilization of the $BF{S}^{\equiv 3}$ construction, all children of the root take the same color, and after one step their children take the root color, and so on, so that a 2-coloring of the bipartite graph is eventually achieved. This very simple application of $\mathrm{𝚃𝚘𝚔𝙱𝚒𝚗}$ still uses constant memory, as opposed to dedicated previous solutions to the same problem found in the literature [29, 28] that require $\mathrm{\Omega }(\log n)$ bits per node.

Two important open problems remain. First, our solution heavily relies on the network operation being fully synchronous (all nodes execute code in a lock-step synchronous fashion). It would be interesting to extend our token stream technique to an asynchronous setting. In this setting, we expect that some synchronization technique will be necessary, and it remains unclear whether such additional mechanism can be done in constant space. Second, while our algorithm uses a constant amount of memory per node, its time complexity (measured in steps) is exponential. This is due to the exponential decay mechanism for tokens that may require the root to send an exponential number of them to finally reach the furthest nodes in the network. One could speed up this process by adding more states to the $b$ variables: if the domain of $b$ becomes $\{\mathrm{𝟎},\mathrm{𝟏},\mathrm{\dots },𝐤,\top \}$, and token are accepted for any value that is not $\mathrm{𝟎}$ or $\top$ (assuming $b$ is incremented modulo $k$ anytime the incoming token is accepted), less tokens are destroyed, but the overall time complexity remains exponential. By contrast, solutions that make use of $O(\log \mathrm{\Delta }+\log \log n)$ bits per node have polynomial time complexity [10]. Whether there exists a constant space and polynomial time solution to the problem is left for future research.