Tight bounds for k-set agreement with limited-scope failure detectors

摘要

In a system with limited-scope failure detectors, there are q disjoint clusters of processes such that some correct process in each cluster is never suspected by any process in that cluster. The failure detector class S_x,q satisfies this property all the time, while ◇S_(x,q) satisfies it eventually. This paper gives the first tight bounds for the k-set agreement task in asynchronous message-passing models augmented with failure detectors from either the S_(x,q) or ◇S_(x,q) classes. For S_(x,q), we show that any k-set agreement protocol that tolerates f failures must satisfy f < k+x — q if q < k and f < x otherwise, where x is the combined size of the q disjoint clusters if q < k (or the k largest, otherwise). This result establishes for the first time that the protocol of Mostefaoui and Raynal for the S_x — S_(x,1) failure detector is optimal. For ◇S_(x,q), we show that any k-set agreement protocol that tolerates / failures must satisfy f < min((n+1)/2, k+x-q) if q < k and f < min((n+1)/2, x) otherwise, where n + 1 is the total number of processes. We give a novel protocol that matches our lower bound, disproving a conjecture of Mostefaoui and Raynal for the ◇S_x = ◇S_(x,1) failure detector. Our lower bounds exploit techniques borrowed from Combinatorial Topology, demonstrating for the first time that this approach is applicable to models that encompass failure detectors.