Abstract
We study the expected self-stabilization time of Hermanʼs algorithm. For N processors the lower bound is 427N2 (0.148N2), and an upper bound of 0.64N2 is presented in Kiefer et al. (2011) [4]. In this paper we give a tighter upper bound 0.521N2. © 2013 Published by Elsevier B.V.
Original language | English |
---|---|
Journal | Information Processing Letters |
Volume | 113 |
Issue number | 13 |
Pages (from-to) | 486-488 |
ISSN | 0020-0190 |
DOIs | |
Publication status | Published - 2013 |
Keywords
- Formal methods
- Self-stabilization algorithm
- Hermanʼs algorithm
- Markov chains