P. , (. , and Q. , Q ? N P } Benchmark B4: Benchmark B3 holds, and either Root_BFS.color = 3 or the Minid Invariants hold

, Benchmark B5: Benchmark B4 holds, and either Root_BFS.color = 1 or the Maxminid Invariants hold

, Benchmark B6: Benchmark B5 holds, and for all P , P.isclusterhead if and only if P ? Clusterhead_Set. Benchmark B7: Benchmark B6 holds, and for all P , the following hold: 1. P.dist = Dist(P )

P. ,

P. Clusterhead,

, Lemma 1 Benchmark B1 is closed, and will hold within O(n) rounds of initialization. Proof: From [3], SSLE is silent, and converges in O(n) rounds of arbitrary initialization

, Lemma 2 Benchmark B2 is closed, and if Benchmark B1 holds, B2 will hold within O(diam) additional rounds

P. If,

M. Invariants, This consists of four parts: (a) P.maxminlevel < P.maxminhilevel (b) For any

Q. For and Q. ,

, If d ? P.maxminlevel then MaxMinId(P, d) ? P.maxminid

, Q)) = Q.minid, then either P.maxminid ? Q

P. If,

, Lemma 6 Benchmark B4 is closed, and if Benchmark B3 holds, then Benchmark B4 will hold within O(nk) additional rounds

, Suppose Benchmark B3 holds. By Lemma 5, Root_BFS.color = 3 within O(nk) rounds, and thus Benchmark B4 holds

, Consider consecutive steps ? ? ? ? in an execution of WeightedClustering, and assume that Benchmark B4 holds at configuration ?

I. Case and . Root_bfs,

I. I. Case, Root_BFS.color = 0 at ? ? . Then P.minid = P.id, P.minlevel = 0, and P.minhilevel = MinHop(P ) for all P

I. Case, Not Case I or Case II

, Suppose all the invariants hold at a configuration ?. We need to show that all invariants hold at configuration ? ?

. Consider-1b and . Suppose-q-?-n-p, If Q does not execute during the step, the inequality cannot change from true to false, since P.minhilevel cannot decrease. If Q executes Action A7 or A8, then Q.minhilevel ? MinHiLevel_F (Q) ? P

, Consider 1c. Suppose Q ? N P , and Q.minid > P.minid at ? ? . If P does not execute

, P.minlevel(P )+w(P, Q) is an upper bound on the value of Q.minhilevel after the step. If P executes, then the new value of P.minlevel+w(P, Q) is equal to the old value of P.minhilevel+w(P, Q)

. Consider-1d and Q. Suppose-q-?-n-p, minid at ? ? . Suppose P does not execute Action A7. If Q does not execute Action A7, and the invariant holds because by the inductive hypothesis, since the inequality does not change. If Q executes A7, then Q.minid > P.minid before the step, Since Invariant 1c holds before the step, P.minlevel + w(P, Q) is at least as great as the old value of Q

, We are done since Invariant 1b holds before the step. Invariant 2: The set of all values of minid over all process cannot gain a member during the step, since any new value of P.minid is copied from R.minid for some neighbor process R, On the other hand, suppose P executes A7, vol.3

P. If, =. Minid, and . Id, Otherwise, by Invariant 2, there is some process Q such that P.minid = Q.id. If P does not execute Action A7 during the step, we are done, since the invariant holds at ?. Otherwise Pick R.minid = Q.id and P.minlevel = R.minlevel + w(P, R), Property, vol.3

R. , W. , and Q. Id, We prove the invariant by contradiction. Suppose R.minid < Q.id < P.minid. By Invariant 3, R.minlevel > w(R, Q). It follows, by Invariant 1c, By Properties, vol.2, issue.3

, Since Invariant 4 holds at configuration ?, R must execute Action A7 during the step, and R.minid = S.id at configuration ? for some process S. MinLevel(R) = R.minhilevel at ? because R is enabled to execute A7. That value is equal to the value of R.minlevel at ? ? , which is greater than w(P, R)

