Self-Stabilizing Algorithms for Computing Maximal Distance-2 Independent Sets and Minimal Dominating Sets in Networks

Self-stabilization emerges as a pivotal fault tolerance paradigm within distributed systems and networks, facilitating convergence to a correct global state from an unspecified initial configuration. Such a self-stabilizing algorithm, operational without the necessity for external intervention, is capable of amending the distributed system's global state within a determinate timeframe. The literature is replete with a spectrum of self-stabilizing algorithms derived from graph theory. These algorithms address an assortment of computational problems including leader election, node coloring, and the provision of solutions to domination and independent set issues, as well as the construction of spanning trees. The practical significance of these algorithms is accentuated in their application to network architectures such as sensor and ad-hoc networks, where they are instrumental in defining cluster heads [1-3].

Let G=(V, E) be a graph where V represents the node set and E is the edge set. The present work employs several variants of independent and dominating sets, which are frequently referenced throughout subsequent sections. The definitions of these terms are as follows:

•  Independent Set: is defined as a subset of nodes in V, denominated S, such that no two nodes within S share an edge.
• Maximal Independent Set (MIS): It is an independent set, denoted as S, for which no larger set exists that preserves independence. It is implicit that within MIS, the distance between any node pair in S exceeds one.
• Maximal Distance-2 Independent Set (MD2IS): This is a particular set of the independent set, S, wherein no node in S is reached by another node in S only through at least 3 edges. In MD2IS, there are no two independent nodes in S that could be reached through two edges.
• Minimal Dominating Set (MDS): is a subset of nodes, denoted as S, where every node in the graph is either included in S or is adjacent to at least one node of S. The dominating set is considered minimal if no smaller subset of S can satisfy the conditions of being a dominating set.

Figure 1 serves as an illustrative guide for conceptualizing the Maximal Independent Set, Maximal Distance-2 Independent Set, and Minimal Dominating Set. In this figure, nodes delineated in green represent members of the respective set. It is noteworthy that, as depicted in Figure 1(a), the MIS showcases a pairwise node distance of at least two edges. In contrast, Figure 1(b) reveals that within the MD2IS, the inter-node distance is strictly greater than two edges. In the case of MDS, any node not inside the MDS (represented with black) is at least adjacent to one member of the MDS, thereby satisfying the domination property.

Historically, the pursuit of solutions for the MDS and MIS conundrums has been vigorous within the realm of self-stabilization research. Traditional approaches predominantly employ the distance-one model, which permits interactions solely between immediate neighboring nodes. In a novel departure, the distance-2 model for self-stabilization-introduced by Turau [4] extends this interaction to nodes within a two-hop radius. This study seeks to highlight the capacity of the distance-2 model to underpin the development of novel self-stabilizing algorithms. The abstraction inherent in the distance-2 model paves the way for the forthcoming design of algorithms targeting both MD2IS and MDS. However, the application of such algorithms within the distance-1 paradigm necessitates the utilization of a transformer. Despite the ease of algorithm design afforded by the distance-2 model, direct application is untenable; hence, transformation to the executable distance-1 model is imperative. The transformer introduced by Turau [4] will be used in this research.

In practical scenarios, the implementation of MIS, MD2IS, and MDS finds resonance in ad hoc and wireless sensor networks. Here, nodes within these sets assume the role of servers or cluster heads, providing a suite of services to adjacent nodes, designated as cluster members. These services encompass but are not limited to routing data, key distribution for encryption, and management of member identity. Given the propensity for failures in ad hoc and, particularly, sensor networks (often attributed to battery limitations) the indispensability of self-stabilizing algorithms becomes pronounced. Such algorithms are integral to the restoration of cluster headsets, thereby ensuring network resilience and operational continuity.

1.png

Figure 1. Three variants of independent and dominating sets composed of green nodes

1.1 Paper organization

