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 条
  • [21] On the Weakest Failure Detector Ever
    Guerraoui, Rachid
    Herlihy, Maurice
    Kouznetsov, Petr
    Lynch, Nancy
    Newport, Calvin
    PODC'07: PROCEEDINGS OF THE 26TH ANNUAL ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2007, : 235 - 243
  • [22] The weakest failure detector for eventual consistency
    Swan Dubois
    Rachid Guerraoui
    Petr Kuznetsov
    Franck Petit
    Pierre Sens
    Distributed Computing, 2019, 32 : 479 - 492
  • [23] The weakest failure detector for eventual consistency
    Dubois, Swan
    Guerraoui, Rachid
    Kuznetsov, Petr
    Petit, Franck
    Sens, Pierre
    DISTRIBUTED COMPUTING, 2019, 32 (06) : 479 - 492
  • [24] Brief Announcement: Gracefully Degrading Consensus and k-Set Agreement under Dynamic Link Failures
    Schwarz, Manfred
    Winkler, Kyrill
    Schmid, Ulrich
    Biely, Martin
    Robinson, Peter
    PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, : 341 - 343
  • [25] The Weakest Failure Detector for Eventual Consistency
    Dubois, Swan
    Guerraoui, Rachid
    Kuznetsov, Petr
    Petit, Franck
    Sens, Pierre
    PODC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2015, : 375 - 384
  • [26] Strongly terminating early-stopping k-set agreement in synchronous systems with general omission failures
    Parvedy, Philippe Raipin
    Raynal, Michel
    Travers, Cotentin
    STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDINGS, 2006, 4056 : 182 - 196
  • [27] Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures
    Parvedy, Philippe Raipin
    Raynal, Michel
    Travers, Corentin
    THEORY OF COMPUTING SYSTEMS, 2010, 47 (01) : 259 - 287
  • [28] Early-stopping k-set agreement in synchronous systems prone to any number of process crashes
    Parvedy, PR
    Raynal, M
    Travers, C
    PARALLEL COMPUTING TECHNOLOGIES, 2005, 3606 : 49 - 58
  • [29] The weakest failure detector to solve nonuniform consensus
    Eisler, Jonathan
    Hadzilacos, Vassos
    Toueg, Sam
    DISTRIBUTED COMPUTING, 2007, 19 (04) : 335 - 359
  • [30] The weakest failure detector to solve nonuniform consensus
    Jonathan Eisler
    Vassos Hadzilacos
    Sam Toueg
    Distributed Computing, 2007, 19 : 335 - 359
1234