<figure><img src="image_1.png" /></figure>

HAL
open science

# Luby's MIS Algorithms Made Self-Stabilizing

George Giakkoupis, Volker Turau, Isabella Ziccardi

► To cite this version:

George Giakkoupis, Volker Turau, Isabella Ziccardi. Luby's MIS Algorithms Made Self-Stabilizing. Information Processing Letters, 2025, 188, pp.106531. 10.1016/j.ipl.2024.106531. hal-05207077

HAL Id: hal-05207077

https://inria.hal.science/hal-05207077v1

Submitted on 12 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Luby's MIS Algorithms Made Self-Stabilizing

George Giakkoupis<sup>a</sup>, Volker Turau<sup>b</sup>, Isabella Ziccardi<sup>c</sup>

<sup>a</sup>Inria, Univ Rennes, CNRS, IRISA, Rennes, France

<sup>b</sup>Institute of Telematics, Hamburg University of Technology, Hamburg, Germany

<sup>c</sup>Bocconi University, Milan, Italy

## Abstract

We reconsider two well-known distributed randomized algorithms computing a maximal independent set, proposed in the seminal work of Luby (1986). We enhance these algorithms such that they become self-stabilizing without sacrificing their run-time, i.e., both stabilize in $O(\log n)$ synchronous rounds w.h.p. on any $n$-node graph. The first algorithm gets along with three states, but needs to know an upper bound on the maximum degree. The second does not need any information about the graph, but uses a number of states that is linear in the node degree. Both algorithms use messages of logarithmic size.

**Keywords:** Self-Stabilization, Fault Tolerance, Distributed Computing, Maximal Independent Set (MIS)

## 1. Introduction

A major challenge for large-scale systems is to handle fault recovery. One way to accommodate this challenge is by employing self-stabilizing algorithms [9, 10]. These algorithms guarantee that starting from an arbitrary state, the system will eventually reach a correct state, and it will stay in a correct state as long as no faults occur. Thus, the system can recover from transient faults without external intervention.

We consider the maximal independent set (MIS) problem—a fundamental problem in parallel and distributed computing. An MIS of a graph $G = (V, E)$ is a subset of vertices $I \subseteq V$, such that no two vertices in $I$ are adjacent to each other and $I$ is maximal with respect to inclusion. The significance of the problem was first recognised in the 80s, due to its importance in symmetry breaking [3, 20], and has been extensively studied ever since (see survey [7] for an overview of works until 2015, and [5, 13] for recent state-of-the-art results).

Several self-stabilizing MIS algorithms have been proposed. The first such algorithms were deterministic, relying on unique node IDs to break symmetry [15, 17, 23, 24]. All these algorithms used just a constant number

of states, and their stabilization time was $O(n)$ or larger, where $n$ is the number of nodes. Their notion of time varied depending on the model used: sequential, synchronous, or a more general adversarial distributed model (see [16] for a survey of models and results). Recently, Barenboime at al. [6] proposed the first sub-linear deterministic self-stabilizing synchronous MIS algorithm, stabilizing in $O(\Delta + \log^* n)$ rounds, where $\Delta$ is the maximum degree, using a number of states polynomial in $\Delta$.

A few randomized self-stabilizing MIS algorithms have also been proposed [1, 11, 14]. All of them assume very weak communication models, such as the beeping model [8]. An MIS algorithm for the beeping model proposed in [1] stabilizes in $O(\log^3 n)$ rounds w.h.p., using a polynomial number of states. A constant state algorithm for the beeping model, proposed in [14], was shown to stabilized in poly-logarithmic rounds w.h.p., but only for specific families of graphs. Finally, assuming a slightly stronger than the beeping communication model, a constant state algorithm proposed in [11] stabilizes in $O(\log^2 n)$ rounds w.h.p., on any constant-diameter graph.

Finally, non self-stabilizing MIS algorithms can be made self-stabilizing by using general schemes for trans-
forming non self-stabilizing synchronous algorithms to self-stabilizing ones [2, 4, 19]. However, these transformations may result in a significant growth in the run-time, the message size, or the number of states. In addition, they only work for deterministic algorithms.

In this paper, we present two new randomized self-stabilizing synchronous MIS algorithms, based on Luby's *MIS algorithms* [20]. Among the most elegant and well-known distributed graph algorithms, Luby's MIS algorithms were originally presented in the parallel (PRAM) model, but can be directly translated to distributed algorithms in the failure-free synchronous message-passing model (see, e.g., [21, 22]).

