Mohammed Haddad
email: mohammed.haddad@univ-lyon1.fr

Colette Johnen
email: johnen@labri.fr

Sven Köhler

Polynomial Silent Self-Stabilizing p-Star Decomposition 1

We present a silent self-stabilizing distributed algorithm computing a maximal p-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most 12∆m + O(m + n) moves, where m is the number of edges, n is the number of nodes, and ∆ is the maximum node degree. Regarding the move complexity, our algorithm outperforms the previously known best algorithm by a factor of ∆. While the round complexity for the previous algorithm was unknown, we show a 5 n p+1 + 5 bound for our algorithm.

Introduction

Fault-tolerance is among the most important requirements for distributed systems. Self-stabilization is a fault-tolerance technique that deals with transient faults. It was first introduced by Dijkstra [START_REF] Dijkstra | Self-stabilizing systems in spite of distributed control[END_REF]. Starting in an arbitrary configuration, a self-stabilizing distributed system converges to a legitimate configuration in finite time by itself, i.e., without any external intervention. This makes self-stabilization an elegant approach for non-masking fault-tolerance [START_REF] Dolev | Self-stabilization[END_REF].

An H-decomposition of a graph G subdivides a graph into disjoint components which which are isomorphic to H. A p-star is a complete bipartite graph K 1,p with one center node and p leaves. One of the famous and well studied graph decompositions in literature is star decomposition [START_REF] Cain | Decomposition of complete graphs into stars[END_REF][START_REF] Lee | Balanced star decompositions of regular multigraphs and lambda-fold complete bipartite graphs[END_REF][START_REF] Merly | Linear star decomposition of lobster[END_REF]. A decomposition of a graph into stars is a way of expressing the graph as the union of disjoint stars [START_REF] Bryant | Star factorizations of graph products[END_REF]. The problem of star decomposition has several applications including scientific computing, scheduling, load balancing and parallel computing [START_REF] Andreev | Balanced graph partitioning[END_REF], important nodes detection in social networks [START_REF] Lemmouchi | Robustness study of emerged communities from exchanges in peer-to-peer networks[END_REF]. Decomposing a graph into stars is also used in parallel computing and programming. This decomposition offers similar feature as Master-Slave paradigm, used in grids [START_REF] Mezmaz | A grid-based parallel approach of the multi-objective branch and bound[END_REF] and P2P infrastructures [START_REF] Bendjoudi | P2p design and implementation of a parallel branch and bound algorithm for grids[END_REF].

Related Work

Self-stabilizing algorithms have been proposed for a large variety of graph theoretical problems such as finding minimal dominating sets [START_REF] Chiu | A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon[END_REF], maximal matchings [START_REF] Hsu | A self-stabilizing algorithm for maximal matching[END_REF][START_REF] Hedetniemi | Maximal matching stabilizes in time O(m)[END_REF], independent sets [START_REF] Guellati | A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs[END_REF], spanning trees [START_REF] Blin | Loop-free super-stabilizing spanning tree construction[END_REF], etc. The graph decomposition problem is defined on a graph G = (V, E), where V is the set of nodes and E is the set of edges, such that the graph G is decomposed into smaller components having specific properties. These properties are often defined on the size of the partitions (clusters), on their shape (subgraphs) or both (patterns). Graph partitioning into clusters was considered by [START_REF] Caron | A self-stabilizing k-clustering algorithm using an arbitrary metric[END_REF] and [START_REF] Bein | A self-stabilizing link-cluster algorithm in mobile ad hoc networks[END_REF]. In [START_REF] Belkouch | Self-stabilizing deterministic network decomposition[END_REF], authors considered a particular graph partitioning problem that consists of decomposing the graph into partitions of order k. [START_REF] Belkouch | Self-stabilizing deterministic network decomposition[END_REF] considered a particular graph decomposition problem that consisted in partitioning a graph with k 2 nodes into k partitions of order k. The proposed algorithm relies on self-stabilizing spanning tree construction and converges within 3(h + 1) steps where h is the height of the spanning tree. Furthermore, [START_REF] Caron | A self-stabilizing k-clustering algorithm using an arbitrary metric[END_REF], [START_REF] Bein | A self-stabilizing link-cluster algorithm in mobile ad hoc networks[END_REF] and [START_REF] Johnen | Robust self-stabilizing clustering algorithm[END_REF] focused on decomposing the graph into clusters while [START_REF] Neggazi | Self-stabilizing algorithm for maximal graph partitioning into triangles[END_REF] considered decomposition of graphs into triangles. Other self-stabilizing algorithms were proposed for graph colorings [START_REF] Ghosh | A self-stabilizing algorithm for coloring planar graphs[END_REF][START_REF] Hedetniemi | Linear time self-stabilizing colorings[END_REF] that can be considered as decompositions into independent sets.

