Proving the Herman-protocol conjecture

DOI10.4230/LIPICS.ICALP.2016.104MaRDI QIDQ4598245zbMATH OpenFDO

Authors Maria Bruna, Radu Grigore, Stefan Kiefer, Joël Ouaknine, James Worrell

Publication date 19 December 2017

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

zbMATH Keywords

expected timeLyapunov functionrandomized protocolsself-stabilization

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Bounds on Herman's algorithm
• On stabilization in Herman's algorithm
• Three tokens in Herman's algorithm
• On the expected time for Herman's probabilistic self-stabilizing algorithm
• An elementary proof that Herman's ring is \(\Theta (N^{2})\)

Cited in

(9)

• An elementary proof that Herman's ring is \(\Theta (N^{2})\)
• Probabilistic verification of Herman's self-stabilisation algorithm
• Three tokens in Herman's algorithm
• Synthesizing optimal bias in randomized self-stabilization
• On stabilization in Herman's algorithm
• A nearly optimal upper bound for the self-stabilization time in Herman's algorithm
• scientific article; zbMATH DE number 4082597 (Why is no real title available?)
• Bounds on Herman's algorithm
• A nearly optimal upper bound for the self-stabilization time in Herman's algorithm

This page was built for publication: Proving the Herman-protocol conjecture

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