Journal article icon

Journal article

Three tokens in Herman's algorithm

Abstract:

Herman's algorithm is a synchronous randomized protocol for achieving self-stabilization in a token ring consisting of N processes. The interaction of tokens makes the dynamics of the protocol very difficult to analyze. In this paper we study the distribution of the time to stabilization, assuming that there are three tokens in the initial configuration.We show for arbitrary N and for an arbitrary timeout t that the probability of stabilization within time t is minimized by choosing as the in...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1007/s00165-012-0228-5

Authors


Murawski, AS More by this author
Ouaknine, J More by this author
Wachter, B More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Journal:
FORMAL ASPECTS OF COMPUTING
Volume:
24
Issue:
4-6
Pages:
671-678
Publication date:
2012-07-05
DOI:
EISSN:
1433-299X
ISSN:
0934-5043
URN:
uuid:c5fa30e7-fd68-431f-bfc1-7cb8dc329014
Source identifiers:
345358
Local pid:
pubs:345358
Language:
English

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP