Self-Stabilizing Fully Adaptive Maximal Matching

Consider a distributed algorithm $\mathrm{𝙰𝚕𝚐}$ running on a message passing communication network represented as a simple undirected graph $G=(V,E)$. Under $\mathrm{𝙰𝚕𝚐}$, the nodes operate in synchronous rounds so that in each round $t\in {\mathbb{Z}}_{\ge 0}$, every node $v\in V$ executes the following operations: (1) $v$ performs local computation that includes reading from and writing to its registers; (2) $v$ sends messages to (a subset of) its neighbors; and (3) $v$ receives the messages sent to it by its neighbors in round $t$. Round $t$ is assumed to span the time interval $[t,t+1)$ so that time $t$ marks the beginning of the round. The configuration of $\mathrm{𝙰𝚕𝚐}$ at time $t$ is an abstract object that encodes the content of all nodes’ registers at that time.

Let $N(v)$ be the set of neighbors of a node $v\in V$ and let $\mathrm{d}(v)=|N(v)|$ be its degree. We adhere to the conventions of the port numbering model of distributed graph algorithms where each node $v\in V$ is associated with an (arbitrarily chosen) port bijection $p_v:[\mathrm{d}(v)]\to N(v)$ so that from $v$’s perspective, node $p_v(i)$ is referred to as neighbor $i$ for each $i\in [\mathrm{d}(v)]$. Assuming that $p_v(i)=u$ and $p_u(j)=v$, when $v$ (resp., $u$) sends a message to its neighbor $i$ (resp., $j$), this message is written into a designated port register ${\pi }_u(j)$ (resp., ${\pi }_v(i)$) that $u$ (resp., $v$) can read during the local computation step of the subsequent round. We do not assume that $v$ (resp., $u$) knows anything about the identity of its neighbor $i$ (resp., $j$) otherwise. In fact, in the current paper, we focus on uniform algorithms, namely, the nodes do not have unique identifiers, nor do they hold any global knowledge of the graph $G$ (including its size).

Our main contribution is cast in the following theorem.

The reader may have noticed that the guarantees of our algorithm do not depend in any way on the size of the graph $G$. Indeed, Theorem 1.1 holds also for infinite graphs as long as the node degrees are finite (though not necessarily bounded).²²2In infinite graphs, the notion of fully adaptive run-time can be extended to support an infinite number of manipulations as long as the manipulated nodes can be partitioned into clusters of size at most $k$ which are sufficiently far away from each other. We believe that distributed computation in infinite graphs is a fascinating research domain and advocate using the notion of (fully) adaptive run-time as a natural complexity measure when it comes to self-stabilizing algorithms in this domain.

As established in [48], any uniform (non-self-stabilizing) distributed MM algorithm with constant size messages requires $\mathrm{\Omega }(\log n)$ time in expectation when running on rings (and paths) of size $n$. This implies that any uniform self-stabilizing MM algorithm with constant size messages requires $\mathrm{\Omega }(\log k)$ time in expectation to stabilize from $k\le n$ transient faults, which means that the fully adaptive run-time bound promised in Thm. 1.1 is asymptotically optimal.

Self-stabilizing symmetry breaking is an extensively studied research topic, see, e.g., [38] for a survey. In particular, there is a long line of works on self-stabilizing algorithms for maximal matching (and closely related problems) [42, 64, 21, 22, 40, 37, 35, 36, 57, 58, 63, 7, 46, 24, 5, 43, 65, 15]. Under synchronous schedules (assumed in the current paper), the state-of-the-art MM self-stabilization run-time upper bounds are $O(\log n)$, obtained by the (randomized uniform) algorithm of Turau [65], and $O(\mathrm{\Delta }+{\log }^{\ast }n)$, obtained by the (deterministic non-uniform) algorithm of Barenboim et al. [15], where $n$ is the number of nodes in the graph and $\mathrm{\Delta }$ is its maximum degree. Notice that those run-time upper bounds are not fully adaptive.

The MM problem received a lot of attention also in the literature on fault free (non-self-stabilizing) distributed graph algorithms, see, e.g., [45, 44, 54, 39, 61, 16, 32, 30, 12, 33]. Some of the algorithmic ideas in the current paper are inspired by ideas originated in that literature, e.g., [44]. Another source of inspiration is the algorithm of [66] for the related task of approximating maximum matching.

The self-stabilizing research community has a special interest in generic transformers that translate non-self-stabilizing algorithms into self-stabilizing ones, see, e.g., [10, 8, 9, 2, 1, 53, 13]. None of the existing transformers though can produce self-stabilizing algorithms that use constant size messages and run in sub-diameter time (as the algorithm developed in the current paper does). Moreover, with the exception of the transformer presented in the full version [18], none of the existing transformers (provably) guarantees a fully adaptive stabilization run-time, regardless of the graph’s size and diameter or any probabilistic assumption on the distribution of faults.

