TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. Making randomized algorithms self-stabilizing
 
Options

Making randomized algorithms self-stabilizing

Publikationstyp
Conference Paper
Date Issued
2019-07
Sprache
English
Author(s)
Turau, Volker  
Institut
Telematik E-17  
TORE-URI
http://hdl.handle.net/11420/3097
First published in
Lecture notes in computer science  
Number in series
11639 LNCS
Start Page
309
End Page
324
Citation
Lecture Notes in Computer Science 11639 LNCS: 309-324 (2019-06)
Contribution to Conference
26th International Colloquium on Structural Information and Communication Complexity SIROCCO 2019  
Publisher DOI
10.1007/978-3-030-24922-9_21
Scopus ID
2-s2.0-85069859129
Publisher
Springer
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.
DDC Class
004: Informatik
Funding(s)
Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken  
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback