research-article

Self-stabilizing synchronous unison in directed networks

Authors:

Karine Altisen,

Alain Cournier,

Geoffrey Defalque,

Stéphane DevismesAuthors Info & Claims

Volume 1001, Issue C

https://doi.org/10.1016/j.tcs.2024.114577

Published: 17 July 2024 Publication History

Abstract

Self-stabilization is a general paradigm that characterizes the ability of a distributed system to recover from transient faults. Since its introduction by Dijkstra in 1974, self-stabilization has been successfully applied to efficiently solve many networking tasks. However, most of the literature focuses on bidirectional networks. Now, in today's networks such as WSNs, some communication channels may be one-way only. Considering such network topologies, a.k.a. directed graphs, makes self-stabilization more complicated, and sometimes even impossible. In this paper, we investigate the gap in terms of requirements and efficiency when considering a directed graph instead of an undirected one as network topology for a self-stabilizing algorithm. Our case study is a variant of a synchronous unison algorithm proposed by Arora et al.; the synchronous unison being a clock synchronization problem.

Highlights

•

We address self-stabilization of dynamic problems in anonymous directed networks.

•

We propose a topology-related necessary condition to solve synchronous unison in directed networks.

•

We present a simple self-stabilizing synchronous unison algorithm for directed networks.

•

We study conditions under which the proposed algorithm is self-stabilizing, and at what cost.

References

[1]

E.W. Dijkstra, Self-stabilizing systems in spite of distributed control, Commun. ACM 17 (11) (1974) 643–644.

Digital Library

[2]

K. Altisen, S. Devismes, S. Dubois, F. Petit, Introduction to Distributed Self-Stabilizing Algorithms, Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, 2019.

[3]

S. Katz, K.J. Perry, Self-stabilizing extensions for message-passing systems, Distrib. Comput. 7 (1) (1993) 17–26.

Digital Library

[4]

Z. Collin, S. Dolev, Self-stabilizing depth-first search, Inf. Process. Lett. 49 (6) (1994) 297–301.

Digital Library

[5]

A. Cournier, S. Devismes, V. Villain, A snap-stabilizing DFS with a lower space requirement, in: SSS'05, 2005, pp. 33–47.

[6]

A. Cournier, S. Devismes, V. Villain, Snap-stabilizing PIF and useless computations, in: ICPADS'06, 2006, pp. 39–48.

[7]

A.K. Datta, L.L. Larmore, P. Vemula, An o(n)-time self-stabilizing leader election algorithm, J. Parallel Distrib. Comput. 71 (11) (2011) 1532–1544.

Digital Library

[8]

S. Bernard, S. Devismes, M. Gradinariu Potop-Butucaru, S. Tixeuil, Optimal deterministic self-stabilizing vertex coloring in unidirectional anonymous networks, in: IPDPS'09, Roma, Italia, 2009, pp. 1–8.

[9]

A.J. Mayer, R. Ostrovsky, M. Yung, Self-stabilizing algorithms for synchronous unidirectional rings, in: SODA'96, 1996, pp. 564–573.

[10]

S. Huang, T. Liu, Self-stabilizing 2^m-clock for unidirectional rings of odd size, Distrib. Comput. 12 (1) (1999) 41–46.

[11]

H. Kakugawa, M. Yamashita, Uniform and self-stabilizing fair mutual exclusion on unidirectional rings under unfair distributed daemon, JPDC 62 (5) (2002) 885–898.

[12]

D. Alstein, J. Hoepman, B. Olivier, P. van der Put, Self-stabilizing mutual exclusion on directed graphs (extended abstract), in: Computing Science in the Netherlands, CSN'94, Utrecht, the Netherlands, November 21-22, 1994, Centrum voor Wiskunde en Informatica, 1994, pp. 42–53.

[13]

Y. Afek, A. Bremler-Barr, Self-stabilizing unidirectional network algorithms by power supply, Chic. J. Theor. Comput. Sci. (1998) 1998.

[14]

S. Dolev, E. Schiller, Self-stabilizing group communication in directed networks, Acta Inform. 40 (9) (2004) 609–636,.

