Self-Stabilizing Algorithms in the Uniform Port Model Liam Brinker # Technion - Israel Institute of Technology, Israel Yuval Emek # Technion - Israel Institute of Technology, Israel
Oren Louidor # Technion - Israel Institute of Technology, Israel
arXiv:2607.08244v1 [cs.DC] 9 Jul 2026
Abstract We introduce a distributed computational model referred to as the uniform port model. An algorithm operating in this model is defined by means of local automata associated with the ports (a.k.a. half-edges) of the input graph. The crux of the uniform port model is that a single constant-size finite automaton is hosted by every port of every graph, making the model truly uniform. Moreover, since the new model explicitly supports the assignment of (input and) output labels to the graph’s (half-)edges, it facilitates natural formulations of (half-)edge-labeling problems such as maximal matching and sinkless orientation, which are outside the expressivity scope of prior node-centric truly uniform distributed computational models. The main technical contribution of this paper is the design of efficient (i.e., with poly-logarithmic runtime) self-stabilizing uniform port algorithms, operating on general graphs, for various fundamental local symmetry breaking problems, including maximal independent set, maximal matching, sinkless orientation, and maximal node/edge k-coloring. While efficient self-stabilizing algorithms for local symmetry breaking problems have been extensively studied in stronger computational models, our work is the first to demonstrate the existence of such algorithms in a truly uniform model. 2012 ACM Subject Classification Theory of computation → Distributed algorithms Keywords and phrases truly uniform algorithms, uniform port model, self-stabilization, local symmetry breaking
0
Self-Stabilizing Algorithms in the Uniform Port Model
Contents 1 Introduction
1
2 Preliminaries
3
3 Maximal Independent Set 3.1 The MIS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 6 8
4 Maximal Matching 4.1 The MM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Stochastic Analysis of the Tournaments . . . . . . . . . . . . . . . . .
12 12 15 20
5 Sinkless Orientation 23 5.1 The SO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6 Maximal Node and Edge k-Coloring
27
7 The 2-State Process may be Slow
28
8 Additional Related Work
30
A Proving Lemma 2.2
34
L. Brinker, Y. Emek, and O. Louidor
1
Introduction
The notion of uniformity in computational models refers to settings in which the algorithm designer is oblivious to the size (and often other parameters) of the problem instances on which the algorithm is executed. The main advantage of uniform algorithms is that they enable a one-size-fits-all approach: the same computational device can be used for all problem instances. In distributed computing, this advantage is amplified as a single execution often involves a multitude of such devices. Traditionally, uniform distributed algorithms were studied without accounting for the memory size of the computational devices, effectively allowing infinite memory. The turning point in this regard came when the research community realized that distributed computing is not limited to computer networks; rather, interesting distributed processes also arise in networks composed of devices that are much weaker than silicon-based computers. A pioneering work in this direction is the paper of Afek et al. [1] who discovered that a biological process occurring during the development of the nervous system of the Drosophila melanogaster is equivalent to solving an instance of the maximal independent set (MIS) problem — a classic local symmetry breaking problem that is among the most extensively studied problems in distributed computing. Motivated by this discovery, as well as by networks of nano-scale mechanical devices [4], Emek and Wattenhofer [15] introduced the stone age model as an abstraction for distributed computing in networks composed of weak devices. In this model, each node hosts the same (randomized) finite state automaton whose description size is bounded by a universal constant, independently of any parameter of the input graph, including the number of nodes and their degrees; that is, the model is truly uniform. Since its introduction, the stone age model has attracted significant attention [15, 2, 3, 14, 13, 18, 28]. A common drawback of most algorithms in this line of work is that they assume graceful initialization, where all automata start the execution in synchrony from a designated initial state. This assumption turns out to be too strong for many practical scenarios, where it is difficult to coordinate between the automata. Moreover, algorithms that rely on graceful initialization are completely helpless if the network experiences some transient disturbance that causes the execution to diverge off course. In contrast, self-stabilizing algorithms [11] are required to recover from arbitrary initial configurations, thus they do not rely on global coordination at startup and can tolerate transient faults. Designing efficient self-stabilizing algorithms in truly uniform models turns out to be challenging and to the best of our knowledge, all existing positive results are limited in scope.1 These include the MIS algorithm of Emek and Keren [13] that assumes graphs of bounded diameter and the MIS algorithm of of Giakkoupis and Ziccardi [18] whose analysis is applicable only to Erdős-Rényi random graphs.2 Another shortcoming of the stone age model is limited expressivity: A constant number of states implies constant-size output labels, thus stone age algorithms are suitable only for the class of problems whose outputs can be encoded by assigning constant-size labels to the nodes of the input graph. For graphs of unbounded degrees, this class is somewhat narrow, excluding some fundamental distributed computing problems such as maximal matching (MM) and sinkless orientation (SO). Indeed, a node of high degree cannot encode the selection
1
In the context of local symmetry breaking problems, an algorithm is regarded as efficient if its runtime is (at most) polylogarithmic in the number of nodes, see Section 2. 2 Giakkoupis and Ziccardi [18] conjectured that a simple self-stabilizing MIS algorithm called the 2-state MIS process is efficient on general graphs, however this turns out to be wrong, see Section 7.
1
2
Self-Stabilizing Algorithms in the Uniform Port Model
of a single incident edge (MM) or the orientation of all incident edges (SO) using only a constant-size label. Motivated by the aforementioned shortcomings of the stone age model, in this paper, we introduce a new truly uniform model, referred to as the uniform port (UP) model. The key idea behind the UP model is that the (truly uniform) automata are hosted by the ports (i.e., half-edges) of the input graph, rather than by the nodes, so that each port may interact with its counter-port on the same edge as well as with its sibling ports on the same node (refer to Section 2 for a formal definition). Importantly, the interaction with sibling ports is highly restricted: the automaton’s transition function observes only the set of sibling states, rather than their multiplicities or identities (cf. the set-broadcast communication scheme of [19]), ensuring that the automaton description remains constant-size and independent of node degree. We emphasize that while prior distributed computational models use the graph ports for communication, the novelty of the UP model is that the ports are the computational entities, each running the same constant-size automaton, while sibling interaction is constrained so as to preserve true uniformity. Switching from a node-centric point-of-view to a (half-)edge-centric one significantly increases the expressivity of the model, thus addressing one major shortcoming of the stone age model.3 Furthermore, the UP model, that enables finer-grained local coordination, turns out to be better suited for self-stabilization, thus circumventing the other shortcoming. A Decentralized Variant of a (non-truly uniform) Node-Centric Model. Recall that in the UP model, each node of degree d hosts d constant-memory automata. As such, the reader may wonder how the UP model compares with an alternative distributed computational model where each node of degree d hosts an automaton with memory size Θ(d) (i.e., with 2Θ(d) states). Since in both models, each node v has the same total number of memory bits, it may seem plausible that the two models are “essentially the same”; put differently, one may hope that the automata hosted by the ports of v under the UP model can collectively simulate the automaton hosted by node v itself under the alternative model. This intuition is misleading: even under ideal conditions (and the conditions of selfstabilizing algorithms are far from ideal), the limited communication capabilities of the UP model do not enable the simulation of an automaton with memory size Θ(d) by d constant-memory automata. In fact, the UP model can be viewed as a “decentralized variant” of the aforementioned alternative model, where each automaton with memory size Θ(d) is distributed over d constant-memory automata. This decentralized variant view is the key to the true uniformity of the UP model and what makes it so appealing: assembling a “node device” from d generic “port devices” is much simpler than having to manufacture (and carry around) different types of “node devices”, one for each value of d; the technician installing the network is likely to appreciate this simplicity (recall that in some of the applications we are interested in, the “technician” is a tiny cell organelle). Technical Contribution. Beyond the conceptual contribution of introducing the UP model, we develop the following (synchronous) self-stabilizing UP algorithms, all applicable to general graphs, where n denotes the number of nodes:
3
It is interesting to point out that although the focus of the current paper is on distributed computing in graphs, the UP model can be naturally extended to distributed computing in hypergraphs. Here, a port may have multiple counter-ports that share the same edge, as well as multiple sibling ports that share the same node; the extended model would apply the set-broadcast communication scheme to both sets, thus preserving true uniformity.
L. Brinker, Y. Emek, and O. Louidor
an MIS algorithm that runs in O(log2 n) time whp;4 an MM algorithm that runs in O(log5 n) time whp; an SO algorithm that runs in O(log2 n) time whp; a maximal node k-coloring algorithm that runs in O(log2 n) time whp for any constant k ≥ 2; and a maximal edge k-coloring algorithm that runs in O(log5 n) time whp for any constant k ≥ 2. We emphasize that to the best of our knowledge, these are the first efficient self-stabilizing algorithms for any natural local symmetry breaking problem (on general graphs), operating under a truly uniform model. Paper’s Outline. The rest of the paper is organized as follows. In Section 2, we present a formal definition of the UP model together with some preliminary definitions and machinery that serve us in the subsequent technical sections. Sections 3, 4, and 5 are dedicated to our self-stabilizing MIS, MM, and SO algorithms, respectively; each of these sections includes a high level presentation of the corresponding algorithm followed by a detailed “port-level description” and analysis. The self-stabilizing node/edge maximal k-coloring algorithms are developed in Section 6. In Section 7, we refute the conjecture of Giakkoupis and Ziccardi [18] regarding the efficiency (in general graphs) of the 2-state MIS process (see footnote 2). We conclude in Section 8 with a discussion of some additional related work.
2
Preliminaries
Graphs. Consider an undirected graph G.5 Let VG and EG denote the node set and edge set of G, respectively. Nodes u, v ∈ V are regarded as adjacent if {u, v} ∈ E; edges e, f ∈ E are regarded as adjacent if |e ∩ f | = 1. For a node v ∈ VG , let NG (v) = {u ∈ VG : {v, u} ∈ EG } denote the set of nodes adjacent to v in G (a.k.a. v’s neighbors) and let degG (v) = |NG (v)| denote the degree of v in G. The subgraph of G induced by a node subset U ⊆ VG is the graph whose node set is U and whose edge set consists of all edges e ∈ EG such that e ⊆ U ; the subgraph of G induced by an edge subset F ⊆ EG is the graph whose edge set is F and whose node set consists of all nodes v ∈ VG such that at least one of the edges incident on v is in F . A half-edge in G is a pair of the form (v, {u, v}), where v ∈ VG and {u, v} ∈ EG ; throughout this paper, we use the term port as a synonym for a half-edge. Given a port p = (u, {u, v}), we refer to u and {u, v} as the node and edge, respectively, incident on port p. Let PG (v) = {(v, {v, u}) : u ∈ NG (v)} be the set of ports incident on node v ∈ VG and let S PG = v∈VG PG (v) be the set of all ports in G. Ports incident on the same node are referred to as siblings; the set of siblings of a port p = (v, {u, v}) is denoted by sibsG (p) = PG (v)− {p}. The counter-port of a port p = (v, {u, v}) is the port (u, {u, v}) incident on the same edge as p and on the node that lies at the other end of the edge, denoted by p̄. When the underlying graph G is clear from the context, we may omit the subscript G and write V , E, N (v), d(v), P(v), P, and sibs(p) instead of VG , EG , NG (v), dG (v), PG (v), PG , and sibsG (p), respectively. Unless stated otherwise, the number of nodes and edges in G are denoted by n = |V | and m = |E|, respectively.
We say that event A holds with high probability (whp) if P(A) > 1 − n−c for an arbitrarily large constant c > 0. 5 Unless stated otherwise, all graphs in this paper are assumed to be finite and simple.
4
3
4
Self-Stabilizing Algorithms in the Uniform Port Model
The Uniform Port Model. Consider a graph problem P defined over a set O of output labels. When invoked on an undirected graph G, a distributed algorithm for P that operates under the uniform port (UP) model associates a (randomized) local automaton with each port p ∈ P.6 The syntax of this local automaton is given by the 3-tuple Alg = ⟨Q, ω, δ⟩ , where Q is a finite set of states; ω : Q → O is a function that maps each state q ∈ Q to an output label ω(q) ∈ O; and δ : Q × Q × 2Q → ∆(Q) is a (randomized) state transition function to be explained soon.7 It is important to note that the description of Alg = ⟨Q, ω, δ⟩ is assumed to be fixed, independently of any parameter of the input graph G. At the risk of slightly abusing the notation, we use Alg for both the syntax of the local automata and the distributed algorithm defined by the collection of the local automata associated with the ports in P (to be explained soon); our intention will be clear from the context. A configuration of algorithm Alg is a function C : P → Q that assigns a state C(p) ∈ Q to (the local automaton associated with) each port p ∈ P. The execution of Alg proceeds in synchronous rounds, where round t ∈ Z≥0 spans the time interval [t, t + 1), denoting the configuration of Alg at time t by C t . Starting from an initial configuration C 0 , the execution advances according to the following inductive mechanism: Assuming that the configuration C t has already been constructed, the configuration C t+1 is constructed so that for each port p ∈ P, the state C t+1 (p) is obtained by picking C t+1 (p) ∼ δ C t (p), C t (p̄), C t (p′ ) : p′ ∈ sibs(p) . That is, to obtain the next state C t+1 (p) of (the local automaton associated with) port p, we apply the state transition function δ to the current state C t (p) of p, the current state C t (p̄) of p’s counter-port, and the set {C t (p′ ) : p′ ∈ sibs(p)} of current states of p’s siblings; the next state C t+1 (p) of p is then picked from the probability distribution determined by δ. We emphasize that the third argument of δ is a set, rather than a multiset or a vector, of states; it is this model choice that decouples the automaton from the node degrees, thus allowing the description size of δ (and Alg) to be a universal constant, making the UP model truly uniform. An output assignment of G is a function Y : P → O that assigns an output label Y (p) to each port p ∈ P. The output assignment associated with a configuration C : P → Q of Alg, denoted by ω(C), is the function Y : P → O defined so that Y (p) = ω(C(p)) for each p ∈ P.8 We say that the execution η = {C t }t≥0 of Alg stabilizes to an output assignment ′ Y : P → O by time t ∈ Z≥0 if ω(C t ) = Y for every t′ ≥ t. Let YP ⊆ OP be the set of legal output assignments for problem P on G. Algorithm Alg is said to be self-stabilizing if for every undirected graph G and for every initial configuration C 0 , it is guaranteed that the execution of Alg stabilizes to some output assignment Y ∈ YP by time t with probability that goes to 1 as t → ∞. The runtime (a.k.a. stabilization time) of a self-stabilizing algorithm Alg on G, starting from C 0 , is defined to be the minimum t such that the execution of Alg stabilizes to a legal output assignment by time t. Notice that the runtime is a random variable, depending on the coin tosses of the local automata, and
6
In the context of the UP model, it is assumed that the input graph does not include nodes of degree 0. Here, ∆(Q) denotes the collection of probability distributions over Q. 8 It is often convenient to augment the output label set O with the designated “nil symbol” ⊥ so that ω(C(p)) = ⊥ indicates that port p ∈ P is undecided in the output assignment associated with configuration C.
7
L. Brinker, Y. Emek, and O. Louidor
we typically aim to bound it whp as a function of n. In particular, Alg is said to be efficient if its runtime is bounded by logO(1) n whp. For the sake of clarity, the UP algorithms developed in this paper are presented in a more human-readable “procedural description”, assuming that the ports maintain local variables that are updated from one round to the next according to a specified logic; translating these descriptions to the syntax of the UP model, as formulated above, is a straightforward (though possibly tedious) task. We stick to the convention that varp denotes the local variable var maintained by a port p ∈ P and when presenting the actions of a UP algorithm during “the current round”, we denote the value of varp at the end of the round (i.e., the beginning of the next round) by var+ p . When analyzing a UP algorithm, we denote the value of a variable var at time t ∈ Z≥0 by vart ; we note that the individual ports do not know t, however, this notation is well defined in the scope of the analysis. Local Leader Election. While the ports of a node v ∈ V are anonymous (and unordered), it is often convenient to mark one port p ∈ P(v) as designated from the rest of the ports in P(v). A basic UP mechanism that does that (and is used by all our algorithms this way or another) is called local leader election (LLE). For the purpose of the current description of the LLE mechanism, assume that each port p ∈ P(v) maintains a variable LLEp ∈ {0, 1}; the UP algorithms presented in the sequel use different names for this variable, but the principle is the same. Port p updates variable LLEp in each round according to the following simple rule: If LLEp = 1 and there exists p′ ∈ sibs(p) such that LLEp′ = 1, then p picks LLEp ∼ Unif({0, 1}). Otherwise, if LLEp′ = 0 for all p′ ∈ sibs(p) ∪ {p}, then p assigns LLEp ← 1. Otherwise, p keeps the current value of LLEp (formally, LLEp ← LLEp ). Clearly, the mechanism stabilizes when, and only when, there exists exactly one port p ∈ P(v) such that LLEp = 1; we refer to such a port p as the leader port of node v. The following lemma, established in Section 4.2 as part of the analysis of our self-stabilizing MM algorithm (see Lemma 4.4), guarantees that this happens sufficiently fast. ▶ Lemma 2.1. Assume that the LLE mechanism is invoked in a node v ∈ V at time t0 ∈ Z≥0 . There exists a time t ≥ t0 such that v admits a leader port p ∈ P(v) at time t and p remains the leader port of v subsequently (as long as the LLE mechanism is not re-invoked in v). Moreover, t ≤ t0 + O(log2 n) whp. Miscellaneous. Throughout, c > 0 denotes a constant whose value may depend on the context. Unless stated otherwise, we stick to the convention that log x = log2 x. The (discrete or continuous) uniform distribution over a set S is denoted by Unif(S) and the geometric distribution, counting the number of independent Bernoulli trials until (including) the first success, where each trial succeeds with probability 0 < p ≤ 1, is denoted by Geom(p). We make an extensive use of the following well known lemma (a proof is provided in Appendix A for completeness). ▶ Lemma 2.2. Let X0 , X1 , . . . be random variables over Z≥0 that satisfy the following two conditions for every i > 0 almost surely: (1) Xi ≤ Xi−1 ; and (2) E(Xi | Xi−1 ) ≤ rXi−1 for some fixed parameter 0 < r < 1. Let x0 = E(X0 ) and define the random variable T = min{i ≥ 0 : Xi = 0}. Then, P(T > ⌈log1/r x0 ⌉ + j) ≤ rj for every j ≥ 0.
5
6
Self-Stabilizing Algorithms in the Uniform Port Model
3
Maximal Independent Set
A node subset S ⊆ V is said to be independent if {u, v} ∈ / E for every u, v ∈ S. A maximal independent set (MIS) is an independent set S ⊆ V that is maximal in the sense that S ′ is not independent for every S ⊂ S ′ ⊆ V . In the MIS problem, the goal is to partition the node set V into IN-nodes and OUT-nodes such that the set of IN-nodes forms an MIS. Under the UP model, this is translated to using {IN, OUT, ⊥} as the output label set so that a node v ∈ V is considered to be an IN-node (resp., an OUT-node) in a configuration C if ω(C(p)) = IN (resp., ω(C(p)) = OUT) for all p ∈ P(v); node v is regarded as undecided in C if it is neither an IN-node nor an OUT-node. ▶ Theorem 3.1. There exists a self-stabilizing UP algorithm that solves the MIS problem and stabilizes in O(log2 n) time whp. The algorithm promised in Theorem 3.1 is presented in Section 3.1, first at a high level and then, from the perspective of the individual ports. Section 3.2 is then dedicated to proving the correctness of our algorithm and bounding its stabilization time, thus establishing Theorem 3.1.
3.1
The MIS Algorithm
High-Level Description Our MIS algorithm maintains an orientation of the graph edges and uses this orientation to determine which nodes join the MIS (i.e., become IN-nodes). In each round, every node generates a reorientation bit from the set {0, 1}. Following that, each edge e = {u, v} ∈ E is oriented according to the reorientation bits of its endpoints based on the following rule: if the reorientation bits of u and v differ, then e is oriented toward the endpoint whose reorientation bit is 1; otherwise, the edge keeps its previous orientation (if one exists). Undecided nodes sample their reorientation bit uniformly at random from {0, 1}, whereas IN-nodes and OUT-nodes fix their reorientation bit to 1 and 0, respectively. Consider an undecided node v ∈ V . Node v becomes an IN-node in round t if all its incident edges are oriented inward (i.e., v is a sink) at time t and the sampled reorientation bit of v in round t is 1; the latter condition guarantees that following the reorientation step of round t, all edges incident on v remain oriented inward. Once v becomes an IN-node, its reorientation bit is fixed to 1, thus ensuring that v remains an IN-node. Node v becomes an OUT-node if it has an adjacent IN-node. Once v becomes an OUT-node, its reorientation bit is fixed to 0, thus v yields the orientation of its incident edges to its neighbors. ▶ Remark. The reader may wonder about the similarity between our MIS algorithm and Luby’s MIS algorithm [22], in particular the adaptations thereof developed by Métivier et al. [23] and by Emek and Wattenhofer [15]. We argue that the similarity is minimal: Luby’s MIS algorithm works in phases, so that in each phase, the undecided nodes “compete” among themselves over the right to become IN-nodes. To this end, each undecided node v picks a random number rv from a sufficiently large set and becomes an IN-node if rv > ru for all undecided neighbors u of v. In Luby’s original algorithm [22], node v sends rv in a single message, thus the competition’s outcome is determined within a single round. As the algorithms of [23] and [15] use constant size messages, node v sends the value of rv over multiple rounds, essentially communicating rv one bit at a time. The key point in this regard is that if i is the index of the most significant bit in which rv and ru differ so that rv (i′ ) = ru (i′ ) for all 1 ≤ i′ < i and rv (i) > ru (i), then the outcome of the competition
L. Brinker, Y. Emek, and O. Louidor
between u and v is determined once v and u exchange the values of rv (i) and ru (i); there is no point for node u to keep sending the values of ru (i′ ) for i′ > i as those values do not affect the outcome of the current phase’s competition. In contrast, our MIS algorithm does not work in phases (as discussed in Section 4.1, phases raise significant synchronization challenges for self-stabilizing algorithms). More importantly, the outcome of the competition between nodes v and u is never fully determined as long as both nodes are undecided: regardless of the history, a single round in which v and u pick 0 and 1, respectively, as their reorientation bits suffices to reorient edge {u, v} toward u, thus marking u as the current “front runner” of the competition between u and v. This “erratic behavior” turns out to be crucial for the fast stabilization of our algorithm.
Port-Level Description For the purpose of orienting the graph edges, each port p ∈ P maintains a variable ortp ∈ {0, 1}, referred to as the local orientation of p. The local orientation variables determine the edge orientations as follows: An edge e = {v1 , v2 } ∈ E is considered to be oriented toward vi , i ∈ {1, 2}, if ort(vi ,{v1 ,v2 }) = 1 and ort(v3−i ,{v1 ,v2 }) = 0; edge e is considered to be unoriented if ort(v1 ,{v1 ,v2 }) = ort(v2 ,{v1 ,v2 }) , that is, the edge is neither oriented toward v1 nor oriented toward v2 . Related to the local orientation variables, each port p ∈ P maintains a Boolean variable uortp ∈ {true, false}, referred to as the unoriented flag of p. Port p updates this variable in each round by setting uortp ← true if and only if ortp = ortp̄ , that is, if and only if the edge shared by p and its counter-port p̄ is unoriented. The unoriented flag variables have an important role in the algorithm: they allow port p to observe whether all edges incident on its siblings are oriented (notice that the local orientation variables alone do not fulfill this task). The mechanism that dictates the edge orientation is controlled by a variable rortp ∈ {0, 1}, referred to as the reorientation bit of port p, that each port p ∈ P maintains. Specifically, variable ortp is updated in each round according to the following simple rule: if rortp ̸= rortp̄ , then ortp ← rortp ; otherwise (rortp = rortp̄ ), the value of ortp remains unchanged (formally, ortp ← ortp ). The update rule of the reorientation bit variables themselves is presented shortly; for now, it suffices to assume that port p updates rortp in each round by adopting a random coin toss shared by all ports incident on the same node (the implementation of this shared coin toss is also presented shortly). The output label associated with port p is determined based on the value of the designated variable stsp ∈ {IN, OUT, OUT∗ , ⊥}, referred to as the status of p. Specifically, the output label associated with p is IN, OUT, or ⊥ if stsp = IN, stsp ∈ {OUT, OUT∗ }, or stsp = ⊥, respectively. Variable stsp is updated in each round according to the following rule: Assign stsp ← IN if (I) ortp = 1; (II) ortp̄ = 0; (III) uortp′ = false for all p′ ∈ sibs(p) ∪ {p}; and (IV) rortp′ = 1 for all p′ ∈ sibs(p) ∪ {p}. Otherwise, assign stsp ← OUT∗ if stsp̄ = IN. Otherwise, assign stsp ← OUT if there exists p′ ∈ sibs(p) such that stsp′ = OUT∗ . Otherwise, assign stsp ← ⊥. Having established the update rule of the status variables, we can now get back to the mechanism that dictates the values of the reorientation bit variables. This mechanism depends on a leader port p∗ = p∗ (v) ∈ P(v) elected in each node v ∈ V by applying the LLE mechanism (see Section 2). Port p∗ maintains a variable coinp∗ ∈ {0, 1}, referred to as the coin toss of v, and updates this variable in each round by picking coinp∗ ∼ Unif({0, 1}).
7
8
Self-Stabilizing Algorithms in the Uniform Port Model
Based on that, ports p ∈ P(v) update the variables rortp in each round according to the following rule: Assign rortp ← 1 if (I) uortp′ = false for all p′ ∈ sibs(p) ∪ {p}; and (II) sts+ p = IN (recall + that stsp denotes the value of stsp at the end of the round). Otherwise, assign rortp ← 0 if (I) uortp′ = false for all p′ ∈ sibs(p) ∪ {p}; and (II) there exists a port p′ ∈ sibs(p) ∪ {p} such that stsp′ = OUT∗ . Otherwise, assign rortp ← coinp∗ .
3.2
Analysis
Throughout the analysis, we fix an arbitrary initial configuration C 0 and consider the (random) execution η = {C t }t≥0 of the MIS algorithm starting from C 0 . A time t ∈ Z>0 is said to be clean with respect to η if the following conditions hold: 1. Every node v ∈ V admits a unique leader port p∗ = p∗ (v) ∈ P(v) in C t . 2. All edges are oriented in C t , i.e., ortt(v1 ,e) ̸= ortt(v2 ,e) for every e = {v1 , v2 } ∈ E. 3. All unoriented flags are down in C t , i.e., uorttp = false for every p ∈ P. 4. If port p ∈ P satisfies ststp = IN, then (I) orttp = 1; (II) rorttp = 1; and (III) ststp′ = IN for all p′ ∈ sibs(p). 5. If port p ∈ P satisfies ststp = OUT∗ , then ststp̄ = IN. 6. If port p ∈ P satisfies ststp = OUT, then there exists p′ ∈ sibs(p) such that ststp′ = OUT∗ . The following lemma allows us to designate a clean suffix of execution η; the subsequent analysis is then dedicated to analyzing that suffix. ▶ Lemma 3.2. There exists a time tclean ∈ Z>0 such that all times t ≥ tclean are clean with respect to η. Moreover, tclean ≤ O(log2 n) whp. Proof. Lemma 2.1 guarantees that there exists a time t1 ∈ Z>0 such that every node v ∈ V admits a (fixed) leader port p∗ = p∗ (v) ∈ P(v) at all times t ≥ t1 and t1 ≤ O(log2 n) whp; condition hereafter on this event. Consider an edge e = {v1 , v2 } ∈ E and let p1 = (v1 , e) and p2 = (v2 , e). The update rule of the local orientation variables ensures that once e becomes oriented, it remains oriented at all subsequent times. By the update rule of the unoriented flag variables, for every time t ≥ t1 , if e is unoriented at time t, then uorttpi = true, i ∈ {1, 2}, and thus, the update rule of the reorientation bit variables ensures that rortt+1 = cointp∗ (vi ) . Therefore, edge pi e becomes oriented during round t + 1 with probability 1/2, independently. We conclude that there exists a time t2 ∈ Z>0 such that all edges are oriented at all times t ≥ t2 and t2 ≤ t1 + O(log n) whp; condition hereafter on this event. By definition, conditions 1 and 2 are satisfied at all times t ≥ t2 . Having established that 2 t ≤ t1 + O(log n) ≤ O(log2 n), we complete the proof by showing that conditions 3, 4, 5, and 6 hold (deterministically) at all times t > t2 + 3. Clearly, condition 3 holds from time t2 + 1 onward as all edges are oriented from time t2 onward. Fix some time t > t2 + 1 and consider a node v ∈ V and a port p ∈ P(v) such that ststp = IN. As t > t2 + 1, we know that all edges incident on v are oriented at time t − 1 ′ and that uortt−1 p′ = false for all p ∈ sibs(p) ∪ {p}. Since port p adopts the IN status during round t − 1, it follows, by the update rule of the status variables, that all edges incident on v are oriented toward v at time t − 1 and that rortt−1 = 1 for all p′ ∈ sibs(p) ∪ {p}. p′ ′ Therefore, all ports p ∈ P(v) adopt the IN status and set rortp′ ← 1 during round t − 1 and the update rule of the local orientation variables ensures that all edges incident on v
L. Brinker, Y. Emek, and O. Louidor
9
remain oriented toward v at time t. Hence, condition 4 holds at time t. By the update rules of the local orientation, reorientation bit, and status variables, we conclude that ststp = IN
=⇒
stst+1 = IN p
(1)
for every port p ∈ P and time t > t2 + 1. Fix some time t > t2 + 2 and consider a port p ∈ P such that ststp = OUT∗ . Since port p adopts the OUT∗ status during round t − 1, it follows, by the update rule of the status variables, that stst−1 = IN. Condition 5 holds at time t due to (1) implying that ststp̄ = IN. p̄ Furthermore, the same argument guarantees that ststp = OUT∗
=⇒
stst+1 = OUT∗ p
(2)
for every port p ∈ P and time t > t2 + 2. Finally, fix some time t > t2 + 3 and consider a port p ∈ P such that ststp = OUT. Since port p adopts the OUT status during round t − 1, it follows, by the update rule of the status ∗ variables, that there exists a port p′ ∈ sibs(p) such that stst−1 p′ = OUT . Condition 6 holds ∗ t at time t due to (2) implying that stsp′ = OUT . The assertion is established by setting tclean = t2 + 4. ◀ Let tclean ∈ Z>0 be the time promised in Lemma 3.2. Our goal in the remainder of this section is to prove that starting from time tclean , the algorithm stabilizes within O(log2 n) rounds whp. To this end, we introduce the following additional definitions. ▶ Definition (INt , OUTt , Gt = (V t , E t ), nt , mt , degt (v)). For t ≥ tclean , let INt ⊆ V and OUTt ⊆ V be the sets of IN-nodes and OUT-nodes, respectively, at time t. Let V t = V − (INt ∪ OUTt ) be the set of undecided nodes at time t and let Gt = (V t , E t ) be the subgraph of G induced by V t ; let nt = |V t | and mt = |E t | be the number of nodes and edges, respectively, in Gt . Let degt (·) = degGt (·) and extend the scope of this operator to all nodes in V by defining degt (v) = 0 for every node v ∈ V − V t . The definition of clean times ensures that the following four properties hold for every node v ∈ V and time t ≥ tclean : (1) if v ∈ INt , then u ∈ / INt for every u ∈ N (v); (2) if v ∈ OUTt , t then there exists u ∈ N (v) such that u ∈ IN ; (3) INt ⊆ INt+1 ; and (4) OUTt ⊆ OUTt+1 . Therefore, if all nodes are decided at time t ≥ tclean , that is, V t = ∅, then the algorithm has stabilized to a legal output assignment by time t. The rest of the analysis is dedicated to 2 proving that V tclean +O(log n) = ∅ whp. We start with the following observation that holds due to the update rule of the reorientation bit variables. ▶ Observation 3.3. For every node v ∈ V , port p ∈ P(v), and time t > tclean , we have (1) if v ∈ INt , then rorttp = 1; (2) if v ∈ OUTt , then rorttp = 0; and (3) if v ∈ V t , then rorttp = coint−1 p∗ (v) . We can now establish the following observation that allows us to focus on E t instead of t
V . ▶ Observation 3.4. For every time t > tclean and node v ∈ V t , if v has no neighbors in Gt (i.e., it is an isolated node), then v ∈ / V t+O(log n) whp. Proof. If there exists a node u ∈ NG (v) such that u ∈ INt , then v is guaranteed to become an OUT node by time t + 2. So, assume that NG (v) ⊆ OUTt and consider some edge e = (u, v) ′ incident on v. Observation 3.3 ensures that rortt(u,e) = 0 for every time t′ ≥ t. Moreover, if
10
Self-Stabilizing Algorithms in the Uniform Port Model ′
′
v is still undecided at time t′ , then rortt(v,e) = cointp∗−1 (v) ∼ Unif({0, 1}). Therefore, edge e is guaranteed to be oriented toward v no later than time t + O(log n) whp and remain oriented toward v subsequently. The assertion follows by a union bound over all edges incident on v as once all these edges are oriented toward v, node v becomes an IN-node. ◀ 2
Owing to Observation 3.4, our goal is to prove that mtclean +O(log n) = 0 whp. To this end, we prove that there exist universal constants α ∈ Z>0 and c > 0 such that E mt+⌈log n⌉+α | mt ≤ cmt almost surely (3) for every t > tclean . Theorem 3.1 follows as a corollary of Lemma 2.2. The remainder of this section is dedicated to establishing (3). As a first step toward this goal, we recall a classic combinatorial lemma of Alon, Babai, and Itai [5] for which we need the following definition. ▶ Definition (good nodes). Consider an undirected graph H. A node v ∈ VH of degree d = degH (v) is said to be good in H if |{u ∈ NH (v) : degH (u) ≤ d}| ≥ d/3. ▶ Lemma 3.5 ([5]). Let H be an undirected graph and let Γ ⊆ VH be the set of good nodes in H. Then, |{e ∈ EH : e ∩ Γ ̸= ∅}| ≥ |EH |/2. We establish (3) by combining Lemma 3.5 and the following lemma. ▶ Lemma 3.6. Fix some time t > tclean and the configuration C t and consider a node v ∈ V t of degree d = degt (v) > 0 that is good in the graph Gt . There exist a universal constant c > 0 such that E degt+⌈log d⌉+4 (v) ≤ cd . Proof. Let t′ = t + ⌈log d⌉ + 1. Given a node u ∈ V t , we say that u is out-destined at time ′ t′ if there exists a node w ∈ NG (u) ∩ INt . Let D(u) be the event that u is out-destined at time t′ and recall that the algorithm is designed so that D(u) implies that u is an OUT-node at time t′ + 2 = t + ⌈log d⌉ + 3 (at the latest). Node u is regarded as weak (with respect to configuration C t ) if P(D(u)) ≥ 1/8; otherwise, node u is regarded as strong. Recall the node v from the lemma’s statement and let NG≤t (v) = {u ∈ NGt (v) : degt (u) ≤ d}; let s1 , . . . , sk be the strong nodes in NG≤t (v). If more than half of the nodes in NG≤t (v) 1 are weak, then E(degt+⌈log d⌉+4 (v)) ≤ E(degt+⌈log d⌉+3 (v)) < d 1 − 16 by the linearity of expectation, thus establishing the assertion. So, assume in what follows that at least half of the nodes in NG≤t (v) are strong, i.e., k ≥ |NG≤t (v)|/2, which implies that k ≥ d/6 as v is a good node in Gt . ′ We say that a node u ∈ V t is lucky if coinτp∗−1 (u) = 1 for all t ≤ τ < t and denote this event by L(u); clearly, the events in {L(u)}u∈V t are mutually independent and 1 1 ≤ P(L(u)) < 2d 4d as t′ − t = ⌈log d⌉ + 1. We can now introduce the following events for each 1 ≤ i ≤ k: ^ ^ ¬L(u) , and Di = D(si ) . Ai = L(si ) ∧ ¬L(sj ) , Bi = 1≤j≤i−1
u∈NGt (si )−{s1 ,...,si−1 }
The key observation now is that Ai ∧Bi ∧¬Di implies that all edges (in E) incident on si are oriented toward si at time t′ . This in turn implies, by the update rule of the status variables,
L. Brinker, Y. Emek, and O. Louidor ′
11 ′
′
that si ∈ INt +1 with probability at least 1/2. Recalling that si ∈ INt +1 =⇒ v ∈ OUTt +3 , we ′ conclude that Ai ∧ Bi ∧ ¬Di implies that degt+⌈log d⌉+4 (v) = degt +3 (v) = 0 with probability at least 1/2. The assertion will be established by proving that _ 1 P Ai ∧ Bi ∧ ¬Di > . (4) 192 1≤i≤k
Since the events in {Ai }1≤i≤k are pairwise disjoint, it follows that the events in {Ai ∧ Bi ∧ ¬Di }1≤i≤k are pairwise disjoint, hence _ X P Ai ∧ Bi ∧ ¬Di = P(Ai ∧ Bi ∧ ¬Di ) . 1≤i≤k
1≤i≤k
We shall establish (4) by proving that P(Ai ∧ Bi ∧ ¬Di ) >
1 1 ≥ 32d 192k
(5)
for each 1 ≤ i ≤ k. To this end, consider some 1 ≤ i ≤ k and develop _ 1 1 1 P(Ai ) = P(L(si )) · 1 − P L(sj ) > · 1 − (i − 1) · > , 4d 2d 8d
(6)
1≤j≤i−1
where the second transition is by the union bound and the last transition holds as i−1 < k ≤ d, and _ 1 1 P(Bi ) = 1 − P L(u) ≥ 1 − degt (si ) · ≥ , (7) 2d 2 u∈NGt (si )−{s1 ,...,si−1 }
where the second transition is by the union bound and the last transition holds as degt (si ) ≤ d. We further develop P(Di | Ai ∧ Bi ) =
P(Di ∧ Ai ∧ Bi ) P(Di ∧ Ai ∧ Bi ) = < 16d · P(Di ∧ Ai ∧ Bi ) P(Ai ∧ Bi ) P(Ai ) · P(Bi )
≤ 16d · P(Di ∧ L(si )) = 16d · P(Di | L(si )) · P(L(si )) 1 1 1 ≤ 16d · P(Di ) · P(L(si )) < 16d · · = , 8 4d 2
(8)
where the second transition holds as events Ai and Bi are independent, the third transition follows from (6) and (7), the sixth transition holds by the definition of event L(si ), and the penultimate transition holds by recalling that si is strong. Inequality (5) is now established by developing P(Ai ∧ Bi ∧ ¬Di ) = P(¬Di | Ai ∧ Bi ) · P(Ai ∧ Bi ) = P(¬Di | Ai ∧ Bi ) · P(Ai ) · P(Bi ) >
1 1 1 1 · · = , 2 8d 2 32d
where the second transition holds as events Ai and Bi are independent and the penultimate transition follows from (8), (6), and (7). ◀
12
Self-Stabilizing Algorithms in the Uniform Port Model
4
Maximal Matching
An edge subset M ⊆ E is a matching if e ∩ e′ = ∅ for every distinct edges e, e′ ∈ M . A maximal matching (MM) is a matching M ⊆ E that is maximal in the sense that M ′ is not a matching for every M ⊂ M ′ ⊆ E. In the MM problem, the goal is to construct a MM M ⊆ E. Under the UP model, this is translated to using {MATCHED, UNMATCHED, ⊥} as the output label set so that an edge e = {v1 , v2 } ∈ E is determined to be included in (resp., excluded from) the constructed MM M in a configuration C if ω(C((vi , e))) = MATCHED (resp., ω(C((vi , e))) = UNMATCHED) for each i ∈ {1, 2}; edge e is regarded as undecided in C if it is neither included in, nor excluded from, M . A node v ∈ V is regarded as undecided in C if at least one of its incident edges is undecided; otherwise, v is regarded as decided in C. ▶ Theorem 4.1. There exists a self-stabilizing UP algorithm that solves the MM problem and stabilizes in O(log5 n) time whp. The algorithm promised in Theorem 4.1 is presented in Section 4.1, first at a high level and then, from the perspective of the individual ports. Section 4.2 is then dedicated to proving the correctness of our algorithm and bounding its stabilization time, thus establishing Theorem 4.1.
4.1
The MM Algorithm
High-Level Description Our MM algorithm is inspired by a classic MM algorithm of Israeli and Itai [20] (in fact, an adaptation thereof, presented in [8]). The algorithm of [20] divides the execution into phases, where each phase lasts for a fixed (constant) number of rounds and is performed in synchrony by all undecided nodes. Each phase of an undecided node v ∈ V has a mode picked by v uniformly at random from {proposing, receiving}. In a proposing-phase, v proposes to an undecided neighbor picked uniformly at random. In a receiving-phase, if v receives at least one proposal, then v selects exactly one of the proposing neighbors u ∈ N (u) (arbitrarily) and accepts u’s proposal, which results in adding the edge {u, v} to the constructed matching and turning both v and u into decided nodes. When trying to implement this general scheme as a self-stabilizing UP algorithm, we encounter two obstacles: First, in the realm of self-stabilizing algorithms, the phases of the individual nodes do not necessarily run in synchrony.9 Second, under the UP model, picking one neighbor (uniformly at random or otherwise) is equivalent to picking one port; this requires symmetry breaking among the sibling ports which generally involves a stochastic process whose length is a random variable, thus we cannot hope for fixed length phases. To overcome the aforementioned two obstacles, we divide each phase of an undecided node v ∈ V into two epochs. In a proposing-phase, the 1st epoch is dedicated to picking an undecided neighbor u ∈ N (v) uniformly at random; the 2nd epoch is then dedicated to proposing to u via port (v, {u, v}). In a receiving-phase, the 1st epoch has no particular role and the 2nd epoch is dedicated to picking the proposal of exactly one neighbor u ∈ N (v)
9
Bitton et al. [8] deal with this obstacle by introducing a general technique called probabilistic phase synchronization. This technique however assumes a fixed phase length, a property that does not hold in our case.
L. Brinker, Y. Emek, and O. Louidor
(assuming that v receives at least one proposal); the proposal is then accepted via the port (v, {u, v}). The length of each epoch is determined by means of a (port) tournament: initially, all ports in P(v) are candidates and in every round, each candidate port retires — i.e., stops being a candidate — independently with probability 1/2; the tournament ends once all ports have retired. In a proposing-phase, the tournament structure of the 1st epoch facilitates picking one undecided neighbor u ∈ N (v) uniformly at random: u is picked if and only if port p = (v, {u, v}) remains the unique last candidate in v’s (1st epoch) tournament among all ports (v, {u′ , v}) such that u′ is undecided. (Notice that the last candidate may not be unique, in which case, node v fails to match in the current phase; this is accounted for in the analysis, see Section 4.2.) Following that, during the 2nd epoch of the phase, v attempts to propose to u, however, this happens with one crucial condition: the 2nd epoch of v should be perfectly synchronized with that of u, that is, the corresponding tournaments start at the same time. Assuming that this condition is satisfied, the proposals of v to u are carried out through port p and continue as long as p is a candidate in v’s (2nd epoch) tournament. In a receiving-phase, the 1st epoch has no particular role, whereas the role of the 2nd epoch is to pick one out of possibly multiple incoming proposals. To this end, we exploit, once again, the tournament structure: Consider the set Q ⊆ N (v) of undecided neighbors of v that (1) start a 2nd epoch tournament in synchrony with the 2nd epoch tournament of v; and (2) propose to v when the tournament begins. Recall that the nodes u ∈ Q keep proposing to v as long as port (u, {u, v}) is a candidate in the corresponding 2nd epoch tournament of u. Node v accepts the proposal of the node u ∈ Q that remains the unique last proposing node. (As before, the last proposing node in Q may not be unique, in which case, node v fails to match in the current phase; this is accounted for in the analysis, see Section 4.2.) ▶ Remark. On the face of it, the structure of the algorithm may seem overly complicated: As mentioned earlier, the 1st epoch of a receiving-phase is “redundant”. Moreover, it is not clear why the 2nd epoch of a proposing-phase does not end as soon as the port through which the proposals are carried out retires. Put differently, is it really necessary that each phase lasts for (exactly) two i.i.d. tournaments? The answer to this question is categorically positive: Recall that a matching between a proposing node u and a receiving node v can be finalized only if the 2nd epochs of their corresponding (proposing- and receiving-)phases are synchronized. The analysis presented in Section 4.2 crucially depends on the argument that such (u, v)-synchronization events occur sufficiently often (see Section 4.2.1). It turns out that the key for establishing this argument is to ensure that the lengths of the phases of u and v are independent, a property that we obtain by insisting that each phase lasts for two i.i.d. tournaments.
Port-Level Description The mechanism behind the tournaments at a node v ∈ V is controlled by a variable p.trnt ∈ {0, 1}, referred to as the tournament variable, that each port p ∈ P(v) maintains. This variable is updated in each round according to the following rule: if trntp = 1, then trntp ∼ Unif({0, 1}), independently; if trntp′ = 0 for all p′ ∈ sibs(p) ∪ {p}, then trntp ← 1; otherwise, the value of trntp remains unchanged (formally, trntp ← trntp ). This means that each tournament ends in a round during which all ports p ∈ P(v) raise the values of their tournament variables from trntp = 0 to trntp = 1; the next round is regarded as the
13
14
Self-Stabilizing Algorithms in the Uniform Port Model
first round of the subsequent tournament.10 For each node v ∈ V , the actions of the ports in P(v) are orchestrated by a leader port p∗ (v) ∈ P(v) selected by running the LLE mechanism in v (see Section 2). Port p∗ (v) maintains two designated variables that the other (“ordinary”) ports do not maintain: variable modp∗ (v) ∈ {proposing, receiving}, referred to as the phase mode variable, that holds the mode of v’s current phase; and variable epcp∗ (v) ∈ {1, 2, 20 }, referred to as the epoch variable, that records the epoch of v’s current phase, where the symbol 20 indicates the first round of the 2nd epoch (as we shall see soon, it is important to distinguish this round from the rest of the rounds in the 2nd epoch). To avoid cumbersome notation, we subsequently denote these variables by modv and epcv instead of modp∗ (v) and epcp∗ (v) , respectively. The epoch variable of node v is updated in each round according to the following rule: Assign epcv ← 1 if (I) trntp = 0 for all p ∈ P(v); and (II) epcv = 2. Otherwise, assign epcv ← 20 if (I) trntp = 0 for all p ∈ P(v); and (II) epcv = 1. Otherwise, assign epcv ← 2 if epcv = 20 . Otherwise, the value of epcv remains unchanged (formally, epcv ← epcv ). The phase mode variable modv is updated whenever the value of epcv changes from epcv = 2 to epcv = 1 (i.e., epcv = 2 and epc+ v = 1); this update consists of picking modv ∼ Unif({proposing, receiving}), independently. The output label associated with each port p ∈ P is determined based on the value of the designated variable stsp ∈ {MATCHED, UNMATCHED, UNMATCHED∗ , ⊥}, referred to as the status of p. Specifically, the output label associated with p is MATCHED, UNMATCHED, or ⊥ if stsp = MATCHED, stsp ∈ {UNMATCHED, UNMATCHED∗ }, or stsp = ⊥, respectively. The update rule of this variable depends on three additional variables and is therefore deferred until those three variables are presented. In a proposing-phase of node v, the proposal mechanism is handled with the help of a variable prpp ∈ {standby, proposing, proposing0 , ⊥}, referred to as the proposal variable, that each port p ∈ P(v) maintains as long as stsp = ⊥. The semantics of these values is as follows: prpp = standby indicates that p is selected as the proposing port of the current (proposing-)phase; and prpp ∈ {proposing, proposing0 } indicates that p is actively proposing to its counter-port, where proposing0 is reserved for the first round of the 2nd epoch. Specifically, this variable is updated in each round according to the following rule: Assign prpp ← standby if (I) modv = proposing; (II) epcv = 1; (III) trntp = 1; and (IV) trntp′ = 0 for all p′ ∈ sibs(p) such that stsp′ = ⊥. Otherwise, assign prpp ← proposing0 if (I) modv = proposing; (II) epcv = 1; (III) prpp = standby; and (IV) trntp′ = 0 for all p′ ∈ sibs(p) ∪ {p}. Otherwise, assign prpp ← proposing if (I) modv = proposing; (II) epcv ∈ {2, 20 }; (III) prpp ∈ {proposing, proposing0 }; (IV) prpp′ = ⊥ for all p′ ∈ sibs(p); and (V) trnt+ p = 1. Otherwise, assign prpp ← ⊥. In a receiving-phase of node v, the mechanism that determines which proposal is accepted (if any) is handled with the help of a variable rcvp ∈ {true, false}, referred to as the receiving flag, that each port p ∈ P(v) maintains as long as stsp = ⊥. Port p updates this variable in each round by setting rcvp ← true if and only if one of the following two conditions is satisfied: (I) modv = receiving; (II) epcv = 20 ; and (III) prpp̄ = proposing0 .
10
In the language of the aforementioned high-level description, a port p ∈ P(v) is regarded as a candidate in a tournament as long as trntp = 1.
L. Brinker, Y. Emek, and O. Louidor
(I) modv = receiving; (II) epcv = 2; (III) rcvp = true; and (IV) prpp̄ = proposing. The actual proposal acceptance mechanism is handled with the help of a variable acptp ∈ {true, false}, referred to as the acceptance flag, that each port p ∈ P(v) maintains as long as stsp = ⊥. Port p updates this variable in each round by setting acptp ← true if and only if (I) modv = receiving; (II) epcv = 2; (III) rcvp = true; (IV) rcvp′ = false for all p′ ∈ sibs(p) such that stsp′ = ⊥; (V) there exists a port p′ ∈ sibs(p) ∪ {p} such that trntp′ = 1; and (VI) prpp̄ = proposing. We are now ready to present the update rule of the status variable stsp maintained by each port p ∈ P(v): Assign stsp ← MATCHED if MATCHED ∈ / {stsp′ : p′ ∈ sibs(p)} and at least one of the following conditions is satisfied: (I) modv = receiving; (II) epcv = 2; and (III) acptp = true. (I) modv = proposing; (II) epcv = 2; and (III) acptp̄ = true. stsp = stsp̄ = MATCHED. Otherwise, assign stsp ← UNMATCHED∗ if there exists a port p′ ∈ sibs(p) such that stsp′ = MATCHED. Otherwise, assign stsp ← UNMATCHED if stsp̄ = UNMATCHED∗ . Otherwise, assign stsp ← ⊥.
4.2
Analysis
Throughout the analysis, we fix an arbitrary initial configuration C 0 and consider the (random) execution η = {C t }t≥0 of the MM algorithm starting from C 0 . A time t ∈ Z>0 is said to be clean with respect to η if the following conditions hold for every node v ∈ V and port p ∈ P(v): 1. Node v admits a unique leader port in C t . 2. If prptp ̸= ⊥, then (I) modtv = proposing; and (II) prptp′ = ⊥ for all p′ ∈ sibs(p). 3. If prptp = standby, then epctv = 1 4. If prptp = proposing0 , then epctv = 20 . 5. If prptp = proposing, then (I) epctv = 2; and (II) trnttp = 1. 6. If rcvp = true, then (I) modv = receiving; and (II) epcv = 2. 7. If acpttp = true, then (I) rcvp = true; and (II) rcvtp′ = false for all p′ ∈ sibs(p) such that stsp′ = ⊥. 8. If ststp = MATCHED, then (I) ststp̄ = MATCHED; and (II) ststp′ ̸= MATCHED for all p′ ∈ sibs(p). 9. If ststp = UNMATCHED∗ , then there exists p′ ∈ sibs(p) such that ststp′ = MATCHED. 10. If ststp = UNMATCHED, then ststp̄ = UNMATCHED∗ . Lemma 2.1 guarantees that there exists a time t0 ∈ Z>0 such that every node admits a (fixed) leader port at all times t ≥ t0 and t0 ≤ O(log2 n) whp; condition hereafter on this event. The following observation is obtained by exhaustive case analysis. ▶ Observation 4.2. All times t > t0 + 3 are clean with respect to η. Let tclean = t0 + 3. Our goal in the remainder of this section is to prove that starting from time tclean , the algorithm stabilizes within O(log5 n) rounds whp. To this end, we introduce the following additional definitions. ▶ Definition (INt , OUTt , Gt = (V t , E t ), nt , mt , degt (v)). For t ≥ tclean , let INt ⊆ E (resp., OUTt ⊆ E) be the set of edges e = {v1 , v2 } such that ststvi ,e = MATCHED (resp.,
15
16
Self-Stabilizing Algorithms in the Uniform Port Model
ststvi ,e ∈ {UNMATCHED, UNMATCHED∗ }) for each i ∈ {1, 2}. Let E t = E − (INt ∪ OUTt ) be the set of undecided edges at time t and let Gt = (V t , E t ) be the subgraph of G induced by E t ; let nt = |V t | and mt = |E t | be the number of nodes and edges, respectively, in Gt . Let degt (·) = degGt (·) and extend the scope of this operator to all nodes in V by defining degt (v) = 0 for every node v ∈ V − V t . The definition of clean times ensures that the following four properties hold for every edge e ∈ E and time t ≥ 0: (1) if e ∈ INt , then e′ ∈ / INt for every e′ ∈ E such that e ∩ e′ ̸= ∅; (2) if e ∈ OUTt , then there exists e′ ∈ E such that e ∩ e′ = ̸ ∅ and e′ ∈ INt ; (3) INt ⊆ INt+1 ; and (4) t t+1 OUT ⊆ OUT . Therefore, if all edges are decided at time t ≥ tclean , that is, E t = ∅, then the algorithm has stabilized to a legal output assignment by time t. The rest of the analysis 5 5 is dedicated to proving that E tclean +O(log n) = ∅, or equivalently mtclean +O(log n) = 0, whp. To this end, we prove that there exist universal constants α ∈ Z>0 and c > 0 such that c t+α⌈log3 n⌉ t E m |m ≤ 1− mt almost surely (9) log n for every t > tclean . Theorem 4.1 follows as a corollary of Lemma 2.2. Recall the definition of good nodes from Section 3.2 and the lemma of [5] (Lemma 3.5) ensuring that in any graph, at least half of the edges are incident on good nodes. Similarly to the proof structure in Section 3.2, we establish (9) by combining Lemma 3.5 and the following lemma. ▶ Lemma 4.3. Fix some time t > tclean and the configuration C t and consider a node v ∈ V t of degree d = degt (v) > 0 that is good in the graph Gt . There exist universal constants α ∈ Z>0 and c > 0 such that 3 c E degt+α⌈log n⌉ (v) ≤ 1 − d. log n Before we can prove Lemma 4.3, we have to introduce some additional definitions. ▶ Definition (geometric tournament, length, Q-winner, repeated geometric tournament). Fix some integer κ ∈ Z>0 and consider κ independent 1+Geom(1/2) random variables X1 , . . . , Xκ (that is, each Xi is defined over the integers x ≥ 2 so that P(Xi = x) = 2−(x−1) ). A geometric tournament T consists of sampling X1 , . . . , Xκ , defining the length of T to be L = L(T ) = maxi∈[κ] Xi . Given a non-empty subset Q ⊆ {X1 , . . . , Xκ }, we say that the random variable Xi wins the geometric tournament T among Q, or, alternatively, that Xi is the Q-winner of T , if Xi > Xi′ for all i′ ∈ Q − {i}. A repeated geometric tournament is a stochastic process S = {Sj }∞ j=0 over Z≥0 defined by sampling countably many independent Pj geometric tournaments T1 , T2 , . . . and setting Sj = h=1 L(Th ). The connection to the algorithm reveals itself by observing that each (port) tournament of a node v ∈ V in the algorithm is a geometric tournament over the {0, 1}-coin tosses of the trnt variables associated with the degG (v) ports in P(v); the notions of length and Q-winner translate accordingly. Moreover, the sequence of starting times of v’s tournaments is a repeated geometric tournament over degG (v) random variables, where each phase includes two consecutive tournaments. The proof of Lemma 4.3 relies on a careful analysis of the geometric tournaments; this analysis is carried out in Section 4.2.1, culminating in Lemmas 4.4, 4.5, 4.6, and 4.7. ▶ Lemma 4.4. Consider an integer κ ∈ Z>0 , κ ≤ n, and a geometric tournament T over the random variables X1 , . . . , Xκ . There exists an integer ν = ν(n) ∈ Z>0 of order ν = Θ(log n) such that the length of T is at most ν whp.
L. Brinker, Y. Emek, and O. Louidor
17
▶ Lemma 4.5. Consider an integer κ ∈ Z>0 and a geometric tournament T over the random variables X1 , . . . , Xκ . There exists a universal constant c > 0 and an integer λ = λ(κ) ∈ Z>0 of order λ = Θ(log κ) such that for every non-empty subset Q ⊆ {X1 , . . . , Xκ }, the following two conditions hold (simultaneously) with probability at least c: (I) the length of T is λ; and (II) T has a Q-winner. Moreover, conditioned on the event that T has a Q-winner, each Xi ∈ Q is the winner with probability 1/|Q|. ▶ Lemma 4.6. Consider two integers κ, κ′ ∈ Z>0 , κ ≤ κ′ , and geometric tournaments T and T ′ over the random variables X1 , . . . , Xκ and X1′ , . . . , Xκ′ ′ , respectively. For every constant α ∈ Z≥0 , there exists a constant c = c(α) > 0 such that for every non-empty subset Q ⊆ {X1 , . . . , Xκ′ }, the following two conditions hold (simultaneously) with probability at least c: (I) L(T ′ ) ≥ L(T ) + α; and (II) T has a Q-winner. ▶ Lemma 4.7. Consider an integer κ ∈ Z>0 and a repeated geometric tournament S = {Sj }∞ j=0 over the random variables X1 , . . . , Xκ . There exist an integer µ = µ(κ) ∈ Z>0 of order µ = Θ(log3 κ) and a universal constant c > 0 such that for every integer j ≥ 0 and for every integer z ≥ µ, conditioned on Sj = s, the probability that Sj+h = s + z for some even (resp., odd) integer h > 0 is at least logc κ . We are now ready to establish Lemma 4.3. Proof of Lemma 4.3. Let v be the node from the lemma’s statement and let {u1 , . . . , uk } = {u ∈ NGt (v) : degt (u) ≤ d}, recalling that k ≥ d/3 as v is good in Gt . For i ∈ [k], let d0i = degG (ui ) and di = degt (ui ). Let λi = Θ(log d0i ) be the integer λ = λ(d0i ) promised in Lemma 4.5. Let Qi = {(ui , {ui , x}) : x ∈ Vt } and recall that |Qi | = di . Let µ = µ(n) = Θ(log3 n) be the integer promised in Lemma 4.7 and let t∗ be the earliest time t∗ ≥ t + µ + maxi∈[k] λi such that v starts a 2nd epoch tournament at time t∗ as part of a receiving-phase. Since each phase of v consists of two tournaments and is a receiving-phase with probability 1/2, it follows by Lemmas 4.4 and 4.7 that t∗ − t ≤ O(log3 n) whp; condition hereafter on this event. Let t̂ = t∗ + α⌈log n⌉ for a sufficiently large constant α ∈ Z>0 to be determined along the proof and let Y = d − degt̂ (v) be a random variable that captures the number of edges incident on v that become decided between time t and time t̂; our goal is to prove that cd E(Y ) ≥ log n for some (no matter how small) constant c > 0. ∗
∗
Let A be the event that v ∈ V t . By definition, ¬A implies that degt̂ ≤ degt (v) = 0. Therefore, if P(¬A) ≥ logc n for any constant c > 0, then E(Y ) ≥ E(Y | ¬A) · P(¬A) ≥ d ·
c , log n
thus completing the proof. Assume hereafter that c P(A) > 1 − log n
(10)
for an arbitrarily small constant c > 0. ti For i ∈ [k], let ti = t∗ − λi and let Ai be the event that ui ∈ V . Since Y ≥ P P i∈[k] 1¬Ai , it follows that E(Y ) ≥ E i∈[k] 1¬Ai , thus if there exists some z > 0 such P zd cd that P ≥ zc for any constant c > 0, then E(Y ) ≥ log i∈[k] 1¬Ai ≥ log n n by Markov’s inequality. Assume hereafter that X zd < c P 1¬Ai ≥ (11) log n z i∈[k]
18
Self-Stabilizing Algorithms in the Uniform Port Model
for any z > 0 and for any arbitrarily small constant c > 0. We further define the following events for i ∈ [k]: Let Bi be the event that node ui starts a phase at time ti . Let Ci be the event that (I) a 1st epoch tournament T of ui ends at time t∗ ; (II) T belongs to a proposing-phase (of ui ); and (III) T has a Qi -winner. Let Di be the ∗ event that port (ui , {ui , v}) is the Qi -winner of a tournament of ui that ends at time t . By Lemma 4.7, we know that P(Bi ) ≥ Ω
1 log d0i
≥Ω
1 log n
, whereas Lemma 4.5 ensures
that P(Ci | Bi ) ≥ Ω(1). Therefore, P(Bi ∧ Ci ) = P(Ci | Bi ) · P(Bi ) ≥
ϕ log n
(12)
for some universal constant ϕ > 0. Moreover, Lemma 4.5 also ensures that P(Di | Bi ∧ Ci ) =
1 1 1 = ≥ , |Qi | di d
(13)
where conditioned on Bi ∧ Ci , event Di is fully determined by the coin tosses of the ports incident on ui during the time interval [ti , t∗ ). W ∗ Let Ri be the event that prpt(ui {ui ,v}) = proposing0 and let R∨ = i∈[k] Ri . The key observation now is that Ai ∧ Bi ∧ Ci ∧ Di =⇒ Ri
and
∗
+1 A ∧ Ri =⇒ rcvt(v,{u = true . i ,v})
∗
+1 Taking Q = {(ui , {ui , v}) : rcvt(v,{u = true}, we can view the process of picking an i ,v}) incoming proposal that runs during the 2nd epoch of v (the one that starts at time t∗ ) as two geometric tournaments: the first one is defined over the coin tosses of the ports in P(v); the second one is defined over the coin tosses of the ports in Q (that is, a subset of the counter-ports of the ports in P(v)). As |P(v)| ≥ |Q|, we can apply Lemma 4.6 to conclude that there exists a universal constant c > 0, such that if A ∧ R∨ occurs, then v accepts a proposal during the phase with probability at least c, thus degt̂ (v) = 0 with probability at least c. Therefore, our goal is to prove that
P (A ∧ R∨ ) ≥
c log n
for some (no matter how small) constant c > 0. As P(A ∧ R∨ ) = P(A) − P(A ∧ ¬R∨ ) ≥ P(A) − P(¬R∨ ) , we can apply (10) to conclude that to establish the assertion, it suffices to prove that P(R∨ ) ≥
c log n
(14)
for an arbitrarily small constant c > 0. At this stage, the proof diverges to two cases according to the value of d: P ϕk ϕd Case 1: d ≥ 24 i∈k 1Bi ∧Ci ≥ log n ≥ 3 log n . Since ϕ log n. Inequality (12) ensures that E the events in {Bi ∧ Ci }i∈[k] are mutually independent, it follows, by Chernoff’s bound, that P
X i∈[k]
ϕd ϕd 1Bi ∧Ci ≤ ≤ exp − ≤ e−1 . 6 log n 24 log n
L. Brinker, Y. Emek, and O. Louidor
ϕ ϕ By plugging z = 12 and c = 12
P
X i∈[k]
1 −1 2 −e
19
into (11), we conclude that
ϕd 1 < − e−1 , 1¬Ai ≥ 12 log n 2
hence, be the union bound,
P
1Ai ∧Bi ∧Ci >
X
i∈[k]
ϕd ≥ P 12 log n
X
1Bi ∧Ci >
i∈[k]
ϕd ∧ 6 log n
X
1¬Ai <
i∈[k]
ϕd 1 > . 12 log n 2
Conditioning on this event and taking J = {i ∈ [k] : Ai ∧ Bi ∧ Ci }, inequality (13) implies V that the probability of j∈J ¬Di is bounded from above by |J| ϕd 1 1 12 log n ϕ ϕ 1− < 1− < exp − <1− , d d 12 log n 24 log n where the last transition holds as e−z < 1 − z2 for all 0 < z < 1. We can now establish (14) by developing
P(R∨ ) ≥ P
_
Ai ∧ B i ∧ C i ∧ D i
i∈[k]
≥P
_
Ai ∧ B i ∧ C i ∧ D i |
i∈[k]
i∈[k]
X
ϕd 1Ai ∧Bi ∧Ci > 12 log n
P
i∈[k]
>
X
ϕd 1Ai ∧Bi ∧Ci > · 12 log n
ϕ 1 ϕ · = . 24 log n 2 48 log n
Case 2: d < 24 ϕ log n. Since the events in {Bi ∧ Ci }i∈[k] are mutually independent, it follows, by (12), that P
^
1−
¬(Bi ∧ Ci ) ≤
i∈[k]
ϕ log n
k
≤
ϕ 1− log n
d/3
ϕd < exp − 3 log n
< 1−
ϕd , 48 log n
where the last transition holds as e−z < 1 − z2 for all 0 < z < 1. By plugging z = logd n and ϕ c = 96 into (11), we conclude that P
_ i∈[k]
¬Ai = P
X
i∈[k]
1¬Ai ≥ 1 <
ϕd . 96 log n
20
Self-Stabilizing Algorithms in the Uniform Port Model
Therefore, _ ^ _ P Ai ∧ B i ∧ C i ≥ P Ai ∧ Bi ∧ C i i∈[k]
i∈[k]
i∈[k]
=P
^
Ai − P
i∈[k]
≥P
Ai − P ¬
>
1−
Bi ∧ Ci
i∈[k]
i∈[k]
_
Ai ∧ ¬
i∈[k]
^
^
_
Bi ∧ Ci
i∈[k]
ϕd 96 log n
− 1−
ϕd 48 log n
=
ϕd . 96 log n
We can now establish (14) by developing _ P(R∨ ) ≥ P Ai ∧ B i ∧ C i ∧ D i i∈[k]
≥P
_
Ai ∧ B i ∧ C i ∧ D i |
i∈[k]
_
Ai ∧ B i ∧ C i · P
i∈[k]
_
Ai ∧ B i ∧ C i
i∈[k]
ϕd ϕ 1 = , > · d 96 log n 96 log n where the penultimate transition follows from (13).
4.2.1
◀
Stochastic Analysis of the Tournaments
Henceforth, for integer κ > 0 and Q ⊂ [κ], we let Lκ (Q) and Jκ (Q) be the length and winner of a tournament T restricted only to those random variables in Q. That is, Lκ (Q) = maxi∈Q Xi and Jκ (Q) is an index j ∈ Q such that Xj > Xi for all i ∈ Q \ {j} if such exists; if not, we set Jκ (Q) = 0. We also abbreviate Lκ ≡ Lκ ([κ]) and Jκ ≡ Jκ ([κ]). Finally, we let mκ := log2 κ , for the typical value of Lκ up to O(1). The following lemma upper bounds the right and left tails of Lκ around mκ and, in particular establishes exponential tightness. ▶ Lemma 4.8. For all integer κ ≥ 0 and t ≥ 0, P(Lκ > mk + t) ≤ C2−t
(15)
and t
P(Lκ < mk − t) ≤ e−2 . In particular, the sequence of random variables {Lκ − mk } is exponentially tight. Proof. By the union bound the probability in (15) is upper bounded by κP(X1 > mκ + t) ≤ κ2−(mκ +t−2) ,
(16)
L. Brinker, Y. Emek, and O. Louidor
21
which is bounded by the right hand side in (15) for suitable constants. On the other hand, by independence, the probability in (16) is equal to P(X1 < mκ − t)
κ
κ −(mκ −t) ≤ 1 − 2−(mκ −t) ≤ e−κ2 ,
which is upper bounded by the right hand side of (16) for suitable constants.
◀
The next lemma lower bounds the right tail of Lκ around mκ , together with the value of Jκ (Q) for all Q. ▶ Lemma 4.9. There exists c > 0, such that for all κ ≥ 1 integer, all t ≥ 0 such that mκ + t ≥ 3 is an integer, all ∅ ⊊ Q ⊆ [κ] and all j ∈ Q, 1 −t 2 P Lκ = mκ + t , Jκ (Q) = j ≥ c |Q|
(17)
In particular, under the same conditions, P Lκ = mκ + t , Jκ (Q) > 0 ≥ c2−t . . Proof. The second statement follows from the first by summation over j ∈ Q. Turning to the first, assume initially that Q = [κ]. P Xj = mκ +t
Y i̸=j
κ−1 −(t−2) 1 P Xi < mκ +t = 2−(mκ +t−1) 1−2−(mκ +t−1) ≥ ×2−t e−2 , κ
whenever 2−t+1 /κ is small enough, so that we can use the inequality 1 − x > e−2x . The right hand side is smaller than the right hand side in (17) with a suitable c > 0. If 2−t+1 /κ is not small enough, it must be that t < t0 and κ < κ0 for some fixed t0 , κ0 . In all these cases, it can be easily checked by hand that the desired probability is lower bounded by a positive constant, thanks to the requirement on mk + t. Modifying c as needed, this shows (17). Now for general Q, if |Q| ≥ κ/2, use independence of the X-s to lower bound the probability in (17) by P Lκ (Q) = m|Q| + (t + mκ − m|Q| ) , Jκ (Q) = j P Lκ (Qc ) = ⌈m|Qc | ⌉ . since ⌈m|Qc | ⌉ ≤ mκ + t. Since mk − m|Q| ∈ [0, 1] and the X-s are identically distributed, the first probability is at least (c/2)|Q|−1 2−t and the second at least c/2, by what we have shown before. On the other hand, if |Q| < κ/2, we lower bound the desired probability by P Lκ (Qc ) = m|Qc | + (t + mκ − m|Qc | ) P Lκ (Q) = ⌈m|Q| ⌉, Jκ (Q) = j Again, the first probability is at least (c/2)2−t and the second (c/2)|Q|−1 . In both cases the product is lower bounded by the right hand side of (17) with c2 /4 > 0 in place of c. ◀ We are now ready to prove the first three lemmas. Proof of Lemma 4.4. Plug in t = log k in the first statement of Lemma 4.8.
◀
Proof of Lemma 4.5. Take λ := ⌈mκ ⌉ ∨ 3 and use Lemme 4.9 with t := λ − mκ ∈ [0, 3]. ◀
22
Self-Stabilizing Algorithms in the Uniform Port Model
Proof of Lemma 4.6. Take λ := ⌈mκ ⌉ ∨ 3, λ′ := ⌈mκ′ ⌉ ∨ 3 + α, so that t := λ − mκ ∈ [0, 3] and t′ := λ′ − mκ′ ∈ [0, 3 + α] Then the desired probability is lower bounded by P Lκ = λ , Jκ (Q) > 0 P Lκ′ = λ′ ) . By Lemma 4.9, the first term is lower bounded by a universal positive constant and the second by an α dependent positive one. ◀ Next we turn to the last lemma. To this end, we shall need a local-central-limit type result. ▶ Lemma 4.10 (Local Central Limit Theorem Approximation). There exists C < ∞ such that for all κ ≥ 1, n ≥ 1, s integers, if S is a repeated tournament with κ nodes, then (s−nµ)2 C 1 P (Sn = s) − √ e− 2nσ2 ≤ n σ 2πn
where µ and σ 2 are the mean and variance of Lκ . Moreover, for all κ ≥ 1, |µ − mκ | ≤ C
|σ| ≤ C
;
Proof. The desired statement does not change if we replace S, σ, µ by S ′ , σ ′ , µ′ , defined as the former only with L′κ := Lκ − ⌊mκ ⌋ in place of Lκ . Then, by Theorem 1.2 from [25] the desired difference is bounded in absolute value for all n, s, by a constant times exp(−c τ 2 α) 1 σ33 + , τα n σ24
(18)
where α := n ·
∞ X
P L′κ = l P L′κ = l + 1
;
τ := σ3−1 n−1/3
;
σp := ∥L′κ ∥p ,
(19)
l=−∞
and c > 0. By the exponential tightness of Lκ , as shown by Lemma 4.8 and the second part of Lemma 4.9, for any p ≥ 1 fixed, σp is bounded from above and away from zero uniformly in κ. These two lemmas also show that the sum in (19) is bounded away from zero uniformly in κ. This bounds the expression in (18) by Cn−1 for a properly chosen C < ∞, which is uniform in κ. The second part is immediate upon noticing that σ = σ2 and, by Jensen’s Inequality, |µ − mκ | ≤ σ1 + 1. ◀ Proof of Lemma 4.7. Assume without loss of generality that j = s = 0. We can also assume that z is arbitrarily large. Indeed, if it is not, then κ must also be small and then one can check by hand that the desired probability is uniformly positive for all such κ-s and z-s. Set √ n0 = ⌈z/µ⌉, n1 = ⌈n0 + σ n0 /µ⌉ where µ, σ are as in Lemma 4.10. By Lemma 4.10,
P ∃n ∈ 2Z+ : Sn = z ≥
n1 X
n1 − n 0 σ P Sn = z ≥ c √ ≥ c′ . n µ 0 n=n0 n∈2Z
Above, we have used and that (z − nµ)2 /(nσ 2 ) is uniformly upper bounded, which holds whenever z and hence n0 are sufficiently large. The result follows, in view of the estimates on µ and σ in Lemma 4.10. The case of odd n is proved exactly in the same way. ◀
L. Brinker, Y. Emek, and O. Louidor
5
Sinkless Orientation
⃗ ⊆ V × V of size |E| ⃗ = |E| such that An orientation of the graph G = (V, E) is a set E ⃗ =⇒ {u, v} ∈ E; an edge {u, v} ∈ E is regarded as oriented outward of u and toward (u, v) ∈ E ⃗ if (u, v) ∈ E. ⃗ The goal in the sinkless orientation (SO) problem is to construct an v in E ⃗ orientation E of G such that for every node v ∈ V of degree degG (v) ≥ 3, the out-degree of v ⃗ = (V, E) ⃗ is at least 1 (i.e., v is not a sink in G). ⃗ Under the UP model, this is in the digraph G translated to using {TO, FROM} as the output label set so that an edge {u, v} ∈ E is oriented toward v in a configuration C if ω(C((u, {u, v}))) = FROM and ω(C((v, {u, v}))) = TO. ▶ Theorem 5.1. There exists a self-stabilizing UP algorithm that solves the SO problem and stabilizes in O(log2 n) time whp. The algorithm promised in Theorem 5.1 is presented in Section 5.1, first at a high level and then, from the perspective of the individual ports. Section 5.2 is then dedicated to proving the correctness of our algorithm and bounding its stabilization time, thus establishing Theorem 5.1.
5.1
The SO Algorithm
High-Level Description As a preliminary step, our SO algorithm orients all edges arbitrarily and selects three incident edges e1 , e2 , e3 for each node v ∈ V of degree deg(v) ≥ 3, referred to in the scope of this section as the designated edges of v. Following that, the goal of the algorithm is to ensure that at least one of the designated edges of v is oriented outward of v. To this end, whenever v becomes a sink with respect to its designated edges, node v flips the orientation of edge ei for some i ∈ {1, 2, 3}. The choice of edge ei , referred to as the next flip of v, is made in the previous round (as a preparation for the event that v becomes a sink) according to the following rule: if exactly 2 of v’s designated edges e1 , e2 , e3 are oriented toward v, then v picks the next flip uniformly at random among these two designated edges; otherwise (zero, one, or three of v’s designated edges are oriented toward v), v picks the next flip uniformly at random among its three designated edges.
Port-Level Description The edge orientation is maintained by means of variables ortp ∈ {0, 1}, referred to as the local orientation variables, that each port p ∈ P maintains. An edge e = {v1 , v2 } ∈ E is considered to be oriented toward vi , i ∈ {1, 2}, if ort(vi ,{v1 ,v2 }) = 1 and ort(v3−i ,{v1 ,v2 }) = 0. As long as edge e is unoriented (that is, ort(v1 ,{v1 ,v2 }) = ort(v2 ,{v1 ,v2 }) ), port (vi , {v1 , v2 }), i ∈ {1, 2}, updates its local orientation variable by picking ort(vi ,{v1 ,v2 }) ∼ Unif({0, 1}). The algorithm is designed so that once e becomes oriented, it remains oriented, although the orientation may flip if certain conditions, presented in the sequel, are satisfied. Consider a node v ∈ V and an incident edge e = {u, v} and let p = (v, e) be the port incident on v and e. Port p maintains a variable dsgp ∈ {1, 2, 3, ⊥}, referred to as the designated edge of p. The semantics of this variable is as follows: dsgp = i for some i ∈ {1, 2, 3} indicates that e is the i-th designated edge of v; dsgp = ⊥ indicates that e is not one of the three designated edges of v. The mechanism that controls the selection of exactly min{3, deg(v)} designated edges for v works as follows:
23
24
Self-Stabilizing Algorithms in the Uniform Port Model
If dsgp ∈ {1, 2, 3} and there exists p′ ∈ sibs(p) such that dsgp′ = dsgp , then p resets dsgp ← ⊥ with probability 1/2; and keeps the current value of dsgp (formally dsgp ← dsgp ) with probability 1/2. Otherwise, if dsgp = ⊥ and {1, 2, 3} ⊈ {dsgp′ : p′ ∈ sibs(p)}, then p assigns dsgp ← imin , where imin is the smallest i ∈ {1, 2, 3} such that i ∈ / {dsgp′ : p′ ∈ sibs(p)}. Otherwise, p keeps the current value of dsgp (formally dsgp ← dsgp ). The aforementioned mechanism guarantees that for each node v ∈ V , once the designated edge variables of the ports in P(v) have stabilized, there exists exactly one port p ∈ P(v) with dsgp = i for each 1 ≤ i ≤ min{3, deg(v)} — we subsequently refer to this port p as the i-th designated port of v and denote it by pi (v). The ports in p ∈ P(v) can distinguish between the cases deg(v) = 1, deg(v) = 2, and deg(v) ≥ 3 based on the maximum index i for which pi (v) exists (notice that p1 (v) must exist as deg(v) ≥ 1). Assuming that deg(v) ≥ 3, let D(v) = {i ∈ {1, 2, 3} : ortpi (v) = 1}; node v is regarded as a designated sink if |D(v)| = 3. Consider a node v ∈ V of degree deg(v) ≥ 3. Port p1 (v) maintains a variable nxtp1 (v) ∈ {1, 2, 3}, referred to as the next flip of v, that determines the designated edge whose orientation is to be flipped in case v becomes a designated sink. Variable nxtp1 (v) is updated in each round according to the following simple rule: if |D(v)| = 2, then nxtp1 (v) ∼ Unif(D(v)); otherwise (|D(v)| = 0, |D(v)| = 1, or |D(v)| = 3), nxtp1 (v) ∼ Unif({1, 2, 3}). The edge orientation flipping mechanism is controlled by a Boolean variable flppi (v) ∈ {true, false}, referred to as the flip flag, that each designated port pi (v), i ∈ {1, 2, 3}, maintains. Port pi (v) turns its flip flag on, setting flppi (v) ← true if and only if (I) D(v) = 3, that is, v is a designated sink; (II) nxtp1 (v) = i; and (III) flppi (v) = false. An orientation flip of an oriented edge e ∈ E is triggered by, and only by, a turned on flip flag: Consider a port p ∈ P and assume that the edge incident on p is oriented, i.e., ortp ̸= ortp̄ . Port p changes the value of its local orientation variable from ortp = 1 to ortp = 0 (resp., from ortp = 0 to ortp = 1) if and only if flpp = true (resp., flpp̄ = true). To complete the algorithm’s description, the output label associated with each port p ∈ P is determined directly from its local orientation variable: the output label associated with p is FROM or TO if ortp = 0 or ortp = 1, respectively.
5.2
Analysis
Throughout the analysis, we fix an arbitrary initial configuration C 0 and consider the (random) execution η = {C t }t≥0 of the SO algorithm starting from C 0 . A time t ∈ Z>0 is said to be clean with respect to η if the following conditions hold: 1. All edges are oriented in C t , i.e., ortt(v1 ,e) ̸= ortt(v2 ,e) for every e = {v1 , v2 } ∈ E. 2. For every node v ∈ V and index 1 ≤ i ≤ min{3, deg(v)}, there exists exactly one port p ∈ P(v) such that dsgtp = i. 3. For every node v ∈ V and port p ∈ P(v) such that dsgtp ∈ {1, 2, 3}, if flptp = true, then (I) |{p′ ∈ P(v) : dsgtp′ ∈ {1, 2, 3} ∧ orttp′ = 1}| = 3; and (II) flptp′ = false for every p′ ∈ sibs(p) such that dsgtp′ ∈ {1, 2, 3}. The following lemma allows us to designate a clean suffix of execution η; the subsequent analysis is then dedicated to analyzing that suffix. ▶ Lemma 5.2. There exists a time tclean ∈ Z>0 such that all times t ≥ tclean are clean with respect to η. Moreover, tclean ≤ O(log2 n) whp. Proof. Consider an edge e ∈ E. The update rule of the local orientation variables ensures that once e becomes oriented, it remains oriented at all subsequent times. Moreover, if
L. Brinker, Y. Emek, and O. Louidor
e is not oriented at time t > 0, then e becomes oriented in round t with probability 1/2, independently. Therefore, there exists a time t1 ∈ Z>0 such that condition (1) holds at all times t ≥ t1 and t1 ≤ O(log n) whp; condition hereafter on this event. Consider a node v ∈ V and an index 1 ≤ i ≤ min{3, deg(v)} and suppose that the designated port pi′ (v) has already been elected for all 1 ≤ i′ < i. The process behind the election of the designated port pi (v) is equivalent to an invocation of the LLE mechanism (see Section 2) and can be analyzed in the same way to conclude that there exists a time t2 ∈ Z>0 such that condition (2) holds at all times t ≥ t2 and t2 ≤ O(log2 n) whp; condition hereafter on this event. The proof is completed by observing that condition (3) holds (deterministically) at all times t > max{t1 , t2 }. ◀ Let tclean ∈ Z>0 be the time promised in Lemma 5.2. Our goal in the remainder of this section is to prove that starting from time tclean , the algorithm stabilizes within O(log2 n) rounds whp. To this end, we introduce the following additional definitions. ▶ Definition (pi (v), ei (v), two-sided designated edge). Consider a node v ∈ V and an index 1 ≤ i ≤ min{3, deg(v)} and recall that port p = (v, {u, v}) ∈ P(v) (resp., edge {u, v}) is regarded as the i-th designated port (resp., edge) of v at time t if dsgtp = i. Let pi (v) (resp., ei (v)) be the i-th designated port (resp., edge) of v at time tclean ; observe that pi (v) (resp., ei (v)) remains the i-th designated port (resp., edge) of v at all times t ≥ tclean as the values of the designated edge variables do not change from time tclean onward. We say that an edge e = (v1 , v2 ) ∈ E is two-sided designated if there exist some 1 ≤ i1 ≤ min{3, deg(v1 )} and 1 ≤ i2 ≤ min{3, deg(v2 )} such that e = ei1 (v1 ) and e = ei2 (v2 ). ▶ Definition (I t (v), designated sink, susceptible node). For a node v ∈ V of degree deg(v) ≥ 3 and a time t > tclean , let I t (v) = {ei (v) : i ∈ {1, 2, 3} ∧ orttpi (v) = 1} be the set of designated edges of v oriented toward v at time t. We say that v is a designated sink at time t if |I t (v)| = 3. We say that v is susceptible at time t if |I t (v)| = 2. The following observation states that after time tclean , no node serves as a designated sink for more than two consecutive rounds. ▶ Observation 5.3. Consider a node v ∈ V of degree deg(v) ≥ 3 and a time t > tclean . If v is a designated sink throughout the time interval [t, t′ ), then t′ ≤ t + 2. It is convenient to view the execution after time tclean through the lens of a virtual token passing process over the graph G, defined by placing a token on node v ∈ V at time t > tclean if and only if v is a designated sink at time t (recall that by definition, this requires that deg(v) ≥ 3). We shall bound the time it takes for the algorithm to stabilize by bounding the time it takes for all tokens to be deleted from G. Consider a node v ∈ V that holds a token τ at time t̂ > tclean and notice that Observation 5.3 guarantees that v cannot hold τ for more than two consecutive rounds. In particular, node v disposes of τ in round t̂ ≤ t ≤ t̂ + 1 by flipping the orientation of some edge e = {u, v} ∈ I t (v) (from the perspective of the ports, this means that ortt(v,e) = 1 = ortt+1 (u,e) and ortt(u,e) = 0 = ortt+1 , thus turning into a susceptible node. From the perspective of τ, (v,e) edge e’s orientation flip in round t results in one of three possible outcomes: A token shifting outcome: We think of token τ as being shifted from v to u in round t (so that τ is placed on u at time t + 1) if (I) deg(u) ≥ 3; (II) e is two-sided designated; and (III) u is susceptible at time t (which means that e is the only designated edge of u that is oriented outward of u at time t).
25
26
Self-Stabilizing Algorithms in the Uniform Port Model
A token deletion outcome: We think of token τ as being deleted from the graph in round t if at least one of the following conditions is satisfied: (I) deg(u) < 3; (II) e is not two-sided designated; or (III) u is not a designated sink at time t + 1.11 A token merging outcome: We think of token τ as being merged with other (at least one) tokens in round t, if (I) deg(u) ≥ 3; (II) e is a two-sided designated; (III) |I t (u)| < 2 (that is, u is neither susceptible, nor a designated sink, at time t); and (IV) u is a designated sink at time t + 1. We establish Theorem 5.1 by proving the following lemma. ▶ Lemma 5.4. Fix some time t > tclean and the configuration C t and let κ be the number of tokens in the graph at time t. Then, at time t + O(log n), the graph includes at most κ/2 tokens whp. Proof. Let U ⊆ V be the set of nodes that hold a token at time t. For each node u ∈ U , we construct a rooted full binary tree Tu , augmented with functions ℓVu and ℓE u that assign V E labels ℓu (x) ∈ V and ℓu (x) ∈ E, respectively, to each vertex x of Tu . The proof will proceed by coupling between the token passing process in G and a process defined over the rooted trees Tu , u ∈ U , presented in the sequel. Fix some node u ∈ U and let τu be the token held by u at time t. Notice that configuration t C determines the designated edge e = ei (u) = {u, v} of u, i ∈ {1, 2, 3}, whose orientation is flipped (in round t or t + 1) when u disposes of τu . Add a new vertex x as the root of Tu and V E set ℓVu (x) ← v and ℓE u (x) ← e. The construction of Tu , ℓu , and ℓu proceeds by applying the following inductive rule to each newly added vertex x with labels ℓVu (x) = v and ℓE u (x) = e: Add new vertices xa and xb as children of x in Tu and set ℓVu (xj ) ← wj and ℓE u (xj ) ← {v, wj } for j ∈ {a, b} if (I) deg(v) ≥ 3; (II) e is two-sided designated; and (III) v is susceptible at time t with I t (v) = {{v, wa }, {v, wb }}. Otherwise (deg(v) < 3, e is not two-sided designated, or v is not susceptible at time t), make x a leaf in Tu . Let S be the set of nodes that are susceptible at time t and recall that ℓVu maps each internal vertex x in Tu to a node ℓVu (x) ∈ S. Since for each node v ∈ S, exactly one of the designated edges ei (v), i ∈ {1, 2, 3}, is oriented outward of v at time t, it follows that there exists at most one u ∈ U and at most one internal vertex x ∈ Tu such that ℓVu (x) = v. S In other words, the restriction of the ℓV· functions to the internal vertices in u∈U Tu is S injective. (This is in contrast to the restriction of the ℓV· functions to the leaves in u∈U Tu that may map many leaves to the same node in V .) We conclude that the total number of S internal vertices in u∈U Tu is smaller than n (recall that the nodes in U are excluded from P S), hence u∈U |Tu | < 2n. Consider a random experiment, referred to as the tree walk process, defined as follows: Initially, a walker is placed on the root of Tu for each u ∈ U . In every (discrete) step, if the walker of tree Tu is placed on an internal vertex x ∈ Tu , then the walker moves to a vertex x′ ∈ Tu picked uniformly at random and independently among the two children of x in Tu . The tree walk process in Tu stops once the walker reaches a leaf. Consider a node u ∈ U and an internal vertex x ∈ Tu and denote the size of the subtree of Tu rooted at x by s(x). Since Tu is a (finite) full binary tree, it follows that (1) s(y) < s(x) 11
Notice that a token deletion outcome does not rule out the possibility that node u becomes a designated sink at some time t′ > t + 1; this however is reflected in the token passing process by u holding another token τ ′ ̸= τ , which, in the grand scheme of things, allows us to argue that the total number of tokens decreases by a factor of (at least) 2.
L. Brinker, Y. Emek, and O. Louidor
for each child y of x in Tu ; and (2) there exists a child y of x in Tu such that s(y) < s(x)/2. We conclude, by standard probabilistic arguments, that the walker in Tu reaches a leaf within O(log |Tu |) ≤ O(log n) steps whp. The key observation now is that we can couple between the tree walk process over the trees Tu , u ∈ U , and the token passing process over G, running the former with the same random source as the latter. Specifically, we keep track of the token τu placed on node u at time t and whenever a node v ∈ V disposes of τu by flipping the orientation of a designated edge e = {v, w}, the walker of tree Tu moves from a vertex x ∈ Tu with ℓVu (x) = v to a vertex ′ x′ ∈ Tu with ℓVu (x′ ) = w and ℓE u (x ) = e. The walker of tree Tu reaching a leaf x ∈ Tu corresponds to one of the following three outcomes with respect to the token τu : (I) τu experiencing a token deletion outcome; (II) τu experiencing a token merging outcome; or (III) τu experiencing a token shifting outcome ′ into node ℓVu (x) over edge ℓE u (x) in some round t > t, however, this implies that another token τũ , ũ = ̸ u, experienced a token deletion outcome in some round t ≤ t̃ < t′ when the orientation of a designated edge ei (ℓVu (x)) ̸= ℓE u (x), i ∈ {1, 2, 3}, flipped from being oriented V outward from ℓu (x) to being oriented toward ℓVu (x) (thus making ℓVu (x) susceptible at time t′ ). We conclude that once all walkers have reached the leaves of their corresponding trees, the number of tokens in the graph have decreased by a factor of at least 2. The assertion follows since each step of the tree walk process lasts (at most) 2 rounds in the token passing process. ◀
6
Maximal Node and Edge k-Coloring
To simplify the following definition, denote X = V (resp., X = E). For an integer k ≥ 2, a maximal node k-coloring (resp., maximal edge k-coloring) [22] of the graph G = (V, E), is a function f : X → [k] that assigns a color f (x) ∈ [k] to each node (resp., edge) x ∈ X and satisfies the following two conditions: (I) for each color 1 ≤ i < k, if nodes (resp., edges) x, y ∈ f −1 (i), then x and y are not adjacent in G; and (II) for each node (resp., edge) x ∈ f −1 (k) and for each color 1 ≤ i < k, there exists a node (resp., edge) y adjacent to x such that f (y) = i. Under the UP model, the problem of constructing a maximal node (resp., edge) k-coloring, where k = O(1), is translated to using [k] as the output label set so that a node (resp., edge) x ∈ X is considered to be colored i ∈ [k] in a configuration C if ω(C(p)) = i for all ports incident on x. ▶ Theorem 6.1. For every constant integer k ≥ 2, there exists a self-stabilizing UP algorithm that solves the maximal node k-coloring problem and stabilizes in O(log2 n) time whp. ▶ Theorem 6.2. For every constant integer k ≥ 2, there exists a self-stabilizing UP algorithm that solves the maximal edge k-coloring problem and stabilizes in O(log5 n) time whp. To establish Theorem 6.1 (resp., Theorem 6.2), we employ the self-stabilizing MIS (resp., MM) algorithm promised in Theorem 3.1 (resp., Theorem 4.1), combined with the well known fact (first observed in [12]) that the composition of self-stabilizing algorithms is also self-stabilizing. Specifically, we run k algorithms, denoted by Alg1 , . . . , Algk , where each Algi is invoked on the subgraph induced by the nodes (resp., edges) that are not colored by algorithms Alg1 , . . . , Algi−1 . For 1 ≤ i ≤ k − 1, algorithm Algi runs the MIS algorithm of Theorem 3.1 (resp., MM algorithm of Theorem 4.1) and assigns the color i to all nodes (resp., edges) selected to be included in the constructed MIS (resp., MM). Algorithm Algk simply assigns the color k to all nodes (resp., edges) in the subgraph it is invoked on.
27
28
Self-Stabilizing Algorithms in the Uniform Port Model
To see why this works, let Si be the set of nodes (resp, edges) colored by Algi and notice that for 1 ≤ i ≤ k − 1, any two nodes (resp., edges) in Si cannot be adjacent as Si is an independent set (resp., a matching). The maximality of Si , 1 ≤ i ≤ k − 1, implies that if x ∈ Si+1 , then x has an adjacent node (resp., edge) in Si′ for every 1 ≤ i′ ≤ i. The correctness of the composed maximal node (resp., edge) k-coloring algorithm follows by plugging k = i + 1. The time it takes for the composed algorithm to stabilize is bounded from above by k times the runtime bound of each individual Algi . Theorem 6.1 (resp., Theorem 6.2) follows from Theorem 3.1 (resp., Theorem 4.1) as k = O(1).
7
The 2-State Process may be Slow
The 2-state process is a simple distributed (stone age) MIS algorithm. The local automaton associated with each node has two states, referred to as IN and OUT, which are identified with the nodes’ output for the MIS problem in the natural manner. An IN node is active if it has some (at least one) IN neighbors; an OUT node is active if it has no IN neighbors. A non-active node is referred to as passive. The algorithm is defined so that each active node updates its state by choosing a new state u.a.r., while passive nodes stick to their current state. It is easy to see that the 2-state process is guaranteed to stabilize to a legal MIS w.p. 1 on any (finite) graph G = (V, E), starting from any initial configuration. Giakkoupis and Ziccardi [18] prove that on Gn,p , the stabilization time is logO(1) (n) whp for “most” values of the parameter p, and conjecture that this stabilization time upper bound holds, in fact, for any n-node graph G. In this section, we refute this conjecture by introducing an (infinite) family G of graphs G = (V, E) and corresponding initial configurations f : V → {IN, OUT} such that the stabilization time of the 2-state process on G under f is nΩ(1) w.p. Ω(1). The construction of an n-node graph G = (V, E) in G relies on a gadget called the (α, β, γ)-gadget, where 0 < α < β < γ < 1 are (rational) constants to be determined in the sequel; for now, we merely require that n is chosen so that nα , nβ , and nγ are all integers. The (α, β, γ)-gadget consists of nγ nodes with an edge connecting every two of them (i.e., the gadget forms a clique). Some nα nodes of the gadget are regarded as α-nodes; out of the remaining nγ − nα nodes of the gadget, some nβ nodes are regarded as β-nodes; all remaining nγ − nβ − nα nodes of the gadget are regarded as γ-nodes. We say that the (α, β, γ)-gadget is activated in round t of the execution if (I) all nodes in the gadget are OUT and passive up to (including) round t − 1; and (II) all nodes in the gadget become active, concurrently, in round t. Once the gadget is activated, the nodes start a tournament so that each node is IN for a (possibly empty) prefix of the tournament whose length is a Geom(1/2) random variable; following that, the node becomes OUT until the tournament ends. A node wins the tournament if it is the unique last IN node, in which case, all nodes in the gadget become (passive and) stable. If the tournament does not admit a (unique) winner, then a new tournament starts, involving a subset S of the nodes, where the content of S depends on events that occur at the rest of the graph. We show in the sequel that with sufficiently high probability, this set S includes all and only the gadget’s γ-nodes. Special attention is paid to the gadget’s first tournament, referred to as the principle tournament, that starts once the gadget is activated (and includes all nodes). The principle tournament is said to be α-completed (if and) when all the α-nodes are OUT, and βcompleted (if and) when all the α- and β-nodes are OUT. The principle tournament is said to be completed when either all nodes are OUT or when some node wins.
L. Brinker, Y. Emek, and O. Louidor
▶ Observation 7.1. For every choice of constants 0 < α < β < γ < 1 and for every sufficiently small constant ϵ > 0, there exists a constant c = c(α, β, γ, ϵ) > 0 such that the principle tournament of an (α, β, γ)-gadget is (1) α-completed in ℓ rounds for some (1 − ϵ)α lg n ≤ ℓ < (1 + ϵ)α lg n w.p. at least 1 − n−c ; (2) β-completed in ℓ rounds for some (1 − ϵ)β lg n ≤ ℓ < (1 + ϵ)β lg n w.p. at least 1 − n−c ; and (3) completed in ℓ rounds for some (1 − ϵ)γ lg n ≤ ℓ < (1 + ϵ)γ lg n w.p. at least 1 − n−c . The node set V of the graph G = (V, E) is partitioned into k = n1−γ clusters, denoted by C1 , . . . , Ck . For each i ∈ [k], the cluster Ci forms an (α, β, γ)-gadget, where we subsequently identify cluster Ci with its corresponding gadget and denote the sets of α-, β-, and γ-nodes in Ci by Ciα , Ciβ , and Ciγ , respectively. This means, in particular, that every possible intra-cluster edge is present in G. The graph G = (V, E) is also augmented with the following inter-cluster edges: For each 1 ≤ i < j ≤ k and for each u ∈ Ci and v ∈ Cj , the edge {u, v} is included in E if and only if one of the following two conditions is satisfied: (I) j = i + 1 and u ∈ Ciα ; or (II) j > i + 1 and u ∈ Ciα ∪ Ciβ . Put differently, the inter-cluster edges form a complete bipartite graph between the α-nodes Sk in Ci and the nodes in j=i+1 Cj ; and a complete bipartite graph between the β-nodes in Ci Sk and the nodes in j=i+2 Cj . Notice that the γ-nodes in Ci are not connected to (the nodes of) Cj for any j > i. The following observation is derived directly from the construction of G. ▶ Observation 7.2. Consider an MIS U ⊆ V of G. Then, |U ∩ C1 | = 1 and |U ∩ Ci | ≤ 1 for every 1 < i ≤ k. Moreover, if |U ∩ Cjγ | = 1 for each 1 ≤ j < i, then |U ∩ Ci | = 1. To complete the construction, we define the initial configuration f : V → {IN, OUT} associated with the graph G = (V, E). To this end, we simply set f (v) = IN if v ∈ C1 ; and f (v) = OUT otherwise. Consider an execution of the 2-state process on G under f and fix some index i ∈ [k]. Assuming that cluster Ci is activated (as defined earlier), let Ti denote the corresponding β principle tournament and let tα i , ti , and ti be the rounds in which Ti is α-completed, β-completed, and completed, respectively, assuming that the former two exist. Notice that cluster C1 is activated when the execution commences, which means that tournament T1 is well defined. Condition hereafter on the events presented in Observation 7.1 β with respect to T1 , which means that tα 1 , t1 , and t1 are also well defined (the latter is actually well defined regardless). The key observation now is that the construction of G guarantees that cluster C2 is α activated in round tα 1 (recall that C2 is dominated by each node in C1 ), hence tournament T2 is well defined. Moreover, cluster Cj cannot be activated before round tβ1 for any j > 2 (recall that Cj is dominated by each node in C1β ). Condition hereafter on the events presented in β Observation 7.1 with respect to T2 , which means that tα 2 , t2 , and t2 are well defined (the latter is actually well defined regardless). By choosing β < 2α and γ > α + β, we ensure that β β α tα 1 < t1 < t2 < t2 < t1 < t2 .
As before, the construction of G guarantees that cluster C3 is activated in round tα 2, hence tournament T3 is well defined. Moreover, cluster Cj cannot be activated before round tβ2 for any j > 3. Condition hereafter on the events presented in Observation 7.1 with respect
29
30
Self-Stabilizing Algorithms in the Uniform Port Model
β to T3 , which means that tα 3 , t3 , and t3 are well defined (the latter is actually well defined regardless). The choice of α, β, and γ ensures that β β α tα 2 < t2 < t3 < t3 < t2 < t3 .
Taking h = Ω(nc ), where c > 0 is the constant promised in Observation 7.1 for a sufficiently small ϵ, we can continue in this manner for i = 2, 3, . . . , h and conclude, by the union bound, that w.p. Ω(1), cluster Ci is activated in round tα i−1 and β β α tα i−1 < ti−1 < ti < ti < ti−1 < ti
for all 1 < i ≤ h (concurrently). In particular, there is a positive overlap between the round β α β intervals [tα i−1 , ti ) and [ti , ti+1 ) for every 1 < i < h. The last statement plays a key role by ensuring that for every round t < tβh , there exists some 1 ≤ j ≤ h such that some (at least one) nodes in Cjβ are IN in round t. Therefore, if cluster Ci starts a non-principle tournament in round t for some i ≤ j − 2, then this tournament involves all and only the nodes in Ciγ ; indeed, the β-nodes of Cj (more accurately, those which are IN) prevent the α- and β-nodes of Ci from joining this tournament. Combined with Observation 7.2, we conclude, in passing, that if U ⊆ V is the output MIS, then |U ∩ Ciγ | = |U ∩ Ci | = 1 for each cluster Ci that admits a winner before round tβh .
8
Additional Related Work
Assigning input/output labels from a finite set to the graph’s half-edges (or ports), rather than to the graph’s nodes, is certainly not a new idea in distributed computing. For example, in the context of round elimination techniques for locally checkable labeling (LCL) problems [24], a formalism based on such assignments was introduced by Brandt [9] and became a common practice since then. The study of uniform distributed algorithms dates back to the classic work of Angluin [6] who proved that uniform Las Vegas algorithms cannot elect a leader if termination detection is required (this impossibility result was extended in [21] to uniform algorithms that are allowed to fail with a bounded probability). In contrast, if the termination detection requirement is lifted, then leader election is possible even under the (truly uniform) stone age model [28]. The domain of self-stabilizing algorithms for local symmetry breaking problems has recently seen a surge of activity, with many algorithms of various levels of uniformity [27, 13, 18, 8, 16, 17]. However, none of the algorithms in those papers is both (1) truly uniform; and (2) efficient on general graphs. Truly uniform distributed computational models extend beyond the domain of distributed graph algorithms. One prominent example is the population protocols model [7], or more generally chemical reaction networks [26], which abstract molecules in a well-mixed solution. Another prominent example is the geometric amoebot model [10] for self-organizing particle systems (a.k.a. programmable matter). Returning to truly uniform distributed graph algorithms, the formulation of the stone age model used in the current paper is a simplified version, introduced in [13], of the original stone age model formulation presented by Emek and Wattenhofer [15]. In this regard, we note that the formulation of [15], which is better suited for asynchronous message-passing schedules, involves the notion of query letters; this means that the signal received by an
L. Brinker, Y. Emek, and O. Louidor
automaton at any given moment is sensitive to only one type of message, determined by the automaton’s current state. Emek and Wattenhofer prove [15] prove that the query letter restriction can be lifted, thus obtaining a formulation similar to that of [13] (and to the one used in the current paper), however this proof assumes graceful initialization and it is not clear if it extends to the realm of self-stabilizing algorithms. A natural question that arises from the results of the current paper is whether there exists an efficient simulation of self-stabilizing stone age algorithms (using the formulation of [13]) under the UP model.12 Given the LLE mechanism that enables the selection of a designated port p∗ (v) ∈ P(v) for each node v ∈ V (see Section 2), one may hope that the simulation becomes straightforward: the designated port p∗ (v) is responsible for simulating the actions of node v in the simulated execution. The caveat of this approach is that port p∗ (v) is mot necessarily directly exposed to the state of port p∗ (u) for the neighbors u of v, thus it takes up to 3 rounds for node v in the simulating execution to gather the information regarding the states of its neighbors. In an execution with a graceful initialization, this can be easily solved by partitioning the simulating execution into 3-round phases, each responsible for one round of the simulated execution, so that the first 2 rounds of a phase are dedicated to gathering information about the states of the neighbors. Unfortunately, this approach fails in the self-stabilization realm as the phases of different nodes are not necessarily synchronized, leaving the aforementioned question of simulating self-stabilizing stone age algorithms under the UP model open. On top of the node-centric stone age model, Emek and Wattenhofer also introduce a stone age variant that includes both “node devices” and “port devices” [15][Section 4.4]. As the variant of [15][Section 4.4] is also defined in terms of query letters, it is not clear how it compares to the UP model introduced in the current paper. In any case, the formulation of the UP model is significantly simpler and in our opinion, more natural.
12
the converse direction is inherently impossible due to the added expressivity of the UP model.
31
32
Self-Stabilizing Algorithms in the Uniform Port Model
References 1 2
3
4 5
6
7
8
9
10
11 12 13
14 15
Y. Afek, N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-Joseph. A biological solution to a fundamental distributed computing problem. Science, 331(6014):183–185, 2011. Yehuda Afek, Yuval Emek, and Noa Kolikant. Selecting a leader in a network of finite state machines. In 32nd International Symposium on Distributed Computing (DISC), pages 4:1–4:17, 2018. Yehuda Afek, Yuval Emek, and Noa Kolikant. The synergy of finite state machines. In 22nd International Conference on Principles of Distributed Systems (OPODIS), pages 22:1–22:16, 2018. Ian F. Akyildiz, Josep Miquel Jornet, and Massimiliano Pierobon. Nanonetworks: a new frontier in communications. Commun. ACM, 54(11):84–89, 2011. doi:10.1145/2018396.2018417. Noga Alon, László Babai, and Alon 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. Dana Angluin. Local and global properties in networks of processors (extended abstract). In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 82–93. ACM, 1980. doi:10.1145/800141.804655. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Comput., 18(4):235–253, 2006. URL: https://doi.org/10.1007/s00446-005-0138-3, doi:10.1007/S00446-005-0138-3. Shimon Bitton, Yuval Emek, Taisuke Izumi, and Shay Kutten. Self-stabilizing fully adaptive maximal matching. In Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni, editors, 28th International Conference on Principles of Distributed Systems, OPODIS 2024, Lucca, Italy, December 11-13, 2024, LIPIcs, pages 33:1–33:21. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2024. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2024.33, doi:10.4230/LIPICS.OPODIS.2024.33. Sebastian Brandt. An automatic speedup theorem for distributed problems. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 379–388. ACM, 2019. doi:10.1145/3293611.3331611. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: amoebot - a new model for programmable matter. In Guy E. Blelloch and Peter Sanders, editors, 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, Prague, Czech Republic - June 23 - 25, 2014, pages 220–222. ACM, 2014. doi:10.1145/2612669.2612712. Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Commun. ACM, 17(11):643–644, 1974. doi:10.1145/361179.361202. Shlomi Dolev, Amos Israeli, and Shlomo Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Comput., 7(1):3–16, 1993. doi:10.1007/BF02278851. Yuval Emek and Eyal Keren. A thin self-stabilizing asynchronous unison algorithm with applications to fault tolerant biological networks. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 93–102. ACM, 2021. doi:10.1145/ 3465084.3467922. Yuval Emek and Jara Uitto. Dynamic networks of finite state machines. Theor. Comput. Sci., 810:58–71, 2020. Yuval Emek and Roger Wattenhofer. Stone age distributed computing. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013, pages 137–146. ACM, 2013. doi: 10.1145/2484239.2484244.
L. Brinker, Y. Emek, and O. Louidor
16
17
18
19
20 21 22 23
24
25
26
27
28
George Giakkoupis, Volker Turau, and Isabella Ziccardi. Self-stabilizing MIS computation in the beeping model. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing, DISC 2024, Madrid, Spain, October 28 - November 1, 2024, LIPIcs, pages 28:1– 28:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL: https://doi.org/10. 4230/LIPIcs.DISC.2024.28, doi:10.4230/LIPICS.DISC.2024.28. George Giakkoupis, Volker Turau, and Isabella Ziccardi. Luby’s MIS algorithms made selfstabilizing. Inf. Process. Lett., 188:106531, 2025. URL: https://doi.org/10.1016/j.ipl. 2024.106531, doi:10.1016/J.IPL.2024.106531. George Giakkoupis and Isabella Ziccardi. Distributed self-stabilizing MIS with few states and weak communication. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 310–320, 2023. Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema. Weak models of distributed computing, with connections to modal logic. Distributed Comput., 28(1):31–53, 2015. URL: https://doi.org/ 10.1007/s00446-013-0202-3, doi:10.1007/S00446-013-0202-3. Amos Israeli and Alon Itai. A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett., 22(2):77–80, 1986. doi:10.1016/0020-0190(86)90144-4. Alon Itai and Michael Rodeh. Symmetry breaking in distributed networks. Inf. Comput., 88(1):60–87, 1990. doi:10.1016/0890-5401(90)90004-2. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036–1053, 1986. doi:10.1137/0215074. Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, and Akka Zemmari. An optimal bit complexity randomized distributed MIS algorithm. Distributed Comput., 23(56):331–340, 2011. URL: https://doi.org/10.1007/s00446-010-0121-5, doi:10.1007/ S00446-010-0121-5. Moni Naor and Larry J. Stockmeyer. What can be computed locally? In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 184–193. ACM, 1993. doi:10.1145/167088.167149. Tatpon Siripraparat and Kritsana Neammanee. An improvement of convergence rate in the local limit theorem for integral-valued random variables. Journal of Inequalities and Applications, 2021(1):57, 2021. doi:10.1186/s13660-021-02590-2. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Nat. Comput., 7(4):615–633, 2008. URL: https: //doi.org/10.1007/s11047-008-9067-y, doi:10.1007/S11047-008-9067-Y. Volker Turau. Making randomized algorithms self-stabilizing. In Keren Censor-Hillel and Michele Flammini, editors, Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, L’Aquila, Italy, July 1-4, 2019, Proceedings, Lecture Notes in Computer Science, pages 309–324. Springer, 2019. doi:10.1007/978-3-030-24922-9\ _21. Robin Vacus and Isabella Ziccardi. Minimalist leader election under weak communication. In Alkida Balliu and Fabian Kuhn, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, Hotel Las Brisas Huatulco, Huatulco, Mexico, June 16-20, 2025, pages 406–416. ACM, 2025. doi:10.1145/3732772.3733559.
33
34
Self-Stabilizing Algorithms in the Uniform Port Model
APPENDIX A
Proving Lemma 2.2
As E(Xi | Xi−1 ) ≤ rXi−1 almost surely, we can apply the low of total expectation and conclude, by induction on i, that E(Xi ) = E(E(Xi | Xi−1 )) ≤ rE(Xi−1 ) ≤ ri E(X0 ) = ri x0 . Fixing λ = ⌈log1/r x0 ⌉, we get E(Xλ+j ) ≤ rλ+j x0 ≤ rj for every j ≥ 0. As Xλ+j is integral and non-negative, Markov’s inequality ensures that P(Xλ+j > 0) = P(Xλ+j ≥ 1) ≤ rj . The assertion follows since Xλ+j > 0 ⇐⇒ T > λ + j.