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 <$gt;S_x. It defines a family of protocols that allows to solve the k-set agreement problem under some condition.