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

Yuan Feng; Lijun Zhang

doi:10.1016/j.ipl.2013.04.006

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

Yuan Feng, Lijun Zhang

Research output: Contribution to journal › Article › Academic › peer-review

5 Citations (Scopus)

Abstract

We study the expected self-stabilization time of Herman's algorithm. For N processors the lower bound is 427N^2 (0.148N^2), and an upper bound of 0.64N^2 is presented in Kiefer et al. (2011) [4]. In this paper we give a tighter upper bound 0.521N^2.

Original language	English
Pages (from-to)	486-488
Number of pages	3
Journal	Information processing letters
Volume	113
Issue number	13
DOIs	https://doi.org/10.1016/j.ipl.2013.04.006
Publication status	Published - Jul 2013

Keywords

EC Grant Agreement nr.: FP7/2007-2013
EC Grant Agreement nr.: FP7/318003

Access to Document

10.1016/j.ipl.2013.04.006

Cite this

@article{4ef9ba41d7744d73b45fb5a42ea30bef,

title = "A tighter bound for the self-stabilization time in Herman's algorithm",

abstract = "We study the expected self-stabilization time of Herman's algorithm. For N processors the lower bound is 427N^2 (0.148N^2), and an upper bound of 0.64N^2 is presented in Kiefer et al. (2011) [4]. In this paper we give a tighter upper bound 0.521N^2.",

keywords = "EC Grant Agreement nr.: FP7/2007-2013, EC Grant Agreement nr.: FP7/318003",

author = "Yuan Feng and Lijun Zhang",

note = "eemcs-eprint-24116 ",

year = "2013",

month = jul,

doi = "10.1016/j.ipl.2013.04.006",

language = "English",

volume = "113",

pages = "486--488",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "13",

}

TY - JOUR

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

AU - Feng, Yuan

AU - Zhang, Lijun

N1 - eemcs-eprint-24116

PY - 2013/7

Y1 - 2013/7

N2 - We study the expected self-stabilization time of Herman's algorithm. For N processors the lower bound is 427N^2 (0.148N^2), and an upper bound of 0.64N^2 is presented in Kiefer et al. (2011) [4]. In this paper we give a tighter upper bound 0.521N^2.

AB - We study the expected self-stabilization time of Herman's algorithm. For N processors the lower bound is 427N^2 (0.148N^2), and an upper bound of 0.64N^2 is presented in Kiefer et al. (2011) [4]. In this paper we give a tighter upper bound 0.521N^2.

KW - EC Grant Agreement nr.: FP7/2007-2013

KW - EC Grant Agreement nr.: FP7/318003

U2 - 10.1016/j.ipl.2013.04.006

DO - 10.1016/j.ipl.2013.04.006

M3 - Article

VL - 113

SP - 486

EP - 488

JO - Information processing letters

JF - Information processing letters

SN - 0020-0190

IS - 13

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this