There has been a lot of interest in saving run-time in dynamic models by adapting to the actual load on the algorithm. In the non-self-stabilizing computing context, Lamport suggested that an algorithm should benefit from the common case where the number of contending processes is small [52]. A maximum matching approximation can be mended following a single topological change in constant distributed time [55]. A distributed algorithm that mends a maximal independent set after a single change in constant time was presented in [20]. Mending other local functions in a similar setting, also in constant distributed time, was addressed in [47]. Mending after a small number of changes was addressed in [59]. In the context of distributed fault tolerance, a similar motivation stands behind the notions of obstruction freedom [41].

In highly dynamic graphs, mending of various functions has been treated recently [14, 19]. Comparing these papers to the current one, their algorithms are not self-stabilizing. Moreover, the authors of [19] optimize the amortized time complexity (vs. the worst case time complexity used in the current paper) assuming that the graph is initially empty, whereas the run-time of the algorithm of [14] is expressed as a (logarithmic) function of $n$ rather than $k$ (so it is not adaptive). Both papers rely on messages of super-constant size.

For non-distributed algorithms, the area of dynamic algorithms started with addressing algorithms that already computed a complete and correct output (say a minimum spanning tree [31]) and need to mend the output following a single change to the input. A non-distributed update of MM in dynamic graphs for the deletion or the removal of a single edge is performed in amortized (expected) $O(\log n)$ time [17] or worst case (deterministic) $O(\sqrt{m})$ time, where $m$ denotes the number of edges [60].

In the context of self stabilization, the notion of super-stabilization [28] is concerned with decreasing the impact of topological changes on the complexity of self-stabilizing algorithms and the notion of containment [34] has been used to ensure that if only a single fault occurred, then the complexity is smaller than in the general fault case. For the maximal independent set problem, multiple simultaneous changes to the input were handled in [50] assuming a model that is only partially self-stabilizing (the adversary may change the data structure, but not other registers, e.g., the program counter). Moreover, while the run-time measure there is adaptive, expressed as a function of the number $k$ of faults, it is not fully adaptive since all the faults are assumed to occur in a single batch before the mending starts. In contrast, the run-time analysis in the current paper is fully adaptive in the sense that it allows the adversary to divide the $k$ faults (and/or topology changes) over multiple batches.

Algorithms whose time adaptivity was at least linear in the number of faults for various tasks were suggested in [25, 6, 49, 11].

A common design pattern in distributed algorithms working under the synchronous fault free model is to divide the execution into phases so that each phase is composed of a fixed number $\varphi$ of single round steps, grouped together to fulfill a task that cannot be achieved in a single round. The execution then progresses by running the phases in succession, where step $0\le j\le \varphi -1$ of phase $i=0,1,\mathrm{\dots }$ is executed in round $t=i\varphi +j$. A key property of this design pattern is that the nodes execute their phases in synchrony so that step $j$ of phase $i$ is executed by all nodes in the same round.

More often than not, the algorithm runs the same code in each phase which means that the nodes do not have to keep track of the current round $t$; rather, it suffices that they have access to a step oracle, denoted hereafter by $\mathrm{𝙶𝚎𝚝}\mathrm{\_}\mathrm{𝚂𝚝𝚎𝚙}$, that simply returns the current step $j=tmod\varphi$. We refer to the family of such algorithms as phase based algorithms and note that this family includes the distributed graph algorithm “classics” of [23] ($3$-coloring of trees), [56, 3] (maximal independent set), and [44] (maximal matching), as well as more recent distributed graph algorithms, see, e.g., [16, 29, 62, 32].

The step oracle discussion is usually avoided in the literature on synchronous fault free algorithms as these algorithms can easily maintain a register that keeps track of $tmod\varphi$. This is not the case in the self-stabilizing setting though: the adversary may modify this register, causing the nodes to execute their phases “out of sync” indefinitely. Indeed, we cannot assume that the nodes in a self-stabilizing algorithm have free access to a step oracle, hence the adaptation of a phase based algorithm designed to operate in a fault free environment to the self-stabilization setting imposes a significant challenge (cf. [65]).

To overcome this challenge, we introduce a technique called probabilistic phase synchronization. In high level terms (refer to Sec. 3 for a formal exposition), this technique replaces the step oracle by a generic (algorithm independent) module, referred to as $\mathrm{𝙿𝙿𝚂}$, whose implementation is based on a simple ergodic Markov chain, maintained independently at each node. The state space of the Markov chain is $\{\mathrm{\hslash },-1,0,1,\mathrm{\dots },\varphi -1\}$, where states $0,1,\mathrm{\dots },\varphi -1$ are identified with the $\varphi$ steps of the phase and $\mathrm{\hslash }$ and $-1$ are auxiliary states whose role is explained in the sequel.

