Document Open Access Logo

Topological Self-Stabilization with Name-Passing Process Calculi

Authors Christina Rickmann, Christoph Wagner, Uwe Nestmann, Stefan Schmid

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2016.19.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Christina Rickmann
Christoph Wagner
Uwe Nestmann
Stefan Schmid

Cite As Get BibTex

Christina Rickmann, Christoph Wagner, Uwe Nestmann, and Stefan Schmid. Topological Self-Stabilization with Name-Passing Process Calculi. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CONCUR.2016.19

Abstract

Topological self-stabilization is the ability of a distributed system to have its nodes themselves establish a meaningful overlay network. Independent from the initial network topology, it converges to the desired topology via forwarding, inserting, and deleting links to neighboring nodes.

We adapt a linearization algorithm, originally designed for a shared memory model, to asynchronous message-passing. We use an extended localized pi-calculus to model the algorithm and to formally prove its essential self-stabilization properties: closure and weak convergence for every arbitrary initial configuration, and strong convergence for restricted cases.

Subject Classification

Keywords
  • Distributed Algorithms
  • Fault Tolerance
  • Topological Self-Stabilization
  • Linearization
  • Process Calculi

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P.-D. Brodmann. Distributability of Asynchronous Process Calculi. Master’s thesis, Technische Universität Berlin, Germany, October 2014. Google Scholar
  2. E. W. Dijkstra. Self-stabilizing Systems in Spite of Distributed Control. Communications of the ACM, 17(11):643-644, November 1974. Google Scholar
  3. S. Dolev. Self-Stabilization. The MIT Press, 2000. Google Scholar
  4. D. Gall et al. A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization. Theory of Computing Systems, 55(1):110-135, 2014. Google Scholar
  5. F. C. Gärtner. Fundamentals of Fault-tolerant Distributed Computing in Asynchronous Environments. ACM Comput. Surv., 31(1):1-26, March 1999. Google Scholar
  6. M. G. Gouda. The Triumph and Tribulation of System Stabilization. In Proc. of the 9th International WDAG, WDAG '95, pages 1-18, 1995. Google Scholar
  7. N. A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., 1996. Google Scholar
  8. M. Merro and D. Sangiorgi. On Asynchrony in Name-Passing Calculi. In Proc. of ICALP, volume 1443 of LNCS, pages 856-867. Springer, 1998. Google Scholar
  9. R. Milner. communicating and mobile systems: the pi-calculus. Cambridge UP, 1999. Google Scholar
  10. C. Rickmann. Topological Self-Stabilization with Name-Passing Process Calculi. Master’s thesis, Technische Universität Berlin, Germany, October 2015. arxiv.org/abs/1604.04197. Google Scholar
  11. D. Sangiorgi and D. Walker. The π-calculus: A Theory of Mobile Processes. Cambridge UP, 2001. Google Scholar
  12. C. Wagner and U. Nestmann. States in Process Calculi. In Proc. of EXPRESS/SOS, volume 160 of EPTCS, pages 48-62, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact