Phase clocks for transient fault repair

被引：23

作者：

Herman, T ^{[1
]}

机构：

[1] Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2000年 / 11卷 / 10期

基金：

美国国家科学基金会;

关键词：

distributed algorithms; fault tolerance; fault containment; synchronizers; self stabilization; time adaptive;

D O I：

10.1109/71.888644

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Phase clocks are synchronization tools that implement a form of logical time in distributed systems. For systems tolerating transient faults by self-repair of damaged data, phase clocks can enable reasoning about the progress of distributed repair procedures. This paper presents a phase clock algorithm suited to the model of transient memory faults in asynchronous systems with read/write registers. The algorithm is self-stabilizing and guarantees accuracy of phase crocks within O(li) time following an initial state that is k-faulty. Composition theorems show how the algorithm can be used for the timing of distributed procedures that repair system outputs.

引用

页码：1048 / 1057

页数：10

共 18 条

[1] Local stabilizer [J].

Afek, Y ;

Dolev, S .

PROCEEDINGS OF THE FIFTH ISRAELI SYMPOSIUM ON THEORY OF COMPUTING AND SYSTEMS, 1997, :74-84

[2]

Arora A., 1991, Parallel Processing Letters, V1, P11, DOI 10.1142/S0129626491000161

[3]

ATTIYA H, 1998, DISTRIBUTED COMPUTIN

[4] COMPLEXITY OF NETWORK SYNCHRONIZATION [J].

AWERBUCH, B .

JOURNAL OF THE ACM, 1985, 32 (04) :804-823

[5]

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

[6]

COUVREUR JM, 1992, INT CON DISTR COMP S, P486, DOI 10.1109/ICDCS.1992.235005

[7] Parallel composition of stabilizing algorithms [J].

Dolev, S ;

Herman, T .

19TH IEEE INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS - WORKSHOP ON SELF-STABILIZING SYSTEMS, PROCEEDINGS, 1999, :25-32

[8]

Dolev S., 2000, Self-Stabilization

[9] An exercise in fault-containment: Self-stabilizing leader election [J].

Ghosh, S ;

Gupta, A .

INFORMATION PROCESSING LETTERS, 1996, 59 (05) :281-288

[10]

Ghosh S., 1996, Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, P45, DOI 10.1145/248052.248057

← 1 2 →