Name
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 initial three-token configuration the configuration in which the tokens are placed equidistantly on the ring. Our result strengthens a corollary of a theorem of McIver and Morgan (Inf. Process Lett. 94(2): 79–84, 2005), which states that the expected stabilization time is minimized by the equidistant configuration. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00165-012-0228-5 | Formal Asp. Comput. |
Keywords | Field | DocType |
expected stabilization time,initial three-token configuration,process lett,initial configuration,equidistant configuration,arbitrary n,token ring,synchronous randomized protocol,arbitrary timeout | Equidistant,Discrete mathematics,Combinatorics,Computer science,Algorithm,Token ring,Timeout,Corollary,Probabilistic automaton | Journal |
Volume | Issue | ISSN |
24 | 4-6 | 1433-299X |
Citations | PageRank | References |
3 | 0.46 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan Kiefer | 1 | 345 | 36.87 |
| Andrzej S. Murawski | 2 | 324 | 32.93 |
| Joël Ouaknine | 3 | 1481 | 99.25 |
| Björn Wachter | 4 | 326 | 20.09 |
| James Worrell | 5 | 1040 | 81.17 |