A tighter bound for the self-stabilization time in Hermanʼs algorithm

Yuan Feng, Lijun Zhang

Research output: Contribution to journalJournal articleResearchpeer-review

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 languageEnglish
JournalInformation Processing Letters
Volume113
Issue number13
Pages (from-to)486-488
ISSN0020-0190
DOIs
Publication statusPublished - 2013

Keywords

  • Formal methods
  • Self-stabilization algorithm
  • Hermanʼs algorithm
  • Markov chains

Fingerprint

Dive into the research topics of 'A tighter bound for the self-stabilization time in Hermanʼs algorithm'. Together they form a unique fingerprint.

Cite this