Publisher DOI: | 10.1007/978-3-030-24922-9_21 | Title: | Making randomized algorithms self-stabilizing | Language: | English | Authors: | Turau, Volker | Issue Date: | Jul-2019 | Publisher: | Springer | Source: | Lecture Notes in Computer Science 11639 LNCS: 309-324 (2019-06) | Abstract (english): | It is well known that the areas of self-stabilizing algorithms and local algorithms are closely related. Using program transformation techniques local algorithms can be made self-stabilizing, albeit an increase in run-time or memory consumption is often unavoidable. Unfortunately these techniques often do not apply to randomized algorithms, which are often simpler and faster than deterministic algorithms. In this paper we demonstrate that it is possible to take over ideas from randomized distributed algorithms to self-stabilizing algorithms. We present two simple self-stabilizing algorithms computing a maximal independent set and a maximal matching and terminate in the synchronous model with high probability in O(log n) rounds. The algorithms outperform all existing algorithms that do not rely on unique identifiers. |
Conference: | 26th International Colloquium on Structural Information and Communication Complexity SIROCCO 2019 | URI: | http://hdl.handle.net/11420/3097 | ISBN: | 978-3-030-24922-9 978-3-030-24921-2 |
ISSN: | 0302-9743 | Institute: | Telematik E-17 | Document Type: | Chapter/Article (Proceedings) | Project: | Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken | Part of Series: | Lecture notes in computer science | Volume number: | 11639 LNCS |
Appears in Collections: | Publications without fulltext |
Show full item record
Add Files to Item
Note about this record
Cite this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.