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
    Chandra, TD
    Toueg, S
    [J]. JOURNAL OF THE ACM, 1996, 43 (02) : 225 - 267
  • [4] The weakest failure detector for solving Consensus
    Chandra, TD
    Hadzilacos, V
    Toueg, S
    [J]. 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
    Delporte-Gallet, C
    Fauconnier, H
    Guerraoui, R
    [J]. INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS, 2002, : 345 - 353
  • [8] IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS
    FISCHER, MJ
    LYNCH, NA
    PATERSON, MS
    [J]. 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
    Hurfin, M
    Mostéfaoui, A
    Raynal, M
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2002, 51 (04) : 395 - 408
12