S. Suppose, &. Id->-p.minid, and . Id, By Invariant 5 at ?, MinId(R, d) = S.id, while MinId(R, d) ? Q.id by definition of MinId, contradiction

P. Pick-p-such-that, &. P. Minid, (. , and ). Id-=-p,

, Since d was chosen to be minimum

R. If, R. Minid->-q.id, (. , and Q. ,

R. Suppose, R. Minid->-q.id, (. , and Q. , Then, by Property 1, and since Invariant 5 holds at R, Q.id ? MinId(R, w(R, Q) ? MinId(R, minhilevel) ? 1) = R.minid, contradiction

, Lemma 7 Benchmark B5 is closed, and if Benchmark B4 holds, then Benchmark B5 will hold within O(nk) additional rounds. Proof: We omit the proof of Lemma 7 since it is similar to the proof of Lemma 6

, Proof: P.isclusterhead is only changed when P executes Action A14. Once Benchmark B5 holds, by Lemma 5, P will execute A14 within O(nk) rounds. At each such execution, P.isclusterhead will be set to the correct value, Lemma 8 Benchmark B6 is closed, and will hold within O(nk) rounds after Benchmark B5 holds

, Proof: We first note that, after B6 holds, Cluster(P ) will execute at least once during every round. Claim: For any 0 ? d ? k, within d + 1 rounds after Benchmark B6 holds: (a) P.dist ? min {Dist(P ), Lemma 9 Benchmark B7 is closed, and will hold within k + 1 rounds after Benchmark B6 holds

, We prove the claim by induction on d. First, note that P.dist ? 0 by definition, which implies that Dist_F (P ) > 0 if ¬P

, Suppose d > 0. If Dist(P ) ? d, then after d rounds, by the inductive hypothesis, either P is a clusterhead or Dist(P ) = min {Q.dist + w(P, Q) : Q ? N P }, and we are done. If Dist(P ) > d

, Theorem 1 Starting from an arbitrary configuration, Weighted-Clustering stabilizes within O(nk) rounds

A. D. Amis, R. Prakash, T. H. Vuong, and D. T. Huynh, Max-min d-cluster formation in wireless ad hoc networks, IEEE INFOCOM, pp.32-41, 2000.

E. Caron and F. Desprez, Diet: A scalable toolbox to build network enabled servers on the grid, International Journal of High Performance Computing Applications, vol.20, issue.3, pp.335-352, 2006.
URL : https://hal.archives-ouvertes.fr/hal-01429861

A. K. Datta, L. L. Larmore, and P. Vemula, Self-stabilizing leader election in optimal space, 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2008.

A. K. Datta, L. L. Larmore, and P. Vemula, A self-stabilizing O(k)-time kclustering algorithm, Computer Journal, 2008.

E. W. Dijkstra, Self-stabilizing systems in spite of distributed control, Commun. ACM, vol.17, issue.11, pp.643-644, 1974.

S. Dolev, Self-stabilization, 2000.
URL : https://hal.archives-ouvertes.fr/inria-00627780

S. Dolev, A. Israeli, and S. Moran, Uniform dynamic self-stabilizing leader election, IEEE Trans. Parallel Distrib. Syst, vol.8, issue.4, pp.424-440, 1997.

Y. Fernandess and D. Malkhi, K-clustering in wireless ad hoc networks, ACM Workshop on Principles of Mobile Computing POMC 2002, pp.31-37, 2002.

M. G. Gouda and N. J. Multari, Stabilizing communication protocols, IEEE Trans. Comput, vol.40, issue.4, pp.448-458, 1991.

M. A. Spohn and J. J. Garcia-luna-aceves, Bounded-distance multi-clusterhead formation in wireless ad hoc networks, Ad Hoc Networks, vol.5, pp.504-530, 2004.

A. Yarkhan, J. Dongarra, and K. Seymour, Grid-Based Problem Solving Environments: IFIP TC2/WG 2.5 Working Conference on Grid-Based Problem Solving Environments, pp.215-226, 2006.