Johanne Cohen
email: johanne.cohen@lri.fr

Jonas Lefèvre
email: jonas.lefevre@irif.fr

Khaled Maamra
email: khaled.maamra@uvsq.fr

George Manoussakis
email: george.manoussakis@lri.fr

Laurence Pilard
email: laurence.pilard@uvsq.fr

Khaled Maâmra

The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs

Keywords: Self-stabilization, 1-maximal matching, 2 3 -approximation

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Matching problems have received a lot of attention in different areas. Dynamic load balancing and job scheduling in parallel and distributed networks can be solved by algorithms using a matching set of communication links [START_REF] Berenbrink | On the stability of dynamic diffusion load balancing[END_REF][START_REF] Ghosh | Dynamic load balancing by random matchings[END_REF]. In the wireless network, the resource management can be modelized as matching problem between resources and users (see [START_REF] Han | Matching theory for wireless networks[END_REF] for a survey).

In graph theory, a matching M in a graph G is a subset of the edges of G without common nodes. A matching is maximal if no proper superset of M is also a matching whereas a maximum matching is a maximal matching with the highest cardinality among all possible maximal matchings. A matching M is 1-maximal if it satisfies the following property: ∀e ∈ M , no matching can be constructed by removing e from M and adding two edges to M \ {e}. A 1-maximal matching is a 2 3 -approximation to the maximum matching, and expected to get more matching pairs than a maximal matching, which only guarantees a 1 2 -approximation. In the following, n is the number of nodes and m is the number of edges in G. Some (almost) linear time approximation algorithm for the maximum weighted matching problem have been well studied [START_REF] Drake | A simple approximation algorithm for the weighted matching problem[END_REF][START_REF] Preis | Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs[END_REF], nevertheless these algorithms are not distributed. They are based on a simple greedy strategy using augmenting path. An augmenting path is a path, starting and ending in an unmatched node, and where every other edge is either unmatched or matched; i.e. for each consecutive pair of edges, exactly one of them must belong to the matching. Let us consider the example in Figure 2.(a). In this figure, u and v are matched nodes and x, y are unmatched nodes. The path (x, u, v, y) is an augmenting path of length 3 (written 3-augmenting path). It is well known [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] that given a graph G = (V, E) and a matching M ⊆ E, if there is no augmenting path of length 2k -1 or less, then M is a k k+1 -approximation of the maximum matching. See [START_REF] Drake | A simple approximation algorithm for the weighted matching problem[END_REF] for the weighted version of this theorem. The greedy strategy in [START_REF] Drake | A simple approximation algorithm for the weighted matching problem[END_REF][START_REF] Preis | Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs[END_REF] consists in finding all augmenting paths of length or less and by switching matched and unmatched edges of these paths in order to improve the maximum matching approximation.

In this paper, we present a self-stabilizing algorithm for finding a 1-maximal matching that uses the greedy strategy presented above. Our algorithm stabilizes after O(m × n 2 ) moves under the adversarial distributed daemon.

For the maximum matching problem, self-stabilizing algorithms have been designed for particular topologies. In anonymous tree networks, a self-stabilizing algorithms converging in O(n 4 ) moves under the sequential adversarial daemon is given by Karaata and Saleh [START_REF] Hakan | Distributed self-stabilizing algorithm for finding maximum matching[END_REF]. Recently, Datta et al. [START_REF] Ajoy | Maximum matching for anonymous trees with constant space per process[END_REF] improve this result, and give a silent self-stabilizing protocol that converges in O(n 2 ) moves. For anonymous bipartite networks, a self-stabilizing algorithms converging in O(n 2 ) rounds under the sequential daemon is given by Chattopadhyay et al. [START_REF] Chattopadhyay | Dynamic and self-stabilizing distributed matching[END_REF].

In unweighted or weighted general graphs, self-stabilizing algorithms for computing maximal matching have been designed in various models (anonymous network [START_REF] Asada | An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks[END_REF] or not [START_REF] Turau | A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2[END_REF], see [START_REF] Guellati | A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs[END_REF] for a survey). For an unweighted graph, Hsu and Huang [START_REF] Hsu | A self-stabilizing algorithm for maximal matching[END_REF] gave the first self-stabilizing algorithm and proved a bound of O(n 3 ) on the number of moves under a sequential adversarial daemon. Hedetniemi et al. [START_REF] Hedetniemi | Maximal matching stabilizes in time o(m)[END_REF] completed the complexity analysis proving a O(m) move complexity. Manne et al. [START_REF] Manne | A new self-stabilizing maximal matching algorithm[END_REF] gave a self-stabilizing algorithm that converges in O(m) moves under a distributed adversarial daemon. Cohen et al. [START_REF] Cohen | A self-stabilizing algorithm for maximal matching in anonymous networks[END_REF] extend this result and propose a randomized self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is O(n 2 ) moves with high probability, under the adversarial distributed daemon.

Manne et al. [START_REF] Manne | A self-stabilizing 2/3-approximation algorithm for the maximum matching problem[END_REF] and Asada and Inoue [START_REF] Asada | An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks[END_REF] presented some self-stabilizing algorithms for finding a 1-maximal matching. Manne et al. gave an exponential upper bound on the stabilization time of their algorithm (O(2 n ) moves under a distributed adversarial daemon). However, they didn't show that this upper bound is tight. In this paper, we prove this lower bound is sub-exponential by exhibiting an execution of Ω(2

√
n/2 ) moves before stabilization. Asada and Inoue [START_REF] Asada | An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks[END_REF] gave a polynomial algorithm but under the adversarial sequential daemon. Recently, Inoue et al. [START_REF] Inoue | An efficient silent self-stabilizing 1-maximal matching algorithm under distributed daemon without global identifiers[END_REF] gave a modified version of [START_REF] Asada | An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks[END_REF] that stabilizes after O(m) moves under the distributed adversarial daemon for networks without cycle whose length is a multiple of three.

In a weighted graph, Manne and Mjelde [START_REF] Manne | A self-stabilizing weighted matching algorithm[END_REF] presented the first self-stabilizing algorithm for computing a weighted matching of a graph with an 1 2 -approximation of the optimal solution. They established that their algorithm stabilizes after at most an exponential number of moves under any adversarial daemon (i.e., sequential or distributed). Turau and Hauck [START_REF] Turau | A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2[END_REF] gave a modified version of the previous algorithm that stabilizes after O(nm) moves under any adversarial daemon.

Figure 1 compares features of the aforementioned algorithms and our result. We are then interested in the following problem: how to efficiently build a 1-maximal matching in an identified graph with a general topology, using an adversarial distributed daemon and in a self-stabilizing way? In this paper, we present two algorithms solving this problem. The first one is the well-known algorithm from Manne et al. [START_REF] Manne | A self-stabilizing 2/3-approximation algorithm for the maximum matching problem[END_REF] that was the only one until now that solved this problem. The second algorithm is our contribution. We show that the Manne et al. algorithm reaches a sub-exponential complexity while we prove that our algorithm is polynomial (in O(m × n 2 )). This paper is an extended version of the conference paper [START_REF] Cohen | Polynomial self-stabilizing maximum matching algorithm with approximation ratio 2/3[END_REF], where we present our polynomial algorithm (but with a sketch of the proof only). In [START_REF] Cohen | Polynomial self-stabilizing maximum matching algorithm with approximation ratio 2/3[END_REF], we obtained a O(n 3 ) moves assuming an already built maximal matching. In this paper, under the same assumption, we obtain a O(n 2 ) moves. Thus, as we will develop this scheme in Sections 3 and 8, using a classical composition [START_REF] Dolev | Self-Stabilization[END_REF] of the self-stabilizing maximal matching algorithm given by Manne et al. [START_REF] Manne | A new self-stabilizing maximal matching algorithm[END_REF] and of our algorithm, we obtain a O(m × n 2 ) move complexity. This result has been improved after this article submission in [START_REF] Inoue | An efficient silent self-stabilizing 1-maximal matching algorithm under distributed daemon for arbitrary networks[END_REF].

In the rest of the document, we present the model (Section 2), then we give the strategy based on a 3-augmenting path deletion that is used to build a 1-maximal matching (Section 3). This strategy is used by both algorithms presented next. In Section 4, we precisely describe the Manne et al. algorithm [START_REF] Manne | A self-stabilizing 2/3-approximation algorithm for the maximum matching problem[END_REF] and present the proof of the existence of a sub-exponential execution in Section 5. Next, we give our polynomial algorithm in Section 6, its correctness proof in Section 7 followed by its convergence proof in Section 8.

Model

The system consists of a set of processes where two adjacent processes can communicate with each other. The communication relation is represented by an undirected graph G = (V, E) where |V | = n and |E| = m. Each process corresponds to a node in V and two processes u and v are adjacent if and only if (u, v) ∈ E. The set of neighbors of a process u is denoted by N (u) and is the set of all processes adjacent to u, and ∆ is the maximum degree of G. We assume all nodes in the system a have distance 3 unique identifier.

√ n ) [20] O(m.n 2 )
Here For the communication, we consider the shared memory model. In this model, each process maintains a set of local variables that makes up the local state of the process. A process can read its local variables and the local variables of its neighbors, but it can write only in its own local variables. A configuration C is the local states of all processes in the system. Each process executes the same algorithm that consists of a set of rules. Each rule is of the form of <name> :: if <guard> then <command>. The name is the name of the rule. The guard is a predicate over the variables of both the process and its neighbors. The command is a sequence of actions assigning new values to the local variables of the process.

A rule is activable in a configuration C if its guard in C is true. A process is eligible for the rule R in a configuration C if its rule R is activable in C and we say the process is activable in C. An execution is an alternate sequence of configurations and actions E = C 0 , A 0 , . . . , C i , A i , . . ., such that ∀i ∈ N * , C i+1 is obtained by executing the command of at least one rule that is activable in C i (a process that executes such a rule makes a move). More precisely, A i is the non empty set of activable rules in C i that has been executed to reach C i+1 and such that each process has at most one of its rules in A i . We use the notation

C i → C i+1 or C i Ai -→ C i+1 to denote this transition in E. Finally, let E = C 0 , A 0 , • • • , C k be a finite execution. We say E is a sub-execution of E if and only if ∃t ≥ 0 such that ∀j ∈ [0, • • • , k]:(C j = C j+t ∧ A j = A j+t ).
If C and C are two configurations in E, then we note C ≤ C if and only if C appears before C in E or if C = C . Moreover, we write E\C to denote all configurations of E except configuration C.

An atomic operation is such that no change can take place during its run, we usually assume that an atomic operation is instantaneous. In the shared memory model, a process u can read the local state of all its neighbors and update its whole local state in one atomic step. Then, we assume here that a rule is an atomic operation. An execution is maximal if it is infinite, or it is finite and no process is activable in the last configuration. All algorithm executions considered here are assumed to be maximal.

A daemon is a predicate on the executions. We consider only the most powerful one: the adversarial distributed daemon that allows all executions described in the previous paragraph. Observe that we do not make any fairness assumption on the executions.

An algorithm is self-stabilizing for a given specification, if there exists a sub-set L of the set of all configurations such that: every execution starting from a configuration of L verifies the specification (correctness) and starting from any configuration, every execution eventually reaches a configuration of L (convergence). L is called the set of legitimate configurations. A configuration is stable if no process is activable in the configuration. The algorithm presented here, is silent, meaning that once the algorithm has stabilized, no process is activable. In other words, all executions of a silent algorithm are finite and end in a stable configuration. Note the difference with a non silent self-stabilizing algorithm that has at least one infinite execution with a suffix only containing legitimate configurations, but not stable ones.

Common strategy to build a 1-maximal matching

In this paper, we present two algorithms. The first one, denoted by ExpoMatch, is the Manne et al. algorithm [START_REF] Manne | A self-stabilizing 2/3-approximation algorithm for the maximum matching problem[END_REF]. The second one, called PolyMatch, is the main contribution of this paper. These two algorithms share different elements and this section is devoted to give these main common points.

Both algorithms operate on an undirected graph, where every node has a distance 3 unique identifier. They also assume an adversarial distributed daemon and that there exists an already built maximal matching, noted M. Based on M, the two algorithms build a 1-maximal matching. To perform that, nodes search and delete any 3-augmenting paths they find in M. An augmenting path is a path in the graph, starting and ending in an unmatched node, and where every other edge is either unmatched or matched. Definition 1. Let G = (V, E) be a graph and M be a maximal matching of G. (x, u, v, y) is a 3-augmenting path on (G, M ) if: (i) (x, u, v, y) is a path in G (so all nodes are distincts); (ii) ∀a ∈ V : (x, a) ∈ M ∧(y, a) ∈ M ; and (iii) (u, v) ∈ M . Let us consider the example in Figure 2.(a). In this figure, u and v are matched nodes and x, y are unmatched nodes. The path (x, u, v, y) is a 3-augmenting path. Once an augmenting path is detected, nodes rearrange the matching accordingly, i.e., transform this path with one matched edge into a path with two matched edges (see Figure 2.(b)). This transformation leads to the deletion of the augmenting path and increases by one the cardinality of the matching. Both algorithms will stabilize when there are no augmenting paths of length three left. Thus the hypothesis of Karps's theorem [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] eventually holds, giving a 2 3 -approximation of the maximum matching (and so a 1-maximal matching). The underlying maximal matching. In the rest of the paper, M is the underlying maximal matching. This underlying matching is locally expressed by variables m v for each node v. If (u, v) ∈ M then u and v are matched nodes and we have:

m u = v ∧ m v = u.
If u is not incident to any edge in M, then u is a single node and m u = null. For a set of nodes A, we define single(A) and matched(A) as the set of single and matched nodes in A, accordingly to the underlying maximal matching M. Since we assume M to be stable, a node membership in matched(V ) or single(V ) will not change throughout an execution, and each node u can use the value of m u to determine which set it belongs to. Note that M can be built with any silent self-stabilizing maximal matching algorithm that works for general graph and with an adversarial distributed daemon. We can then use, for instance, the self-stabilizing maximal matching algorithm from [START_REF] Manne | A new self-stabilizing maximal matching algorithm[END_REF] that stabilizes in O(m) moves. Observe that this algorithm is silent, meaning that the maximal matching remains constant once the algorithm has stabilized.