Using the $\mathrm{𝙿𝙿𝚂}$ module, the adaptation of a fault free phase based algorithm $\mathrm{𝙰𝚕𝚐}$ into a self-stabilizing algorithm becomes almost a “black-box compiler” based on the following two modifications: (i) Replace each call to $\mathrm{𝙶𝚎𝚝}\mathrm{\_}\mathrm{𝚂𝚝𝚎𝚙}$ by a call to a procedure named $\mathrm{𝙶𝚎𝚝}\mathrm{\_}\mathrm{𝚂𝚝𝚎𝚙}\mathrm{\_}\mathrm{𝙿𝙿𝚂}$ that returns the current state of $\mathrm{𝙿𝙿𝚂}$. (ii) When executing the phase, node $v$ restricts its communication to its phase synchronized neighbors, namely, adjacent nodes whose $\mathrm{𝙿𝙿𝚂}$ state agrees with that of $v$.

We design the $\mathrm{𝙿𝙿𝚂}$ module so that (a) if nodes $u$ and $v$ start a phase in the same round, then they remain phase synchronized until the phase ends; and (b) the Markov chain admits a $\mathrm{poly}(\varphi )$ mixing time, ensuring that every pair of adjacent nodes become phase synchronized sufficiently often. As we show in the sequel (see [18] for more details), these two properties guarantee progress on behalf of the algorithm, allowing us to bound the stabilization time. While our analysis is specific to maximal matching, the aforementioned adaptation is fairly generic and serves as the cornerstone for the transformer discussed in the full version [18].

Like the algorithm of [44], algorithm $\mathrm{𝙵𝙵𝙼𝙼}$, presented in Algorithm 3, is phase based with a phase of length $3$. In round $0$ of the phase, each undecided node $v$ tosses an unbiased coin that determines if $v$ is active or passive (for the duration of the current phase); active nodes then send a matching request to an undecided neighbor picked uniformly at random. In round $1$ of the phase, a passive node $v$ that received a matching request from at least one neighbor picks one such neighbor $u$ (arbitrarily) and replies that $u$’s matching request is accepted. Finally, in round $2$ of the phase, each edge over which a matching request was accepted is added to the output MM. To implement this logic, the messages sent by $\mathrm{𝙵𝙵𝙼𝙼}$ use one additional field (on top of the aforementioned $\sigma$-field), namely, the $r$-field that takes values in $\{\mathrm{𝙼𝚛𝚎𝚚},\mathrm{𝙰𝚌𝚌}\}$ (stands for ’matching request’ and ’accept’, respectively).

Our self-stabilizing algorithm $\mathrm{𝚂𝚂𝙼𝙼}$, presented in Algorithm 5, is obtained from $\mathrm{𝙵𝙵𝙼𝙼}$ through the following two modifications: (1) We add an error detection subroutine, presented in Algorithm 4, which is invoked in every round (see line 2 in Algorithm 5). In this subroutine, node $v$ checks whether its available local information indicates that it is either strongly matched or strongly unmatched; if $v$ is neither, then it becomes undecided by setting $m_v\leftarrow \perp$. (2) We apply the probabilistic phase synchronization “compiler” of Sec. 3. To this end, the outgoing messages are augmented with an additional $s$-field (stands for ’step’). This field is used to communicate $v$’s current step so that ${\mathrm{𝑂𝑢𝑡}}_v^s(\cdot )$ is set to the value of ${\mathrm{𝑠𝑡𝑒𝑝}}_v$ before the message is sent by calling $\mathrm{𝙶𝚎𝚝}\mathrm{\_}\mathrm{𝚂𝚝𝚎𝚙}\mathrm{\_}\mathrm{𝙿𝙿𝚂}$ (see line 23 in Algorithm 5).

This section presents the general structure of $\mathrm{𝚂𝚂𝙼𝙼}$’s analysis. It hinges on Prop. 5.1–5.6 whose combination yields Thm. 1.1. We start with Prop. 5.1 ensuring that once the algorithm reaches a legal configuration, it stays in a legal configuration.

We say that $v$ is locally matched to node $u\in N(v)$ if (i) $m_v=u$; and (ii) ${\mathrm{𝐼𝑛}}_v^{\sigma }(u)=𝙷$; when the identity of $u$ is not important, we may refer to $v$ as being locally matched without explicitly mentioning $u$. Notice that by definition, if $v$ is strongly matched, then $v$ is also locally matched. Given some $t\ge t_0^{\ast }$, let $V_t$ be the set of nodes which are not locally matched at time $t$, let $E_t=E\cap (V_t\times V_t)$, and let $G_t=(V_t,E_t)$ be the graph induced on $G$ by $V_t$. When combined with Prop. 5.1, the following proposition implies that we do not have to worry about the nodes that are no longer in $G_t$.

