A condition for k-set agreement in asynchronous distributed systems

The k-set agreement problem has no solution in fully asynchronous distributed systems made up of n processes (where at most f of them can crash), when f⩾k. This paper presents a condition on the occurrence pattern of proposed values that allows to solve the problem whatever the value of f. More specifically, it is shown that if there is a set of more than (kn+f)/(k+1) processes that propose at most k different values, then the k-set agreement problem can be solved. When we consider the particular case of the consensus problem (k=1), this means that, whatever the value of f, this problem can be solved when more than (n+f)/2 processes propose the same value. As an example of the usefulness of this condition, it is used to improve Ben-Or´s randomized consensus protocol