Observe that the maximal node-disjoint p-star decomposition problem when restricted to p = 1 is equivalent to maximal matching problem in graphs. Thus the general problem when p ≥ 1 is NP-complete since generalized matching and general graph factor problems were proved to be NP-complete in [START_REF] Kirkpatrick | On the completeness of a generalized matching problem[END_REF] and [START_REF] Kirkpatrick | On the complexity of general graph factor problems[END_REF] respectively. The maximal matching problem has received much interest due the abundant number of applications in fields as diverse as transversal theory, assignment problems, network flows, and scheduling. Many studies have addressed this problem even in the field of self-stabilization [START_REF] Hsu | A self-stabilizing algorithm for maximal matching[END_REF][START_REF] Tel | Maximal matching stabilizes in quadratic time[END_REF][START_REF] Hedetniemi | Maximal matching stabilizes in time O(m)[END_REF][START_REF] Goddard | Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks[END_REF]. The best known move complexity for maximal matching problem is O(m) and was obtained by [START_REF] Manne | A new self-stabilizing maximal matching algorithm[END_REF].

The first self-stabilizing algorithm for the p-star decomposition problem was proposed in [START_REF] Neggazi | A self-stabilizing algorithm for maximal p-star decomposition of general graphs[END_REF]. It finds a maximal decomposition into node-disjoint p-stars. The decomposition is maximal in the sense that the nodes not part of any p-star cannot form a p-star. However, the algorithm proposed in [START_REF] Neggazi | A self-stabilizing algorithm for maximal p-star decomposition of general graphs[END_REF] always converges to a unique legitimate configuration according to the input graph and does not guarantee a polynomial move complexity. An improvement was proposed in [START_REF] Neggazi | A new self-stabilizing algorithm for maximal p-star decomposition of general graphs[END_REF] where authors dealt with the uniqueness of legitimate state and proved their algorithm to converge within O(∆ 2 m) moves under the unfair distributed scheduler where m is the number of edges and ∆ is maximum node degree in the graph. A bound on the round complexity of the algorithm was not given.

Our Results

In this paper, we improve the move complexity of the previous algorithm to 12∆m + O(m + n) and prove an O(n) bound on the round complexity. The algorithm is proven correct and analyzed under the unfair distributed scheduler, the most powerful adversary. The algorithm does not converge to a unique legitimate configuration. In fact, there is a legitimate configuration for any valid maximal p-star decomposition.

The paper is organized as follows : Computation model is defined in Section 2, then details of the p-star decomposition algorithm are presented in Section 3. Proofs of correctness and convergence are given in Sections 4 and 5, respectively.

Model of Computation

We model the distributed system as a simple undirected graph G = (V, E), where V is a set of nodes, and E is a set of edges representing the communication links. We denote by N (v) the set of all neighbors of v in G, i.e., N (v) contains all nodes that can communicate with v. We call N (v) the open neighborhood and denote the closed neighborhood by N

[v] = N (v) ∪ {v}.
A distributed algorithm defines a set of shared variables and a set of rules for each node. In this paper, we only discuss uniform algorithms, i.e., each nodes has the same set of variables and executes the same set of rules. The (ordered) tuple of the values assigned to the variables of a node is called the local state. The (ordered) tuple of all local states constitutes the current configuration of the distributed system. Each rule is given in the form guard(v) → action, where guard(v) is a Boolean predicate over the variables within the closed neighborhood of node v. The action may read all shared variables within the closed neighborhood but may modify only the variables of v itself. We say that a rule is enabled, if its guard evaluates to true. We say that a node is enabled, it any of its rules is enabled. For the algorithm given in this paper, at most one rule per node is enabled at a time.

Executions of a distributed algorithm are represented by a sequence of configurations e = c 0 , c 1 , c 2 , . . . , where c 0 is called the initial configuration. Executions are organized in steps. The i-th step, where c i is reached from c i-1 , denoted by c i-1 → c i , consists of three phases. In the first phase, an adversarial scheduler selects a non-empty set S i of nodes that are enabled in c i-1 . In the second phase, all selected nodes perform the action of an enabled rule and compute their new local state. The computed local state is then made visible to neighboring nodes in the third phase. This model is called composite atomicity. If a node was selected, then we say that the node has made a move during that step. The sequence S 1 , S 2 , S 3 , . . . is called the schedule of e.

