@inproceedings{61ea0ca315934b74a9bbbfa9a85f7745,
title = "The weakest failure detector for solving k-set agreement",
abstract = "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.",
keywords = "BG-simulation, Failure detectors, K-set agreement, Synchrony assumptions",
author = "Eli Gafni and Petr Kuznetsov",
year = "2009",
month = aug,
day = "10",
doi = "10.1145/1582716.1582735",
language = "English",
isbn = "9781605583969",
series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
publisher = "Association for Computing Machinery (ACM)",
pages = "83--91",
booktitle = "PODC'09 - Proceedings of the 2009 ACM Symposium on Principles of Distributed Computing",
note = "28th ACM symposium on Principles of distributed computing, PODC 2009 ; Conference date: 10-08-2009 Through 12-08-2009",
}