By combining Prop. 5.1 and 5.2 with the following proposition, we deduce that if $E_t=\mathrm{\varnothing }$, then $\mathrm{𝚂𝚂𝙼𝙼}$ is in a legal configuration at time $t+1$ and will remain so indefinitely.

The rest of the analysis is devoted to showing that it takes $O(\log k)$ rounds in expectation and w.h.p. for the set $E_t$ to become empty. Let $\tau =O({\varphi }^3)$ be the parameter promised in Cor. 3.3. The next proposition implies that from time $t>t_0^{\ast }$, algorithm $\mathrm{𝚂𝚂𝙼𝙼}$ stabilizes in $O\left(\frac{{\varphi }^5}{\log (1+1/{\varphi }^2)}\log |E_t|+\log k\right)$ rounds in expectation and w.h.p. (in $k$), which is $O(\log |E_t|+\log k)$ when $\varphi$ is a constant as in $\mathrm{𝚂𝚂𝙼𝙼}$. This means in particular that once $\mathrm{𝚂𝚂𝙼𝙼}$ reaches a configuration in which $|E_t|\le \mathrm{poly}(k)$, it takes $O(\log k)$ additional rounds in expectation and w.h.p. for the algorithm to stabilize.

Unfortunately, by manipulating $k$ nodes, the adversary can lead the algorithm to a graph $G_{t_0^{\ast }}$ whose edge set is arbitrarily large (and not polynomially bounded) with respect to $k$. To resolve this obstacle, we prove that it takes the algorithm $O(\log k)$ rounds in expectation and w.h.p. to reduce the number of edges in $G_t$ down to $O(k^2)$. This relies on the following proposition derived from a nice combinatorial property of maximal matching.

Consider the sets $K$ and $I$ promised in Prop. 5.5 and some positive constant $\xi =\xi (\varphi )$ whose value is determined later on. For $t>t_0^{\ast }$, let $D_t=\{v\in K\cap V_t\mid {\mathrm{d}}_{G_t}(v)\ge \xi k\}$ and let $T$ be the random variable that takes on the earliest time $t$ such that $D_t=\mathrm{\varnothing }$. Since $I$ is an independent set, every edge in $E_T$ is incident on at least one vertex in $K$, thus . Recalling that $\varphi$ is a constant in $\mathrm{𝚂𝚂𝙼𝙼}$, the proof of Thm. 1.1 is completed due to the following proposition, implying, by standard probabilistic arguments (see Appendix B), that $T\le O(\log k)$ in expectation and w.h.p.

We begin the journey towards proving Prop. 5.1–5.6 by establishing two simple structural observations regarding the operation of $\mathrm{𝚂𝚂𝙼𝙼}$.

Our goal in this section is to establish Prop. 5.4– 5.6, starting with some additional definitions. For every time $t\ge t_0^{\ast }$, let

be the subset of nodes that start a phase in round $t$, recalling that ${\mathrm{𝑠𝑡𝑒𝑝}}_{v,t}$ is the state of $v$’s $\mathrm{𝙿𝙿𝚂}$ module at time $t$. Let ${\tilde{E}}_t=E_t\cap ({\tilde{V}}_t\times {\tilde{V}}_t)$ and let ${\tilde{G}}_t=({\tilde{V}}_t,{\tilde{E}}_t)$ be the graph induced on $G_t$ by ${\tilde{V}}_t$.

A key feature of $\mathrm{𝚂𝚂𝙼𝙼}$ is that in each phase, node $v\in V$ writes to ${\mathrm{𝚛𝚎𝚐}}_v$ before reading from it for every register ${\mathrm{𝚛𝚎𝚐}}_v$ other than $m_v$ and ${\mathrm{𝐼𝑛}}_v(\cdot )$. Therefore, we can conceptually assume that these registers are reset to an arbitrary default value at step $-1$.

Consider some graph $H=(V_H,E_H)$. Node $v\in V_H$ is said to be good in $H$ if at least $1/3$ of its neighbors $u$ in $H$ have degree ${\mathrm{d}}_H(u)\le {\mathrm{d}}_H(v)$. The following lemma is established by Alon et al. [3, Lem. 4.4].

Lem. 5.9 is exploited in the following two lemmas to show that sufficiently many edges are removed with a sufficiently high probability; Prop. 5.4 follows by a standard Markov inequality argument (see Appendix B).