Three scheduler models are commonly discussed in the literature. The central scheduler selects exactly one enabled node per step. The synchronous scheduler selects all enabled nodes in each step. The most general model is the distributed scheduler, where the adversary may chose any non-empty of enabled nodes. A scheduler may satisfy certain fairness properties. We say that a scheduler is fair, if it selects any continuously enabled process after a finite number of steps. An unfair scheduler may indefinitely delay the move of a node as long as there are other enabled nodes. The algorithm given in this paper is proven correct and analyzed under the most general model, i.e., the unfair distributed scheduler.

A set CS of configurations is closed if any step from a configuration of CS reaches a configuration of CS. By extension, a predicate Pr on configurations is said closed if the set of configurations verifying Pr is closed.

A distributed algorithm is called self-stabilizing, if it satisfies the following requirements:

• Any execution reaches a legitimate configuration after a finite number of steps. (Convergence)

• The set of legitimate configurations is closed. (Closure) The legitimacy of a configuration typically expresses that the output of the algorithm is correct.

The algorithm given in this paper is silent, i.e., any execution eventually reaches a terminal configuration in which no node is enabled. Note that for any silent self-stabilizing algorithm, terminal configurations are also legitimate. Its runtime complexity is analyzed with respect to two different metrics: the move and the round complexity. The move complexity is defined as i |S i |. The round complexity is obtained by partitioning the execution e into asynchronous rounds as follows: The first round is the minimal prefix c 0 , c 1 , . . . , c x of e such that V \ D 0 ⊆ x i=1 D i ∪ S i , where D i is the set of nodes that are not enabled in c i . The second round of e is the first round of the remaining suffix c x , c x+1 , c x+2 , . . . , and so forth. One asynchronous round allows each node that was enabled at the beginning of the round to make a move, unless the node becomes disabled due to a move by a neighbor.

The p-Star Decomposition Algorithm

In this section we describe the implementation of the p-star decomposition algorithm. First we give an overview of how the algorithm works. Assume that some nodes are already a member of a star, while others are not. Nodes indicate to their neighbors whether they are a member of a star or not. In addition, each node indicates whether it may be viable center of a new star. That is the case only if the node itself and p of its neighbors are not a member of a star, yet.

Nodes keep track of the viable centers within the closed neighborhood. Unless they are a member of a star, they invite the viable center having the minimum identifier to form new p-star. The invitation is updated as needed if the set of viable centers within the closed neighborhood changes. Directing the invitation at the viable center with the minimum identifier makes sure that no deadlocks can occur. Eventually, a viable center is invited by itself and at least p neighbors. Such a viable center v then picks p neighbors as the leaves of the star and assigns them to a new p-star centered at v.

In the remainder of this section, we present the shared variables and predicates used by the algorithm. Then, the rules are presented.

Variables and Predicates

Algorithm 1 gives an overview over the variables, their domain, their meaning, and the predicates that the algorithm uses. Node v is the center of a p-star if and only if v verifies correctCenter(v). The set stored in the shared variable leaves(v) contains the p neighbors of v belonging to the star centered in v. So star(v), as defined below, is the set of nodes in the p-star centered in v.

Definition 1. star(v) = ∅ if leaves(v) = ∅ and star(v) = {v} ∪ leaves(v) otherwise.
For any p-star centered in v, the following statements are proven (Observation 1, Lemma 2):

• The shared variable center is equal to v for every node in star(v); • Every node in star(v) verifies the predicate correctLeaf or correctCenter; • The star is well formed, i.e., the star contains v and p neighbors of v.

The values of the shared variables center and leaves in its neighborhood are enough to allow a node v to determine the value of the predicates correctCenter(v) and correctLeaf (v); so they suffice to compute the value of isInStar(v).

Algorithm 1 Shared Variables, Predicates, Macros and Guard predicates

Shared variables of each node

v ∈ V • center(v) -a node identifier or ⊥
The center of the p-star that v belongs to or the viable center that v invites to form new p-star. The value ⊥ is used if v is not a member of a p-star and is not inviting any node.

• leaves(v) -a set of up to p node identifiers

The set is empty if v is not the center of a p-star.

Otherwise it contains the leaves of the p-star.

• inStar(v) ∈ Boolean

Indicates whether v is a member of a p-star.

• viableCenter(v) ∈ Boolean

Indicates whether v is a viable center for a new p-star.

• lockedCenter(v) ∈ Boolean

Indicates whether the value of center(v) is locked or not.

