| Citation key |
GK-WFDSKSA-09 |
| Author |
Gafni, Eli and Kuznetsov, Petr |
| Title of Book |
28th ACM SIGACT/SIGOPS Symposium on Principles of Distributed Computing (PODC 2009) |
| Pages |
83–91 |
| Year |
2009 |
| ISBN |
978-1-60558-396-9 |
| DOI |
http://dx.doi.org/10.1145/1582716.1582735 |
| Location |
Calcary, AB, Canada |
| Address |
New York, NY, USA |
| Month |
August |
| Publisher |
ACM |
| 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. |
