This paper considers the failure detector classes that have been considered in the literature to solve $k$-set agreement, and studies their relative power. It shows that the family of failure detector classes $\Diamond {\cal S}_x$ ($0\leq x \leq n$), and $\Diamond \psi^y$ ($0\leq y \leq n$), can be ``added'' to provide a failure detector of the class $\Omega^z$ (a generalization of $\Omega$). It also characterizes the power of such an ``addition'', namely, $\Diamond {\cal S}_x +\Diamond \psi^y \leadsto \Omega^z \Leftrightarrow x+y+z>t+1$, where $t$ is the maximum number of processes that can crash in a run. As an example, the paper shows that, while $\Diamond {\cal S}_{t}$ allows solving 2-set agreement (and not consensus) and $\Diamond \psi^{1}$ allows solving $t$-set agreement (but not $(t-1)$-set agreement), a system with failure detectors of both classes can solve consensus. More generally, the paper studies the failure detector classes $\Diamond {\cal S}_x$, $\Diamond \psi^y$ and $\Omega^z$, and shows which reductions among these classes are possible and which are not.The paper presents also a message-passing $\Omega^k$-based $k$-set agreement protocol. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the $k$-set agreement problem.
展开▼
机译：本文考虑了文献中已经考虑过的故障检测器类别，以解决$ k $ -set协议，并研究了它们的相对功效。它显示了故障检测器类的族$ \ Diamond {\ cal S} _x $（$ 0 \ leq x \ leq n $）和$ \ Diamond \ psi ^ y $（$ 0 \ leq y \ leq n $），可以被``添加''以提供$ \ Omega ^ z $类的故障检测器（$ \ Omega $的概括）。它还表征了这种``加法''的功能，即$ \ Diamond {\ cal S} _x + \ Diamond \ psi ^ y \ leadsto \ Omega ^ z \ Leftrightarrow x + y + z> t + 1 $ ，其中$ t $是运行中可能崩溃的最大进程数。例如，该论文显示，虽然$ \ Diamond {\ cal S} _ {t} $允许求解2集合的协议（而非共识），而$ \ Diamond \ psi ^ {1} $允许求解$ t $集合协议（但不是（t-1）集合协议），则具有两个类别的故障检测器的系统都可以解决共识。更一般而言，本文研究了故障检测器类别$ \ Diamond {\ cal S} _x $，$ \ Diamond \ psi ^ y $和$ \ Omega ^ z $，并显示了这些类别中哪些可以减少而哪些不可以减少本文还提出了一种基于消息传递$ \ Omega ^ k $的$ k $设置协议协议。从这个意义上讲，这可以看作是表征最弱故障检测器类的步骤，该类可以解决$ k $ -set协议问题。
展开▼
