Partition Approach to Failure Detectors for k-Set Agreement

Wei Chen, Jialin Zhang, Yu Chen, and Xuezheng Liu

Abstract

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 ΠSk, 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 ΠSk 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.

Details

Publication typeTechReport
NumberMSR-TR-2007-49
Pages33
InstitutionMicrosoft Research
> Publications > Partition Approach to Failure Detectors for k-Set Agreement