Self-stabilizing PIF algorithm in arbitrary rooted networks

被引：14

作者：

Cournier, A ^{[1
]}

Datta, AK ^{[1
]}

Petit, F ^{[1
]}

Villain, V ^{[1
]}

机构：

[1] Univ Picardie Jules Verne, LaRIA, F-80025 Amiens, France

来源：

21ST INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS, PROCEEDINGS | 2001年

关键词：

fault-tolerance; propagation of information with feedback; reset; self-stabilization; snapshot; wave algorithms;

D O I：

10.1109/ICDSC.2001.918937

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present a deterministic distributed Propagation of information with Feedback (PIF) protocol in arbitrary rooted networks. The proposed algorithm does not use a pre-constructed spanning tree. The protocol is self-stabilizing, meaning that starting from an arbitrary state (in response to an arbitrary perturbation modifying the memory state), it is guaranteed to behave according to its specification. Every PIF wave initiated by the root inherently creates a tree in the graph. So, the tree is dynamically created according to the progress of the PIF wave. This allows our PIF algorithm to take advantage of the relative speed of different components of the network. The proposed algorithm can be easily used to implement any self-stabilizing system which requires a (self-stabilizing) wave protocol running on an arbitrary network.

引用

页码：91 / 98

页数：8

共 21 条

[1] AFEK Y, 1991, LECT NOTES COMPUT SC, V486, P15
[2] Self-stabilization with Global Rooted Synchronizers
Alima, LO
Beauquier, J
Datta, AK
Tixeuil, S
[J]. 18TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS, PROCEEDINGS, 1998, : 102 - 109
[3] DISTRIBUTED RESET
ARORA, A
GOUDA, M
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (09) : 1026 - 1038
[4] AWERBUCH B, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P268, DOI 10.1109/SFCS.1991.185378
[5] AWERBUCH B, 1993, STOC93 P 25 ANN ACM, P652
[6] AWERBUCH B, 1991, FOCS91 P 31 ANN IEEE, P258
[7] Bui A., 1999, SIROCCO 6. Proceedings of the 6th International Colloquium on Structural Information and Communication Complexity, P32
[8] Space optimal PIF algorithm: Self-stabilized with no extra space
Bui, A
Datta, AK
Petit, F
Villain, V
[J]. 1999 IEEE INTERNATIONAL PERFORMANCE, COMPUTING AND COMMUNICATIONS CONFERENCE, 1999, : 20 - 26
[9] State-optimal snap-stabilizing PIF in tree networks
Bui, A
Datta, AK
Petit, F
Villain, V
[J]. 19TH IEEE INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS - WORKSHOP ON SELF-STABILIZING SYSTEMS, PROCEEDINGS, 1999, : 78 - 85
[10] DISTRIBUTED SNAPSHOTS - DETERMINING GLOBAL STATES OF DISTRIBUTED SYSTEMS
CHANDY, KM
LAMPORT, L
[J]. ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1985, 3 (01): : 63 - 75

← 1 2 3 →