ELECTION IN ASYNCHRONOUS COMPLETE NETWORKS WITH INTERMITTENT LINK FAILURES

被引:28
作者
ABUAMARA, H
LOKRE, J
机构
[1] Department of Electrical Engineering, Texas A&M University, College Station
关键词
ELECTION; INTERMITTENT LINK FAILURE; COMPLETE NETWORKS; ASYNCHRONOUS NETWORKS; DISTRIBUTED ALGORITHMS; MESSAGE COMPLEXITY;
D O I
10.1109/12.293257
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We consider the problem of fault-tolerant leader election in asynchronous complete (fully-connected) distributed networks. The processors are reliable, but some of the communication channels may fail intermittently before or during the execution of the algorithm. Channel failures are undetectable due to the asynchronous nature of the network. Let n be the number of processors in the network and f be the maximum number of faulty channels incident on each processor, where f less-than-or-equal-to [n-1/2]. Our algorithm uses at most O(n2 + nf2) messages to elect a unique leader of the network. Each message consists of at most O(log \T\) bits, where \T\ is the cardinality of the set of processor identifiers. AH previous algorithms either tolerated only benign failures such as fail-stop failures, assumed that the network is synchronous, tolerated only a small number of failures, or assumed that the faults are detectable. Our algorithm is the first election algorithm that is designed specifically for asynchronous intermittently faulty complete networks in which up to n/2 [n-1/2] channels may be faulty, where each processor is adjacent to no more than [n-1/2] faulty channels, and where the faults are undetectable.
引用
收藏
页码:778 / 788
页数:11
相关论文
共 21 条
[1]   FAULT-TOLERANT DISTRIBUTED ALGORITHM FOR ELECTION IN COMPLETE NETWORKS [J].
ABUAMARA, HH .
IEEE TRANSACTIONS ON COMPUTERS, 1988, 37 (04) :449-453
[2]  
Afek Y., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P358, DOI 10.1109/SFCS.1987.7
[3]  
AFEK Y, 1988, 7TH P ACM S PRINC DI, P131
[4]  
AFEK Y, 1985, 4TH ACM S PRINC DIST, P186
[5]  
Alsberg P. A., 1976, 2nd International Conference on Software Engineering, P562
[6]  
Awerbuch B., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P206, DOI 10.1109/SFCS.1988.21938
[7]  
BARYEHUDA R, 1988, J ALGORITHM, V9, P569
[8]  
BARYEHUDA R, 1987, 4TH P S THEOR ASP CO, P432
[9]  
CIMET IA, 1986, ACM SIGCOMM S COMM A, P358
[10]  
Gafni Eli, 1985, P 4 ANN ACM S PRINC, P175, DOI 10.1145/323596