The inherent price of indulgence

被引:15
作者
Dutta, P [1 ]
Guerraoui, R [1 ]
机构
[1] Ecole Polytech Fed Lausanne, Distributed Programming Lab, CH-1015 Lausanne, Switzerland
关键词
fault tolerance; distributed algorithms; consensus time complexity;
D O I
10.1007/s00446-005-0124-9
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
An indulgent algorithm is a distributed algorithm that tolerates asynchronous periods of the network when process crash detection is unreliable. This paper presents a tight bound on the time complexity of indulgent consensus algorithms. We consider a round-based eventually synchronous model, and we show that any t-resilient consensus algorithm in this model, requires at least t + 2 rounds for a global decision even in runs that are synchronous. We contrast our lower bound with the well-known t + 1 round tight bound on consensus in the synchronous model. We then prove the bound to be tight by exhibiting a new t-resilient consensus algorithm in the eventually synchronous model that reaches a global decision at round t + 2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we know of, which requires 2t + 2 rounds in synchronous runs. Our lower bound applies to round-based consensus algorithms with unreliable failure detectors such as lozenge P and lozenge S, and our matching algorithm can be adapted to such failure detectors.
引用
收藏
页码:85 / 98
页数:14
相关论文
共 14 条
  • [1] A simple bivalency proof that t-resilient consensus requires t+1 rounds
    Aguilera, MK
    Toueg, S
    [J]. INFORMATION PROCESSING LETTERS, 1999, 71 (3-4) : 155 - 158
  • [2] Unreliable failure detectors for reliable distributed systems
    Chandra, TD
    Toueg, S
    [J]. JOURNAL OF THE ACM, 1996, 43 (02) : 225 - 267
  • [3] Synchronous system and perfect failure detector: solvability and efficiency issues
    Charron-Bost, B
    Guerraoui, R
    Schiper, A
    [J]. DSN 2000: INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS, 2000, : 523 - 532
  • [4] CHARRONBOST B, 2000, 200028 SWISS FED I T
  • [5] DUTTA P, 2003, P 1M INT C DISTR COM
  • [6] CONSENSUS IN THE PRESENCE OF PARTIAL SYNCHRONY
    DWORK, C
    LYNCH, N
    STOCKMEYER, L
    [J]. JOURNAL OF THE ACM, 1988, 35 (02) : 288 - 323
  • [7] IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS
    FISCHER, MJ
    LYNCH, NA
    PATERSON, MS
    [J]. JOURNAL OF THE ACM, 1985, 32 (02) : 374 - 382
  • [8] Gafni E., 1998, Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, P143, DOI 10.1145/277697.277724
  • [9] Guerraoui R., 2000, Proceeding of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, P289, DOI 10.1145/343477.343630
  • [10] A simple and fast asynchronous consensus protocol based on a weak failure detector
    Hurfin, M
    Raynal, M
    [J]. DISTRIBUTED COMPUTING, 1999, 12 (04) : 209 - 223