Predicates • isCenter(v) ≡ |leaves(v)| = p • incorrectCenter(v) ≡ (leaves(v) = ∅) ∧ ((center(v) = v) ∨ (∃u ∈ leaves(v) : center(u) = v) ∨ ¬isCenter(v) ∨ (leaves(v) ⊆ N (v))) • correctLeaf (v) ≡ (center(v) ∈ N (v)) ∧ isCenter(center(v)) ∧ (v ∈ leaves(center(v)) • correctCenter(v) ≡ isCenter(v) ∧ ¬incorrectCenter(v) • isInStar(v) ≡ correctLeaf (v) ∨ correctCenter(v) • isViableCenter(v) ≡ ¬isInStar(v) ∧ (|{ u ∈ N (v) | ¬inStar(u) }| ≥ p) Macros • bestCenter(v) is the element of {u ∈ N [v] | viableCenter(u) ∧ leaves(u) = ∅} having the smallest identifier or ⊥ if the set is empty • potentialLeaves(v) is the set {u ∈ N (v) | center(u) = v ∧ lockedCenter(u)} Guard Predicates • starToUpdate(v) ≡ ¬isInStar(v) ∧ (|potentialLeaves(v)| ≥ p) ∧ (v = center(v)) • centerToUpdate(v) ≡ ¬isInStar(v) ∧ (center(v) = bestCenter(v) ∨ ¬lockedCenter(v)) • variablesToUpdate(v) ≡ (inStar(v) = isInStar(v)) ∨ (viableCenter(v) = isViableCenter(v)) ∨ incorrectCenter(v) Observation 1. leaves = ∅ ∧ ¬incorrectCenter(v) ⇒ correctCenter(v) leaves(v) = ∅ ⇒ ¬incorrectCenter(v) variablesToUpdate(v) ⇒ v is enabled incorrectCenter(v) ⇒ v is enabled Algorithm 2 : p-star rules on v Procedures • updateBooleans(v) : inStar(v) := isInStar(v); viableCenter(v) := isViableCenter(v); • updateVariables(v) : if incorrectCenter(v) then leaves(v) := ∅; updateBooleans(v); Rules RA(v) : starToUpdate(v) -→
leaves(v) := subset of potentialLeaves(v) with exactly p elements; updateBooleans(v);

RI(v) : ¬starToUpdate(v) ∧ centerToUpdate(v) ∧ ¬lockedCenter(v) -→ lockedCenter(v) := true; center(v) := bestCenter(v); updateVariables(v); RGI(v) : ¬starToUpdate(v) ∧ centerToUpdate(v) ∧ lockedCenter(v) -→ lockedCenter(v) := false; updateVariables(v); RU(v) : ¬starToUpdate(v) ∧ ¬centerToUpdate(v) ∧ variablesToUpdate(v) -→ updateVariables(v);
Lemma 2. Every node v verifying ¬incorrectCenter(v) and star(v) = ∅ satisfies the following assertions:

|star(v)| = p + 1 (1) star(v) ⊆ N [v] ( 2
)
center(u) = v ∀u ∈ star(v) (3) correctLeaf (u) = true ∀u ∈ leaves(v) (4) isInStar(u) = true ∀u ∈ star(v) (5)
Proof. We have leaves(v) = ∅ and ¬incorrectCenter(v). According to Observation 1, v verifies correctCenter(v). By definition of correctCenter(v), we have leaves(v) ⊆ N (v), |leaves(v)| = p, so assertions (1) and ( 2) are verified. Assertion (3) is verified by v because we have ¬incorrectCenter(v). We conclude that assertion (4) is verified. So assertion ( 5) is also verified.

p-Star Construction

The shared variable inStar allows nodes to determine whether they are a viable center of a new p-star. If a node v and at least p neighbors of v are not a member of a p-star, then v may become the center of a new p-star (i.e., v verifies the predicate isViableCenter).

The shared variable viableCenter(v) informs neighbors of node v that in the current configuration, v may become the center of an new p-star. The shared variables inStar and viableCenter are updated by any rule during the execution of procedure updateBooleans. Note that if the value of inStar(v) or viableCenter(v) is not accurate, then v is enabled (Observation 1).

In the remainder of the algorithm presentation, we will study the behavior of nodes (v, u) that are not in a p-star (i.e., nodes in CS).

Definition 2.

Let S be the set of nodes belonging to a p-star, i.e., S = v∈V star(v). Then CS = V \ S is the complement of S, i.e., the nodes that do not belong to a p-star.

The macro bestCenter(v) returns the viable center that v should invite to create a new p-star. If v is not connected to a viable center, then ⊥ is returned. More precisely, bestCenter(v) chooses the node having the smallest identifier among the viable centers at a distance less than 2 from v. In particular, we have viableCenter(u) and leaves(u

) = ∅ if bestCenter(v) = u.
To invite u, node v sets its shared variable center to u via rule RI. Rule RI is the only rule modifying the value of center(v). If rule RI is enabled for node v, then ¬lockedCenter(v) is verified. Node v is enabled if lockedCenter(v) = true or center(v) = bestCenter(v) because centerToUpdate(v) is verified. So v will invite node bestCenter(v) to be the center of its star or it will set center(v) to ⊥ if it is isolated (rule RI).

The set potentialLeaves(v) contains the neighbors of v that can safely be in the p-star centered at v if the p-star is created during the next step. Any node of this set invites v to be the potential center and they cannot update their variable center during the next step because the value of their shared variable lockedCenter is true. To change the value of center, a node with must first execute rule RGI before it can change center using rule RI in a subsequent step.

Let v be a node of CS. If the size of potentialLeaves(v) is at least p and center(v) = v then v can form a p-star centered in itself by executing rule RA.

p-Star Stability

The execution of rule RA by some node v builds a p-star. After this move, v is the center of a p-star containing p members of potentialLeaves(v), as proven in Lemma 4. The p-star stays unchanged (i.e., the set star(v) stays unchanged) along any execution, which is proven in Lemma 3.

Lemma 3. Let c be a configuration where v verifies correctCenter(v). Along any execution from c, the predicate correctCenter(v) is verified. The set leaves(v) stays unchanged along any execution from c.

Proof. Only a move of a node in star(v) may change the value of the predicates isCenter(v) and incorrectCenter(v) or the set leaves(v).

According to Lemma 2 and the definitions of correctCenter(v) and star(v), the nodes of star(v) verify the predicate isInStar. For these nodes, only rule RU may be enabled.

The action of rule RU does not change the value of leaves(v) and center(v) since incorrectCenter(v) = false in c. For a node u of leaves(v), the action of rule RU does not change the value of center(u). So the values of leaves(v), isCenter(v), and incorrectCenter(v) stay unchanged.

Lemma 4. If a node v executes rule RA during the step

c 1 → c 2 , then correctCenter(v) is verified in c 2 .
Proof. In c 1 , potentialLeaves(v) is a set of at least p nodes of N (v) and any node u of potentialLeaves(v) verifies center(u) = v and lockedCenter(u).

Let u be a neighbor of v with u ∈ potentialLeaves(v) in c 1 . In c 1 , u is disabled with respect to rule RI. Hence center(u) cannot change during the step c 1 → c 2 . So in c 2 , leaves(v) is a set of p distinct nodes of N (v) and any node of leaves(v) verifies center(u) = v. Also center(v) = v in c 2 , according to rule RA. Thus, correctCenter(v) is verified in c 2 .

Correctness of Terminal Configurations

In this section we establish that any terminal configuration represents a maximal p-star decomposition of the graph. More precisely, we prove that S contains only well formed disjoint p-stars and S is maximal, i.e., no p-star can be added to S. Lemma 5. Let u, v be two nodes verifying the predicate ¬incorrectCenter. Then the sets star(v) and star(u) are disjoint.

Proof. The claim is trivial if either star(u) or star(v) is empty. According to Lemma 2, center(w) = u (resp. center(x) = v) for all w ∈ star(u) (resp. for all x ∈ star(v)). Thus star(u) and star(v) cannot intersect. Proof. Let w be a node of CS. According to the definition of S, w / ∈ v∈V leaves(v) and leaves(w) = ∅. So, we have ¬isCenter(w) and ¬correctLeaf (w). According to Observation 1, any node w of CS, isInStar(w) = inStar(w) = false because w is disabled.

Let z be a node of P S. z has at least p neighbors having their shared variable inStar set to false. Thus isViableCenter(z) is verified. According to Observation 1, viableCenter(z) = true, because z is disabled.

Let CPS denote the set of nodes of CS having at most p -1 neighbors in CS (i.e., CPS

= CS \ PS = {z ∈ CS | |N (z) ∩ CS| < p}).
Let cz be a node of CPS. Node cz does not have p neighbors having their shared variable inStar set to false. ¬isViableCenter(cz) is verified. So, viableCenter(cz) = f alse. Let u be a node of S. According to Lemma 2, isInStar(u) = inStar(u) = true. So, viableCenter(u) = f alse because u is disabled. We conclude that for any node not in P S, viableCenter(x) = f alse. P S is the set of nodes that could be the center of a star set containing only nodes that are not yet in a p-star.

Lemma 7. In any terminal configuration, P S is empty.

Proof. Assume that P S is not empty. Let cz be the node of P S having the smallest identifier. Consider any node w ∈ CS ∩ N [cz]. We have bestCenter(w) = cz and isInStar(w) = f alse are according to Lemma 6. As w is disabled, ¬centerToUpdate(w) is verified (Observation 1). We have lockedCenter(w) = true and center(w) = bestCenter(w) = cz. As |CS ∩ N (cz)| ≥ p, starToUpdate(cz) is verified; so node cz is enabled with respect to rule RA. That is a contradiction to the assumption that the configuration is terminal. Thus P S is empty.

Theorem 8. In any terminal configuration, S = v∈V star(v) is a valid maximal p-star decomposition.

Proof. According to Observation 1, any node v verify the predicate ¬incorrectCenter(v) in a terminal configuration.

According to Lemma 2, and the definition of star, star(v) is empty or is a p-star centered to v in a terminal configuration. According to Lemma 5, the star sets are pairewise disjoint.

According to Lemma 7 and the definitions of P S, and S is maximal.

Move Complexity

Round Complexity

The proofs of the round complexity utilize the notion of attractors [START_REF] Gouda | Stabilizing communication protocols[END_REF]. An attractor A is a set of configuration that is closed under the execution of the algorithm. That is, for any execution, configurations subsequent to a configuration of A are also in A. A self-stabilizing always has two attractors: the set of all configurations and the set of all legitimate configurations.

Let C denote the set of all configurations. First we will establish that attractor A 0 , as defined below, is reached in a single round.

Definition 4. A 0 = {c ∈ C | ∀v ∈ V : ¬incorrectCenter(v)} 6.1. Properties of A 0
The following corollary is a direct consequence of the Observation 1 and Lemmas 10 and 11.

Corollary 24. After at most one round of execution starting in any configuration, A 0 has been reached and A 0 is closed under any execution of the algorithm.

Properties of executions starting in A 0

In the following, we establish that in any configuration of A 0 , at most nbMaxStars nodes verify the predicate isCenter. According to Corollary 25, in A 0 the predicate isCenter is closed. Thus, the rule RA is performed at most nbMaxStars times along any execution in A 0 .

Properties of RA-restricted executions starting in A 0

We call a step c 1 → c 2 RA-restricted, if no node executes rule RA during that step. Similarly, we say that a round is RA-restricted if it consists of only RA-restricted steps. In the remainder we study executions starting in configurations of A 0 . We show that any such execution contains at most 4 consecutive RArestricted rounds, i.e., after 4 consecutive RA-restricted rounds, either a terminal configuration is reached or in the following round at least one node executes rule RA. In any execution starting in A 0 , there are at most nbMaxStars RA-unrestricted rounds (Corollary 26). So the number total of rounds, in any execution from A 0 is at most 5nbMaxStars + 4.

First, we establish that the value of leaves(v) and isInStar(v) for any node v in a configuration of A 0 stays unchanged during any execution till no node performs the RA action. Proof. After two RA-restricted rounds from c, the configurations c2 ∈ A 2 is reached (Lemmas 33). Since A 2 is closed the have c3 ∈ A 2 .

Let v be a node with centerToUpdate(v) = true in c2. Without loss of generality, assume that lockedCenter(v) = true in c2. Node v is enabled as long as centerToUpdate(v) = true holds and no node performs RA action. Thus node v makes an RGI move during the third RA-restricted round. After the move of v, we have lockedCenter(v) = false. So node v remains enabled until it performs another move or RA action is performed.

Let v be a node with centerToUpdate(v) = true, and lockedCenter(v) = false in c3 (the configuration reached after 3 RA-restricted rounds from c). Before the end of the fourth RA-restricted round, v executes rule RI which updates center(v) with the value of bestCenter(v) and sets lockedCenter(v) to true. After that move, centerToUpdate(v) = false holds as bestCenter(v) does not change (Lemma 34). Proof. By Corollary 24, any non-restricted execution reaches A 0 after at most 1 round. Afterwards, an execution of rule RA occurs at least every 5 rounds by Corollary 37. Also by Corollary 37, any trailing suffix not containing any executions of rule RA can be at most 4 rounds in length. By Corollary 26, there are at most nbMaxStars rounds having a RA action along any execution starting in A 0 . This completes the proof.

Conclusion

We studied in this paper the problem of decomposing a graph into node-disjoint p-stars from a selfstabilization point of view. This problem is a generalization of maximal matching problem in graphs. We proposed a new self-stabilizing algorithm for maximal p-star decomposition problem performing better than both previously proposed algorithms. In fact, we improve the move complexity to O(∆m) instead of O(∆ 2 m) in [START_REF] Neggazi | A new self-stabilizing algorithm for maximal p-star decomposition of general graphs[END_REF] and solve the uniqueness legitimate configuration problem that [START_REF] Neggazi | A self-stabilizing algorithm for maximal p-star decomposition of general graphs[END_REF] suffered from, without losing linearity of round complexity. As future work, we aim to generalize the proposed algorithm to the weighted p-star decomposition problem.

Definition 3 .Lemma 6 .

 36 PS denotes the set of nodes of CS having at least p neighbors in CS (definition 2), i.e., PS = {z ∈ CS | |N (z) ∩ CS| ≥ p}. In any terminal configuration, we have • leaves(z) = ∅, for any node z in CS • isInStar(u) = f alse for any node x in CS • viableCenter(z) = true for any node z in P S • viableCenter(x) = f alse for any node x not in P S

10

 10

Definition 5 .Corollary 25 .Corollary 26 .

 52526 nbMaxStars = n p+1 .The following corollary follows from the definition of A 0 , and star and Lemmas 3 and 2. In A 0 , isCenter is a closed predicate. In A 0 , if isCenter(v) is verified, then |star(v)| = p+1. In any execution from A 0 , the rule RA is performed at most nbMaxStars times.Proof. Let c be a configuration of A 0 According to Corollary 25, if isCenter(v) is verified in c then |star(v)| = p + 1. According to Lemma 5, in c, if u = v then star(u) is disjoint of star(v). So, in c, the number of nodes satisfying the predicate isCenter is bounded by nbMaxStars.

Lemma 27 .

 27 Consider an RA-restricted step c 1 → c 2 with c 1 ∈ A 0 . For any node v, the value of leaves(v) does not change during this step.Proof. The rules RI, RGI and RU modify leaves(v) if incorrectCenter(v) = true in c 1 . We have incorrectCenter(v) = false in c 1 ∈ A 0 . Thus, leaves(v) does not change during this step. Lemma 28. Consider a step c 1 → c 2 with c 1 ∈ A 0 . If correctCenter(v) changes from false to true, then node v executed rule RA during this step. Lemma 34. Consider an RA-restricted step c 1 → c 2 with c 1 ∈ A 2 . For every node v, the value of bestCenter(v) does not change during this step. Proof. The value bestCenter(v) can only change if viableCenter(u) or leaves(u) change for some u ∈ N [v]. Since c 1 ∈ A 2 we have viableCenter(u) = isViableCenter(u) for all nodes u ∈ V . By Lemma 32 we know that the value of isViableCenter(u) does not change during this step for all nodes u ∈ V . Also, by Lemma 27, we know that the set leaves(u) does change for any node u ∈ V . Therefore, the value bestCenter(v) does change during this step. Definition 8. A 3 = {c ∈ A 2 | ∀v ∈ V : ¬centerToUpdate(v)} 6.6. Properties of A 3 Lemma 35. Let c be a configuration of A 0 and c3 be the configuration reached after four RA-restricted rounds from c. We have c3 ∈ A 3 and A 3 is closed under any RA-restricted step.

Lemma 36 .

 36 Consider a configuration of A 3 . Each node is either disabled or only enabled with respect to rule RA. Proof. Let v be a node. By definition of A 3 we have centerToUpdate(v) = false. Thus v is disabled with respect to rules RI and RGI. Also, by definition of A 2 ⊇ A 3 we have variablesToUpdate(v) = false. Thus rule RU is disabled. So v is either disabled or enabled with respect to rule RA. Combining Lemmas 35, and 36 yields the following result. Corollary 37. Any execution starting in A 0 contains at most 4 consecutive RA-restricted rounds. Theorem 38 (Upper bound on the number of rounds). The algorithm terminates after at most 5(nbMaxStars + 1) = 5( n p+1 + 1) rounds.

  Every node v executes rule RA at most once.

	5.1. Number of RA and RU moves per node
	Lemma 9.

 [START_REF] Dijkstra | Self-stabilizing systems in spite of distributed control[END_REF]This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02) and by the Sustainability Center Freiburg, Germany. The Sustainability Center Freiburg is a cooperation of the Fraunhofer Society and the University of Freiburg and is supported by grants from the Baden-Württemberg Ministry of Economics and the Baden-Württemberg Ministry of Science, Research and the Arts.

