On the road to the weakest failure detector for k-set agreement in message-passing systems

In the k-set agreement problem, each process (in a set of n processes) proposes a value and has to decide a proposed value in such a way that at most k different values are decided. While this problem can easily be solved in asynchronous systems prone to t process crashes when k > t, it cannot be solved when k <= t. For several years, the failure-detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the k-set agreement problem in read/write shared memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases k = 1 (consensus) and k = n - 1 (set agreement). This paper presents four contributions whose aim is to help pave the way to discover the weakest failure detector class for k-set agreement in message-passing systems. These contributions are the following. (a)The first is a new failure detector class, denoted Pi(k), that is such that Pi(1) = Sigma x Omega (the weakest class for k = 1), and Pi(n-1) = L (the weakest class for k = n - 1). (b) The second is an investigation of the structure of Pi(k) that shows that Pi(k) is the combination of two failure detector classes Sigma(k) (that is new) and Omega(k) (they generalize the previous "quorums" and "eventual leaders" failure detector classes, respectively). (c) The third contribution concerns Sigma(k) that is shown to be a necessary requirement (as far as information on failure is concerned) to solve the k-set agreement problem in message-passing systems. (d) Finally, the last contribution is a Pi(n-1)-based algorithm that solves the (n - 1)-set agreement problem. This algorithm provides us with a new algorithmic insight on the way the (n - 1)-set agreement problem can be solved in asynchronous message-passing systems. It is hoped that these contributions will help discover the weakest failure detector class for k-set agreement in message-passing systems. (C) 2010 Elsevier B.V. All rights reserved.