Bounds on Herman's algorithm

DOI10.1016/J.TCS.2014.07.023MaRDI QIDQ401316zbMATH OpenOpenAlexFDO

Authors John Haslegrave

Publication date 26 August 2014

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

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

zbMATH Keywords

Herman's algorithmprobabilistic self-stabilizationrandomized algorithms

Mathematics Subject Classification ID

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

Abstract: Herman's self-stabilisation algorithm allows a ring of $N$ processors having any odd number of tokens to reach a stable state where exactly one token remains. McIver and Morgan conjecture that the expected time taken for stabilisation is maximised when there are three equally-spaced tokens. We prove exact results on a related cost function, and obtain a bound on expected time which is very close to the conjectured bound.

Recommendations

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

Cites work

• An elementary proof that Herman's ring is \(\Theta (N^{2})\)
• Coupling and self-stabilization
• On stabilization in Herman's algorithm
• On the expected time for Herman's probabilistic self-stabilizing algorithm
• Probabilistic self-stabilization
• Probability with Martingales
• Self-stabilization
• Self-stabilizing systems in spite of distributed control
• Three tokens in Herman's algorithm

Cited in

(10)

• 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
• A tighter bound for the self-stabilization time in Herman's algorithm
• On stabilization in Herman's algorithm
• A nearly optimal upper bound for the self-stabilization time in Herman's algorithm
• Proving the Herman-protocol conjecture
• Computing and Combinatorics
• A nearly optimal upper bound for the self-stabilization time in Herman's algorithm
• Faster algorithms for computing Hong's bound on absolute positiveness

This page was built for publication: Bounds on Herman's algorithm

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