Probabilistic self-stabilization

DOI10.1016/0020-0190(90)90107-9zbMath0697.68027OpenAlexW1992996044MaRDI QIDQ911752

Ted Herman

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90107-9

zbMATH Keywords

probabilistic algorithmsdistributed computingself-stabilizationuniform rings

Mathematics Subject Classification ID

Distributed systems (68M14) Theory of operating systems (68N25) Theory of software (68N99)

Related Items

Synthesizing optimal bias in randomized self-stabilization ⋮ Model checking finite-horizon Markov chains with probabilistic inference ⋮ Randomized uniform self-stabilizing mutual exclusion ⋮ Analysis of Distributed Token Circulation Algorithm with Faulty Random Number Generator ⋮ EVENTUAL DETERMINISM: USING PROBABILISTIC MEANS TO ACHIEVE DETERMINISTIC ENDS ⋮ Parametric Markov chains: PCTL complexity and fraction-free Gaussian elimination ⋮ Weak vs. Self vs. Probabilistic Stabilization ⋮ Bounds on Herman's algorithm ⋮ Deterministic, constant space, self-stabilizing leader election on uniform rings ⋮ Parameter synthesis in Markov models: a gentle survey ⋮ Probabilistic verification of Herman's self-stabilisation algorithm ⋮ Three tokens in Herman's algorithm ⋮ Coupling and self-stabilization ⋮ A tighter bound for the self-stabilization time in Herman's algorithm ⋮ Torus orientation ⋮ Are Parametric Markov Chains Monotonic? ⋮ Binary self-stabilization in distributed systems ⋮ Fair Termination for Parameterized Probabilistic Concurrent Systems ⋮ Probabilistic communicating processes ⋮ A nearly optimal upper bound for the self-stabilization time in Herman's algorithm ⋮ RANDOMIZED SELF-STABILIZING LEADER ELECTION IN PREFERENCE-BASED ANONYMOUS TREES ⋮ On Stabilization in Herman’s Algorithm ⋮ A self-stabilizing algorithm for maximal matching ⋮ Self-stabilization: Randomness to reduce space ⋮ Randomization adaptive self-stabilization ⋮ Automated Analysis of Impact of Scheduling on Performance of Self-stabilizing Protocols ⋮ Inductive synthesis for probabilistic programs reaches new horizons ⋮ Model Checking Parameterised Multi-token Systems via the Composition Method ⋮ Self-stabilizing ring orientation using constant space ⋮ Unnamed Item ⋮ An elementary proof that Herman's ring is \(\Theta (N^{2})\) ⋮ A SELF-STABILIZING ALGORITHM FOR FINDING ARTICULATION POINTS ⋮ On probabilistic snap-stabilization ⋮ On the expected time for Herman's probabilistic self-stabilizing algorithm

Cites Work

• Uniform self-stabilizing ring orientation
• Self-stabilizing systems in spite of distributed control
• Token systems that self-stabilize