Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
On Failure Detectors Weaker Than Ever

Wei Chen, Yu Chen, and Jialin Zhang

Abstract

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.

Details

Publication typeTechReport
NumberMSR-TR-2007-50
Pages34
InstitutionMicrosoft Research
> Publications > On Failure Detectors Weaker Than Ever