The self-stabilizing variants we propose maintain the run-time of the original algorithms, stabilizing in $O(\log n)$ rounds w.h.p. The first one uses a constant number of states, and requires an upper bound $\Delta'$ on the maximum degree $\Delta$. The second algorithm does not need any information about the graph, and uses a number of states that is linear in the node's degree. Both algorithms use messages of logarithmic size. Precisely, in the first algorithm messages have size $O(\log \Delta')$, and in the second they have size at most $O(\log \Delta)$.

Unlike the existing randomized self-stabilizing MIS algorithms [1, 11, 14], which assume a very week communication model but have super logarithmic stabilization times, the algorithms we propose assume a more powerful model but stabilize in logarithmic time.

## 2. Two Self-Stabilizing MIS Algorithms

The self-stabilizing MIS algorithms we propose, Algorithm 1 and Algorithm 2, operate in the synchronous message-passing model. In each synchronous round, all nodes in parallel: send messages to their neighbors, then read the incoming messages, and finally update their state. The network is anonymous, i.e., nodes do not have IDs, and execute the same code. For each node, both algorithms maintain a variable *status* that can assume values *active*, *in*, and *out*. This is the only state that Algorithm 1 needs to maintain from one round to the next, while Algorithm 2 uses an additional variable *d* (discussed later).

In both algorithms, starting from an arbitrary state, each node changes its status at most once after the second round. Active nodes try to enter the MIS in a contention-based style, and eventually nodes with status *in* form an

MIS and all other nodes have status *out*. Symmetry breaking between active nodes is based on random values, *r*, that active nodes generate independently in each round. In Algorithm 1, the generation of values *r* is governed by global parameter $\Delta'$, which is an upper bound on the maximum degree; while in Algorithm 2, it is governed by the number of active neighbors of each node. For that, Algorithm 2 must maintain an additional local variable *d* storing the number of active neighbors. Hence, in Algorithm 1 each node has three states, while in Algorithm 2 each node has a number of states linear in its degree.

Luby's MIS algorithms operate in phases of a fixed number of rounds. In Algorithms 1 and 2, we dispense with the idea of phases, since synchronizing the nodes would require diameter many rounds. This results in a 'stale information' problem, which manifests itself in two ways. The first one, which applies to both algorithms, is that a neighbor *u* of a node *v* joining the MIS in round *t* may prevent some other neighbor *w* of *u* from joining the MIS in round *t*, even though *u* will change its status to *out* in the next round, *t* + 1. The second problem, which applies only to Algorithm 2, is that variable *d* contains the number of active neighbors *from two rounds ago*, which may be much larger than the current number. Nevertheless, our refined analysis proves that both algorithms stabilize in $O(\log n)$ rounds w.h.p.

**Algorithms 1 and 2 are not silent:** All nodes in the MIS broadcast a single bit (zero) in each round, while all other nodes become silent eventually. It is easy to show that it is impossible to have a silent self-stabilizing MIS algorithm (for otherwise, we could initializing each node to a silent state such that the node is in the MIS).

*Notation.* Let $G = (V, E)$ be a graph with $n$ nodes. For each node $v \in V$, $N_G(v)$ denotes the set of neighbors of $v$ in $G$, and $\text{deg}_G(v) = |N_G(v)|$ is the degree of $v$. Also, for any set $X \subseteq V$, we define $N_G(X) = \bigcup_{v \in X} N_G(v)$. We will often omit subscript $G$ from these notations, when it is clear from the context. For $X \subseteq V$, $G[X]$ denotes the subgraph induced by $X$, and $E(X)$ is the set of edges of $G[X]$. By $E(v, X)$ we denote the set of edges incident to $v$ in graph $G[X]$.

For both Algorithms 1 and 2, we use the following notation. For each node $v$, each state variable $x$, and any $t \ge 0$, we denote by $v.x_t$ the value of variable $x$ of node $v$.
<caption>**Algorithm 1:** Self-stabilizing version of Luby's Algorithm A [20].</caption>

```text
state: status ∈ {in, out, active}

in each round t = 1, 2, ..., do
    if status = active then
        choose r uniformly at random from
        1, ..., 2Δ'
    else if status = in then r ← 0
    if status ∈ {active, in} then
        send message r to all neighbors
    receive messages sent by neighbors
    M ← set of received values of r
    update(M)

function update(M)
    if (status = in ∧ 0 ∈ M) ∨ (status = out ∧ 0 ∉ M)
        then status ← active
    else if status = active ∧ 0 ∈ M then
        status ← out
    else if status = active ∧ max(M ∪ {0}) < r then
        status ← in
```

at the end of round t,<fnref n="1" /> e.g., v.status_t. For non-state variables x, i.e., r and M, we write v.x_t, for t ≥ 1, to denote the variable's value during round t. For t ≥ 0, we let I_t = {v ∈ V: v.status_t = in} be the set of node with status in at the end of round t. Similarly, O_t and A_t are the sets of nodes of status out and active, respectively, at the end of round t. Clearly, V = I_t ∪ O_t ∪ A_t. By $\mathcal{F}_t$ we denote the filtration of the execution process up to the end of round t. This includes the initial states of nodes, and their random choices in each round r ∈ {1, ..., t}. Thus, from $\mathcal{F}_t$ we can compute the state of every nodes after each round r.

## 2.1. Algorithm 1

The first self-stabilizing MIS algorithm we propose, Algorithm 1, is an adaptation of parallel Algorithm A proposed by Luby in [20] (see also LubyMIS algorithm described by Lynch [21] in the synchronous message-

passing model). Algorithm A of [20] (adapted to the message-passing model) operates in phases of three rounds: In the first round each active node samples a uniformly random number $r$ from a large enough range, then it broadcasts $r$ to its active neighbors, and if its $r$ value is larger than those of its neighbors' then it joins the MIS. In the second round nodes that have just joined the MIS inform their active neighbors, which remove themselves from the competition. In the third round newly removed nodes inform their neighbors, so that the remaining active nodes know which of their neighbors are still active. Technically, the third round is not necessary, it just reduces the number of messages. All node are active initially.

The range from which uniformly random values $r$ were sampled in Algorithm A [20] was chosen for convenience to be $\{1, ..., n^4\}$. We observe that it suffices to use a range of linear size in the maximum degree $\Delta$ (or in an upper bound $\Delta'$ of $\Delta$).

Algorithm 1 does not have phases, and nodes that have joined the MIS signal this in every future round by broadcasting special value 0. Thus, one round later, active nodes know if any of their neighbors are in the MIS, in which case they change their status to out and remain silent in future rounds. As mentioned earlier, this one-round delay complicates the analysis. Besides that, any inconsistencies, i.e., adjacent nodes of status in, or nodes of status out without neighbors in status in, are resolved in the first round (see the first case of update() procedure).

**Lemma 1.** Let $v \in V$.

(a) For any $t \ge 1$, if $v \in I_t$ then $v \in I_{t+1}$ and $w \in O_{t+1}$ for all $w \in N(v)$.

(b) For any $t \ge 2$, if $v \in O_t$ then $v \in O_{t+1}$ and $w \in I_{t-1}$ for some $w \in N(v)$.

*Proof.* From the algorithm, for any $t \ge 0$, (i) if $v \in I_t$ and $w \notin I_t$ for all $w \in N(v)$ then $v \in I_{t+1}$; (ii) if $v \in I_t$ and $w \in I_t$ for some $w \in N(v)$ then $v \in A_{t+1}$; (iii) if $v \notin I_t$ and $w \in I_t$ for some $w \in N(v)$ then $v \in O_{t+1}$. Also, (iv) if $v \notin I_t$ and $v \in I_{t+1}$ then $w \notin I_{t+1}$ for all $w \in N(v)$, because $v \in A_t$ and $w \notin I_t$ for all $w \in N(v)$ and $v \in I_{t+1} > w \in I_{t+1}$ for all $w \in N(v) \cap A_t$, thus no $w \in N(v) \cap A_t$ can change its status to in in the same round, $t+1$.

Let $t \ge 1$ and suppose that $v \in I_t$. If $v \in I_{t-1}$ then from (ii), $w \notin I_{t-1}$ for all $w \in N(v)$, and from (iii), $w \in O_t$ for

<footnote n="1">¹The ‘end of round 0’ refers to the initial configuration, before the first round.</footnote>
all $w \in \mathcal{N}(v)$. Applying (i) and again (iii) gives $v \in I_{t+1}$ and $w \in O_{t+1}$ for all $w \in \mathcal{N}(v)$.

If $v \in I_t$ but $v \notin I_{t-1}$ then from (iv), $w \notin I_t$ for all $w \in \mathcal{N}(v)$. Then, as before, (i) gives $v \in I_{t+1}$, and (iii) gives $w \in O_{t+1}$ for all $w \in \mathcal{N}(v)$.

Next let $t \ge 2$ and suppose that $v \in O_t$. Then, from the algorithm, $w \in I_{t-1}$ for some $w \in \mathcal{N}(v)$, and since $t-1 \ge 1$ part (a) applied twice gives $v \in O_{t+1}$. $\square$

The following corollary can be readily deduced from Lemma 1.

**Corollary 2.** Let $t \ge 2$. Then $I_{t-1} \subseteq I_t$, $O_t \subseteq O_{t+1}$, $A_{t+1} \subseteq A_t$, and $O_t = N(I_{t-1})$. Also, if $A_t = \emptyset$ then $I_t$ is an MIS.

**Theorem 3.** Algorithm 1 computes an MIS in $O(\log n)$ rounds w.h.p.

*Proof.* Let $G_t = G[A_t]$ be the subgraph of $G$ induced by $A_t$, and $E_t = E(A_t)$ be its set of edges. We will write $N_t(v)$ and $d_t(v)$ to denote $N_{G_t}(v)$ and $\deg_{G_t}(v)$, respectively. Note that, by Corollary 2, $E_{t+1} \subseteq E_t$ for $t \ge 2$.

We prove that for all $t \ge 2$,

$$ \mathbb{E} [|E_t \setminus E_{t+2}| | \mathcal{F}_t] \ge e^{-1} \cdot |E_t|/2. $$

Let $X_t = A_t \cap N(I_t)$ and $Y_t = A_t \setminus N(I_t)$. We use the idea of preemptive removal from [22], which we adapt to the current setting. For each $v \in Y_t$ and $u \in N(v) \cap Y_t$, we say that v preemptively removes u in round $t+1$, if $v \cdot r_{t+1} > w \cdot r_{t+1}$ for all $w \in N_t(v) \cup N_t(u) \setminus \{v\}$. Clearly, a node $u \in Y_t$ is preemptively removed by at most one neighbor in round $t+1$ (by definition only neighbors $v \in Y_t$ may preemptively remove u). If v preemptively removes u in round $t+1$ then $v \in I_{t+1}$, thus $u \in O_{t+2}$ and for all $w \in \mathcal{N}(u)$ edge $\{u, w\}$ is not in $E_{t+2}$. Therefore, an edge $\{v, u\} \in E_t$ is not in $E_{t+2}$, if at least one of $u, v$ belongs to $Y_t$ and is preemptively removed in round $t+1$, or at least one of $u, v$ belongs to $X_t$, since $X_t \subseteq N(I_t) = O_{t+1} \subseteq O_{t+2}$ by Corollary 2.

Next we compute the probability that v preemptively removes u in round $t+1$, for any given nodes $v \in Y_t$ and $u \in N(v) \cap Y_t$. The probability that $v \cdot r_{t+1} \ne w \cdot r_{t+1}$ for all $w \in N_t(v) \cup N_t(u) \setminus \{v\}$ is at least

$$ \left( \frac{2\Delta' - 1}{2\Delta'} \right)^{d_t(v)+d_t(u)-1} \ge \left( \frac{2\Delta' - 1}{2\Delta'} \right)^{2\Delta'-1} \ge e^{-1}. $$

And given that this holds, the conditional probability that $v \cdot r_{t+1}$ is the largest among these values is at least $1/(d_t(v) + d_t(u))$, due to symmetry and because there at most $d_t(v) + d_t(u)$ distinct values. Therefore, the probability that v preemptively removes u in round $t+1$ is at least $e^{-1}/(d_t(v) + d_t(u))$.

Recall now that $\{v, u\} \in E_t \setminus E_{t+2}$ if u or v either belongs to $Y_t$ and is preemptively removed in round $t+1$, or belongs to $X_t$. Since this condition may hold simultaneously for both endpoints u and v, we obtain that $2 \cdot \mathbb{E} [|E_t \setminus E_{t+2}| | \mathcal{F}_t]$ is at least

$$ \sum_{v \in Y_t} \sum_{u \in N(v) \cap Y_t} \frac{e^{-1} \cdot d_t(v)}{d_t(v) + d_t(u)} + \sum_{v \in X_t} d_t(v) = \\ \sum_{\{v, u\} \in E_t, v, u \in Y_t} \left( \frac{e^{-1} \cdot d_t(v)}{d_t(v) + d_t(u)} + \frac{e^{-1} \cdot d_t(u)}{d_t(v) + d_t(u)} \right) + \\ \sum_{\{v, u\} \in E_t, v, u \in X_t} 1 + \sum_{\{v, u\} \in E_t, v, u \in X_t} 2 \ge \sum_{\{v, u\} \in E_t} e^{-1} = e^{-1} \cdot |E_t| $$

Therefore, $\mathbb{E} [|E_t \setminus E_{t+2}| | \mathcal{F}_t] \ge e^{-1} \cdot |E_t|/2$, as desired.

It follows $\mathbb{E} [|E_{t+2}|] \le \delta \cdot \mathbb{E} [|E_t|]$, where $\delta = 1 - 1/(2e)$. Applying this inequality repeatedly, we obtain for any even $t \ge 2$ that $\mathbb{E} [|E_t|] \le \delta^{t/2-1} \cdot |E|$. Choosing $t = O(\log(n \cdot |E|)/\log \delta) = O(\log n)$ large enough, we obtain that $\mathbb{E} [|E_t|] \le 1/\text{poly}(n)$, and Markov's inequality yields that w.h.p. $|E_t| = 0$ and thus $A_{t+1} = \emptyset$, where the extra round deals with any isolated nodes left in $G_t$. The theorem then follows by applying Corollary 2. $\square$

## 2.2. Algorithm 2

The second self-stabilizing MIS algorithm, Algorithm 2, is based on parallel Algorithm B proposed by Luby in [20] (a similar algorithm was proposed independently by Alon, Babai, and Itai [3]). Algorithm B of [20] (adapted to the message-passing model) operates in phases of three rounds, similarly to Algorithm A of [20] described in Section 2.1. In the first round, each active node v samples a random bit b that is 1 with probability $1/\max\{2d, 1\}$, where d is the number of active neighbors of v, and broadcasts b to those neighbors along with d; if b = 1 and for every active neighbor v' of v, its bit b' and active neighbor count d' satisfy b' = 0 or d' < d, then v enters the MIS. The second and third rounds of a
**Algorithm 2:** Self-stabilizing version of Luby's Algorithm B [20]

state: status ∈ {in, out, active},
d ∈ {0, 1, ..., deg(v)}
in each round t = 1, 2, ... do
| if status = active then
| r ← d + 1 with probability 1 / (max{2d, 1}) and
| r ← 1 otherwise
| else if status = in then r ← 0
| if status ∈ {active, in} then
|   send message r to all neighbors
|   receive messages sent by neighbors
|   M ← set of messages received
|   d ← number of non-zero messages received
|   update(M) // function of Algorithm 1

phase are identical to those of Algorithm A [20]: newly
added nodes to MIS inform their neighbors to remove
themselves from the competition, and then removed nodes
notify their neighbors. Unlike in Algorithm A, however,
the third round is essential as it allows an active node v
to update variable d to the current number of its active
neighbors.

Algorithm 2 does not use phases. Also, instead of sending pair b, d, each active node broadcasts a single value r = 1 + b · d; and each node with status in broadcasts the special value 0 similarly to Algorithm 1. The same update() procedure is used in both algorithms. An additional complication we have to deal with in the analysis of Algorithm 2 is that, at the beginning of round t, variable d does not contain the current number of active neighbors (i.e., the number at the end of round t − 1), but rather the number at the end of round t − 2.

Lemma 1 and Corollary 2 only rely on the function
update(), thus they hold for Algorithm 2 as well. From
the algorithm it is also immediate that for any node v and
round $t \ge 1$,

$v.d_t = |N(v) \cap A_{t-1}|.$

Next we bound the stabilization time. We start with a
lemma which lower bounds the probability that at least
one node from a given set Z ⊆ A_t \ N(I_t) changes its status
from active to in in round t + 1. A similar lemma was

shown in [20, Lemma B].

**Lemma 4.** Let $t \ge 3$, and let $Z \subseteq V$ be a non-empty set. If $Z \subseteq A_t \setminus N(I_t)$ then

$$
\mathbb{P}[Z \cap I_{t+1} \neq \emptyset | \mathcal{F}_t] \geq \frac{1}{4} \min \left\{ 1, \sum_{v \in Z} \frac{1}{\max\{1, 2v \cdot d_t\}} \right\}.
$$

Proof. We fix the execution up to the end of round $t$, so we do not have to condition probabilities on $\mathcal{F}_t$. Let $Z = \{v_1, \dots, v_Z\}$, and for each $1 \le i \le |Z|$, let $k_i = v_i \cdot d_i = |N(v_i) \cap A_{t-1}|$.

We argue that $k_i \neq 0$ for all $1 \le i \le |Z|$: Since $v_i \in A_t$ we have also $v_i \in A_{t-1}$, because $A_t \subseteq A_{t-1}$ for $t \ge 3$ by Corollary 2. Suppose that $k_i = 0$. Then $N(v_i) \cap A_{t-1} = \emptyset$ and thus $v.M_t = \emptyset$ or $\{0\}$. In either case, since $v_i \in A_{t-1}$ it follows from the update() function that $v_i \notin A_t$, which contradicts the definition of Z. Thus $k_i \neq 0$.

Let $\mathcal{E}$ be the event that $v.r_{t+1} > 1$ for some $v \in Z$. Then

$$
\begin{align}
\mathbb{P}[\mathcal{E}] &= 1 - \prod_{1 \le i \le |Z|} \left(1 - \frac{1}{2k_i}\right) \ge 1 - e^{-\sum_{1 \le i \le |Z|} \frac{1}{2k_i}} \tag{1} \\
&\ge \frac{1}{2} \min \left\{ 1, \sum_{1 \le i \le |Z|} \frac{1}{2k_i} \right\}, \nonumber
\end{align}
$$

where in the first equality we used $v_i \cdot d_t = k_i \neq 0$, and in
the last inequality we used $e^{-x} \le 1 - x/2$ for $0 \le x \le 1$.

For $1 \le i \le |Z|$, let $\mathcal{E}_i$ be the event that $v_i \cdot r_{t+1} = \dots = v_{i-1} \cdot r_{t+1} = 1$ and $v_i \cdot r_{t+1} > 1$. Then $\mathcal{E} = \bigcup_{1 \le i \le |Z|} \mathcal{E}_i$, and $\mathbb{P}[\mathcal{E}] = \sum_{1 \le i \le |Z|} \mathbb{P}[\mathcal{E}_i]$.

Consider the case that event $\mathcal{E}_i$ occurs. For every $w \in N(v_i) \cap A_t$, either $w \cdot r_{t+1} = 1$ or $w \cdot r_{t+1} = 1 + w \cdot d_t$. Let $U_i = \{w \in N(v_i) \cap A_t : w \cdot d_t \ge k_i\}$. Then, $v_i \in I_{t+1}$ if $w \cdot r_{t+1} = 1$ for all $w \in U_i$, because then $v_i \cdot r_{t+1} = 1 + k_i > w \cdot r_{t+1}$ for all $w \in N(v_i) \cap A_t$, and since $v_i \in A_t \setminus N(I_t)$ the last if-case of update() applies, implying $v_i \in I_{t+1}$. Therefore,

$$
\mathbb{P}[v_i \in I_{t+1} | \mathcal{E}_i] = \mathbb{P} \left[ \bigwedge_{w \in U_i} w \cdot r_{t+1} = 1 \middle| \mathcal{E}_i \right].
$$

We have $|U_i| \le |N(v_i) \cap A_t| \le |N(v_i) \cap A_{t-1}| = v_i \cdot d_t = k_i$,
and for each $w \in U_i \setminus \{v_1, \dots, v_{i-1}\}$ the probability that
$w \cdot r_{t+1} = 1$ is $1 - \frac{1}{2w \cdot d_t} \ge 1 - \frac{1}{2k_i}$, while $v_j \cdot r_{t+1} = 1$ for $j < i$.
It follows

$$
\mathbb{P}[v_i \in I_{t+1} | \mathcal{E}_i] \ge \left(1 - \frac{1}{2k_i}\right)^{k_i} \ge 4^{-\frac{1}{2k_i}} k_i = \frac{1}{2},
$$
where in the second inequality we used that $1 - x \ge 4^{-x}$ when $x \le 1/2$.

Finally, since the events $\mathcal{E}_i$ are disjoint,

$$ 
\begin{aligned}
\mathbb{P}[Z \cap I_{t+1} \neq \emptyset] &\geq \sum_{1 \leq i \leq |Z|} \mathbb{P}[Z \cap I_{t+1} \neq \emptyset | \mathcal{E}_i] \cdot \mathbb{P}[\mathcal{E}_i] \\
&\geq \sum_{1 \leq i \leq |Z|} \mathbb{P}[v_i \in I_{t+1} | \mathcal{E}_i] \cdot \mathbb{P}[\mathcal{E}_i] \\
&\geq \sum_{1 \leq i \leq |Z|} \frac{1}{2} \cdot \mathbb{P}[\mathcal{E}_i] \\
&= \frac{1}{2} \cdot \mathbb{P}[\mathcal{E}].
\end{aligned}
$$

Combining this and (1) completes the proof. □

We use the definition of good nodes and edges from [3].

**Definition 5** (Good Nodes & Edges). Let $H = (V_H, E_H)$ be a graph. A node $v \in V_H$ of $H$ is good if

$$ |\{u \in N_H(v) : \deg_H(u) \le \deg_H(v)\}| > \deg_H(v)/3, $$

i.e., the degree of more than 1/3 of v's neighbors is smaller or equal to the degree of v. An edge $\{v, u\} \in E_H$ is good if at least one of v and u is a good node.

**Lemma 6** ([3, Lemma 4.4]). At least half of the edges in any graph are good edges.

Recall that for $X \subseteq V$, $G[X] = (X, E(X))$ is an induced subgraph of $G$. Next we show that at least a constant fraction of the edges incident to a good node $v$ of $G[A_{t-1} \setminus I_t]$ are not present in $G[A_{t+1} \setminus N(I_{t+1})]$.

**Lemma 7.** Let $t \ge 3$, and for any $s \ge 1$ let

$$ X_s = A_{s-1} \setminus I_s, \quad Y_s = A_s \setminus N(I_s). $$

If $v$ is a good node of $G[X_t]$, the expected number of its incident edges $\{v, u\} \in E(X_t)$ not belonging to $E(Y_{t+1})$ is

$$ \mathbb{E}[|E(v, X_t) \setminus E(Y_{t+1})| | \mathcal{F}_t] \ge |E(v, X_t)|/30. $$

*Proof.* Let $k = |E(v, X_t)| = |N(v) \cap X_t|$ be the number of neighbors of $v$ in $G[X_t]$. The statement is obviously true if $k = 0$, so we assume $k \ne 0$.

If the number of $v$'s neighbors in $G[X_t]$ belonging to $N(I_t)$ is at least $k/30$, i.e., $|N(v) \cap X_t \cap N(I_t)| \ge k/30$, then

using that $N(I_t) \cap Y_{t+1} \subseteq N(I_t) \cap A_{t+1} = O_{t+1} \cap A_{t+1} = \emptyset$ (by Corollary 2), we obtain

$$ |E(v, X_t) \setminus E(Y_{t+1})| \ge |N(v) \cap X_t \cap N(I_t)| \ge k/30. $$

This implies the lemma.

It remains the case $|N(v) \cap X_t \cap N(I_t)| < k/30$. Let

$$ Z = \{u \in N(v) \cap X_t \setminus N(I_t) : |N(u) \cap X_t| \le k\}. $$

Since $v$ is a good node in $G[X_t]$, at least $k/3$ of $v$'s neighbors in $G[X_t]$ have degree at most $k$, and among these, at least $k/3 - k/30 = 3k/10$ are not in $N(I_t)$. Thus

$$ |Z| \ge 3k/10. $$

Also

$$ Z \subseteq A_t \setminus N(I_t), $$

because $Z \subseteq X_t \setminus N(I_t)$ and

$$ 
\begin{aligned}
(X_t \setminus N(I_t)) \setminus (A_t \setminus N(I_t)) &= (X_t \setminus A_t) \setminus N(I_t) \\
&= (A_{t-1} \setminus (I_t \cup A_t)) \setminus N(I_t) \subseteq O_t \setminus N(I_t) = \emptyset,
\end{aligned}
$$

where in the last equation we used $N(I_t) = O_{t+1} \supseteq O_t$, by Corollary 2. Last, if $u \in Z$, then $u \notin N(I_t)$, which implies $N(u) \cap I_t = \emptyset$, and thus $N(u) \cap A_{t-1} = N(u) \cap A_{t-1} \setminus I_t = N(u) \cap X_t$. Hence, if $u \in Z$,

$$ u \cdot d_t = |N(u) \cap A_{t-1}| = |N(u) \cap X_t| \le k, $$

by the definition of $Z$.

We can now apply Lemma 4 to obtain

$$ \mathbb{P}[Z \cap I_{t+1} \neq \emptyset | \mathcal{F}_t] \ge \frac{1}{4} \min \left\{ 1, \frac{3k}{10} \cdot \frac{1}{2k} \right\} = \frac{3}{80} > \frac{1}{30}. $$

If $Z \cap I_{t+1} \neq \emptyset$, then $v \in N(I_{t+1})$, and thus $v \notin Y_{t+1}$ and $|E(v, X_t) \setminus E(Y_{t+1})| = E(v, X_t)$. It follows that

$$ \mathbb{E}[|E(v, X_t) \setminus E(Y_{t+1})| | \mathcal{F}_t] \ge \frac{1}{30} \cdot |E(v, X_t)|. \quad \square $$

We are now ready to prove the main statement.

**Theorem 8.** *Algorithm 2 computes an MIS in $O(\log n)$ rounds w.h.p.*
*Proof.* Define $X_t = A_{t-1} \setminus I_t$ and $Y_t = A_t \setminus N(I_t)$, as in Lemma 7, and let $X_t^g \subseteq X_t$ and $E^g(X_t) \subseteq E(X_t)$ be the set of good nodes and the set of good edges of graph $G[X_t]$, respectively. Let $t \ge 3$. The expected number of edges in $E(X_t)$ not belonging to $E(Y_{t+1})$ is

$$ 
\begin{aligned}
\mathbb{E}[|E(X_t) \setminus E(Y_{t+1})| | \mathcal{F}_t] &= \frac{1}{2} \sum_{v \in X_t} \mathbb{E}[|E(v, X_t) \setminus E(Y_{t+1})| | \mathcal{F}_t] \\
&\ge \frac{1}{2} \sum_{v \in X_t^g} \mathbb{E}[|E(v, X_t) \setminus E(Y_{t+1})| | \mathcal{F}_t] \\
&\ge \sum_{v \in X_t^g} |E(v, X_t)|/60 \\
&\ge |E^g(X_t)|/120 \\
&\ge |E(X_t)|/240,
\end{aligned}
$$

where in the third line we used Lemma 7, and in the last we used Lemma 6. It follows

$$ \mathbb{E}[|E(X_t) \setminus E(Y_{t+1})|] \ge \mathbb{E}[|E(X_t)|]/240. $$

From this and $E(Y_{t+1}) \subseteq E(X_t)$, which holds because $Y_{t+1} \subseteq A_{t+1} \subseteq A_t = A_t \setminus I_t \subseteq A_{t-1} \setminus I_t = X_t$, we obtain

$$ \mathbb{E}[|E(Y_{t+1})|] \le (239/240) \cdot \mathbb{E}[|E(X_t)|]. $$

This further implies

$$ \mathbb{E}[|E(A_{t+2})|] \le (239/240) \cdot \mathbb{E}[|E(A_{t-1})|], $$

since $Y_{t+1} \supseteq A_{t+2} \setminus N(I_{t+1}) = A_{t+2} \setminus O_{t+2} = A_{t+2}$, and $X_t \subseteq A_{t-1}$. Finally, applying repeatedly the last inequality above and using Markov's inequality, similarly to the proof of Theorem 3, we obtain that $|A_t| = 0$ w.h.p. for $t = O(\log n)$ large enough; and the theorem follows from Corollary 2. □

### 3. Conclusion

In this paper, we presented synchronous self-stabilizing variants of Luby's celebrated MIS algorithms.<fnref n="2" /> Jeavon et al. [18] and independently Ghaffari [12] proposed an elegant MIS algorithm for the beeping model that completes

in $O(\log n)$ rounds w.h.p. We believe that this algorithm can also be made self-stabilizing, maintaining its logarithmic run-time, if nodes have access to a rough upper bound on the maximum degree $\Delta$ that is at most poly(n).

### References

[1] Y. Afek, N. Alon, Z. Bar-Joseph, A. Cornejo, B. Haeupler, and F. Kuhn. Beeping a maximal independent set. *Distributed Comput.*, 26(4):195–208, 2013. doi:10.1007/s00446-012-0175-7.

[2] Y. Afek and S. Dolev. Local stabilizer. *J. Parallel Distributed Comput.*, 62(5):745–765, 2002. doi:10.1006/JPDC.2001.1823.

[3] N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. *J. Algorithms*, 7(4):567–583, 1986. doi:10.1016/0196-6774(86)90019-2.

[4] B. Awerbuch and G. Varghese. Distributed program checking: A paradigm for building self-stabilizing distributed protocols. In *Proc. IEEE Symp. on Foundations of Computer Science, FOCS*, pages 258–267, 1991. doi:10.1109/SFCS.1991.185377.

[5] A. Balliu, S. Brandt, J. Hirvonen, D. Olivetti, M. Rabie, and J. Suomela. Lower bounds for maximal matchings and maximal independent sets. *J. ACM*, 68(5):39:1–39:30, 2021. doi:10.1145/3461458.

[6] L. Barenboim, M. Elkin, and U. Goldenberg. Locally-Iterative distributed ($\Delta + 1$)-coloring and applications. *J. ACM*, 69(1):5:1–5:26, 2022. doi:10.1145/3486625.

[7] L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. *J. ACM*, 63(3):20:1–20:45, 2016. doi:10.1145/2903137.

[8] A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In *Proc. Int. Symp. on Distributed Computing*, DISC, pages 148–162, 2010. doi:10.1007/978-3-642-15763-9\_15.

[9] E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. *Commun. ACM*, 17(11):643–644, 1974. doi:10.1145/361179.361202.

[10] S. Dolev. *Self-Stabilization*. MIT Press, 2000.

[11] Y. Emek and E. Keren. A thin self-stabilizing asynchronous unison algorithm with applications to fault tolerant biological networks. In *Proc. ACM Symp. on Principles of Distributed Computing*, PODC, pages 93–102, 2021. doi:10.1145/3465084.3467922.

<footnote n="2">²Luby was awarded the 2016 Dijkstra Prize in Distributed Computing for his paper [20].</footnote>
[12] M. Ghaffari. Distributed MIS via All-to-All communication. In *Proc. ACM Symp. on Principles of Distributed Computing, PODC*, pages 141–149, 2017. doi:10.1145/3087801.3087830.

[13] M. Ghaffari, C. Grunau, and V. Rozhon. Improved deterministic network decomposition. In *Proc. ACM-SIAM Symp. on Discrete Algorithms, SODA*, pages 2904–2923, 2021. doi:10.1137/1.9781611976465.173.

[14] G. Giakkoupis and I. Ziccardi. Distributed self-stabilizing MIS with few states and weak communication. In *Proc. ACM Symp. on Principles of Distributed Computing, PODC*, pages 310–320, 2023. doi:10.1145/3583668.3594581.

[15] W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani. Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks. In *Proc. Int. Parallel and Distributed Processing Symp., IPDPS*, page 162, 2003. doi:10.1109/IPDPS.2003.1213302.

[16] N. Guellati and H. Kheddouci. A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. *J. Parallel Distributed Comput.*, 70(4):406–415, 2010. doi:10.1016/j.jpdc.2009.11.006.

[17] M. Ikeda, S. Kamei, and H. Kakugawa. A space-optimal self-stabilizing algorithm for the maximal independent set problem. In *Proc. Int. Conf. on Parallel and Distributed Computing, Applications and Technologies, PD-CAT*, pages 70–74, 2002.

[18] P. Jeavons, A. Scott, and L. Xu. Feedback from nature: Simple randomised distributed algorithms for maximal independent set selection and greedy colouring. *Distributed Comput.*, 29(5):377–393, 2016. doi:10.1007/s00446-016-0269-8.

[19] C. Lenzen, J. Suomela, and R. Wattenhofer. Local algorithms: Self-stabilization on speed. In *Proc. Int. Symp. on Stabilization, Safety, and Security of Distributed Systems*, pages 17–34, 2009. doi:10.1007/978-3-642-05118-0_2.

[20] M. Luby. A simple parallel algorithm for the maximal independent set problem. *SIAM J. Comput.*, 15(4):1036–1053, 1986. doi:10.1137/0215074.

[21] N. A. Lynch. *Distributed Algorithms*. Morgan Kaufmann, 1996.

[22] Y. Métivier, J. M. Robson, N. Saheb-Djahromi, and A. Zemmari. An optimal bit complexity randomized distributed MIS algorithm. *Distributed Comput.*, 23(5-6):331–340, 2011. doi:10.1007/s00446-010-0121-5.

[23] S. K. Shukla, D. J. Rosenkrantz, and S. S. Ravi. Observations on self-stabilizing graph algorithms for anonymous networks. In *Proc. Workshop on Self-Stabilizing Systems, SSS*, 1995.

[24] V. Turau. Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler. *Inf. Process. Lett.*, 103(3):88–93, 2007. doi:10.1016/j.ipl.2007.02.013.