2-phases algorithms. Both algorithms ExpoMatch and PolyMatch are based on two phases for each edge (u, v) in M: (1) detecting augmenting paths and (2) exploiting the detected augmenting paths. Node u keeps track of four variables. The pointer p u is used to define the final matching. The variables α u , β u are used to detect augmenting paths and contain single neighbors of u. Also, s u is a boolean variable used for the augmenting path exploitation. We will see in section 6 that algorithm PolyMatch uses a fifth variable named end u . In the rest of the paper, we will call M + the final 1-maximal matching built by any of the two algorithms. M + is defined as follows:

Definition 2. The built set of edges is:

M + = {(u, v) ∈ M : p u = p v = null} ∪ {(a, b) ∈ E \ M : p a = b ∧ p b = a}
The first set in the union is pairs of nodes that do not perform any rematch. These pairs come from M. The second set in the union is pairs of nodes that were not matched together in M, but after a 3-augmenting path detection and exploitation, they matched together.

Augmenting path detection. First, every pair of matched nodes u, v (v=m u and u=m v ) tries to find single neighbors they can rematch with. These single neighbors have to be available, in particular, they should not be married in a final way with another matched node. We will see in the next sections, that the meaning of being available is not the same in PolyMatch and ExpoMatch. We say that a single node x is a candidate for a matched node u if x is an available single neighbor of u. Note that u and v need to have a sufficient number of candidates to detect a 3-augmenting path: each node should have at least one candidate and the sum of the number of candidates for u and v should be at least 2. In both algorithms, the BestRematch predicate is used to compute candidates of a matched node u, writing in α u and β u . Then, the condition below is used in both algorithms -in the AskFirst predicate -to ensure the number of candidates is sufficiently high to detect if u belongs to a 3-augmenting path.

α u = null ∧ α mu = null ∧ 2 ≤ U nique({α u , β u , α mu , β mu }) ≤ 4
where U nique(A) returns the number of unique elements in the multi-set A.

Augmenting path exploitation. The exploitation is done in a sequential way. First, two nodes matched together u and v agree on which one starts to build a rematch and which one ends. This local consensus is done using AskFirst and AskSecond functions. Observe that these predicates are exactly the same in both algorithms. These predicates use the local state of u and v to assign a role to these two nodes. If AskFirst(u) is not null then u starts to rematch and v ends. Otherwise, AskSecond(u) is not null and then v starts to rematch and u ends.

Observe that there are only three distinct possible values for the quadruplet (AskFirst(u), AskSecond(u), AskFirst(v), AskSecond(v)) for any couple (u, v) ∈ M and whatever the α and β values are. These are: (null, null, null, null) or (x, null, null, y) or (null, x, y, null), with x and y are two distincts single nodes. The first case means that there is no 3-augmenting path that contains the couple (u, v). The two other cases mean that (x, u, v, y) is a 3-augmenting path. The second case occurs when x < y, otherwise we are in the third case. Node u is said to be First if AskF irst(u) = null. In the same way, u is Second if AskSecond(u) = null. So, if a 3-augmenting path is detected though (u, v), the roles of u and v depend on the identifiers of single nodes (candidates) in the augmenting path, i.e., u is First iff its single neighbor in the augmenting path has a smaller identifier than the single neighbor of v in the augmenting path.

Graphical convention. We will follow the above conventions in all the figures: matched nodes are represented with thick circles and single nodes with thin circles. Node identifiers are indicated inside the circles. Moreover, all edges that belong to the maximal matching M are represented with a thick line, whereas the other edges are represented with a simple line. We illustrate the use of the p-values by an arrow, and the absence of the arrow or symbol 'T' mean that the p-value of the node equals to null. A prohibited value is first drawn in grey, then scratched out in black. For instance, in Figure 8, node x 1 is single, nodes u 1 and v 1 are matched, the edge (u 1 , v 1 ) ∈ M and p x3 = v 2 .

Description of the algorithm ExpoMatch

We precisely describe here the algorithm ExpoMatch [START_REF] Manne | A self-stabilizing 2/3-approximation algorithm for the maximum matching problem[END_REF]. The algorithm itself is shown in Figure 3.

Augmenting path detection. In this algorithm, a single node x is a candidate for a matched node u if it is not involved in another augmenting path exploitation, i.e., if p x = null ∨ p x = u.

Augmenting path exploitation. A 3-augmenting path is exploited in two phases. These two phases are performed in a sequential way. Recall that node u is said to be First if AskF irst(u) = null and node u is Second if AskSecond(u) = null. Let us consider two nodes u and v such that (u, v) ∈ M. Let us assume that u and v detects an augmenting path.

1. The First node starts : Exactly one node among u and v attempts to rematch with one of its candidates.

This phase is complete when the first node, let say u, is such that s u = T rue and this indicates to the Second node (v) that the first phase is over. 2. The Second node continues: only when the first node succeeds will the second node attempt to rematch with one of its candidates. (a) If this also succeeds, the exploitation is done and the augmenting path is said to be fully exploited ; (b) Otherwise the rematch built by the First node is deleted and candidates α and β are computed again, allowing then the detection of some new augmenting paths.

-----Rules for each node u in single(V)

SingleNode :: if (pu = null ∧ Lowest({v ∈ N (u) | pv = u}) = null) ∨ pu / ∈ matched(N (u)) ∪ {null}∨ (pu = null ∧ pp u = u) then pu := Lowest({v ∈ N (u) | pv = u}) ------Rules for each node u in matched(V) Update :: if (αu > βu) ∨ (αu, βu / ∈ single(N (u)) ∪ {null}) ∨ (αu = βu ∧ αu = null) ∨ pu / ∈ single(N (u)) ∪ {null} ∨ ((αu, βu) = BestRematch(u) ∧ (pu = null ∨ pp u / ∈ {u, null})) then (αu, βu) := BestRematch(u)
(pu, su) := (null, f alse)

MatchFirst :: MatchSecond ::

ResetMatch :: Let x = AskFirst(u) Let y = AskSecond(u) if AskFirst(u) = AskSecond(u) = null if x = null ∧ (pu = x ∨ su = (pp u = u)) if y = null ∧ sm u = true ∧ pu =y ∧ (pu, su) = (null, f alse) then pu := x
then pu := y then (pu, su) := (null, f alse) su := (pp u = u) -----Predicates and functions Rules description. There are four rules for matched nodes. The Update rule is the rule with the highest priority. This rule allows a matched node to update its α and β variables, using the BestRematch predicate. Then, predicates AskFirst and AskSecond are used to define the role the node will have in the 3-augmenting path exploitation. If the node is First (resp. Second ), then it will execute MatchFirst (resp. MatchSecond ) several times for this 3-augmenting path exploitation. The ResetMatch rule is performed to reset bad initialization and also to reset an augmenting path exploitation that did not terminate. For instance, this case happens when the single candidate of the Second node rematch with some other node in the middle of the exploitation path process. Let us consider (u, v) ∈ M and assume that u and v detects an augmenting path with u is First. The MatchFirst rule is used by u to build its rematch. The rule is performed a first time by u to propose a rematch to its candidate x (u sets p u to x). Then, if x accepts (p x = u), u performs this rule a second time to communicate to v that its rematch attempt is a succeed (u sets s u to T rue). The MatchSecond rule is used by the node v to build its rematch. This rule can only be performed if s u = T rue. Then, the rule is performed once by v to propose a rematch to its candidate y (v sets p v to y). Then, if y accepts (p y = v), the path is fully exploited and will not change during the rest of the execution.

