A space-efficient self-stabilizing algorithm for measuring the size of ring networks

被引：2

作者：

Lee, KC

Tzeng, CH

Huang, ST ^{[1
]}

机构：

[1] Natl Cent Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan

[2] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu, Taiwan

来源：

INFORMATION PROCESSING LETTERS | 2005年 / 94卷 / 03期

关键词：

distributed systems; self-stabilization; ring network; token circulation;

D O I：

10.1016/j.ipl.2005.01.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A self-stabilizing algorithm to measure the size of ring networks under synchronized distributed model was proposed. It was found that the maximum stabilization time was O(n3). It was observed that the system was semi-uniform and the communication links were unidirectional. It was also observed that each processor other than the roots cost five boolean variables, or 32 states only.

引用

页码：125 / 130

页数：6

共 9 条

[1]

Beauquier J., 1999, Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, P199, DOI 10.1145/301308.301358

[2]

Datta A. K., 2000, Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000, P465, DOI 10.1109/IPDPS.2000.846023

[3]

Dijkstra E. W, 1976, A Discipline of Programming

[4] SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL [J].