The structure of the paper is methodically divided into seven sections for clarity and coherence. Section 2 discusses the prior art and delineates the contributions of the current study. Section 3 presents the model and the terminological foundation used in self-stabilization. The algorithms proposed for identifying the Maximal Independent Set at a distance-2 and then for the computation of the Minimal Dominating Set using the distance-2 model are introduced in Sections 4 and 5. In Section 6, we illustrate the simulation tests to demonstrate the efficiency of the proposed algorithms. Lastly, in Section 7, the conclusion summarizes the main points presented in this paper.

Distributed systems are typically represented as graphs, denoted as G(V, E). The set V of vertices, called also nodes, represents the processing units of the distributed system. The connections between units are represented by the set of links E, called also edges. Nodes u which shares a link with $v \in V$ is the set of v neighbors defined as $N(v)=\{u \in V: v u \in E\}$. Two nodes $v, u$ are considered adjacent if $u \in N(v)$.

We define the concept of the neighborhood at distance-2, denoted as $N(v)_{{dist } 2}=N(v) \cup\{w \in V: \exists u \in N(v): w \in N(u)\}$. Consequently, all neighbors of v at distance 2 are either at a distance of 1 or 2 from v.

A subset $S$ in $V$ is said independent if there are no adjacent nodes in $S$, or there are no pair of nodes in $S$ that are linked by an edge. Similarly, a subset $S$ is called distance-k independent if there are no two nodes in S that are linked by k (or less) edges. Any pair of nodes in $S$ are connected only through k+1 (or more) edges [20]. Thus, we call a set S distance-2 independent, if any two nodes in S are reached only through a number of edges that is strictly greater than 2. It is worth noting that in the Maximal Independent Set (MIS), every node v is either independent if v is inside the MIS, or dominated at least by an independent node u if v is outside the MIS [4]. In the literature, the MIS is also known as the independent dominating set.

Any node $u$ outside of the maximal distance-2 independent set, called MD2IS, is:

-either, u has at least an adjacent node $v \in M D 2 I S$, (hence, u is dominated),

-or u is dominated (at distance-2) by a node $v \in M D 2 I S$ where u could reach v only through 2 edges.

Note that multiple nodes from the MD2IS set could dominate a node u outside the MD2IS set. Figure 1(b) illustrates an example of a node u that could be dominated by a couple of nodes v₁ and v₂. The distance between u and v₁ is 1 and the distance between u and v₂ is 2.

Definition 1: In a graph G(V, E), a subset S in V is said a distance-2 independent set if and only if any two nodes in S are reached only through a number of edges that is greater or equal to 3. S is maximal if there is no other set S’ that contains S such that S’ is a distance-2 independent set.

Definition 2: In a graph G(V, E), a dominating set is a subset S in V where every node u outside of S has at least an adjacent node v inside S.

In the self-stabilization context, an algorithm needs to (1) attain a globally legitimate configuration (2) within a finite period called convergence. Upon reaching the legitimate configuration, the algorithm must remain within the legitimate configuration and cannot move again outside the legitimate configuration. This condition is referred to, in the literature, as closure. Consequently, to demonstrate the self-stabilizing nature of an algorithm, it is necessary to show the closure and the convergence. The closure aims to illustrate that the reached legitimate configuration remains legitimate without any risk of moving again to an illegitimate state. The convergence is the certainty of achieving a legitimate configuration in a finite period.

In a self-stabilizing system, each node has a number of rules: R1, R2, … Ri. For every rule, written generally as guard $\rightarrow$ statement, the guard is checked using an infinite loop. The statement can be executed if the guard is true. If all nodes execute the same rules i.e. the same code, the distributed system is known as uniform in contrary to other systems where some nodes could execute a different code such as semi-uniform systems wherein one node has a different code. Generally, local variables are used at the level of each node to define the node state. The local state can be read and modified only by the local owner. Adjacent nodes can read the state of the local node, but cannot write in the local variable of their neighbor node.

