The Weakest Failure Detector for Solving k-Set Agreement

被引：5
|
作者：
Gafni, Eli [1 ]
Kuznetsov, Petr [1 ]
机构：
[1] TU Berlin, Deutsch Telekom Labs, D-10587 Berlin, Germany
来源：
PODC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING | 2009年
关键词：
k-set agreement; synchrony assumptions; failure detectors; BG-simulation;
D O I：
10.1145/1582716.1582735
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A failure detector is a distributed oracle that provides processes in a distributed system with hints about failures. The notion of a weakest failure detector captures the exact amount of synchrony needed for solving a given distributed computing problem. In this paper, we determine the weakest failure detector for solving k-set agreement among n processes (n > k) using reads and writes in shared memory, regardless of the assumptions on when and where failures might occur. This failure detector is derived directly from the impossibility of wait-free k+1-process k-set agreement. Our approach can be viewed as an extension of the asynchronous BG-simulation technique to partially synchronous systems.
引用
收藏
页码：83 / 91
页数：9
相关论文
共 35 条
  • [1] On the road to the weakest failure detector for k-set agreement in message-passing systems
    Bonnet, Francois
    Raynal, Michel
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (33) : 4273 - 4284
  • [2] Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks
    Jeanneau, Elise
    Rieutord, Thibault
    Arantes, Luciana
    Sens, Pierre
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2017, 28 (05) : 1484 - 1499
  • [3] Anti-Ω: The Weakest Failure Detector for Set Agreement
    Zielinski, Piotr
    PODC'08: PROCEEDINGS OF THE 27TH ANNUAL ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2008, : 55 - 64
  • [4] Anti-Ω: the weakest failure detector for set agreement
    Zielinski, Piotr
    DISTRIBUTED COMPUTING, 2010, 22 (5-6) : 335 - 348
  • [5] Anti-Ω: the weakest failure detector for set agreement
    Piotr Zieliński
    Distributed Computing, 2010, 22 : 335 - 348
  • [6] Partition Approach to Failure Detectors for k-Set Agreement
    Chen, Wei
    Zhang, Jialin
    Chen, Yu
    Liu, Xuezheng
    PODC'07: PROCEEDINGS OF THE 26TH ANNUAL ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2007, : 306 - 307
  • [7] The Weakest Failure Detector for Message Passing Set-Agreement
    Delporte-Gallet, Carole
    Fauconnier, Hugues
    Guerraoui, Rachid
    Tielmann, Andreas
    DISTRIBUTED COMPUTING, PROCEEDINGS, 2008, 5218 : 109 - +
  • [8] The Generalized Loneliness Detector and Weak System Models for k-Set Agreement
    Biely, Martin
    Robinson, Peter
    Schmid, Ulrich
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2014, 25 (04) : 1078 - 1088
  • [9] Tight bounds for k-set agreement
    Chaudhuri, S
    Herlihy, M
    Lynch, NA
    Tuttle, MR
    JOURNAL OF THE ACM, 2000, 47 (05) : 912 - 943
  • [10] Weakening failure detectors for k-set agreement via the partition approach
    Chen, Wei
    Zhang, Jialin
    Chen, Yu
    Liu, Xuezheng
    Distributed Computing, Proceedings, 2007, 4731 : 123 - 138
1234