Output details
11 - Computer Science and Informatics
University of Oxford
Return to search
Output 0 of 0 in the submission
Output title
On stabilization in Herman's algorithm
Type
E - Conference contribution
Name of conference/published proceedings
(ICALP ’11) Proceedings of the 38th International Conference on Automata, Languages and Programming
Volume number
6756 LNCS
Issue number
PART 2
First page of article
466
ISSN of proceedings
0302-9743
Year of publication
2011
Number of additional authors
4
Additional information
<10>
Herman’s algorithm is a synchronous randomized protocol for achieving self-stabilization in a token ring. Based on Herman's original paper and subsequent work by Dolev there is an O(N^2) bound on the expected stabilization time on a ring of size N. Assuming that errors arise from the corruption of some number of bits fixed independently of N, we show that the expected time to stabilization is O(N). This reveals a hitherto unknown and highly desirable property of Herman’s algorithm: it recovers quickly from bounded errors.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
1
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
