1;3409;0c The Weakest Failure Detector for Message Passing Set-Agreement

The Weakest Failure Detector for Message Passing Set-Agreement

Distributed Computing, 22nd International Symposium, DISC 2008, vol. 5218, 2008
Pages: 109-120DOI: 10.1007/978-3-540-87779-0_8

DISC

bibtex

In the set-agreement problem, n processes seek to agree on at most n − 1 different values. This paper determines the weakest failure detector to solve this problem in a message-passing system where processes may fail by crashing. This failure detector, called the Loneliness detector and denoted Lmathcal{L} , outputs one of two values, “true” or “false” such that: (1) there is at least one process where Lmathcal{L} outputs always “false”, and (2) if only one process is correct, Lmathcal{L} eventually outputs “true” at this process.