research-article

A Self-Stabilizing Minimal k-Grouping Algorithm

Authors:

Ajoy K. Datta,

Laurence L. Larmore,

Toshimitsu Masuzawa,

Yuichi SudoAuthors Info & Claims

ICDCN '17: Proceedings of the 18th International Conference on Distributed Computing and Networking

Article No.: 3, Pages 1 - 10

https://doi.org/10.1145/3007748.3007772

Published: 05 January 2017 Publication History

Get Access

Abstract

We consider the minimal k-grouping problem: given a graph G = (V, E) and a constant k, partition G into subgraphs of diameter no greater than k, such that the union of any two subgraphs has diameter greater than k. We give a silent self-stabilizing asynchronous distributed algorithm for this problem in the composite atomicity model of computation, assuming the network has unique process identifiers. Our algorithm works under the weakly-fair daemon. The time complexity (i.e. the number of rounds to reach a legitimate configuration) of our algorithm is O (nD/k) where n is the number of processes in the network and D is the diameter of the network. The space complexity of each process is O((n + nfalse) log n) where nfalse is the number of false identifiers, i.e., identifiers that do not match the identifier of any process, but which are stored in the local memory of at least one process at the initial configuration. Our algorithm guarantees that the number of groups is at most 2n/k + 1 after convergence. We also give a novel composition technique to concatenate a silent algorithm repeatedly, which we call loop composition.

References

[1]

A. D Amis, R. Prakash, T. HP. Vuong, and D. T. Huynh. Max-min d-cluster formation in wireless ad hoc networks. In Proc. of INFOCOM 2000, volume 1, pages 32--41, 2000.

Crossref

Google Scholar

[2]

A. K. Datta, S. Gurumurthy, F. Petit, and V. Villain. Self-stabilizing network orientation algorithms in arbitrary rooted networks. In Proc. of ICDCS 2000, pages 576--583, 2000.

Crossref

Google Scholar

[3]

A. K. Datta, L. L. Larmore, S. Devismes, K. Heurtefeux, and Y. Rivierre. Competitive self-stabilizing k-clustering. In Proc. of ICDCS 2012, pages 476--485, 2012.

Digital Library

Google Scholar

[4]

A. K. Datta, L. L. Larmore, S. Devismes, K. Heurtefeux, and Y. Rivierre. Self-stabilizing small k-dominating sets. International Journal of Networking and Computing, 3(1):116--136, 2013.

Crossref

Google Scholar

[5]

A. K Datta, L. L Larmore, and P.l Vemula. An O(n)-time self-stabilizing leader election algorithm. Journal of Parallel and Distributed Computing, 71(11):1532--1544, 2011.

Digital Library

Google Scholar

[6]

J. S. Deogun, D. Kratsch, and G. Steiner. An approximation algorithm for clustering graphs with dominating diametral path. IPL, 61(3):121--127, 1997.

Digital Library

Google Scholar

[7]

EW Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the ACM, 17:643--644, 1974.

Digital Library

Google Scholar

[8]

S. Dolev. Self-stabilization. MIT press, 2000.

Google Scholar

[9]

S. Dolev and T. Herman. Parallel composition of stabilizing algorithms. In Proc. of WSS 1999, pages 25--32, 1999.

Crossref

Google Scholar

[10]

B. Ducourthial, S. Khalfallah, and F. Petit. Best-effort group service in dynamic networks. In Proc. of SPAA 2010, pages 233--242, 2010.

Digital Library

Google Scholar

[11]

Y. Fernandess and D. Malkhi. K-clustering in wireless ad hoc networks. In Proceedings of the second ACM international workshop on Principles of mobile computing, pages 31--37, 2002.

Digital Library

Google Scholar

[12]

T. R. Herman. Adaptivity through distributed convergence. PhD thesis, University of Texas at Austin, 1992.

Google Scholar

[13]

Y. Yamauchi, S. Kamei, F. Ooshita, Y. Katayama, H. Kakugawa, and T. Masuzawa. Hierarchical composition of self-stabilizing protocols preserving the fault-containment property. IEICE transactions on information and systems, 92(3):451--459, 2009.