Besides a local variable, the expression model proposes that every node can use (read/write) a local expression exp to have a partial view in the neighborhood at distance-1. Since any other node can read (but not write) the expression exp of its neighbors, it reaches in fact, information at distance 2. Thus, the expression model is executed based on information obtained at distance 2.

The guard consists of Boolean conditions using variables and/or expressions of the local node or the neighbor nodes. During the infinite check loop, when a guard is true, its corresponding rule is known as enabled or privileged. Thus, a node is enabled or privileged if there is an enabled rule among its set of rules. The execution of a statement leads to a change in the local state and consequently, to a new configuration of the global configuration. This transition through an enabled node is known in the literature as a move. However, the execution of a move is only allowed after getting the permission of a scheduler or a daemon. The algorithm is self-stabilizing if the sequence of executed moves is finite (whatever serial or distributed) leading certainly to a legitimate configuration.

3.1 Daemon notion

Before starting to design a new self-stabilizing algorithm, an important hypothesis must be assumed whether the algorithm is executed in a parallel or sequential way. Despite the parallel execution seems more efficient, it is difficult to formally show the correctness and the convergence under the distributed execution compared to the sequential execution.

In this direction, the daemon concept, known also as a scheduler, comes to provide researchers with an abstract tool to make a suitable hypothesis according to the context in which is facing.

In a central daemon, it is supposed that privileged nodes are executed one by one in a sequential order determined by the daemon which is also referred to as serial daemon. Conversely, in a distributed daemon, the daemon may select many privileged nodes to execute a move simultaneously, forming a round. In the case the daemon allows all privileged nodes to execute a move simultaneously, this scheduler is said synchronous.

3.2 Transformers

A commonly employed method, as discussed in the work of Turau et al. [4, 22], involves the conversion of a self-stabilizing algorithm A, which operates within specific assumptions, into a new algorithm A^T, that runs under other assumptions. Despite this transformation, both algorithms are equivalent and ensure to achieve the same final configuration. Various types of transformers, such as distance transformers and daemon transformers, can be found in the literature. However, the transformation typically introduces additional time complexity by algorithm A^T to reach the final correct configuration.

In this paper, we adopt the transformer of Turau [4], to convert the initially proposed algorithm A under the expression model and a central daemon to obtain a distributed algorithm A^T. The expression distance-2 model provides an abstraction on the proposed algorithm A which facilitates proving the correctness and convergence. On the contrary, the design of new algorithms is complicated under the distance-1 context due to the details presented in this case. However, the hypotheses, on which the algorithm A is supposed to run, are either not feasible or not efficient for the execution of A. For instance, self-stabilizing algorithms cannot use directly distance-2 in reality and need to use gradually distance-1. Since distributed execution is more efficient than serial execution in terms of time of convergence, the transformation is an imperative necessity for an algorithm developed under the expression model.

3.3 Our execution model

We assume first that our algorithm is executing with the expression model and a central scheduler. The transformer is adopted then to allow our algorithm to function under other hypotheses.

In the literature, Hedetniemi et al. [6] have introduced an algorithm for MDS based on using In and Out states. To converge to the legitimate configuration, nodes move from In to Out or from Out to In until reaching stabilization. The authors use also a pointer for nodes out of S to determine nodes that have exactly one neighbor inside S. For nodes having more than a neighbor in S, the pointer is null. Figure 3 illustrates this additional process of pointing (node out S points its unique neighbor in S) in moves 2 and 3. This section aims to show how the expression model could simplify designing a new algorithm in the self-stabilization context. The expression model has the power to make abstraction on distance-2 in contrast to the habitual distance-1 model. It allows masking details like the above-mentioned process of pointing which is considered as an additional complication in proposing new algorithms. Using the expression distance-2 model, we propose an algorithm called MDSD2 to compute the minimal dominating set.

3.png

Figure 3. Convergence to the MDS using Hedetniemi algorithm [7]

4.png

Figure 4. Convergence to the MDS using expression distance-2 model

