Randomization adaptive self-stabilization

DOI10.1007/S00236-010-0119-2zbMATH Open1206.68361arXiv0810.4440OpenAlexW1490515484MaRDI QIDQ707595FDOQ707595

Authors: Shlomi Dolev, Nir Tzachar 

Publication date: 8 October 2010

Published in: Acta Informatica (Search for Journal in Brave)

Abstract: We present a scheme to convert self-stabilizing algorithms that use randomization during and following convergence to self-stabilizing algorithms that use randomization only during convergence. We thus reduce the number of random bits from an infinite number to a bounded number. The scheme is applicable to the cases in which there exits a local predicate for each node, such that global consistency is implied by the union of the local predicates. We demonstrate our scheme over the token circulation algorithm of Herman and the recent constant time Byzantine self-stabilizing clock synchronization algorithm by Ben-Or, Dolev and Hoch. The application of our scheme results in the first constant time Byzantine self-stabilizing clock synchronization algorithm that uses a bounded number of random bits.

Full work available at URL: https://arxiv.org/abs/0810.4440

Recommendations

• Stochastic self-stabilization
• Probabilistic self-stabilization
• Synthesizing optimal bias in randomized self-stabilization
• scientific article; zbMATH DE number 2015368
• Making randomized algorithms self-stabilizing
• Low communication self-stabilization through randomization
• Adaptive stabilization of nonlinear stochastic systems
• Robust adaptive systems and self stabilization

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Cites Work

• Self-stabilizing extensions for message-passing systems
• Self-stabilization
• Probabilistic self-stabilization
• Local stabilizer
• Fast self-stabilizing Byzantine tolerant digital clock synchronization
• Self-stabilizing clock synchronization in the presence of Byzantine faults
• Self-stabilization over unreliable communication media
• Resource Bounds for Self-Stabilizing Message-Driven Protocols
• EVENTUAL DETERMINISM: USING PROBABILISTIC MEANS TO ACHIEVE DETERMINISTIC ENDS

Cited In (8)

• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• When graph theory helps self-stabilization
• Synthesizing optimal bias in randomized self-stabilization
• Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave
• Self-stabilization: Randomness to reduce space
• Low communication self-stabilization through randomization
• Stochastic self-stabilization
• Anonymous Daemon Conversion in Self-stabilizing Algorithms by Randomization in Constant Space

This page was built for publication: Randomization adaptive self-stabilization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q707595)