Partition Approach to Failure Detectors for k-Set Agreement

In k-set agreement problem, every process proposes a value and eventually at most k different values can be decided. When k>1, different subset of processes may decide on different values, and thus it naturally exhibits partition among processes based on their decision values. In this paper, we propose the partition approach to define failure detectors that capture the partition nature of k-set agreement. The power of the partition approach is to further weaken failure detectors that are already very weak in solving k-set agreement, and thus invalid the failure detectors as candidates for the weakest failure detectors for k-set agreement. Using the approach, we propose two new classes of failure detectors, statically partitioned failure detectors Π_k and splittable partitioned failure detectors Π^S_k, both are strong enough to solve k-set agreement in the message passing model. However, we show that Π_k is strictly weaker than Ω_k, the weakest failure detectors known so far for k-set agreement, and Π^S_k is even weaker than Π_k. The partition approach provides a new dimension to weaken failure detectors related to k-set agreement. It is an effective way to check whether a failure detector is the weakest one solving k-set agreement or not. Together with [4], we show that so far all candidates for the weakest failure detectors including Ω_k and Υ in both the message-passing model and the shared-memory model have failed our partition test.