A nearly optimal upper bound for the self-stabilization time in Herman's algorithm

doi:10.1007/s00446-015-0241-z

CSpace

	A nearly optimal upper bound for the self-stabilization time in Herman's algorithm
	Feng, Yuan 1,2; Zhang, Lijun 3
	2015-08-01
发表期刊	DISTRIBUTED COMPUTING
ISSN	0178-2770
卷号	28 期号:4 页码:233-244
摘要	Self-stabilization algorithms are very important in designing fault-tolerant distributed systems. In this paper we consider Herman's self-stabilization algorithm and study its expected termination time. McIver and Morgan have conjectured the optimal upper bound being , where denotes the number of processors. We present an elementary proof showing a bound of , a sharp improvement compared with the best known bound . Our proof is inspired by McIver and Morgan's approach: we find a nearly optimal closed form of the expected stabilization time for any initial configuration, and apply the Lagrange multipliers method to give an upper bound.
关键词	Herman's algorithm Self-stabilization Lagrange multipliers method
DOI	10.1007/s00446-015-0241-z
语种	英语
资助项目	Australian Research Council[DP130102764] ; National Natural Science Foundation of China[61428208] ; National Natural Science Foundation of China[61472473] ; National Natural Science Foundation of China[61472412] ; National Natural Science Foundation of China[61361136002] ; CAS/SAFEA International Partnership Program for Creative Research Teams
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000358780800002
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/20440
专题	中国科学院数学与系统科学研究院
通讯作者	Zhang, Lijun
作者单位	1.Univ Technol Sydney, Ctr Quantum Computat & Intelligent Syst, Sydney, NSW 2007, Australia 2.Chinese Acad Sci, AMSS UTS Joint Res Lab Quantum Computat, Beijing, Peoples R China 3.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Feng, Yuan,Zhang, Lijun. A nearly optimal upper bound for the self-stabilization time in Herman's algorithm[J]. DISTRIBUTED COMPUTING,2015,28(4):233-244.
APA	Feng, Yuan,&Zhang, Lijun.(2015).A nearly optimal upper bound for the self-stabilization time in Herman's algorithm.DISTRIBUTED COMPUTING,28(4),233-244.
MLA	Feng, Yuan,et al."A nearly optimal upper bound for the self-stabilization time in Herman's algorithm".DISTRIBUTED COMPUTING 28.4(2015):233-244.