A highly safe self-stabilizing mutual exclusion algorithm

被引:11
作者
Yen, IL
机构
[1] Department of Computer Science, A-714 Wells Hall, Michigan State University, East Lansing
基金
美国国家科学基金会;
关键词
self-stabilizing systems; mutual exclusion; fault tolerance; distributed computing;
D O I
10.1016/0020-0190(96)00026-9
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Conventional self-stabilizing algorithms cannot be used for safety-critical systems due to the period of vulnerability that exists after a transient failure occurs till the system stabilizes. In this paper, we consider a highly safe self-stabilizing system where the vulnerability problem is tackled. The design principles we use to achieve this goal include sobriety test and processor specialization. Sobriety test is used to prevent the system from performing incorrect actions when the system state is faulty. Specialization disables individual processors from making faulty moves. We have developed a self-stabilizing mutual exclusion algorithm that guarantees mutual exclusion with a very high probability even in the presence of failures.
引用
收藏
页码:301 / 305
页数:5
相关论文
共 8 条
[1]  
ARORA A, 1990, P 2 IEEE S PAR DISTR, P288
[2]   SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL [J].
DIJKSTRA, EW .
COMMUNICATIONS OF THE ACM, 1974, 17 (11) :643-644
[3]  
DIJKSTRA EW, 1973, EWD 306 SOLUTION CYC
[4]  
GHOSH S, 1991, 3 IEEE S PAR DISTR S
[5]   STABILIZING COMMUNICATION PROTOCOLS [J].
GOUDA, MG ;
MULTARI, NJ .
IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (04) :448-458
[6]  
RIVEST RL, 1978, COMMUN ACM, V21, P120, DOI [10.1145/359340.359342, 10.1145/357980.358017]
[7]   SELF-STABILIZATION [J].
SCHNEIDER, M .
COMPUTING SURVEYS, 1993, 25 (01) :45-67
[8]   A SELF-ADJUSTING ALGORITHM FOR BYZANTINE AGREEMENT [J].
ZHAO, Y ;
BASTANI, FB .
DISTRIBUTED COMPUTING, 1992, 5 (04) :219-226