BestRematch(u) ≡ a := Lowest ({v ∈ single(N (u)) ∧ (pv = null ∨ pv = u)}) b := Lowest ({v ∈ single(N (u)) \ {a} ∧ (pv = null ∨ pv = u)}) return (a, b) AskFirst(u) ≡ if αu = null ∧ αm u = null ∧ 2 ≤ U nique({αu, βu, αm u , βm u }) ≤ 4 then if αu < αm u ∨ (αu = αm u ∧ βu = null) ∨ (αu = αm u ∧ βm u = null ∧ u <
There is only one rule for single nodes, called SingleNode. Recall that all neighbors of a single node are matched, since M is a maximal matching. A single node should always point to its smallest neighbor that points to it. This rule allows to point to such a neighbor but also to reset a bad p-value to null. Observe that a single node x cannot perform this rule if p px = x, which means that if x point to some neighbor that points back to x, then x is locked.

The ExpoMatch algorithm is sub-exponential

In this section, we exhibit an execution of length 2 N in a chosen graph having Θ(N 2 ) nodes. To do that, we define, under some conditions, how to translate a configuration into a binary integer. Then, we give an execution where all configurations corresponding to integers from 0 to 2 N -1 appear. This gives us an execution of length in Ω(2 N ).

State of a matched edge

A bit in the binary integer of a given configuration correspond to a particular state of the nodes in a 3-augmenting path. More precisely, according to the p-values of these nodes, the associated bit of the path will be 0, 1 or undef. Figure 5 represents an instance of the chosen graph for N = 4. Observe that any matched node only has one single neighbor. This property will hold for any N . Thus, a 3-augmenting path can be determined by its matched edge.

Definition 3 (State of a matched edge). Let e = (u, v) be an edge in the maximal matching M such that u (resp. v) has one single neighbor x (resp. y). Assume y < x. Edge e is said to be:

• in state Off if p x = null, p u = null, p v = null and p y = null. • in state AlmostOff if p x / ∈ {null, u}, p u = null, p v = null, and p y = null. • in state On if p x = null, p u = x, p v = y and p y = v. • in state AlmostOn if p x / ∈ {null, u}, p u = x, p v = y and p y = v.
Note that a matched edge can be in none of the states presented below. The states of an edge represents the different steps of an augmenting path exploitation. Now, we exhibit an execution to switch an edge (u, v) from state Off to state On in Lemma 1 and then, from state AlmostOn to state AlmostOff in Lemma 2.

Lemma 1. Let e = (u, v) be an edge in the maximal matching M such that u (resp. v) has one single neighbor x (resp. y). Assume y < x. Let C be a configuration where e is in state Off and v = min({w ∈ N (y) : p w = y} ∪ {v}). There exists a finite execution starting in C and ending in D such that:

(i) only nodes u, v and y make moves between C and D and (ii) edge e is in state On in D.

Proof. We describe a finite execution starting in C and ending in D that allows to switch edge (u, v) from state Off to state On and where only nodes u, v and y make moves. Nodes u and v belong to a 3-augmenting path in C since p x = p y = null by assumption. If α u = x, then node u executes an Update move and sets (α u , β u ) = (x, null). If α v = y, then node v executes an Update move and sets (α v , β v ) = (y, null). Now, the variables α u and α v are well defined. Since y < x, we have AskF irst(v) = y and AskSecond(u) = x. So node v executes a MatchFirst move and sets p v = y. Let C 1 → C 2 be the transition where v makes this M atchF irst move. Observe that only u and v made some moves from C to C 2 . Moreover, u ∈ N (y) since u has only one single neighbor that is x. Thus v = min({w ∈ N (y) : p w = y} ∪ {v}) still holds in C 2 and so, node y chooses node v to match with by executing a SingleNode move. Finally, node u is eligible to execute a MatchSecond move and it then points to node x. The edge (u, v) is now in state On. Now, we exhibit an execution to switch edge (u, v) from state AlmostOn to state AlmostOff. Lemma 2. Let e = (u, v) be an edge in the maximal matching M such that u (resp. v) has one single neighbor x (resp. y). Assume y < x. Let C be a configuration where: e is in state AlmostOn and {w ∈ N (y) : p w = y} = {v}. There exists a finite execution starting in C and ending in D such that:

(i) only nodes u, v and y make moves between C and D and (ii) edge e is in state AlmostOff in D.

Proof. We describe a finite execution starting in C and ending in D that allows to switch edge (u, v) from state AlmostOn to state AlmostOff and where only nodes u, v and y make moves. Since edge (u, v) is in state AlmostOn, then p x ∈ {null, u} and so BestRematch(u) = (null, null). If (α u , β u ) = (null, null) then node u executes an Update move. Otherwise, AskFirst(u) = AskSecond(u) = null and, since p u = null, u executes a ResetMatch move. In both cases, after the move, (p u , s u ) = (null, f alse) and (α u , β u ) = (null, null). α u = null implies AskF irst(v) = null, and AskFirst(u) = null implies AskSecond(v) = null. Moreover, since p v = null, v executes a ResetMatch move and sets p v = null. Let C 1 → C 2 be the transition where v makes this ResetM atch move. Since {w ∈ N (y) : p w = y} = {v} holds in the configuration C and since only u and v made some moves from C to C 2 then we have: {w ∈ N (y) : p w = y} = ∅ holds in C 2 . Thus node y performs a SingleNode move and sets p y = null. The edge (u, v) is now in state AlmostOff.

The graph G N and how to interpret a configuration into a binary integer

In the following, we describe an execution corresponding to count from 0 to 2 N -1, where N is an arbitrary integer. This execution occurs in a graph denoted by G N with Θ(N 2 ) nodes. G N is composed by N sub-graphs, each of them representing a bit. The whole graph then represents an integer, coded from these N bits. G N has 2 kind of nodes: the nodes represented by circles (• -nodes) and those represented by squares ( -nodes). The • -nodes are used to store bit values and hence an integer. The -nodes are used to implement the "+1" operation as we count from 0 to 2 N -1. We now formally describe the graph G N = (V N , E N ):

V N = V • N ∪ V N where V • N = 0≤i<N {b(i, k)|k = 1, 2, 3, 4} V N = 0≤j<i<N {r 1 (i, j), r 2 (i, j)} E N = E • N ∪ E N where E • N = 0≤i<N {(b(i, k), b(i, k + 1))|k = 1, 2, 3} E N = 0≤j<i<N {(b(i, 1), r 1 (i, j)) , (r 1 (i, j), r 2 (i, j)) , (r 2 (i, j), b(j, 4
))} Figure 4 gives a partial view of the graph G N corresponding to the ith bit-block.

b(i, 1) b(i, 2) b(i, 3) b(i, 4) r2(i + 1, i) r2(i + 2, i) r2(N -1, i) b(i -1, 4) b(i -2, 4) b(0, 4) r1(i, i -1) r1(i, i -2) r1(i, 0) r2(i, i -1) r2(i, i -2) r2(i, 0) Bit i
M = {(b(i, 2), b(i, 3))|0 ≤ i < N } ∪ {(r 1 (i, j), r 2 (i, j))|0 ≤ j < i < N } This maximal matching is encoded with the m-variables then we have: ∀i, j with 0 ≤ j < i < N : m b(i,2) = b(i, 3), m b(i,3) = b(i, 2), m r1(i,j) = r 2 (i, j) and m r2(i,j) = r 1 (i, j)
The matching M is a 1 2 -approximation of the maximum matching and the algorithm ExpoMatch updates this approximation building M + , a 2 3 -approximation of the maximum matching. M + is encoded with the p-variable and we also use this variable to encode the binary integer associated to a configuration.

Example. As an illustration, graph G 4 is shown in Figure 5. In this example, the bold edges are those belonging to the maximal matching M and arrows represent the local variable p of the algorithm ExpoMatch. A node having no outgoing arrow has its p-variable equal to null.

As we said, the •-nodes are used to encode the N bits. Each bit i is encoded with the local state of the 4 following nodes: b(i, 1), b(i, 2), b(i, 3), b(i, 4). These nodes are then named b(i, k), for "the k th node of the bit i ". For instance, node 10 is the fourth node of the bit 0, thus node 10 is called b(0, 4). In the following, we will refer to these four nodes as the i th bit-block. The binary value associated to a bit-block is computed accordingly to the p-value of each node in the bit-block. The following definition gives this association:

Definition 4 (Bit-block encoding). In graph G N , nodes {b(i, 1), b(i, 2), b(i, 3), b(i, 4)} are the i th bit-block, for some 0 ≤ i < N . This bit-block encodes the value 1 ( resp. 0) if the edge (b(i, 2), b(i, 3)) is in state On ( resp. Off) and if ∀j with 0 ≤ j < i, p r1(i,j) = p r2(i,j) = null.
Note that the value encoded by a bit-block is not always defined. But when all bit-blocks encode a bit in a given configuration, then we can associate a positive integer ω to this configuration.

Definition 5 (ω-configuration).

Let ω be an integer s.t. 0 ≤ ω < 2 N , a configuration C is said to be an ω-configuration if for any integer 0 ≤ i < N , the i th bit of ω is the value encoded by the i th bit-block in C.

Observe that all the p-values of the -nodes have to be null in any ω-configuration. In Figure 5, all p-values of -nodes are null. Moreover, the edges (9, 8), [START_REF] Hakan | Distributed self-stabilizing algorithm for finding maximum matching[END_REF][START_REF] Inoue | An efficient silent self-stabilizing 1-maximal matching algorithm under distributed daemon for arbitrary networks[END_REF] and [START_REF] Preis | Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs[END_REF][START_REF] Manne | A self-stabilizing 2/3-approximation algorithm for the maximum matching problem[END_REF] are in state Off while the edge [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF][START_REF] Hedetniemi | Maximal matching stabilizes in time o(m)[END_REF] is in state On. Thus, G 4 encodes the binary integer 0010 and so Figure 5 shows a 2-configuration.

Identifiers in G N

In order to exhibit our execution counting from 0 to 2 N -1, we need to be able to switch edges between On and Off. This can be done executing the guarded rules of ExpoMatch. Since this algorithm uses identifiers, we need some properties on identifiers of nodes in G N . The Ident function gives the identifier associated to a node in V N . Recall that we assume each node has a unique identifier. These identifiers must satisfy the three following properties:

Property 1 (Identifiers order in G N ). Let b(i, k), b(i , k ), b(i, 2
) and b(i, 3) be nodes in V • N , and r 1 (i, j) and r 2 (i, j) be nodes in V N . We have:

1. Ident(b(i, k)) > Ident(b(i , k )) if (i > i ) ∨ (i = i ∧ k > k ) 2. Ident(b(i, 2)) < Ident(r 1 (i, j)) 3. Ident(b(i, 3)) > Ident(r 2 (j, i))
We now show that in graph G N , there exists an Ident function that satisfies Property 1. Indeed, the property holds for the following naming:

Let c = |V • N | and s = |V N | 2 .
There are c nodes of kind b, s nodes of kind r 1 and s nodes of kind r 2 as well. Nodes of kind r 2 are named from 1 to s. Nodes of kind b are named from

s + 1 to s + c such that: ∀i, 0 ≤ i < N, ∀k ∈ {1, 2, 3, 4} : Ident(b(i, k)) = s + 4i + k.
And finally, nodes of kind r 1 are named from s+c+1 to s+c+s. Figure 5 shows graph G 4 with such a naming (c=16 and s=6).

Counting from

0 to 2 N -1
We build an execution containing all ω-configurations with 0 ≤ ω < 2 N -1. To to this, we build an execution from an ω-configuration to the (ω + 1)-configuration using a '+1' operation. Thus we need to be able to switch bit from 0 to 1 and from 1 to 0. The main scheme is the following: let us consider a binary integer x. The '+1' operation consists in finding the rightmost 0 in x. Then all 1 at the right of this 0 have to switch to 0 and this 0 has to switch to 1 (if x = x 011 . . . 1 then x + 1 = x 100 . . . 0). Then if 0 is the i th bit of x, the i th bit-block has to switch from 0 to 1 during the '+1'operation. And each j th bit-block, with 0 ≤ j < i, has to switch from 1 to 0.

The switch of a bit-block from 0 to 1 only needs the •-nodes to perform moves (see Lemma 1). However, this is not the case when we want to switch a bit-block from 1 to 0. Indeed, we use some other nodes to help to perform the switch: the -nodes.

Theorem 1. Let ω be an integer such that 0 ≤ ω < 2 N -1. There exists a finite execution to transform an ω-configuration into an (ω + 1)-configuration.

Proof. Let C be an ω-configuration. Let ρ be the integer such that the ρ -1 first bits of ω equal to 1 and the value of its ρ th bit to 0. This implies that the ρ th bit of ω + 1 is the first bit equal to 1. We distinguish two cases: ρ = 0 and ρ > 0. (i) In the case where ρ = 0, edge (b(0, 2), b(0, 3)) is in state Off by definition. Since the 0th bit of integer ω + 1 is equal to 1, (b(0, 2), b(0, 3)) must be in state On in the (ω + 1)-configuration. By Property 1, we have Ident(b(0, 1)) < Ident(b(0, 4)). Moreover nodes b(0, 3) and b(0, 2) only have one single neighbor, so the hypotheses of Lemma 1 are satisfied. Thus, from Lemma 1, there exists an execution to switch edge (b(0, 2), b(0, 3)) from state Off to state On and in this execution, only nodes b(0, 1), b(0, 2) and b(0, 3) make moves. At the end, the 0th bit has changed from 0 to 1 and the other did not change. We then have an (ω + 1)-configuration. (ii) In the case where ρ > 0, for every integer i from 0 to ρ -1, edge (b(i, 2), b(i, 3)) is in state On and edge (b(ρ, 2), b(ρ, 3)) is in state Off. We can execute the following sequence of moves to obtain the (ω + 1)-configuration:

1. We first consider the 3-augmenting path (b(ρ, 1), r 1 (ρ, j), r 2 (ρ, j), b(j, 4)) for any integer j, 0 ≤ j < ρ.

We prove that the matched edge of this path is in state Off and that it satisfies the assumptions of Lemma 1. Then, we switch this edge from state Off to state On applying Lemma 1 (where the path (x, u, v, y) in this lemma corresponds to the path (b(ρ, 1), r 1 (ρ, j), r 2 (ρ, j), b(j, 4))). Note that ∀j, 0 ≤ j < ρ, node r 1 (ρ, j) (resp. r 2 (ρ, j)) is adjacent to one single node b(ρ, 1) (resp. b(j, 4)). As for any j, 0 ≤ j < ρ, the j th bit-block encodes the value 1 in C, then p b(j,4) = null in C.

In the same way, as the ρ th bit-block encodes the value 0 in C, then p b(ρ,1) = null in C. As C is an ω-configuration, then p r1(ρ,j) = null and p r2(ρ,j) = null. Thus the edge (r )) from state Off to state On. 4. Now, for each integer j, 0 ≤ j < ρ, edge (r 1 (ρ, j), r 2 (ρ, j)) is now in state AlmostOn. From Lemma 2, there exists an execution to switch edge (r 1 (ρ, j), r 2 (ρ, j)) from state AlmostOn to state AlmostOff.

