An elementary proof that Herman's ring is \(\Theta (N^{2})\)

DOI10.1016/j.ipl.2004.12.013zbMath1182.68358OpenAlexW2150056141MaRDI QIDQ1041727

Carroll Morgan, Annabelle McIver

Publication date: 4 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.12.013

zbMATH Keywords

analysis of algorithmsrandomized algorithmsabstractionnondeterminismprobabilistic variant

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (7)

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 ⋮ Preface

Cites Work

• Probabilistic self-stabilization
• Termination of Probabilistic Concurrent Program
• Self-stabilizing token circulation on asynchronous uniform unidirectional rings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An elementary proof that Herman's ring is \(\Theta (N^{2})\)