Proof. After v executes rule RA, it verifies the predicate correctCenter(v) (Lemma 4). From a configuration where correctCenter(v) is verified this predicate stays verified along any execution (Lemma 3). So along any execution, v may perform only the rule RU, because isInStar(v) is always verified (Lemma 2). Lemma 10. For every node v, ¬incorrectCenter(v) is a closed predicate.

Proof. Assume ¬incorrectCenter(v) is verfied in configuration c. According to Observation 1, in c, we have leaves(v) = ∅ or isCenter (v). Assuming that isCenter(v) in c, the claim follows from Lemma 3. Assume that leaves(v) = ∅ in c. Only the action of rule RA sets leaves(v) to a non-empty set. The claim follows from Lemmas 3 and 4. Proof. The proof is by contradiction, i.e., assume that node u has not executed rule RA during the step. The action of rules RI, RGI, or RU, if they change leaves(u), assign the empty set to leaves(u). As v ∈ leaves(u) in c 2 , we conclude that u does not update its set leaves during this step.

So correctLeaf (v) could change from false to true during this step only if center(v) changes and leaves(u) does not change. That implies that v executed rule RI during the step. However, rule RI can only set center(v) to u if bestCenter(v) = u which implies that leaves(u) = ∅ in c 1 and in c 2 . That is a contradiction to v ∈ leaves(u) in c 2 .

