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.
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
Cites work
- EVENTUAL DETERMINISM: USING PROBABILISTIC MEANS TO ACHIEVE DETERMINISTIC ENDS
- Fast self-stabilizing Byzantine tolerant digital clock synchronization
- Local stabilizer
- Probabilistic self-stabilization
- Resource Bounds for Self-Stabilizing Message-Driven Protocols
- Self-stabilization
- Self-stabilization over unreliable communication media
- Self-stabilizing clock synchronization in the presence of Byzantine faults
- Self-stabilizing extensions for message-passing systems
Cited in
(8)- Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
- Synthesizing optimal bias in randomized self-stabilization
- When graph theory helps 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)