1 (ρ, j), r 2 (ρ, j)) is in state Off in C. Moreover, Ident(b(j, 4)) < Ident(b(ρ, 1
At the end of this execution, we obtain a configuration where the ρ -1 first bits of ω are equal to 0 and the ρ th bit is 1. Moreover, observe that all -nodes are in state AlmostOff or Off, thus they all have their p-value sets to null. We are then in an (ω + 1)-configuration.

Corollary 1. Let n be the number of nodes. In the worst case, Algorithm ExpoMatch stabilizes after Ω(2

√ n/2
)moves under the central daemon.

Proof. We can build an execution that contains all the ω-configurations for every value ω, 0 ≤ ω < 2 N . By applying Theorem 1, this execution can be split into 2 N parts corresponding to the execution from ωconfiguration to (ω + 1)-configuration, for 0 ≤ ω < 2 N . Thus, this execution contains 2 N configurations. Since graph G N has 4N + N (N + 1) vertices, then n ≤ 2N 2 for n ≥ 5, and then

√ n ≤ N √ 2. Thus 2 √
n/2 ≤ 2 N and the corollary holds.

Our algorithm PolyMatch

The algorithm presented in this paper is called PolyMatch, and is based on the algorithm presented by Manne et al. [START_REF] Manne | A self-stabilizing 2/3-approximation algorithm for the maximum matching problem[END_REF], called ExpoMatch. As in ExpoMatch, PolyMatch assumes there exists an underlying maximal matching, called M. PolyMatch algorithm is presented in Figure 6. Predicates AskF irst and AskSecond are not given since they are the same as in ExpoMatch algorithm (see Fig. 3).

Variables description

Our algorithm has the same set of local variables as in ExpoMatch plus one additional boolean variable, called end. As in ExpoMatch, for a matched node u, the pointer p u refers to a neighbor of u that u is trying to (re)match with, and pointers α u and β u refer to two candidates for a possible rematching with u. And again, s u is a boolean variable that indicates if u has performed a successful rematching with its candidate. Finally, the new variable end u is a boolean variable that indicates if both u and m u have performed a successful rematching or not. For a single node x, only one pointer p x and one boolean variable end x are needed. p x has the same purpose as the p-variable of a matched node. The end-variable of a single node allows the matched nodes to know whether it is available or not. A single node x is available for a matched node u if it is not involved in another augmenting path that is fully exploited, i.e., if it is possible for x to eventually rematch with u, and thus if p x = u ∨ end x =False (see BestRematch predicate).

Augmenting paths exploitation

A 3-augmenting path is exploited in three phases. These phases are performed in a sequential way. Let us consider two nodes u and v such that (u, v) ∈ M. Let us assume that u and v detects a 3-augmenting path.

1. The First node starts (same as in ExpoMatch): The First node, let say u, tries to rematch with its candidate. This phase is complete when s u = T rue and this indicate to the Second node, let say v, that the first phase is over. 2. The Second node continues: only when the first node succeeds will the second node attempt to rematch with one of its candidates. This phase is complete when end v = T rue and this indicate to the v's neighbors that the second phase is over. 3. All nodes in the path set their end variable to True: the end value of v is propagated in the path. The goal of this phase is to write True in the end variables of the two single nodes in the path in order to make them unavailable for other married nodes. Indeed, the end variable is used to compute the candidates of a matched node.

The scenario for an augmenting path exploitation when everything goes well is given in the following. Node u starts trying to rematch with x performing a MatchFirst move and p u := x. If x accepts the proposition, performing an UpdateP move and p x := u, then u will inform v of this first phase success, once again by performing a MatchFirst move and s u :=True. Observe that at this point, x cannot change its p-value since p px = x. Finally, node v tries to rematch with y, performing a MatchSecond move and p v := y. If y accepts the proposition, performing an UpdateP move and p y := v, then v will inform u of this final success, by performing a MatchSecond move again and end v :=True. This complete the second phase. From then, all nodes in this 3-augmenting path will set there end-variable to True: u by performing a last MatchFirst move, and x and y by performing an UpdateEnd move. From this point, non of these nodes x, u, v, or y will ever be eligible for any move again. Moreover, once single nodes have their end-variables set to True, they are not available anymore for any other matched nodes.

Rules description

There are four rules for matched nodes. As in ExpoMatch, the Update rule allows a matched node to update its α and β variables, using the BestRematch predicate. Then, predicates AskFirst and AskSecond are used to define the role the node will have in the 3-augmenting path exploitation. If the node is First (resp. Second ), then it will execute MatchFirst (resp. MatchSecond ) for this 3-augmenting path exploitation. The ResetMatch rule is performed to reset bad initialization and also to reset an augmenting path exploitation that did not terminate.

The MatchFirst rule is used by the node when it is First. Let u be this node. The rule is performed three times in a usual path exploitation: ------Rules for each node u in matched(V) Update ::

if (αu > βu) ∨ (αu, βu / ∈ (single(N (u)) ∪ {null})) ∨ (αu = βu ∧ αu = null) ∨ pu / ∈ (single(N (u)) ∪ {null}) ∨ ((αu, βu) = BestRematch(u) ∧ (pu = null ∨ (pp u = u ∧ endp u = T rue))) then (αu, βu) := BestRematch(u)
(pu, su, endu) := (null, F alse, F alse) 1. The first time, u seduces its candidate setting (end u , s u , p u ) to (F alse, F alse, AskF irst(u)). 2. Then this rule is performed a second time after the u's candidate has accepted the u's proposition, i.e., when AskF irst(u) has set its p-variable to u. So the second MatchFirst execution sets (end u , s u , p u ) to (F alse, T rue, AskF irst(u)). Now, variable s u is equal to T rue, allowing node m u that is Second to seduce its own candidate. 3. Finally, the MatchFirst rule is performed a third time when m u completed his own rematch, i.e., when end mu = T rue. Observe that when there is no bad information due to some bad initializations, then end mu = T rue means p mu = AskSecond(m u ) ∧ p pm u = m u (see the third line of the MatchSecond rule). So this third MatchFirst execution sets (end u , s u , p u ) to (T rue, T rue, AskF irst(u)), meaning that the 3-augmenting path has been fully exploited.

MatchFirst :: if (AskF irst(u) = null) ∧ [ pu = AskF irst(u) ∨ su = (pu = AskF irst(u) ∧ pp u = u ∧ pm u ∈ {AskSecond(mu), null}) ∨ endu = (pu = AskF irst(u) ∧ pp u = u ∧ su ∧ pm u = AskSecond(mu) ∧ endm u ) ] then endu := (pu = AskF irst(u) ∧ pp u = u ∧ su ∧ pm u = AskSecond(mu) ∧ endm u ) su := (pu = AskF irst(u) ∧ pp u = u ∧ (pm u ∈ {AskSecond(mu), null}) pu := AskFirst(u)
In the MatchFirst rule, observe that we make the assignment operation of s u before the one of p u , because the s u value must be computed accordingly to the value of p u before activating u. Indeed, when u executes MatchFirst for the first time, it allows to set p u from ⊥ to AskF irst(u) while s u remains F alse. Then when u executes MatchFirst for the second time, s u is set from F alse to T rue while p u remains equal to AskF irst(u). For the same argument, we make the end u assignment before the s u assignment. Thus, the "normal" values sequence for (p u , s u , end u ) is: ((⊥, F alse, F alse), (AskF irst(u), F alse, F alse), (AskF irst(u), T rue, F alse), (AskF irst(u), T rue, T rue)).

The MatchSecond rule is used by the node when it is Second. This rule is performed only twice in a usual path exploitation. For the first execution, u has to wait for m u to set its s mu to True. Then u can perform MatchSecond and update its p-variable to AskSecond(u). When the u's candidate has accepted his proposition, u can perform MatchSecond for the second time, setting s u and end u to True. As in the MatchFirst rule, we set the end and s assignments before the p assignment.

There are three rules for single nodes. The ResetEnd rule is used to reset bad initializations. In the UpdateP rule, the node updates its p-value according to the propositions done by neighboring matched nodes. If there is no proposition, the node sets its p-value to null. Otherwise, p is set to the minimum identifier among all proposals. Afterward, the p-value can only change when the proposition is canceled. When a single node u has accepted a proposition, its end value should be equal to the end value of p u . The UpdateEnd rule is used for this purpose.

Execution examples

We give two different executions of algorithm PolyMatch under the adversarial distributed daemon. The first execution points out the main differences between our algorithm PolyMatch and algorithm ExpoMatch. In the second execution, we focus on the end variable role for the exploited path process.

Main difference between PolyMatch and ExpoMatch algorithms. When two neighboring augmentingpaths are exploited in parallel, then at most one among the two will eventually become a fully exploited augmented-path. In Manne et al. algorithm, a destruction of a partially exploited augmenting-path can be done while no fully exploited augmenting-path has been built instead. Moreover, for one fully exploited augmented-path, we can exhibit some executions where we destroy a sub-exponential number of exploited augmented-paths (see Section 5). In our algorithm, this is not possible since we do not destroy any partially exploited augmented-path while there is still hope to exploit it. This difference is implemented in the algorithm through the BestRematch(u) predicate. The condition p x = null in Manne et al. algorithm has been replaced by the condition end x =False in our algorithm, meaning that node x must belong to a fully exploited augmented-path in order to disappear from the candidates of u.

How to handle the end-variable?

Second, we consider the following execution in order to illustrate the role of local end-variable. Figure 7(a) shows the initial state of the execution. The underlying maximal matching contains one edge [START_REF] Berenbrink | On the stability of dynamic diffusion load balancing[END_REF][START_REF] Chattopadhyay | Dynamic and self-stabilizing distributed matching[END_REF]. Then nodes 2, 3 are matched nodes, and nodes 1, 7, and 8 are single nodes. At the beginning, there are two 3-augmenting paths: (1, 2, 3, 7) and [START_REF] Drake | A simple approximation algorithm for the weighted matching problem[END_REF][START_REF] Berenbrink | On the stability of dynamic diffusion load balancing[END_REF][START_REF] Chattopadhyay | Dynamic and self-stabilizing distributed matching[END_REF][START_REF] Dolev | Self-Stabilization[END_REF].

The initial configuration (Figure 7(a)). In the initial configuration, we assume that all α-values and βvalues are defined as follows: (α 2 , β 2 ) = (8, null), and (α 3 , β 3 ) = (7, null). We also assume all s-values are well defined (i.e., equal to False) whereas all end-values are False but end 1 that is True. At this moment, node 2 considers that since end 1 =True, node 1 already belongs to a fully exploited 3-augmenting path:

BestRematch(2) = (8, null).
The 3-augmenting path is (7, 3, 2, 8). Node 2 considers that node 1 is not available because end 1 =True. Since 2 ≤ U nique({α 2 , β 2 , α 3 , β 3 }) ≤ 4, nodes 2 and 3 detect a 3-augmenting path and start to exploit it. Since node 3 is First (AskF irst(3) = 7 and AskF irst(2) = null), node 3 may execute a MatchFirst move. Let us assume it does.

The 3-augmenting path exploitation starts (Figure 7(b)). Node 3 executes here a MatchFirst move and points to node 7. Since node 3 is pointing to node 7, node 7 is the only activable node among all nodes except node 1. Node 7 points to node 3 by executing a UpdateP move. Let us focus on node 1. Its end-value is not well defined since end 1 =True while node 1 does not belong to a fully exploited augmenting path. Thus, node 1 is eligible for ResetEnd rule. Let us assume it makes this move. After this move, we have end 1 =False. This implies that BestRematch(2) = (1, 8) and thus (α 2 , β 2 ) = (8, null) = BestRematch(2). So, only node 2 is activable, and is eligible for Update rule. Thus, after this mode, node 2 is First. This implies that node 3 is Second, and it is eligible for ResetMatch because AskSecond(3) = null ∧ p 3 = null ∧ s 2 =False. Let us assume it does it.

A second 3-augmenting path exploitation starts (Figure 7(d)). Let us consider node 2. It is First and it can execute a MatchFirst rule. After this activation, it sets p 2 = 1 and s 2 = end 2 =False. Now, node 1 accepts the node 2 proposition by executing a UpdateP move. After this activation, node 1 points to node 2 (p 1 = 2). Now, node 2 is eligible for executing a MatchFirst rule. It sets p 2 = 1 and s 2 = True. This implies that node 3 becomes eligible for MatchSecond.

In the configuration shown in Figure 7(e), node 3 can propose to node 7 with a MatchSecond. Note that node 7 is also eligible for UpdateP since p 3 = 7. Let us assume these two nodes do the move in parallel. Figure 7(e) shows the configuration obtained after theses moves: p 3 = 7, p 7 = null. Note that after these activations, we have s 3 = False since, before these activations, the p-values of nodes 3 and 7 are not as follow: p 3 = 7 and p 7 = 3. This kind of transitions, where a matched node proposition is performed in parallel with a single node abandonment, is the reason why we make the s-assignment, then the p-assignment in the MatchFirst rule. This trick allows to obtain after a MatchFirst rule: s u = True implies p pu = u. Finally, observe at this step that node 3 still waits for an answer of node 7.

The path (1, 2, 3, 7) becomes fully exploited (Figure 7(f )). Now, node 7 can choose 3 by executing UpdateP. Assume that it does. Since end 3 = (p 3 = 7 ∧ p 3 = AskSecond(3) ∧ p 2 = AskF irst(2)), node 3 is eligible for a MatchSecond rule to set end 3 to True and then to make the other nodes aware that the path is fully exploited. Assume node 3 executes a MatchSecond move. This will cause node 7 (resp. 2) to execute an UpdateEnd move (resp. a MatchFirst move) and sets end 7 =True (resp. end 2 =True). Now, it is the turn to node 1 to execute an UpdateEnd move. As the end-value of nodes 1, 2, 3, and 7 are equal to True, the 3-augmenting path is fully exploited. The system has reached a stable configuration (see Figure 7(f)). Thus, the size of the matching is increasing by one and there is no 3-augmenting path left.

Correctness Proof

A natural way to prove the correction of PolyMatch algorithm could have been to follow the approach below. We consider a stable configuration C in PolyMatch and we prove C is also stable in the Manne et al. algorithm. As we use the exact same variables but the end-variable and because the matching is only defined on the common variables, the correctness follows from Manne et By the way, this is why our algorithm has a better time complexity since the number of partially exploited augmented path destruction in our algorithm is smaller than in the Manne et al. algorithm. In particular, we have to prove that in a stable configuration, for any matched node, if p u = null, then end pu = True. To prove that, we need Lemmas 3, 4, 5, 6 and a part of the proof from Theorem 2. Observe that from these results, the correctness is straightforward without using the Manne et al. proof.

We first introduce some notations. A matched node u is said to be First if AskF irt(u) = null. In the same way, u is Second if AskSecond(u) = null. Let Ask : V → V ∪ {null} be a function where Ask(u) = AskF irst(u) if AskF irst(u) = null, otherwise Ask(u) = AskSecond(u). We will say a node makes a match rule if it performs a M atchF irst or M atchSecond rule.

Recall that the set of edges built by our algorithm PolyMatch is

M + = {(u, v) ∈ M : p u = p v = null} ∪ {(a, b) ∈ E \ M : p a = b ∧ p b = a}.
For the correctness part of the proof, we prove that in a stable configuration, M + is a 2/3-approximation of a maximum matching on graph G. To do that we demonstrate there is no 3-augmenting path on (G, M + ). In particular we prove that for any edge (u, v) ∈ M, we have either p u = p v = null, or u and v have two distincts single neighbors they are rematched with, i.e., ∃x ∈ single(N (u)), ∃y ∈ single(N (v)) with x = y such that (p x = u) ∧ (p u = x) ∧ (p y = v) ∧ (p v = y). In order to prove that, we show every other case for (u, v) is impossible. Finally, we prove that if p u = p v = null then (u, v) does not belong to a 3-augmenting-path on (G, M + ). Lemma 3. In any stable configuration, we have the following properties:

• ∀u ∈ matched(V ) :

p u = Ask(u); • ∀x ∈ single(V ) : if p x = u with u = null, then u ∈ matched(N (x)) ∧ p u = x ∧ end u = end x .
Proof. First, we will prove the first property. We consider the case where AskF irst(u) = null. We have p u = AskF irst(u), otherwise node u can execute rule AskF irst. We can apply the same result for the case where AskSecond(u) = null. Finally, we consider the case where AskF irst(u) = AskSecond(u) = null. If p u = null, then node u can execute rule ResetM atch which yields the contradiction. Thus, p u = null. Second, we consider a stable configuration C where p x = u, with u = null. u ∈ matched(N (x)), otherwise x is eligible for an UpdateP rule. Now there are two cases: p u = x and p u = x. If p u = x, this means that p px = x. Thus, x is eligible for rule U pdateP , and this yields to a contradiction with the fact that C is stable. Finally, we have end u = end x , otherwise x is eligible for rule U pdateEnd. Lemma 4. Let (u, v) be an edge in M. Let C be a configuration. If p u = null ∧ p v = null holds in C, then C is not stable.

Proof. By contraction. We assume C is stable. From Lemma 3, we have p u = Ask(u) = null and p v = Ask(v). So, by definition of predicates AskF irst and AskSecond, Ask(u) = x = null implies that Ask(v) = null. This contradicts that fact that p v = Ask(v) = null. Lemma 5. Let (x, u, v, y) be a 3-augmenting path on (G, M). Let C be a stable configuration. In C, if p x = u, p u = x, p v = y and p y = u, then end x = end u = end v = end y = T rue.

Proof. From Lemma 3, p u = Ask(u) (resp. p v = Ask(v)) thus Ask(u) = null and Ask(v) = null. W.l.o.g, we can assume that AskF irst(u) = null. We have s u = T rue, otherwise u can execute M atchF irst rule. Now, as s u = T rue, we must have end v = T rue, otherwise v can execute M atchSecond rule. As s u = end v = T rue, we must have end u = T rue, otherwise u can execute M atchF irst rule. From Lemma 3, we can deduce that end x = end u = end v = end y = T rue and this concludes the proof.

Lemma 6. Let (x 1 , u 1 , v 1 , x 2 ) be a 3-augmenting path on (G, M). Let C be a configuration. If p x1 = u 1 ∧ p u1 = x 1 ∧ p v1 = x 2 ∧ p x2 = v 1 holds in C, then C is not stable.
Proof. By contraction. We assume C is stable. From Lemma 3, Ask(u 1 ) = x 1 and Ask(v 1 ) = x 2 .

First we assume that AskSecond(u 1 ) = x 1 and AskF irst(v 1 ) = x 2 . The local variable s v1 is F alse, otherwise v 1 would be eligible for executing the M atchF irst rule. Since AskSecond(u 1 ) = null ∧ p u1 = null ∧ s v1 = F alse, this implies that u 1 is eligible for the ResetM atch rule which is a contradiction.

Second, we assume that AskF irst(u 1 ) = x 1 and AskSecond(v 1 ) = x 2 . We have s u1 = T rue, otherwise u 1 can execute the M atchF irst rule. This implies that end v1 = F alse, otherwise v 1 can execute the M atchSecond rule. As end v1 = F alse, then end u1 = F alse, otherwise u 1 can execute the M atchF irst rule. From Lemma 3, end x1 = end u1 = end v1 = F alse. Since Ask(v 1 ) = x 2 , we have x 2 ∈ {α v1 , β v1 }. Let us assume end x2 = T rue. Then x 2 ∈ BestRematch(v 1 ) and then v 1 is elligible for an U pdate. Thus end x2 = F alse.

Therefore, C is a configuration such that u 1 is F irst and v 1 is Second with end x1 = end u1 = end v1 = end x2 = F alse. Now we are going to show there exists another augmenting path (x 2 , u 2 , v 2 , x 3 ) with end x2 = end u2 = end v2 = end x3 = F alse and p u2 = x 2 , p x2 = u 2 , p v2 = x 3 and p x3 = v 2 such that u 2 is F irst and v 2 is Second (see Figure 8). p x2 = null otherwise x 2 is elligible for an UpdateP rule. Thus there exists a vertex u 2 = v 1 such that p x2 = u 2 . From Lemma 3, u 2 ∈ matched(N (x 2 )) and p u2 = x 2 . Therefore, there exists a node v 2 = m u2 . From Lemma 4, we can deduce that p v2 = null and there exists a node x 3 such that p v2 = x 3 .

x 1 x 1 u 1 u 1 v 1 v 1 x 2 x 2 u 2 u 2 v 2 v 2 x 3 x 3
x 3 ∈ single(N (v 2 )) otherwise v 2 is eligible for an Update rule. Finally, if p x3 = v 2 , then Lemma 5 implies that end x2 = end a2 = end b2 = end x3 = T rue. This yields the contradiction with the fact end x2 = F alse. So, we have

p x3 = v 2 .
We can then conclude that (x 2 , u 2 , v 2 , x 3 ) is a 3-augmenting path such that

p x2 = u 2 ∧ p u2 = x 2 ∧ p v2 = x 3 ∧ p x3 = v 2 .
This augmenting path has the exact same properties than the first considered augmenting path (x 1 , u 1 , v 1 , x 2 ) and in particular u 1 is First. Now we can continue the construction in the same way. Therefore, for C to be stable, it has to exist a chain of 3-augmenting paths (x 1 , u 1 , v 1 , x 2 , u 2 , v 2 , x 3 , . . . , x i , u i , v i , x i+1 , . . .) where ∀i ≥ 1 : (x i , u i , v i , x i+1 ) is a 3-augmenting path with p xi = u i ∧ p ui = x i ∧ p vi = x i+1 ∧ p xi+1 = v i+1 and u i is First. Thus, x 1 < x 2 < . . . < x i < . . . since the u i will always be First. Since the graph is finite some x k must be equal to some x with = k which contradicts the fact that the identifier' sequence is strictly increasing. Lemma 7. Let (x, u, v, y) be a 3-augmenting path on (G, M). Let C be a configuration. If

p u = x ∧ p x = u ∧ p v = y ∧ p y = v holds in C, then C is not stable.
Proof. By contradiction, assume C is stable. From Lemma 3, Ask(u) = x. Assume to begin that AskF irst(u) = null. Because p pu = u we have s u = F alse, otherwise u is eligible for M atchF irst. Since AskSecond(v) = null and s mv = s u = F alse then v can apply the ResetM atch rule which yields a contradiction. Therefore assume that AskSecond(u) = null. The situation is symmetric (because now AskF irst(v) = null) and therefore we get the same contradiction as before.

Lemma 8. Let (x, u, v, y) be a 3-augmenting path on (G, M). Let C be a configuration. If p y = p u = p v = p y = null holds in C, then C is not stable.

Proof. By contradiction, assume C is stable. end x = F alse (resp. end y = F alse), otherwise x (resp. y) is eligible for a ResetMatch. (α u , β u ) = BestRematch(u) (resp. (α v , β v ) = BestRematch(v)), otherwise u (resp. v) is eligible for an Update. Thus, there is at least an available single node for u and v and so Ask(u) = null and Ask(v) = null. Then, this contradicts the fact that Ask(u) = null (see Lemma 3).

Theorem 2. In a stable configuration we have, ∀(u, v) ∈ M:

(i) p u = p v = null or (ii) ∃x ∈ single(N (u)), ∃y ∈ single(N (v)) with x = y such that p x = u ∧ p u = x ∧ p y = v ∧ p v = y.
Since single nodes just follow orders from their neighboring matched nodes, we can count the number of times single nodes can change the value of their end variable. There are σ possible modifications due to bad initializations. A matched node u can write True twice in end u , so end u can be True during 3 distinct sub-executions. As a single node x copies the end-value of the matched node it points to (p x = u), then a single node can change its end-value at most 3 times as well. And we obtain 6µ modifications. Lemma 21. In any execution, the number of transitions where a single node changes the value of its end variables (from True to False or from False to True) is at most σ + 6µ times.

We count the maximal number of Update rule that can be performed in any execution. To do that, we observe that the first line of the Update guard can be True at most once in an execution (Lemma 12). Then we prove for the second line of the guard to be True, a single node has to change its end value. Thus, for each single node modification of the end-value, at most all matched neighbors of this single node can perform an Update rule.

Corollary 5. Matched nodes can execute at most ∆(σ + 6µ) + µ times the Update rule.

Third, we consider two particular matched nodes u and v and an execution with no U pdate rule performed by these two nodes. Then we count the maximal number of moves performed by these two nodes in this execution. The idea is that in such an execution, the α and β values of u and v remain constant. Thus, in these small executions, u and v detect at most one augmenting path and perform at most one rematch attempt. We obtain that the maximal number of moves of u and v in these small executions is 12. By the previous remark and Corollary 5, we obtain: Theorem 4. In any execution, matched nodes can execute at most 12∆(σ + 6µ) + 18µ rules.

Finally, we count the maximal number of moves that single nodes can perform, counting rule by rule. The ResetEnd is done at most once. The number of UpdateEnd is bounded by the number of times single nodes can change their end-value, so it is at most σ + 6µ. Finally, UpdateP is counted as follows: between two consecutive UpdateP executed by a single node x, a matched node has to make a move. The total number of executed UpdateP is then at most 12∆(σ + 6µ) + 18µ + 1.

Corollary 3. The algorithm PolyMatch converges in O(n 2 ) moves under the adversarial distributed daemon and in a general graph, provided that an underlying maximal matching has been initially built.

The Manne et al. algorithm [START_REF] Manne | A new self-stabilizing maximal matching algorithm[END_REF] builds a self-stabilizing maximal matching under the adversarial distributed daemon in a general graph, in O(m) moves. This leads to a O(m.n 2 ) moves complexity to build a 1-maximal matching with our algorithm without any assumption of an underlying maximal matching. Now, the next section is devoted to the description of the technical proof.

A matched node can write T rue in its end-variable at most twice

The first three lemmas are technical lemmas.

Lemma 10. Let u be a matched node. Consider an execution E starting after u executed some rule. Let C be any configuration in E. If end u = T rue in C then s u = T rue as well.

Proof. Let C 0 → C 1 be the transition in E or in its prefix in which u executed a rule for the last time before C. Observe first that this transition necessarily exists by definition of E and second that C may be equal to C 1 . The executed rule is necessarily a match rule, otherwise end u could not be T rue in C 1 . If it is a M atchSecond the lemma holds since in that case s u is a copy of end u . Assume now it is a M atchF irst. For end u to be T rue in C 1 , p u = AskF irst(u) ∧ p pu = u ∧ p mu = AskSecond(m u ) must hold in C 0 , according to the action of MatchFirst. This implies that u writes T rue in s u in transition C 0 → C 1 .

Lemma 11. Let u be a matched node. Consider an execution E starting after u executed some rule. Let C be any configuration in E. In C, if s u = T rue then ∃x ∈ single(N (u)) :

p u = x ∧ p x = u.
Proof. Consider transition C 0 → C 1 in which u executed a rule for the last time before C. Observe that this transition necessarily exists by definition of E. The executed rule is necessarily a match rule, otherwise s u could not be T rue in C 1 . Observe now that whichever match rule is applied, Ask(u) = null -let us assume Ask(u) = x -and p u = x and p x = u must hold in C 0 for s u to be T rue in C 1 . p u = x still holds in C 1 and until C. Moreover, x must be in single(N (u)), otherwise u would have executed an Update instead of a match rule in C 0 → C 1 , since Update has the higest priority among all rules. Finally, in transition Lemma 12. Let u be a matched node and E be an execution containing a transition C 0 → C 1 where u makes a move. From C 1 , the predicate in the first line of the guard of the U pdate rule will never hold.

C 0 → C 1 , x cannot execute U pdateP nor ResetEnd since p x ∈ matched(N (x)) ∧ p px = x holds in C 0 . Thus in C 1 , p u =
Proof. Let C 2 be any configuration in E such that C 2 ≥ C 1 . Let C 10 → C 11 be the last transition before C 2 in which u executes a move. Notice that by definition of E, this transition exists. Assume by contradiction that one of the following predicates holds in

C 2 . 1. (α u > β u ) ∨ (α u , β u / ∈ (single(N (u)) ∪ {null})) ∨ (α u = β u ∧ α u = null) 2. p u /
∈ (single(N (u)) ∪ {null}) By definition between C 11 and C 2 , u does not execute rules. To modify the variables α u , β u and p u , u must execute a rule. Thus one of the two predicates also holds in C 11 .

We first show that if predicate (1) holds in C 11 then we get a contradiction. If u executes an U pdate rule in transition C 10 → C 11 , then by definition of the BestRematch function, predicate (1) cannot hold in C 11 (observe that the only way for α u = β u is when α u = β u = null). Thus assume that u executes a match or ResetM atch rule. Notice that these rules do not modify the value of the α u and β u variables. This implies that if u executes one of these rules in C 10 → C 11 , predicate (1) not only hold in C 11 but also in C 10 . Observe that this implies, in that case that u is eligible for U pdate in C 10 → C 11 , which gives the contradiction since U pdate is the rule with the highest priority among all rules. Now assume predicate (2) holds in C 11 . In transition C 10 → C 11 , u cannot execute U pdate nor ResetM atch as this would imply that p u = null in C 11 . Assume that in C 10 → C 11 u executes a match rule. Since in C 11 , p u / ∈ (single(N (u)) ∪ {null}) this implies that in C 10 , Ask(u) / ∈ (single(N (u)) ∪ {null}). This implies that α u , β u / ∈ (single(N (u)) ∪ {null}) in C 10 . Thus u is eligible for U pdate in transition C 10 → C 11 and this yields the contradiction since U pdate is the rule with the highest priority among all rules.

Since these two predicates cannot hold in C 2 , this concludes the proof. Now, we focus on particular configurations for a matched edge (u, v) corresponding to the fact they have completely exploited a 3-augmenting path.

Lemma 13. Let (u, v) be a matched edge, E be an execution and C be a configuration of E. If in C, we have:

1. p u ∈ single(N (u)) ∧ p u = AskF irst(u) ∧ p pu = u; 2. p v ∈ single(N (v)) ∧ p v = AskSecond(v) ∧ p pv = v; 3. s u = end u = s v = end v =
T rue; then neither u nor v will ever be eligible for any rule from C.

Proof. Observe first that neither u nor v are eligible for any rule in C. Moreover, p u (resp. p v ) is not eligible for an U pdateP move since u (resp. v) does not make any move. Thus p pu and p pv will remain constant since u and v do not make any move and so neither u nor v will ever be eligible for any rule from C.

The configuration C described in Lemma 13 is called a stop uv configuration. From such a configuration neither u nor v will ever be eligible for any rule. In Lemmas 15 and 16, we consider executions where a matched node u writes T rue in end u twice, and we focus on the transition C 0 → C 1 where u performs its second writing. Lemma 15 shows that, if u is First in C 0 , then C 1 is a stop umu configuration. Lemma 16 shows that, if u is Second in C 0 , then either C 1 is a stop umu configuration or there exists a configuration C 3 such that C 3 > C 1 , u does not make any move from C 1 to C 3 and C 3 is a stop umu configuration. Lemma 14 and Corollary 4 are required to prove Lemmas 15 and 16. Lemma 14. Let (u, v) be a matched edge. Let E be some execution in which v does not execute any rule. If there exists a transition C 0 → C 1 in E where u writes T rue in end u , then u is not eligible for any rule from C 1 . Proof. To write T rue in end u in transition C 0 → C 1 , u must have executed a match rule. According to this rule, (p u = Ask(u) ∧ p pu = u) holds C 0 with p u ∈ single(N (u)), otherwise u would have executed an Update instead of a match rule. Now, in C 0 → C 1 , p u cannot execute UpdateP then it cannot change its p-value and v does not execute any move then it cannot change Ask(u). Thus, (p u = Ask(u) ∧ p pu = u) holds in both C 0 and C 1 .

Assume now by contradiction that u executes a rule after configuration C 1 . Let C 2 → C 3 be the next transition in which it executes a rule. Recall that between configurations C 1 and C 2 both u and v do not execute rules. Observe also that p u is not eligible for U pdateP between these configurations. Thus (p u = Ask(u) ∧ p pu = u) holds from C 0 to C 2 . Moreover the following points hold as well between C 0 and C 2 since in C 0 → C 1 u executed a match rule and v does not apply rules in E:

• α u , α v , β u and β v do not change.

• The values of the variables of v do not change.

• Ask(u) and Ask(v) do not change.

• If u was F irst in C 0 it is F irst in C 2 and the same holds if it was Second.

Using these remarks, we start by proving that u is not eligible for ResetM atch in C 2 . If it is F irst in C 2 , this holds since AskF irst(u) = null and AskSecond(u) = null. If it is Second then to be eligible for ResetM atch, s v = F alse must hold in C 2 since AskSecond(u) = null. Since u executed end u = T rue in C 0 → C 1 and since u was Second in C 0 , then necessarily s v = T rue in C 0 and thus in C 2 (using remark 2 above). So u is not eligible for ResetM atch in C 2 .

We show now that u is not eligible for an U pdate in C 2 . The α and β variables of u and v remain constant between C 0 and C 2 . Thus if any of the three first disjunctions in the U pdate rule holds in C 2 then it also holds in C 0 and in C 0 → C 1 u should have executed an U pdate since it has higher priority than the match rules. Moreover since in C 2 (p u = Ask(u) ∧ p pu = u) holds, the last two disjunctions of U pdate are F alse and we can state u is not eligible for this rule.

We conclude the proof by showing that u is not eligible for a match rule in C 2 . If u was F irst in C 0 then it is F irst in C 2 . To write T rue in end u then (p u = AskF irst(u) ∧ p pu = u ∧ s u ∧ p mu = AskSecond(m u ) ∧ end mu ) must hold in C 0 . Since in C 0 → C 1 v does not execute rules, it also holds in C 1 . The same remark between configurations C 1 and C 2 implies that this predicate holds in C 2 . Thus in C 2 , all the three conditions of the M atchF irst guard are F alse and u not eligible for M atchF irst. A similar remark if u is Second implies that u will not be eligible for M atchSecond in C 2 if it was Second in C 0 . Corollary 4. Let (u, v) be a matched edge. In any execution, if u writes T rue in end u twice, then v executes a rule between these two writing. Lemma 15. Let (u, v) be a matched edge and E be an execution where u writes T rue in its variable end u at least twice. Let C 0 → C 1 be the transition where u writes T rue in end u for the second time in E. If u is First in C 0 then the following holds:

1. in configuration C 0 , (a) s v = end v = T rue; (b) p u = AskF irst(u) ∧ p pu = u ∧ s u = T rue ∧ p v = AskSecond(v); (c) p u ∈ single(N (u)); (d) p v ∈ single(N (v)) ∧ p pv = v; 2. v does not execute any move in C 0 → C 1 ; 3. in configuration C 1 , (a) s u = end u = T rue; (b) p u ∈ single(N (u)) ∧ p v ∈ single(N (v)); (c) s v = end v = T rue; (d) p u = AskF irst(u) ∧ p v = AskSecond(v); (e) p pu = u ∧ p pv = v.
Proof. We prove Point 1a. Observe that for u to write T rue in end u , end v must be T rue in C 0 . By Lemma 10 this implies that s v is True as well. Now Point 1b holds by definition of the M atchF irst rule.

As in C 0 , u already executed an action, then according to Lemma 12, Point 1c holds and will always hold. By Corollary 4, u cannot write T rue consecutively if v does not execute moves. Thus at some point before C 0 , v applied some rule. This implies that in configuration C 0 , since s v = T rue, by Lemma 11, ∃x ∈ single(N (v)) : p v = x ∧ p x = v. Thus Point 1d holds. We now show that v does not execute any move in C 0 → C 1 (Point 2). Recall that v already executed an action before C 0 , so by Lemma 12, line 1 of the U pdate guard does not hold in C 0 . Moreover, by Point 1d, line 2 does not hold either. Thus, v is not eligible for U pdate in C 0 . We also have that s u = T rue and AskSecond(v) = null in C 0 , thus v is not eligible for ResetM atch. Observe now that by Points 1a, 1b and 1d, v is not eligible for M atchSecond in C 0 . Finally v cannot execute M atchF irst since AskF irst(v) = null. Thus v does not execute any move in C 0 → C 1 and so Point 2 holds.

In C 1 , end u is True by hypothesis and according to Point 1b, u writes T rue in s u in transition C 0 → C 1 . Thus Point 3a holds. Points 3b holds by Points 1c and 1d. Points 3c holds by Points 1a and 2. AskF irst(u) and AskSecond(v) remain constant in C 0 → C 1 since neither u nor v executes an U pdate in this transition. Moreover p v remains constant in C 0 → C 1 by Point 2 and p u remains constant also since it writes AskF irst(u) in p u in this transition while p u = AskF irst(u) in C 0 . Thus Points 3d holds. Observe that nor p u neither p v is eligible for an U pdateP in C 0 , thus Point 3e holds. Now, we consider the case where u is Second.

Lemma 16. Let (u, v) be a matched edge and E be an execution where u writes T rue in its variable end u at least twice. Let C 0 → C 1 be the transition where u writes T rue in end u for the second time in E. If u is Second in C 0 then the following holds:

1. in configuration C 0 , (a) (vi) end v = T rue;

s v = T rue ∧ p v = AskF irst(v); (b) p v ∈ single(N (v)) ∧ p pv = v; 2. in transition C 0 → C 1 , v is not eligible for U pdate nor ResetM atch; 3. in configuration C 1 , (a) s u = end u = T rue; (b) p v ∈ single(N (v)) ∧ p v = AskF irst(v) ∧ p pv = v; (c) p u ∈ single(N (u)) ∧ p u = AskSecond(u) ∧ p pu = u; (d
Proof. We show Point 1a. For u to write T rue in transition C 0 → C 1 , u executes a M atchSecond in this transition. Thus s v = T rue must hold in C 0 and p v = AskF irst(v) as well. By Corollary 4, u cannot write T rue consecutively if v does not execute any move. Thus at some point before C 0 , v applied some rule. Thus, and by Lemma 11, ∃x ∈ single(N (v)) :

p v = x ∧ p x = v in configuration C 0 , so Point 1b holds.
As AskF irst(v) = null in C 0 , v is not eligible for ResetM atch in C 0 . We prove now that v is not eligible for U pdate. By Corollary 4 and Lemma 12, line 1 of the U pdate guard does not hold in C 0 . Finally, according to Point 1b, the second line of the U pdate guard does not hold, which concludes Point 2.

We consider now Point 3a. In C 1 , s u = end u = T rue holds because, executing a M atchSecond, u writes T rue in end u and writes end u in s u during transition C 0 → C 1 .

We now show Point 3b. AskF irst(v) and AskSecond(u) remain constant in C 0 → C 1 since neither u nor v execute an U pdate in this transition. Moreover, the only rule v can execute in C 0 → C 1 is a M atchF irst, according to Point 2. Thus v does not change its p-value in C 0 → C 1 and so We now prove Point 4. If end v = T rue in C 1 , then according to Lemma 13, u is not eligible for any rule in C 1 . Now, let us consider the case end v = F alse in C 1 . By Points 3c and 3d, u is not eligible for ResetM atch. By Point 3c and Lemma 12, u is not eligible for U pdate. By Points 3a, 3b and 3c, u is not eligible for M atchSecond. Finally, since u is Second in C 1 , u is not eligible for M atchF irst neither and Point 4 holds. Now since between C 1 and C 2 , v does not execute any rule (by Point 5b), and since p u (resp. p v ) is not eligible for U pdateP while u (resp. v) does not move (because p pu = u (resp. p pv = v)), then Ask(u), Ask(v), p pu and p pv remain constant while u does not make any move. And so, properties 3a, 3b, 3c and 3d hold for any configuration between C 1 and C 2 , thus u is not eligible for any rule between C 1 and C 2 and u will not execute any move from C 1 to C 3 . Moreover, the end v -value is the same from C 1 to C 2 .

p v = AskF irst(v) in C 1 . Now, in C 0 , v ∈ matched(N (p v )) ∧ p pv = v thus p v cannot execute U pdateP in C 0 → C
If end v = F alse in C 2 , then v is eligible for a M atchF irst and it will write T rue in its end v -variable while all properties of Point 3 will still hold in C 3 . Thus Point 5 holds. Theorem 3. In any execution, a matched node u can write end u := T rue at most twice.

Proof. Let (u, v) be a matched edge and E be an execution where u writes T rue in its variable end u at least twice. Let C 0 → C 1 be the transition where u writes T rue in end u for the second time in E. If u is First (resp. Second) in C 0 then from Lemmas 13 and 15, (resp. 16), from C 1 , neither u nor v will ever be eligible for any rule.

The number of times single nodes can change their end-variable

In the following, µ denote the number of matched nodes and σ the number of single nodes.

Lemma 17. Let x be a single node. If x writes T rue in end x in some transition

C 0 → C 1 then, in C 0 , ∃u ∈ matched(N (x)) : p x = u ∧ p u = x ∧ end x = F alse ∧ end u = T rue.
Proof. To write True in its end variable, a single node must apply U pdateEnd. Observe now that to apply this rule, the conditions described in the Lemma must hold.

Lemma 18. Let u be a matched node. Consider an execution E starting after u executed some rule and in which end u is always T rue, except for the last configuration D of E in which it may be F alse. Let E\D be all configurations of E but configuration D. In E\D, the following holds: (a) p u ∈ single(N (u)); (b) p u remains constant.

Proof. Since end u = T rue in E\D, the last rule executed before E is necessarily a M atch rule. So, at the beginning of E, p u ∈ single(N (u)), otherwise, u would not have executed a M atch rule, but an U pdate instead. We prove now that in E\D, p u remains constant. Assume by contradiction that there exists a transition in which p u is modified. Let C 0 → C 1 be the first such transition. First, observe that in E\D, u cannot execute ResetM atch nor U pdate since that would set end u to F alse. Thus u must execute a M atch rule in C 0 → C 1 . Since the value of p u changes in this transition, this implies that Ask(u) = p u in C 0 . Thus, whatever the M atch rule, observe now that in C 1 , end u must be F alse, which gives a contradiction and concludes the proof. Definition 6. Let u be a matched node. We say that a transition C 0 → C 1 is of type "a single copies True from u" if there exists a single node x such that (p x = u ∧ p u = x ∧ end x = F alse) in C 0 and end x = T rue in C 1 . Notice that by Lemma 17, end u = T rue in C 0 and x ∈ single(N (u)).

If a transition C 0 → C 1 is of type "a single node copies True from u" and if x is the single node with (p x = u ∧ p u = x ∧ end x = F alse) in C 0 and end x = T rue in C 1 , then we will say x copies T rue from u.

Lemma 19. Let u be a matched node and E be an execution. In E, there are at most three transitions of type "a single copies T rue from u".

Proof. Let E be an execution. We consider some sub-executions of E.

Let E init be a sub-execution of E that starts in the initial configuration of E and that ends just after the first move of u. Let C 0 → C 1 be the last transition of E init . Observe that u does not execute any move until configuration C 0 and executes its first move in transition C 0 → C 1 . We will write E init \ C 1 to denote all configurations of E init but the configuration C 1 . We prove that there is at most one transition of type "a single copies T rue from u" in E init .

There are two possible cases regarding end u in all configuration of E init \ C 1 : either end u is always T rue or end u is always F alse. If end u = F alse then by Definition 6, no single node can copy T rue from u in E init , not even in transition C 0 → C 1 , since no single node is eligible for such a copy in C 0 . If end u = T rue, once again, there are two cases: either

(i) (p u = null ∨ p u / ∈ single(N (u))) in all configuration of E init \ C 1 , or (ii) (p u ∈ single(N (u))) in E init \ C 1 .
In case (i) then by Definition 6 no single node can copy T rue from u in E init , not even in C 0 → C 1 . In case (ii), observe that p u remains constant in all configurations of E init \ C 1 , thus at most one single node can copy T rue from u in E init .

Let E true be a sub-execution of E starting after u executed some rule and such that: for all configurations in E true but the last one, end u = T rue. There is no constraint on the value of end u in the last configuration of E true . According to Lemma 18, p u ∈ single(N (u)) and p u remains constant in all configurations of E true but the last one. This implies that at most one single can copy T rue from u in E true .

Let E f alse be an execution starting after u executed some rule and such that: for all configurations in E f alse but the last one, end u = F alse. There is no constraint on the value of end u in the last configuration of E f alse . By Definition 6, no single node will be able to copy T rue from u in E f alse .

To conclude, by Corollary 3, u can write T rue in its end variable at most twice. Thus, for all executions E, E contains exactly one sub-execution of type E init , and at most two sub-executions of type E true and the remaining sub-executions are of type E f alse . This implies that in total, we have at most three transitions of type "a single copies T rue from u" in E.

Lemma 20. In any execution, the number of transitions where a single node writes T rue in its end variable is at most 3µ.

Proof. Let E be an execution and x be a single node. If x writes T rue in end x in some transition of E, then x necessarily executes an U pdateEnd rule and by Definition 6, this means x copies T rue from some matched node in this transition. Now the lemma holds by Lemma 19.

Lemma 21. In any execution, the number of transitions where a single node changes the value of its end variables (from T rue to F alse or from F alse to T rue) is at most σ + 6µ times.

Proof. A single node can write T rue in its end variable at most 3µ times, by Corollary 20. Each of this writing allows one writing from T rue to F alse, which leads to 6µ possible modifications of the end variables. Now, let us consider a single node x. If end x = F alse initially, then no more change is possible, however if end x = T rue initially, then one more modification from T rue to F alse is possible. Each single node can do at most one modification due to this initialization and thus the Lemma holds. Lemma 22. Let u be a matched node. If there exists a transition C 0 → C 1 such that the value of BestRematch(u) is not the same in C 0 and in C 1 , then there exists a single node x such that x ∈ Cand(u, C 0 )\Cand(u, C 1 ) or x ∈ Cand(u, C 1 )\Cand(u, C 0 ). Moreover, in transition C 0 → C 1 , x flips the value of its end variable.

Proof. We prove the first point by contradiction. Since BestRematch(u) is a deterministic function over Cand(u, C) for some configuration C, so if Cand(u, C 0 ) = Cand(u, C 1 ) then the value of BestRematch(u) is the same in C 0 and C 1 which yields the contradiction.

Lemma 26. Let (u, v) be a matched edge. Assume that in F, u is F irst, v is Second and that u writes T rue in s u in some transition of F. Let C 0 → C 1 be the transition in F in which u writes T rue in s u for the first time. Let F 1 be the execution starting in C 1 and finishing in D E . In F 1 , u can apply at most 3 rules and v at most 2.

Proof. We first prove that in F 1 , s u remains T rue. Observe that u cannot execute U pdate neither ResetM atch since it is F irst. So u can only execute M atchF irst in F 1 . For u to write F alse in s u , there must exist a configuration in F 1 such that p u = AskF irst(u) ∨ p pu = u ∨ p v ∈ {AskSecond(v), null}. Let us prove that none of these cases are possible.

Since u executed M atchF irst in transition C 0 → C 1 writting T rue in s u then, by definition of this rule, p u = AskF irst(u) ∧ p pu = u ∧ p v ∈ {AskSecond(v), null} holds in C 0 . As there is no U pdate of u and v in F, then AskF irst(u) and AskSecond(v) remain constant throughout F (and F 1 ). So each time u executes a M atchF irst, it writes the same value AskF irst(u) in its p-variable. Thus p u = AskF irst(u) holds throughout F 1 . Moreover, each time v executes a rule, it writes either null or the same value AskSecond(v) in its p-variable. Thus p v ∈ {AskSecond(v), null} holds throughout F 1 . Now by Lemma 11, in C 1 we have, ∃x ∈ single(N (u)) : p u = x ∧ p x = u, since s u = T rue . This stays T rue in F 1 as p u remains constant and x will then not be eligible for U pdateP in F 1 . Thus p pu = u holds throughout F 1 . Thus, p u = AskF irst(u) ∧ p pu = u ∧ p v ∈ {AskSecond(v), null} holds throughout F 1 and so s u = T rue throughout F 1 .

This implies that in F 1 , v is only eligible for M atchSecond. The first time it executes this rule in some transition

B 0 → B 1 , with B 1 ≥ C 1 , then in B 1 , p v = AskSecond(v), s v = end v
and this will hold between B 1 and D E . If end v = T rue in B 1 then this will stay T rue between B 1 and D E . Indeed, p v is not eligible for U pdateP and we already showed that p u = AskF irst(u) holds in F 1 . In that case, between B 1 and D E , v will not be eligible for any rule and so v will have executed at most one rule in F 1 . In the other case, that is end v (= s v ) = F alse in B 1 , since p v = AskSecond(v) holds between B 1 and D E , necessarily, the next time v executes a M atchSecond rule, it is to write T rue in end v . After that observe that v is not eligible for any rule. Thus, v can execute at most 2 rules in F 1 .

To conclude the proof it remains to count the number of moves of u in F 1 . Recall that we proved s u is always T rue in F 1 . Thus whenever u executes a M atchF irst, it is to modify the value of its end variable. Observe that this value depends in fact of the value of end v and of p v since we proved p u = AskF irst(u) ∧ p pu = u ∧ s u ∧ p v ∈ {AskSecond(v), null} holds throughout F 1 . Since we proved that in F 1 , v can execute at most two rules, this implies that these variables can have at most three different values in F 1 . Thus u can execute at most 3 rules in F 1 .

Lemma 27. Assume that in F, u is F irst and v is Second. If s u is T rue throughout F and if u does not execute any move in F, then v can execute at most two rules in F.

Proof. By Definition 8, v cannot execute U pdate in F. Since we suppose that in F, s u = T rue then v is not eligible for ResetM atch. Thus in F, v can only execute M atchSecond. After it executed this rule for the first time, p v = AskSecond(v) and s v = end v will always hold, since v is only eligible for M atchSecond. Thus the second time it executes this rule, it is necessarily to modify its end v and s v variables. Observe that after that, since u does not execute rules, v is not eligible for any rule.

Lemma 28. In F, u and v can globally execute at most 12 rules.

Proof. If Ask(u) = Ask(v) = null, the Lemma holds by Lemma 23. Assume now that u is F irst and v Second. We consider two executions in F.

Let C 0 → C 1 be the first transition in F in which u executes a rule. Let F 0 be the execution starting in D E and finishing in C 0 . There are two cases. If s u = F alse in F 0 then v is only eligible for ResetM atch in this execution. Observe that after it executes this rule for the first time in F 0 , it is not eligible for any rule after that in F 0 . If s u = T rue in F 0 then by Lemma 27, v can execute at most two rules in this execution. In transition C 0 → C 1 , u and v can execute one rule each.

Let F 1 be the execution starting in C 1 and finishing in D E . Whatever rule u executes in transition C 0 → C 1 observe that u either writes T rue or F alse in s u . If u writes T rue in s u in transition C 0 → C 1 , then by Lemma 26, u and v can execute at most five rules in total in F 1 .

Composition

Recall that the algorithm PolyMatch assumes an underlying maximal matching. Let MaxMatch be a silent self-stabilizing maximal matching algorithm having a complexity of z = O(f (n, m)) moves under the distributed daemon. In this section, we prove the fair composition of MaxMatch and PolyMatch has a complexity in O(zn 2 ) moves under the distributed daemon. The MaxMatch algorithm could be for instance the Manne et al. algorithm [START_REF] Manne | A new self-stabilizing maximal matching algorithm[END_REF] that has a complexity in O(m) moves that would lead to a final complexity of the composition in O(n 2 .m) moves.

An execution of such a composition is an alternated concatenation of two kinds of finite sub executions. The first kind only contains actions from PolyMatch and the second one contains any action. Les us call the first kind of executions, the PolyMatch-sub-executions. We do not know any upper bound on the number of moves of a PolyMatch-sub-executions in the case where MaxMatch has not stabilized yet. Indeed, Corollary 6 only says that such a sub-execution contains O(n 2 ) moves when MaxMatch is already stabilized.

Let G be the input graph and e be an execution on G of the composition between MaxMatch and PolyMatch. We consider two transitions of e containing a move from MaxMatch and such that there is no more move from it between them. Let us call E the execution between these two transitions and let C 0 be the first configuration of E (E is a PolyMatch-sub-execution). In C 0 , if MaxMatch is in a stable configuration, then the underlying matching is maximal in E, and every node u is either single (i.e., m u =⊥) or matched (i.e., ∃v ∈ N (u) such that m u = v ∧ m v = u). However, MaxMatch is not necessarily in a stable configuration in C 0 . Therefore, in that case, a node can also be falsy-matched in E, i.e., ∃v ∈ N (u) such that m u = v ∧ m v = u. Observe that a node x cannot decide if a neighbor u is matched or falsy-matched since it can only check if m u =⊥ but cannot read the variable m mu . Thus, all falsy-matched nodes are considered as matched by their neighbors. Finally, observe that only single and matched nodes are activable for PolyMatch moves in E (by definition of the guarded rules of the algorithms). Therefore, by definition of E, no falsy-matched nodes perform move in E.

In the following, informally we build a new graph G from G and a new configuration C 0 from C 0 such that the values of the MaxMatch variables in C 0 makes this configuration stable for MaxMatch. Then, we define H as the set of all possible executions of the composition of algorithms PolyMatch and MaxMatch starting from C 0 in graph G . Finally, we show that E is an execution that can be "projected into" an execution in H. Since C 0 is stable for MaxMatch, all executions in H contain O(n 2 ) moves by Corollary 6, and so this projection result would prove that E contains O(n 2 ) moves.

We now define G and C 0 . First assume that F ⊆ V is the set of all falsy-matched nodes of G in C 0 . G is a copy of G in which, for every node x ∈ F , we create a new node x and an edge (x, x ) in G . Finally, we delete from the edge set of G all the edges between two single nodes. We define C 0 as follow:

• the local states of single and matched nodes are the same as in C 0 ; • for each node x in F :

the local states of x is the same as in C 0 for the PolyMatch algorithm but is such that m x = x where x is the new node associated to x; -the local state of x is initialized with all boolean variables at false and all other variables at ⊥ but m x that is set to x for MaxMatch.

Observe that there is no falsy-matched node anymore in G and C 0 is a stable configuration for MaxMatch. Figure 9 shows an example of a construction from G/C 0 to G /C 0 . Also observe that any execution of H has two properties: (i) it does not contain any action of MaxMatch since C 0 is a stable configuration for MaxMatch ; and (ii) it contains at most O(n 2 ) moves from PolyMatch, according to Corollary 6. Let us assume E = C 0 a 0 C 1 a 1 . . . C k a k C k+1 . . . We now prove there exists an execution E ∈ H with E = C 0 a 0 C 1 a 1 . . . C k a k C k+1 . . . and such that ∀i ≥ 0, a i = a i . To do that, we start by proving any move π ∈ a 0 , with C 0 a0 -→ C 1 can be performed from C 0 . First note that π is performed by a single or a matched node, let say u. Observe that u belongs to both graphs G and G . By definition of C 0 , u has the exact same local state in C 0 and in C 0 . Between G/C 0 and G /C 0 , the neighborhood of u can be different on two points only. The first point appears when u has a falsy-matched neighbor on G, let say x. Indeed, x becomes a matched node in G . However, this modification does not change the local view of u at distance 1, since as we previously stated, u does not make any distinction between a falsy-matched neighbor and a matched one. Thus as long as x do not perform any move, the local change in node x do not have any impact on the actions performed by u. Recall that x does not make any move in E since it is falsy-matched.

The second point appears when u is single and it has a single neighbor x in G. In this case, the edge (u, x) disappears in G leading to a modification of the local view of u at distance 1. However, this suppression has no impact on the actions performed by u since u consider all its single neighbors as nodes that are not in its neighborhood. Indeed, all references to neighbors of a single node in PolyMatch rules are combined with the matched predicate.

Finally, we can conclude that if u can perform π ∈ a 0 from C 0 , it can also perform it from C 0 . Thus from the transition C 0 a0 -→ C 1 in G, we can exhibit a configuration C 1 such that the transition C 0 a0 -→ C 1 exists in G . Observe that the relation between C 1 and C 1 is the same as the one between C 0 and C 0 . Indeed, falsy-matched nodes in C 0 as well as nodes in F do not change their local state neither in C 0 → C 1 nor in C 0 → C 1 . Moreover, single and matched nodes changed their local state in the same way in C 0 → C 1 and in C 0 → C 1 , since they performed the exact same action(s). Thus, this leads to the following result : ∀i ≥ 0, from the transition C i ai -→ C i+1 in G, we can exhibit a configuration C i+1 such that the transition C i a0 -→ C i+1 exists in G . Finally, from E, we can build E as defined above and so E contains at most O(N 2 ) moves, with N is the number of nodes in G . Note that we added at most n nodes in G , so E contains at most O(n 2 ) moves.

A last observation is about the possibility for G to be an unconnected graph, according to the suppression of all single-to-single edges in G. However, the result still hold with this possibility, since PolyMatch will stabilize in each connected component in O( i N 2 i ), where N i is the size of the i th connected component in G . And obviously, i N 2 i ≤ N 2 when i N i ≤ N , for any large value of N .

Figure 1 :

 1 Figure 1: Best results in maximum matching approximation. In bold, our contributions.

  A 3-augmenting path (one matched edge). (b) The path after being exploited (two matched edges).

Figure 2 :

 2 Figure 2: How to exploit a 3-augmenting path?

Figure 3 :

 3 Figure 3: ExpoMatch algorithm

Figure 4 :

 4 Figure 4: A partial view of graph G N Our exponential execution used the following underlying maximal matching M:M = {(b(i, 2), b(i, 3))|0 ≤ i < N } ∪ {(r 1 (i, j), r 2 (i, j))|0 ≤ j < i < N } This maximal matching is encoded with the m-variables then we have: ∀i, j with 0 ≤ j < i < N : m b(i,2) = b(i, 3), m b(i,3) = b(i,2), m r1(i,j) = r 2 (i, j) and m r2(i,j) = r 1 (i, j)

Figure 5 :

 5 Figure 5: Graph G 4 encoding 0010

  )) by Property 1. Finally, in C, we have {w ∈ N (b(j, 4)) : p w = b(j, 4)} = {b(j, 3)} since all neighbors of b(j, 4) but b(j, 3) are -nodes, and so they have their p-value equal to null in C. We have Ident(r 2 (ρ, j)) < Ident(b(j, 3)) by Property 1, then r 2 (ρ, j) = min({w ∈ N (b(j, 4)) : p w = b(j, 4)} ∪ {r 2 (ρ, j)}) and the hypotheses of Lemma 1 are satisfied. Thus from Lemma 1, we can exhibit an execution to switch edges (r 1 (ρ, j), r 2 (ρ, j)) from state Off to state On and where only nodes r 1 (ρ, j), r 2 (ρ, j) and b(j, 4) make moves. 2. Now, for each integer j, 0 ≤ j < ρ, edge (b(j, 2), b(j, 3)) is in state AlmostOn. Ident(b(j, 1)) < Ident(b(j, 4)) and {w ∈ N (b(j, 1)) : p w = b(j, 1)} = {b(j, 2)} so hypothesis of Lemma 2 hold. Thus from Lemma 2, an execution to switch edge (b(j, 2), b(j, 3)) from state AlmostOn to state AlmostOff is performed. 3. Edge (b(ρ, 2), b(ρ, 3)) is still in state Off. Using the same argument of step (1), from Lemma 1, we can exhibit an execution to switch edges (b(ρ, 2), b(ρ, 3

-

  ----Rules for each node u in single(V) ResetEnd :: UpdateEnd :: if pu = null ∧ endu = T rue if (pu ∈ matched(N (u)) ∧ (pp u = u) ∧ (endu = endp u ) then endu := F alse then endu := endp u UpdateP :: if (pu = null ∧ {w ∈ matched(N (u)) | pw = u} = ∅) ∨ (pu / ∈ (matched(N (u)) ∪ {null})) ∨ (pu = null ∧ pp u = u) then pu := Lowest{w ∈ matched(N (u)) | pw = u} endu := F alse -----Predicates and functions BestRematch(u) ≡ ( a := Lowest{x ∈ single(N (u)) ∧ (px = u ∨ endx = F alse)} b := Lowest{x ∈ single(N (u)) \ {a} ∧ (px = u ∨ endx = F alse)} return (a, b) )

  MatchSecond :: if (AskSecond (u) = null) ∧ (sm u = T rue) ∧ [ pu = AskSecond (u) ∨ endu = (pu = AskSecond(u) ∧ pp u = u ∧ pm u = AskF irst(mu)) ∨ su = endu ] then endu := (pu = AskSecond(u) ∧ pp u = u ∧ pm u = AskF irst(mu)) su := endu pu := AskSecond (u) ResetMatch :: if [(AskFirst(u) = AskSecond (u) = null) ∧ ((pu, su, endu) = (null, F alse, F alse))] ∨ [AskSecond(u) = null ∧ pu = null ∧ sm u = F alse] then (pu, su, endu) := (null, F alse, F alse)

Figure 6 :

 6 Figure 6: PolyMatch algorithm

  MatchFirst, then 7 executes UpdateP and chooses 3.

  ResetEnd, then 2 executes Update and becomes First. Finally, 3 executes ResetMatch.

  MatchFirst, then 1 executes UpdateP and accepts the proposition of 2. Finally, 2 executes MatchFirst (s 2 :=True).

  In parallel 7 and 3 execute UpdateP and MatchSecond respectively.

  UpdateP, then 3 executes MatchSecond, then the True value of end 3 is propagated in the path (1, 2, 3, 7).

Figure 7 :

 7 Figure 7: An execution of Algorithm PolyMatch (Only the True value of the end-variables are given)

Figure 8 :

 8 Figure 8: A chain of 3-augmenting paths.

  x and p x = u holds. Using the same argument, x cannot execute U pdateP nor ResetEnd between configurations C 1 and C. Thus p u = x ∧ p x = u in C.

5 .

 5 ) s v = T rue; 4. u is not eligible for any move in C 1 ; If end v = F alse in C 1 then the following holds: (a) From C 1 , v executes a next move and this move is a M atchF irst; (b) Let us assume this move (the first move of v from C 1 ) is done in transition C 2 → C 3 . In configuration C 3 , we have: (i) s u = end u = T rue; (ii) p v ∈ single(N (v)) ∧ p v = AskF irst(v) ∧ p pv = v; (iii) p u ∈ single(N (u)) ∧ p u = AskSecond(u) ∧ p pu = u; (iv) s v = T rue; (v) u does not execute moves between C 1 and C 3 ;

1

 1 and thus it cannot change its p-value. So, p pv = v in C 1 . Point 3c holds since after u executed a M atchSecond in C 0 → C 1 , observe that necessarily p u = AskSecond(u) in C 1 . Moreover, s u = T rue in C 1 so, according to Lemma 11, ∃y ∈ single(N (u)) : p u = y ∧ p y = u in C 1 . p v = AskF irst(v) and p pv = v hold in C 0 , according to Points 1a and 1b. Moreover, p u = AskSecond(u) holds in C 0 since u writes T rue in end u while executing a M atchSecond in C 0 → C 1 . Finally, by Point 2, v can only execute M atchF irst in C 0 → C 1 , thus variable s v remains T rue in transition C 0 → C 1 and Point 3d holds.

8. 3 .

 3 How many U pdate in an execution? Definition 7. Let u be a matched node and C be a configuration. We define Cand(u, C) = {x ∈ single(N (u)) : (p x = u ∨ end x = F alse)} which is the set of vertices considered by the function BestRematch(u) in configuration C.

  Only the m variable from MaxMatch are drawn.

Figure 9 :

 9 Figure 9: The transformation from G/C 0 (on the left) to G /C 0 (on the right)

  al. paper. Moreover, we can easily show that if C is stable in PolyMatch, then no rule from the Manne et al. algorithm but the Update rule can be performed in C. Unfortunately, it is not straightforward to prove that the Update rule from Manne et al. algorithm cannot be executed in C. Indeed, our Update rule is more difficult to execute than the one of Manne et al. in the sense that some possible Update in Manne et al. are not possible in our algorithm.

Proof. We will prove that all cases but these two are not possible in a stable configuration. First, Lemma 4 says the configuration cannot be stable if exactly one of p u or p v is not null. Second, assume that p u = null ∧ p v = null. Let p u = x and p v = y. Observe that x ∈ single(N (u)) (resp. y ∈ single(N (v))), otherwise u (resp. v) is eligible for Update. [Case x = y]: If p x = u and p y = v then Lemma 7 says the configuration cannot be stable. If p x = u and p y = v then Lemma 6 says the configuration cannot be stable. Thus, the only remaining possibility when p u = null and p v = null is: p x = u and p y = v. [Case x = y]: Ask(u) = null (resp. Ask(v) = null), otherwise u (resp. v) is eligible for a ResetMatch. W.l.o.g. let us assume that u is First. x = AskF irst(u) (resp. x = AskSecond(v)), otherwise u (resp. v) is eligible for MatchFirst (resp. MatchSecond ). Thus AskF irst(u) = AskSecond(v) which is impossible according to these two predicates. Lemma 9. Let x be a single node. In a stable configuration, if p x = u, u = null then there exists a 3-augmenting path

Proof. By lemma 3, if p x = u with u = null then u ∈ matched(N (x)) and p u = x. Since p u = null, by Theorem 2 the result holds.

Corollary 2. In a stable configuration, there is no 3-augmenting path on (G, M + ) left.

Proof. Let us assume in a stable configuration, there is a 3-augmenting path on (G, M + ). By Theorem 2, any remaining augmenting-path (x, u, v, y) contains an edge (u, v) ∈ M + such that p u = p v = null. From Lemma 8, p x = null ∨ p y = null. W.l.o.g let us assume p x = null. By Lemma 9, (x, p x ) ∈ M + and so (x, u, v, y) is not an augmenting path. Contradiction.

Convergence Proof

This section is devoted to a sketch of the convergence proof. In the following, µ will denote the number of matched nodes and σ the number of single nodes.

The first step consists in proving that the values of s and end represent the different phases of the path exploitation. Recall that s u = True means p pu = u. Moreover end u = True means that the path is fully exploited. We can easily prove that after one activation of a matched node u, s u = True implies p pu = u: Lemma 11. Let u be a matched node. Consider an execution E starting after u executed some rule. Let C be any configuration in E. In C, if s u =True then ∃x ∈ single(N (u)) :

However, a bad initialization of end mu to True can induce u to wrongly write True in end u . But this can appear only once and thus, the second time u writes True in end u means that a 3-augmenting path involving u has been fully exploited.

Theorem 3. In any execution, a matched node u can write end u :=True at most twice.

We now count the number of destruction of partially exploited augmenting paths. Recall that in Manne et al. algorithm, for one fully exploited augmenting path, it is possible to destroy a sub-exponential number of partially exploited ones.

In our algorithm, observe that for a path destruction, the set of single neighbors that are candidates for a matched edge has to change and this change can only occur when a single node changes its end-value. Such a change induces a path destruction if a matched node takes into account this modification by applying an Update rule. So, we first count the number of times a single node can change its end-value (Lemma 21) and then we deduce the number of times a matched node can execute Update (Corollary 5). Finally, we conclude we destroy at most O(n 2 )(= O(∆(σ + µ))) partially exploited augmenting path.

The rest of the proof consists in counting the number of moves that can be performed between two Update, allowing us to conclude the proof (Theorem 4).

In the following, we detailed point by point the idea behind each result cited above.

For the second point, we first consider the case x ∈ Cand(u, C 1 ) and x / ∈ Cand(u, C 0 ). Necessarily

x has executed an U pdateP and the second point holds. Assume now that p x = u in C 1 . Necessarily end x = F alse in C 1 and the Lemma holds.

We consider the second case in which x / ∈ Cand(u, C 1 ) and x ∈ Cand(u, C 0 ). Necessarily in C 1 , p x = u and end x = T rue. Thus if end x = F alse in C 0 the lemma holds. Assume by contradiction that end x = T rue in C 0 . This implies p x = u in C 0 . But since in C 1 p x = u then x executed U pdateP in C 0 → C 1 which implies end x = F alse in C 1 , a contradiction. This completes the proof.

Corollary 5. Matched nodes can execute at most ∆(σ + 6µ) + µ times the U pdate rule.

Proof. Let u be a matched node. Initially each matched node can be eligible for an U pdate. Thus, let us consider a sub-execution E staring after u has executed a move and in which BestRematch(u) remains constant. By Lemma 12, the first line of the U pdate rule is always false for u in E. So u can execute the U pdate rule at most once in E. So, for u to become eligible again for an U pdate after E, BestRematch(u) must change and so, by Lemma 22, at least one single node must change the value of its end variable. Each change of the end value of a single node can generate at most ∆ matched nodes to be eligible for an U pdate. By Lemma 21, the number of transitions where a single node changes the value of its end variables is at most σ + 6µ times. Thus at most ∆(σ + 6µ) U pdate generated by a change of the end value of a single node and the Lemma holds.

8.4.

A bound on the total number of moves in any execution Definition 8. Let (u, v) be a matched edge. In the following, we call F, a finite execution where neither u nor v execute the U pdate rule. Let D E be the first configuration of F and D E be the last one.

Observe that in the execution F, all variables α and β of nodes u and v remain constant and thus, predicates AskF irst and AskSecond for these two nodes remain constant too.

Lemma 23. If Ask(u) = Ask(v) = null in F, then u and v can both execute at most one ResetM atch.

Proof. In the execution F, by definition, u and v do not execute the U pdate rule. Moreover, these two nodes are not eligible for M atch rules since Ask(u) = Ask(v) = null. Thus they are only eligible for ResetM atch. Observe now it is not possible to execute tis rule twice in a row, which completes the proof.

Lemma 24. Assume that in F, u is F irst and v is Second. If s u is False in all configurations of F but the last one, then v can execute at most one rule in F. Proof. Since s u =F alse in all configurations of F but the last one, node v which is Second can only be eligible for ResetM atch. If v executes ResetM atch, it is not eligible for a rule anymore and the Lemma holds.

Lemma 25. Assume that in F, u is F irst and v is Second. If s u is False throughout F, then u can execute at most one rule in F.

Proof. Node u can only be eligible for M atchF irst. Assume u executes M atchF irst for the first time in some transition C 0 → C 1 , then in C 1 , necessarily, p u = AskF irst(u), s u = F alse (by hypothesis) and end u = F alse by Lemma 10. Let F 1 be the execution starting in C 1 and finishing in D E . Since in F 1 , there is no U pdate of nodes u and v, observe that p u = AskF irst(u) remains T rue in this execution. Assume by contradiction that u executes another M atchF irst in F 1 . Consider the first transition C 2 → C 3 after C 1 when it executes this rule. Notice that between C 1 and C 2 it does not execute rules. Thus in C 2 , p u = AskF irst(u), s u = F alse and end u = F alse hold. Now if u executes M atchF irst in C 2 it is necessarily to modify the value of s u or end u . By definition, it cannot change the value of s u . Moreover it cannot modify the value of end u as this would imply by Lemma 10 that s u = T rue in C 3 . This completes the proof.

Consider the other case in which u writes F alse in C 1 . Let C 2 → C 3 be the first transition in F 1 in which u writes T rue in s u . Call F 10 the execution between C 1 and C 3 and F 11 the execution between C 3 and D E . By definition, s u stays F alse in F 10 \C 3 . Thus in F 10 \C 3 , u can execute at most one rule, by Lemma 25. Now in F 10 , u can execute at most two rules. By Lemma 24, v can execute at most one rule in F 10 . In total, u and v can execute at most three rules in F 10 . In F 11 , u and v can execute at most five rules by Lemma 26. Thus in F 1 , u and v can apply at most eight rules. Theorem 4. In any execution, matched nodes can execute at most 12∆(σ + 6µ) + 18µ rules.

Proof. Let k be the number of edges in the underlying maximal matching, k = µ 2 . For i ∈ [1, .., k], let {(u i , v i ) = a i } be the set of matched edges. By U pdate(a i ) we denote an U pdate rule executed by node u i or v i . By Lemma 28, between two U pdate(a i ) rules, nodes u i and v i can execute at most 12 rules. By Corollary 5, there are at most ∆(σ + 6µ) + µ executed U pdate rules. Thus in total, nodes can execute at most Proof. We prove that a single node x can execute the ResetEnd rule at most once. Assume by contradiction that it executes this rule twice. Let C 0 → C 1 be the transition when it executes it the second time. In C 0 , end x = T rue, by definition of the rule. Since x already executed a ResetEnd rule, it must have some point wrote T rue in end x . This is only possible through an execution of U pdateEnd. Thus consider the last transition D 0 → D 1 in which it executed this rule. Observe that D 1 ≤ C 0 . Since between D 1 and C 0 , end x remains T rue, observe that x does not execute any rule between these two configurations. Now since in D 1 , p x = null and this holds in C 0 then x is not eligible for ResetEnd in C 0 , which gives the contradiction. This implies that single nodes can execute at most σ times the ResetEnd rule.

Lemma 30. In any execution, single nodes can execute at most σ + 6µ times the U pdateEnd rule. Proof. By Lemma 21, single nodes can change the value of their end variable at most σ + 6µ times. Thus they can apply U pdateEnd at most σ + 6µ times, since in every application of this rule, the value of the end variable must change.

Lemma 31. In any execution, single nodes can execute O(∆(σ + µ)) times the U pdateP rule.

Proof. Let x be a single node. Let C 0 → C 1 be a transition in which x executes an U pdateP rule and let C 2 → C 3 be the next transition after C 1 in which x executes an U pdateP rule. We prove that for x to execute the U pdateP rule in C 2 → C 3 , a matched node had to execute a move between C 0 and C 2 .

In C 1 there are two cases: either p x = null or p x = null. Assume to begin that p x = null. This implies that in C 0 the set {w ∈ N (x)|p w = x} is empty. In C 2 , p x = null, since between C 1 and C 2 , x can only apply U pdateEnd or ResetEnd. Thus if it applies U pdateP in C 2 , necessarily {w ∈ N (x)|p w = x} = ∅. This implies that a matched node must have executed a M atch rule between C 1 and C 2 and the lemma holds in that case. Consider now the case in which p x = u with u = null in C 1 . By definition of the U pdateP rule, we also have u ∈ matched(N (x)) ∧ p u = x holds in C 0 . In C 2 we still have that p x = u since between C 1 and C 2 , x can only execute U pdateEnd or ResetEnd. Thus if x executes U pdateP in C 2 , necessarily p px = x. This implies that p u = x and so u executed a rule between C 0 and C 2 . Now, the lemma holds by Theorem 4.