Lemma 13. Consider a step c 1 → c 2 in which correctLeaf (v) changes from false to true. Along any execution starting in c 2 , correctLeaf (v) stays verified.

Proof. Let u be the node such that u = center(v) in c 2 . During the step c 1 → c 2 , u performs the rule RA (Lemma 12). So in c 2 , node u = center(v) verifies the predicate correctCenter(u) (Lemma 4). According to Lemma 3, v belongs to leaves(u) along any execution from c 2 . In c 2 , star(v) = ∅ and ¬incorrectCenter(v), so correctLeaf (v) stays verified along any execution (Lemma 2).

Lemma 14. For each node v, the value of isInStar(v) changes at most 2 times.

Proof. Consider a step c 1 → c 2 in which isInStar(v) changes from false to true. This is either due to the fact that correctLeaf (v) became true, or correctCenter(v) became true.

correctCenter(v) is closed (Lemma 3). correctLeaf (v) stays verified after that step (Lemma 13).

So isInStar(v) may change from false to true at most once; then it keeps the value true. Thus true, false, true is the maximum sequence of values that isInStar(v) may assume.

Accounting for an initial inconsistencies, we obtain the following result.

Corollary 15. Each node v changes the variable inStar(v) at most 3 times.

Lemma 16. For each node v, the value of isViableCenter(v) changes at most 3 deg(v) + 2 times.

