On the expected time for Herman's probabilistic self-stabilizing algorithm

DOI10.1016/j.tcs.2005.05.022zbMath1086.68020OpenAlexW1967465461MaRDI QIDQ817822

Toshio Nakata

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.05.022

zbMATH Keywords

random walkHerman's algorithmprobabilistic self-stabilizationcoalescing time

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Distributed systems (68M14)

Related Items (6)

Bounds on Herman's algorithm ⋮ Probabilistic verification of Herman's self-stabilisation algorithm ⋮ Three tokens in Herman's algorithm ⋮ A tighter bound for the self-stabilization time in Herman's algorithm ⋮ A nearly optimal upper bound for the self-stabilization time in Herman's algorithm ⋮ On Stabilization in Herman’s Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic self-stabilization
• Distributed probabilistic polling and applications to proportionate agreement
• Collisions Among Random Walks on a Graph
• Convergence of the Iterated Prisoner's Dilemma Game
• Maximum hitting time for random walks on graphs
• A simple coupling of renewal processes
• Self-stabilizing systems in spite of distributed control
• A Simple Proof of 1 + 1 2 2 + 1 3 2 + ⋯ = π 2 6 and Related Identities
• Coalescing times for IID random variables with applications to population biology
• A more rapidly mixing Markov chain for graph colorings
• Coupling and Self-stabilization

This page was built for publication: On the expected time for Herman's probabilistic self-stabilizing algorithm