A weakest failure detector-based asynchronous consensus protocol for f < n

被引：3
作者：
Friedman, R [1 ]
Mostefaoui, A [1 ]
Raynal, M [1 ]
机构：
[1] Univ Rennes 1, IRISA, F-35042 Rennes, France
来源：
INFORMATION PROCESSING LETTERS | 2004年 / 90卷 / 01期
关键词：
asynchronous distributed system; consensus; distributed algorithms; fault tolerance; process crash; unreliable failure detector;
D O I：
10.1016/j.ipl.2004.01.001
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
P-f x lozengeS has been shown to be the weakest realistic failure detector class needed to solve the consensus problem in an asynchronous distributed system prone to f < n process crashes in which communication is by message-passing. However, the only protocol that is known to meet this bound is based on three layers of protocol construction, and is therefore not efficient. This paper presents a surprisingly simple and very efficient direct message-passing implementation of a Pf x lozengeS-based consensus protocol, and proves its correctness. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：39 / 46
页数：8
相关论文
共 13 条
[1]  
ATTIYA H, 1988, DISTRIB COMPUT, P451
[2]  
Ben-Or Michael, 1983, Proceedings of the second ACM Symposium on Principles of Distributed Computing (PODC), P27
[3]   Unreliable failure detectors for reliable distributed systems [J].
Chandra, TD ;
Toueg, S .
JOURNAL OF THE ACM, 1996, 43 (02) :225-267
[4]   The weakest failure detector for solving Consensus [J].
Chandra, TD ;
Hadzilacos, V ;
Toueg, S .
JOURNAL OF THE ACM, 1996, 43 (04) :685-722
[5]  
CHU F, 1998, INFORMATION PROCESSI, V76, P293
[6]  
Delporte-Gallet C, 2002, LECT NOTES COMPUT SC, V2508, P237
[7]   A realistic look at failure detectors [J].
Delporte-Gallet, C ;
Fauconnier, H ;
Guerraoui, R .
INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS, 2002, :345-353
[8]   IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS [J].
FISCHER, MJ ;
LYNCH, NA ;
PATERSON, MS .
JOURNAL OF THE ACM, 1985, 32 (02) :374-382
[9]  
FRIEDMAN R, 2003, WEAKEST FAILURE DETE, V1
[10]   A versatile family of consensus Protocols based on Chandra-Toueg's unreliable failure detectors [J].
Hurfin, M ;
Mostéfaoui, A ;
Raynal, M .
IEEE TRANSACTIONS ON COMPUTERS, 2002, 51 (04) :395-408
12