Proof. isViableCenter(v) may change its value each time a neighbors u ∈ N (v) change its value of inStar (v). By Corollary 15, this may occur at most 3 deg(v) times. Furthermore, isViableCenter(v) may also change its value if isInStar(v) changes. By Lemma 14, this can occur at most 2 times.

Accounting for an initial inconsistencies, we obtain the following result. The total number of moves over all nodes is then bounded by

Proof. The proof is by contradiction, i.e., assume that node v has not executed rule RA during the step. ¬incorrectCenter(v) and ¬correctCenter(v) are verified in c 1 . So leaves(v) = ∅ in c 1 (according to Observation 1). According to Lemma 27, in c 2 , we have leaves Proof. By Corollary 24, the set A 0 is closed and thus c1 ∈ A 0 . Let v be a node with inStar(v) = isInStar(v) in c. Node v is enabled as long as this inequality holds and no node executes rule RA. Thus node v performs a move during the first RA-restricted round. After the move of v, we have inStar(v) = isInStar(v). This equality stays verify until a node does the RA action (Lemma 30).

Lemma 32. Consider an RA-restricted step c 1 → c 2 with c 1 ∈ A 1 . For every node v, the value of isViableCenter(v) does not change during this step.

Proof. The value of isViableCenter(v) may only changes when the value of inStar(u) for some node u ∈ N (v) changes. As c 1 ∈ A 1 we have inStar(u) = isInStar(u) for all nodes u ∈ V . So no node changes the value of its inStar variable during this step. Proof. After the first RA-restricted round from c, the configuration c1 ∈ A 1 is reached (Lemma 31). Since A 1 is closed we have c2 ∈ A 1 .

Let v be a node with isViableCenter(v) = viableCenter(v) in c1. As long as this inequality holds and no node performs RA action, the node v is enabled. Thus node v performs a move during the second RArestricted round. After the move of v, we have isViableCenter(v) = viableCenter(v). This equality stays verify until a node does the RA action (Lemma 32).