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


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Journal:
FORMAL ASPECTS OF COMPUTING
Volume:
24
Issue:
4-6
Pages:
671-678
Publication date:
2012-07-01
DOI:
EISSN:
1433-299X
ISSN:
0934-5043
Source identifiers:
345358
Language:
English
Pubs id:
pubs:345358
UUID:
uuid:c5fa30e7-fd68-431f-bfc1-7cb8dc329014
Local pid:
pubs:345358
Deposit date:
2013-11-17

Terms of use


Views and Downloads






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

TO TOP