中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 会议论文
Title:
A nearly optimal upper bound for the self-stabilization time in Herman's algorithm
Author: Feng, Yuan (1) ; Zhang, Lijun (3)
Conference Name: 25th International Conference on Concurrency Theory, CONCUR 2014
Conference Date: September 2, 2014 - September 5, 2014
Issued Date: 2014
Conference Place: Rome, Italy
Publish Place: Springer Verlag
Indexed Type: EI
ISSN: 3029743
ISBN: 9783662445839
Department: (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
Abstract: 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 2, where N denotes the number of processors. We present an elementary proof showing a bound of 0.167N2, a sharp improvement compared with the best known bound 0.521N2. 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.
English Abstract: 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 2, where N denotes the number of processors. We present an elementary proof showing a bound of 0.167N2, a sharp improvement compared with the best known bound 0.521N2. 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.
Language: 英语
Citation statistics:
Content Type: 会议论文
URI: http://ir.iscas.ac.cn/handle/311060/16592
Appears in Collections:软件所图书馆_会议论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
Feng, Yuan ,Zhang, Lijun . A nearly optimal upper bound for the self-stabilization time in Herman's algorithm[C]. 见:25th International Conference on Concurrency Theory, CONCUR 2014. Rome, Italy. September 2, 2014 - September 5, 2014.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Feng, Yuan (1)]'s Articles
[Zhang, Lijun (3)]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Feng, Yuan (1)]‘s Articles
[Zhang, Lijun (3)]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2020  中国科学院软件研究所 - Feedback
Powered by CSpace