Abstract
The clustering problem consists of partitioning network nodes into groups called clusters. Each cluster has a single clusterhead that acts as local coordinator of cluster.
A technique for designing solutions that tolerate transient faults is selfstabilization. Self-stabilizing protocols are attractive because they need not be initialized: they converge from any configuration to a legitimate one. Also, they are adaptive to topological changes. If the current configuration is inconsistent with the network topology, the self-stabilizing protocol eventually converges to a legitimate configuration. Nevertheless, self-stabilizing protocols do not guarantee any property during the convergence period. In addition, the convergence time may be proportional to the size of the network; particularly, in weight-based clustering protocols. In order to overcome these drawbacks, we are interested to the robust stabilization. Robust stabilization guarantees that from an illegitimate configuration, the system reaches quickly a safe configuration, in which the safety property is satisfied. The safety property has to be defined such that the system performs correctly its task in a safe configuration. During the convergence to a legitimate configuration, the safety property stays always verified.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Kamei, S., Kakugawa, H.: A self-stabilizing approximation for the minimum connected dominating set with safe convergence. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 496–511. Springer, Heidelberg (2008)
Johnen, C., Nguyen, L.H.: Robust self-stabilizing weight-based clustering algorithm. Theoretical Computer Science 410(6-7), 581–594 (2009)
Chatterjee, M., Das, S.K., Turgut, D.: WCA: A weighted clustering algorithm for mobile ad hoc networks. Journal of Cluster Computing 5(2), 193–204 (2002)
Johnen, C., Nguyen, L.H.: Self-stabilizing construction of bounded size clusters. In: ISPA 2008, pp. 43–50 (2008)
Tomoyuki, O., Shinji, I., Yoshiaki, K., Kenji, I., Kaori, M.: An adaptive maintenance of hierarchical structure in ad hoc networks and its evaluation. In: ICDCS 2002, pp. 7–13 (2002)
Johnen, C., Mekhaldi, F.: Robust self-stabilizing construction of bounded size weight-based clusters. Technical Report No 1518, LRI (2009), http://www.lri.fr/~bibli/Rapports-internes/2009/RR1518.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnen, C., Mekhaldi, F. (2009). Brief Announcement: Robust Self-stabilizing Construction of Bounded Size Weight-Based Clusters. In: Guerraoui, R., Petit, F. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2009. Lecture Notes in Computer Science, vol 5873. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-05118-0_61
Download citation
DOI: https://doi.org/10.1007/978-3-642-05118-0_61
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-05117-3
Online ISBN: 978-3-642-05118-0
eBook Packages: Computer ScienceComputer Science (R0)