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 条

[31] Decision optimal early-stopping k-set agreement in synchronous systems prone to send omission failures
Parvédy, PR
Raynal, M
Travers, C
11TH PACIFIC RIM INTERNATIONAL SYMPOSIUM ON DEPENDABLE COMPUTING, PROCEEDINGS, 2005, : 23 - 30
[32] The Weakest Failure Detector to Solve the Mutual Exclusion Problem in an Unknown Dynamic Environment
Mauffret, Etienne
Jeanneau, Denis
Arantes, Luciana
Sens, Pierre
ICDCN '19: PROCEEDINGS OF THE 2019 INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING, 2019, : 11 - 20
[33] The Weakest Failure Detector for Wait-Free Dining under Eventual Weak Exclusion
Sastry, Srikanth
Pike, Scott M.
Welch, Jennifer L.
SPAA'09: PROCEEDINGS OF THE TWENTY-FIRST ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, 2009, : 111 - 120
[34] Distributed computability: Relating k-immediate snapshot and x-set agreement
Delporte, Carole
Fauconnier, Hugues
Rajsbaum, Sergio
Raynal, Michel
INFORMATION AND COMPUTATION, 2022, 285
[35] Anonymous obstruction-free (n, k)-set agreement with n - k+1 atomic read/write registers
Bouzid, Zohir
Raynal, Michel
Sutra, Pierre
DISTRIBUTED COMPUTING, 2018, 31 (02) : 99 - 117

← 1 2 3 4 →