k-Set Agreement with Limited Accuracy Failure Detectors
Achour MOSTEFAOUI, Michel RAYNAL
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
Let the "scope" of the accuracy property of an unreliable failure detector
be the number x of processes that may not suspect a correct process. This
notion gives rise to new classes of failure detectors among which S_x and
<>S_x. The k-set agreement problem generalizes the consensus problem
in the sense that the number of decided values is bounded by k. There exist
protocols that solve this problem in asynchronous distributed systems when
f<k (f being the maximum number of processes that
may crash). It has been shown that there are solutions in those
systems only if f>=k.
The paper considers asynchronous distributed systems equipped with limited
scope accuracy failure detectors. It studies conditions on n, f, k and
x that allow to solve the k-set agreement problem in those systems and
presents two protocols. The first protocol solves the problem in asynchronous
distributed systems augmented with a failure detector of the class S_x.
It requires f<k+x-1.
The second protocol works with any failure detector of the
class <>S_x.
It defines a family of protocols that allows to solve the k-set agreement
problem under some condition.