Institutional Repository
| A nearly optimal upper bound for the self-stabilization time in Herman's algorithm | |
| Feng, Yuan (1); Zhang, Lijun (3) | |
| 2014 | |
| Conference Name | 25th International Conference on Concurrency Theory, CONCUR 2014 |
| Pages | 342-356 |
| Conference Date | September 2, 2014 - September 5, 2014 |
| Conference Place | Rome, Italy |
| Indexed Type | EI |
| Publish Place | Springer Verlag |
| 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 |
| 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.; 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 | 英语 |
| WOS ID | WOS:000358780800002 |
| Citation statistics | |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16592 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment