Early consensus in an asynchronous system with a weak failure detector

被引:91
作者
Schiper, A
机构
[1] Ecl. Polytech. Federale, Département d'Informatique
关键词
asynchronous system; unreliable failure detector; consensus; latency;
D O I
10.1007/s004460050032
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Consensus is one of the most fundamental problems in the context of fault-tolerant distributed computing. The problem consists, given a set Omega of processes having each an initial value vi, in deciding among Omega on a common value v. In 1985, Fischer, Lynch and Paterson proved that the consensus problem is not solvable in an asynchronous system subject to a single process crash. In 1991, Chandra and Toueg showed that, by augmenting the asynchronous system model with a well defined unreliable failure detector, consensus becomes solvable. They also give an algorithm that solves consensus using the lozenge l failure detector. In this paper we propose a new consensus algorithm, also using the lozenge l failure detector, that is more efficient than the Chandra-Toueg consensus algorithm. We measure efficiency by introducing the notion of latency degree, which defines the minimal number of communication steps needed to solve consensus. The Chandra-Toueg algorithm has a latency degree of 3 (it requires at least three communication steps), whereas our early consensus algorithm requires only two communication steps (latency degree of 7). We believe that this is an interesting result, which adds to our current understanding of the cost of consensus algorithms based on lozenge l.
引用
收藏
页码:149 / 157
页数:9
相关论文
共 11 条
[1]  
Bernstein P.A., 1987, Concurrency Control and Recovery in Database Systems
[2]   Unreliable failure detectors for reliable distributed systems [J].
Chandra, TD ;
Toueg, S .
JOURNAL OF THE ACM, 1996, 43 (02) :225-267
[3]   The weakest failure detector for solving Consensus [J].
Chandra, TD ;
Hadzilacos, V ;
Toueg, S .
JOURNAL OF THE ACM, 1996, 43 (04) :685-722
[4]  
CHOR B, 1989, ADV COMPUTING RES, V5, P443
[5]   ON THE MINIMAL SYNCHRONISM NEEDED FOR DISTRIBUTED CONSENSUS [J].
DOLEV, D ;
DWORK, C ;
STOCKMEYER, L .
JOURNAL OF THE ACM, 1987, 34 (01) :77-97
[6]   CONSENSUS IN THE PRESENCE OF PARTIAL SYNCHRONY [J].
DWORK, C ;
LYNCH, N ;
STOCKMEYER, L .
JOURNAL OF THE ACM, 1988, 35 (02) :288-323
[7]   IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS [J].
FISCHER, MJ ;
LYNCH, NA ;
PATERSON, MS .
JOURNAL OF THE ACM, 1985, 32 (02) :374-382
[8]  
GUERRAOUI R, 1995, LNCS, V972, P87
[9]  
Hadzilacos V., 1993, Fault-Tolerant Broadcasts and Related Problems, P97, DOI DOI 10.5555/302430.302435
[10]   TIME, CLOCKS, AND ORDERING OF EVENTS IN A DISTRIBUTED SYSTEM [J].
LAMPORT, L .
COMMUNICATIONS OF THE ACM, 1978, 21 (07) :558-565