In Algorithm 2, each node v includes a local variable state and an expression exp. The state value can be either "In" or "Out", indicating whether a node is inside the dominating set. Once the system reaches a legitimate state, the set $S=\{v \in V: v$. state $=\operatorname{In}\}$ represents the dominating set. For the local expression exp, it calculates the number of neighbors in S of the current node. It helps to determine whether every node outside of S is dominated. Rule R1 guarantees that every node outside S must be dominated, otherwise, it moves any node outside of S that is not dominated from Out to In. In contrast, R2 aims to minimize the set S as small as possible. If a given node v inside S exits S so that S remains a dominating set, then R2 forces v to leave S. Note that before a node v decides to exit S, exp is used to ensure that all neighbors $u \in N_{V-S}(v)$ maintain the domination condition after v's departure. If it is determined that after v switches from In to Out, at least one neighbor $w \in N_{V-S}(v)$ would become undominated, and v cannot exit S. Figure 4 illustrates an example of the algorithm's execution converging to the minimal dominating set within 3 moves.

5.1 Closure

Lemma 4 The set S is a minimal dominating set when all nodes are inactivated.

Proof We demonstrate that (a) S is a dominating set and (b) S is minimal.

(a) Given that R1 is inactivated, it follows that for any node v outside of S, the local expression v.exp≥1. Consequently, every node v outside of S is dominated. Thus, S is a dominating set.

(b) We show that S is minimal by contradiction. Let's assume that all system nodes are inactive, and there exists a dominating set S₀ which is a subset of S such that S₀=S−{v}. Consequently, |N_S0(v)| ≥ 1 (since S₀ is a dominating set), implying that |N_S(v)|≥1 due to N_S0(v)=N_S(v). Since none of the S nodes is activated (R2 is not enabled for v) and v.exp ≥ 1, there exists a node u neighbor of v outside of S such that u.exp ≤ 1, leading to |N_S(u)|≤1. Also, since v is a neighbor of u and S₀=S−{v} thus |N_S0(u)|=|N_S(u)|−1. Hence |N_S0(u)|<1 due to |N_S(u)|≤1. This is a contradiction because every node outside of S₀ must be dominated.

5.2 Convergence and Complexity Analysis

Lemma 5 For every node w outside of S which is dominated (w.exp≥ 1), the value w.exp remains greater than or equal to 1 and cannot decrease below 1.

Proof Consider a node w outside of S with u.exp≥1. The value of u.exp may decrease if and only if any neighbor node v moves from inside to outside S. According to rule R2, when node v switches from inside to outside S, all neighbors u of v that are outside S have u.exp>1. Let’s denote S₂ as the new set of nodes with state=In after v is removed from S, therefore, |N_S2(u)|=|N_S(u)−1|. Consequently, |N_S(u)−1|≥1 implies |N_S2(u)|≥1, ensuring that u.exp remains ≥1 through recurrence.

Lemma 6 Once a node exits set S, it cannot return to S thereafter.

Proof As any node exits S has exp ≥1, R1 cannot be executed. Lemma 5 indicates that Rule R1 cannot be triggered again.

Lemma 7 Using the expression distance-2 model with the central daemon, if each node executes R1 followed by R2, algorithm 2 terminates in the worst case by executing 2n moves.

Proof The proof is evident according to Lemma 5 and Lemma 6.

Theorem 3 Using a central daemon and under the expression model, the self-stabilizing algorithm MDSD2 reaches the minimal dominating set in O(n) moves.

Proof According to Lemma 4 and Lemma 7, the proof is adopted.

In the following theorem, we employ the transformer of Turau [4] that provides an alternative self-stabilizing algorithm MDSD2^D which executes under a distributed daemon with the habitual distance-one model.

Theorem 4 Using a distributed daemon and under the distance-1 model, the self-stabilizing algorithm MDSD2^D computes the minimal dominating set and converges to the legitimate configuration within O(nm) moves.

Proof The proof is adopted according to Theorem 18 of Turau [4], where m is the number of edges in the graph.