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

ISCAS OpenIR

	A nearly optimal upper bound for the self-stabilization time in Herman's algorithm
	Feng, Yuan (1); Zhang, Lijun (3)
	2014
会议名称	25th International Conference on Concurrency Theory, CONCUR 2014
页码	342-356
会议日期	September 2, 2014 - September 5, 2014
会议地点	Rome, Italy
收录类别	EI
出版地	Springer Verlag
ISSN	3029743
ISBN	9783662445839
部门归属	(1) Centre for Quantum Computation and Intelligent Systems, University of Technology Sydney, Australia; (2) AMSS-UTS Joint Research Laboratory for Quantum Computation, Chinese Academy of Sciences, Beijing, China; (3) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
摘要	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 self-stabilization time. McIver and Morgan have conjectured the optimal upper bound being 0.148N ², where N denotes the number of processors. We present an elementary proof showing a bound of 0.167N², a sharp improvement compared with the best known bound 0.521N². 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 of it. © 2014 Springer-Verlag.; 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 self-stabilization time. McIver and Morgan have conjectured the optimal upper bound being 0.148N ², where N denotes the number of processors. We present an elementary proof showing a bound of 0.167N², a sharp improvement compared with the best known bound 0.521N². 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 of it. © 2014 Springer-Verlag.
语种	英语
WOS记录号	WOS:000358780800002
引用统计
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16592
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Feng, Yuan ,Zhang, Lijun . A nearly optimal upper bound for the self-stabilization time in Herman's algorithm[C]. Springer Verlag,2014:342-356.