LSV 15th anniversary, February 6–7, 2012, Cachan
Herman's Algorithm: A Brief Survey and Some Recent Results
Talk by
Joël Ouaknine
(University of Oxford)
Slides
Abstract
Herman's algorithm is a well-studied, two-decades-old synchronous randomised
protocol for achieving distributed self-stabilization (or leader election) in a
token ring consisting of N processes. The interaction of tokens however makes
the dynamics of the protocol fairly difficult to analyse. In particular, the
exact worst-case expected stabilisation time of this protocol remains an open
problem dating back to the inception of the algorithm, despite a series of
partial results, advances and conjectures over the last twenty years.
I will present Herman's algorithm, review some of the existing body of work on
it, and present some recent results which improve on the best-known upper bounds
for expected stabilisation time. I will also briefly discuss some connections to
other scientific areas such statistical mechanics, epidemiology, and Brownian
motion.
This is joint work with Stefan Kiefer, Andrzej Murawski, James Worrell, and
Lijun Zhang.