Crossref

Google Scholar

[14]

Y. Yamauchi, S. Kamei, F. Ooshita, Y. Katayama, H. Kakugawa, and T. Masuzawa. Timer-based composition of fault-containing self-stabilizing protocols. Information Sciences, 180(10):1802--1816, 2010.

Digital Library

Google Scholar

Cited By

View all

Kakugawa HKamei SShibata MOoshita F(2023)A self-stabilizing distributed algorithm for the 1-MIS problem under the distance-3 model2023 Eleventh International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW60564.2023.00025(100-106)Online publication date: 27-Nov-2023
https://doi.org/10.1109/CANDARW60564.2023.00025
Maruyama SSudo YKamei SKakugawa H(2023)Self-stabilizing 2-minimal dominating set algorithms based on loop compositionTheoretical Computer Science10.1016/j.tcs.2023.114314(114314)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114314
Maruyama SSudo YKamei SKakugawa H(2022)A self-stabilizing 2-minimal dominating set algorithm based on loop composition in networks of girth at least 72022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00114(1140-1150)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00114
Show More Cited By

Recommendations

A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks

The maximum planarization problem is to find a spanning planar subgraph having the largest number of edges for a given graph. In this paper, we propose a self-stabilizing algorithm to solve this problem for complete bipartite networks. The proposed ...
Self-stabilizing algorithm for two disjoint minimal dominating sets
Abstract
We propose a new self stabilizing algorithm to compute two mutually disjoint minimal dominating sets in an arbitrary graph G with no isolates (this is always possible due to famous Ore's theorem in [1] that says “In a graph having no isolated ...
Highlights
- New self-stabilizing algorithm for two disjoint minimal dominating sets in a graph.
- An improvement by a factor of n over the best existing algorithm [2].
- Interleaving of two copies of an algorithm on mutually disjoint state ...
A self-stabilizing algorithm for optimally efficient sets in graphs

The efficiency of a set S@__ __V in a graph G=(V,E), is defined as @e(S)=|{v@__ __V-S:|N(v)@__ __S|=1}|; in other words, the efficiency of a set S equals the number of vertices in V-S that are adjacent to exactly one vertex in S. A set S is called ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICDCN '17: Proceedings of the 18th International Conference on Distributed Computing and Networking

January 2017

367 pages

ISBN:9781450348393

DOI:10.1145/3007748

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

IDRBT: IDRBT

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 January 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

ICDCN '17

ICDCN '17: 18th International Conference on Distributed Computing and Networking

January 5 - 7, 2017

Hyderabad, India

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
102
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kakugawa HKamei SShibata MOoshita F(2023)A self-stabilizing distributed algorithm for the 1-MIS problem under the distance-3 model2023 Eleventh International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW60564.2023.00025(100-106)Online publication date: 27-Nov-2023
https://doi.org/10.1109/CANDARW60564.2023.00025
Maruyama SSudo YKamei SKakugawa H(2023)Self-stabilizing 2-minimal dominating set algorithms based on loop compositionTheoretical Computer Science10.1016/j.tcs.2023.114314(114314)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114314
Maruyama SSudo YKamei SKakugawa H(2022)A self-stabilizing 2-minimal dominating set algorithm based on loop composition in networks of girth at least 72022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00114(1140-1150)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00114
Tanaka HSudo YKakugawa HMasuzawa TDatta A(2019)A Self-stabilizing 1-Maximal Independent Set AlgorithmStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-34992-9_27(338-353)Online publication date: 14-Nov-2019
https://doi.org/10.1007/978-3-030-34992-9_27
Sudo YDatta ALarmore LMasuzawa T(2018)Constant-Space Self-stabilizing Token Distribution in TreesStructural Information and Communication Complexity10.1007/978-3-030-01325-7_4(25-29)Online publication date: 31-Oct-2018
https://doi.org/10.1007/978-3-030-01325-7_4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks

Self-stabilizing algorithm for two disjoint minimal dominating sets

A self-stabilizing algorithm for optimally efficient sets in graphs