Weakening failure detectors for k-set agreement via the partition approach

In this paper, we propose the partition approach and define several new classes of partitioned failure detectors weaker than existing failure detectors for the k-set agreement problem in both the shared-memory model and the message-passing model. In the shared-memory model with n + 1 processes, for any 2 <= k <= n, we first propose a partitioned failure detector Pi Omega(k) that solves k-set agreement with shared read/write registers and is strictly weaker than Omega(k), which was conjectured to be the weakest failure detector for k-set agreement in the shared-memory model [19]. We then propose a series of partitioned failure detectors that can solve n-set agreement, yet they are strictly weaker than gamma [10], the weakest failure detector ever found before our work to circumvent any asynchronous impossible problems in the shared-memory model. We also define two new families of partitioned failure detectors in the message-passing model that are strictly weaker than the existing ones for k-set agreement. Our results demonstrate that the partition approach opens a new dimension for weakening failure detectors related to set agreement, and it is an effective approach to check whether a failure detector is the weakest one or not for set agreement. So far, all previous candidates for the weakest failure detectors of set agreement have been disproved by the partitioned failure detectors.