Digital Library

[15]

S. Delaët, B. Ducourthial, S. Tixeuil, Self-stabilization with r-operators revisited, J. Aerosp. Comput. Inf. Commun. 3 (10) (2006) 498–514.

[16]

S. Tixeuil, Vers l'auto-stabilisation des systèmes à grande échelle, Habilitation à diriger des recherches, Université Paris Sud - Paris XI, May 2006.

[17]

B.A. Coan, D. Dolev, C. Dwork, L.J. Stockmeyer, The distributed firing squad problem, SIAM J. Comput. 18 (5) (1989) 990–1012,.

Digital Library

[18]

M. Raynal, J. Hélary, Synchronization and Control of Distributed Systems and Programs, Wiley Series in Parallel Computing, Wiley, 1990.

[19]

K. Altisen, S. Devismes, On probabilistic snap-stabilization, Theor. Comput. Sci. 688 (2017) 49–76.

[20]

A. Arora, S. Dolev, M.G. Gouda, Maintaining digital clocks in step, Parallel Process. Lett. 1 (1991) 11–18.

[21]

S. Even, S. Rajsbaum, Unison in distributed networks, in: R.M. Capocelli (Ed.), Sequences, Springer New York, New York, NY, 1990, pp. 479–487.

[22]

M.G. Gouda, T. Herman, Stabilizing unison, Inf. Process. Lett. 35 (4) (1990) 171–175.

[23]

C. Johnen, L.O. Alima, A.K. Datta, S. Tixeuil, Optimal snap-stabilizing neighborhood synchronizer in tree networks, Parallel Process. Lett. 12 (3–4) (2002) 327–340.

[24]

J.-M. Couvreur, N. Francez, M.G. Gouda, Asynchronous unison (extended abstract), in: 12th International Conference on Distributed Computing Systems, (ICDCS'92), 1992, pp. 486–493.

[25]

B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-Shamir, G. Varghese, Time optimal self-stabilizing synchronization, in: 25th Annual Symposium on Theory of Computing, (STOC'93), 1993, pp. 652–661.

[26]

C. Boulinier, F. Petit, V. Villain, When graph theory helps self-stabilization, in: 23rd Annual Symposium on Principles of Distributed Computing, (PODC'04), 2004, pp. 150–159.

[27]

Y. Emek, E. Keren, A thin self-stabilizing asynchronous unison algorithm with applications to fault tolerant biological networks, in: 40th Annual Symposium on Principles of Distributed Computing, (PODC'23), 2021, pp. 93–102.

[28]

C. Boulinier, L'unisson. (the unison), Ph.D. thesis University of Picardie Jules Verne, Amiens, France, 2007, https://tel.archives-ouvertes.fr/tel-01511431.

[29]

S. Devismes, C. Johnen, Self-stabilizing distributed cooperative reset, in: 39th International Conference on Distributed Computing Systems, (ICDCS'19), 2019, pp. 379–389.

[30]

J. Couvreur, N. Francez, M.G. Gouda, Asynchronous unison (extended abstract), in: ICDCS'92, 1992, pp. 486–493.

Recommendations

Self-stabilizing Synchronous Unison in Directed Networks
ICDCN '23: Proceedings of the 24th International Conference on Distributed Computing and Networking

Self-stabilization is a general paradigm that characterizes the ability of a distributed system to recover from transient faults. Since its introduction by Dijkstra in 1974, self-stabilization has been successfully applied to efficiently solve many ...
On Self-stabilizing Leader Election in Directed Networks
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing

We consider identified directed networks where processes know an upper bound on the maximum ancestor distance. Under these settings, we study the conditions on the network topology allowing the self-stabilization of two fundamental problems: the leader ...
Self-stabilizing group communication in directed networks

This paper presents the first self-stabilizing group membership service, multicast service, and resource allocation service for directed networks. The first group communication algorithm is based on a token circulation over a virtual ring. The second ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 1001, Issue C

Jun 2024

111 pages

Issue’s Table of Contents

The Author(s).

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 17 July 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

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

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents