×

Topological self-stabilization with name-passing process calculi. (English) Zbl 1392.68314

Desharnais, Josée (ed.) et al., 27th international conference on concurrency theory, CONCUR 2016, Québec City, Canada, August 23–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-017-0). LIPIcs – Leibniz International Proceedings in Informatics 59, Article 19, 15 p. (2016).
Summary: 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.
For the entire collection see [Zbl 1351.68014].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI