On Failure Detectors Weaker Than Ever

In this paper, we apply the partition approach proposed in [6] to study weak failure detectors for set agreement problem for the shared-memory model. In a system with n+1 processes, for any 2 <= k <= n, we first propose a partitioned failure detector ΠΩ_k that solves k-set agreement with shared read/write registers and is strictly weaker than Ω_k, which was conjectured to be the weakest failure detector for k-set agreement in the shared-memory model [16]. We then propose a series of partitioned failure detectors that can solve n-set agreement, yet they are strictly weaker than Υ [8], the weakest failure detector ever found before our work to circumvent any asynchronous impossible problems in the shared-memory model. Our results not only lower the upper bound on the failure detectors for set agreement, but also further demonstrate the power of the partition approach. They strongly reinforce the statement we made in [6] that the partition approach opens a new dimension for weakening failure detectors related to set agreement, and it is an effective test to check whether a failure detector is the weakest one or not for set agreement. So far, no candidates for the weakest failure detectors of set agreement pass our partition test.