[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Exploring Worst Cases of Self-stabilizing Algorithms Using Simulations

  • Conference paper
  • First Online:
Stabilization, Safety, and Security of Distributed Systems (SSS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14310))

  • 251 Accesses

Abstract

Self-stabilization qualifies the ability of a distributed system to recover after transient failures. sasa is a simulator of self-stabilizing algorithms written in the atomic-state model, the most commonly used model in the self-stabilizing area.

A simulator is, in particular, useful to study the time complexity of algorithms. For example, one can experimentally check whether existing theoretical bounds are correct or tight. Simulations are also useful to get insights when no bound is known.

In this paper, we use sasa to investigate the worst cases of various well-known self-stabilization algorithms. We apply classical optimization methods (such as local search, branch and bound, Tabu list) on the two sources of non-determinism: the choice of initial configuration and the scheduling of process activations (daemon). We propose a methodology based on heuristics and an open-source tool to find tighter worst-case lower bounds.

This work has been partially funded by the ANR project SkyData (ANR-22-CE25-0008-01).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 55.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 69.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The (classical) weakly fair daemon, for example, does not provide such a guarantee.

  2. 2.

    Even using the optimizations of Sect. 2.

References

  1. Adamek, J., Farina, G., Nesterenko, M., Tixeuil, S.: Evaluating and optimizing stabilizing dining philosophers. J. Parallel Distrib. Comput. 109, 63–74 (2017)

    Article  Google Scholar 

  2. Adamek, J., Nesterenko, M., Tixeuil, S.: Evaluating practical tolerance properties of stabilizing programs through simulation: the case of propagation of information with feedback. In: Richa, A.W., Scheideler, C. (eds.) SSS 2012. LNCS, vol. 7596, pp. 126–132. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33536-5_13

    Chapter  Google Scholar 

  3. Aflaki, S., Bonakdarpour, B., Tixeuil, S.: Automated analysis of impact of scheduling on performance of self-stabilizing protocols. In: Pelc, A., Schwarzmann, A.A. (eds.) SSS 2015. LNCS, vol. 9212, pp. 156–170. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21741-3_11

    Chapter  MATH  Google Scholar 

  4. Altisen, K., Corbineau, P., Devismes, S.: A framework for certified self-stabilization. Log. Methods Comput. Sci. 13(4) (2017)

    Google Scholar 

  5. Altisen, K., Corbineau, P., Devismes, S.: Certification of an exact worst-case self-stabilization time. Theor. Comput. Sci. 941, 262–277 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  6. Altisen, K., Cournier, A., Devismes, S., Durand, A., Petit, F.: Self-stabilizing leader election in polynomial steps. Inf. Comput. 254(Part 3), 330–366 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  7. Altisen, K., Devismes, S., Dubois, S., Petit, F.: Introduction to Distributed Self-Stabilizing Algorithms, Volume 8 of Synthesis Lectures on Distributed Computing Theory (2019)

    Google Scholar 

  8. Altisen, K., Devismes, S., Durand, A.: Acyclic strategy for silent self-stabilization in spanning forests. In: Izumi, T., Kuznetsov, P. (eds.) SSS 2018. LNCS, vol. 11201, pp. 186–202. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03232-6_13

    Chapter  MATH  Google Scholar 

  9. Altisen, K., Devismes, S., Jahier, E.: SASA: a SimulAtor of self-stabilizing algorithms. Comput. J. 66(4), 796–814 (2022)

    Article  MathSciNet  Google Scholar 

  10. Couvreur, J.-M., Francez, N., Gouda, M.G.: Asynchronous unison (extended abstract). In: ICDCS 1992 (1992)

    Google Scholar 

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

    Article  MATH  Google Scholar 

  12. Datta, A.K., Devismes, S., Heurtefeux, K., Larmore, L.L., Rivierre, Y.: Competitive self-stabilizing k-clustering. Theor. Comput. Sci. 626, 110–133 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  13. Datta, A.K., Larmore, L.L., Vemula, P.: Self-stabilizing leader election in optimal space under an arbitrary scheduler. Theor. Comput. Sci. 412(40), 5541–5561 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  14. Devismes, S., Johnen, C.: Silent self-stabilizing BFS tree algorithms revisited. J. Parallel Distrib. Comput. 97, 11–23 (2016)

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

  16. Dolev, S., Gouda, M.G., Schneider, M.: Memory requirements for silent stabilization. Acta Informatica 36(6), 447–462 (1999). https://doi.org/10.1007/s002360050180

    Article  MathSciNet  MATH  Google Scholar 

  17. Evcimen, H.T., Arapoglu, O., Dagdeviren, O.: SELFSIM: a discrete-event simulator for distributed self-stabilizing algorithms. In: International Conference on Artificial Intelligence and Data Processing (2018)

    Google Scholar 

  18. Flatebo, M., Datta, A.K.: Simulation of self-stabilizing algorithms in distributed systems. In: Annual Simulation Symposium (1992)

    Google Scholar 

  19. Christian, G., Nicolas, H., David, I., Colette, J.: Disconnected components detection and rooted shortest-path tree maintenance in networks. In: Felber, P., Garg, V. (eds.) SSS 2014. LNCS, vol. 8756, pp. 120–134. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11764-5_9

    Chapter  Google Scholar 

  20. Glacet, C., Hanusse, N., Ilcinkas, D., Johnen, C.: Disconnected components detection and rooted shortest-path tree maintenance in networks. J. Parallel Distrib. Comput. 132, 299–309 (2019)

    Article  Google Scholar 

  21. Har-Tal, O.: A simulator for self-stabilizing distributed algorithms (2000). https://www.cs.bgu.ac.il/~projects/projects/odedha/html/

  22. Huang, S.-T., Chen, N.-S.: A self-stabilizing algorithm for constructing breadth-first trees. Inf. Process. Lett. 41(2), 109–117 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kosowski, A., Kuszner, Ł: A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Waśniewski, J. (eds.) PPAM 2005. LNCS, vol. 3911, pp. 75–82. Springer, Heidelberg (2006). https://doi.org/10.1007/11752578_10

    Chapter  Google Scholar 

  24. Müllner, N., Dhama, A., Theel, O.E.: Derivation of fault tolerance measures of self-stabilizing algorithms by simulation. In: Annual Simulation Symposium (2008)

    Google Scholar 

  25. Trivedi, K.S.: Probability and Statistics with Reliability, Queuing and Computer Science Applications, 2nd edn. Wiley, Hoboken (2002)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Univ. Grenoble Alpes, CNRS, Grenoble INP, VERIMAG, Grenoble, France

    Erwan Jahier & Karine Altisen

  2. Université de Picardie Jules Verne, MIS, Amiens, France

    Stéphane Devismes

Authors
  1. Erwan Jahier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Karine Altisen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stéphane Devismes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Erwan Jahier .

Editor information

Editors and Affiliations

  1. Ben-Gurion University of the Negev, Be'er-Sheva, Israel

    Shlomi Dolev

  2. New Jersey Institute of Technology, Newark, NJ, USA

    Baruch Schieber

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Jahier, E., Altisen, K., Devismes, S. (2023). Exploring Worst Cases of Self-stabilizing Algorithms Using Simulations. In: Dolev, S., Schieber, B. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2023. Lecture Notes in Computer Science, vol 14310. Springer, Cham. https://doi.org/10.1007/978-3-031-44274-2_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-44274-2_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-44273-5

  • Online ISBN: 978-3-031-44274-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation