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 |
| 会议日期 | September 2, 2014 - September 5, 2014 |
| 会议地点 | Rome, Italy |
| 页码 | 342-356 |
| 中文摘要 | 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. |
| 收录类别 | EI |
| 会议录出版地 | Springer Verlag |
| 语种 | 英语 |
| ISSN号 | 3029743 |
| ISBN号 | 9783662445839 |
| WOS记录号 | WOS:000358780800002 |
| 源URL | [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]. 见:25th International Conference on Concurrency Theory, CONCUR 2014. Rome, Italy. September 2, 2014 - September 5, 2014. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。