On the computability power and the robustness of set agreement-oriented failure detector classes
On the computability power and the robustness of set agreement-oriented failure detector classes
复制标题
面向集合协议的故障检测器类的可计算能力和鲁棒性
DOI：
10.1007/s00446-008-0064-2
复制
发表时间：
2008
影响因子：
1.3
通讯作者：
Corentin Travers
中科院分区：
文献类型：
--
作者：
A. Mostéfaoui;S. Rajsbaum;M. Raynal;Corentin Travers
在容易出现无限进程故障的异步分布式系统中，确定性地解决一致性问题是不可能的，例如一致性和k集协议。为了避免这种不可能性，针对碰撞故障模型的不可靠故障检测器已被广泛研究。这些是提供故障信息的先知。这种信息的确切性质由特定类别的故障检测器所满足的一组抽象属性来定义。能够解决共识的这类故障检测器中最弱的一类是Ω。本文从文献中考虑故障检测器类在碰撞故障模型中的解集合一致性，并研究了它们的相对功率。它表明故障检测器类族(1≤x≤n)和(0≤y≤n)可以被添加以提供类Ωz(1≤z≤n，Ω的推广)的故障检测器。它还刻画了这种加法的能力，即可以构造Ωziffy+z>；t，可以构造Ωziffx+z>；t+1，其中是一次运行中可以崩溃的最大进程数。作为一个例子，本文证明了，虽然允许求解2集一致(但不允许一致)，但允许求解t集一致(但不允许(t−)-集一致)，具有这两类故障检测器的系统可以求解任意值的一致。更一般地，本文研究了故障检测器类和Ωz，并说明了在这些类中哪些缩减是可能的，哪些是不可能的。文中还提出了一个消息传递的Ωk-Basedk-Set协议，并证明了Ωk不足以解决(k-−)-Set协议。从这个意义上说，它可以被看作是朝着描述最弱故障检测器类的方向迈出了一步，从而可以解决k集一致性问题。
Solving agreement problems deterministically, such as consensus andk-set agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable failure detectors for the crash failure model have been widely studied. These are oracles that provide information on failures. The exact nature of such information is defined by a set of abstract properties that a particular class of failure detectors satisfy. The weakest class of such failure detectors that allow to solve consensus isΩ. This paper considers failure detector classes from the literature that solvek-set agreement in the crash failure model, and studies their relative power. It shows that the family of failure detector classes(1 ≤x≤n), and(0 ≤y≤n), can be “added” to provide a failure detector of the classΩz(1 ≤z≤n, a generalization ofΩ). It also characterizes the power of such an “addition”, namely,,can constructΩziffy+z>t, andcan constructΩziffx+z>t+ 1, wheretis the maximum number of processes that can crash in a run. As an example, the paper shows that, whileallows solving 2-set agreement (but not consensus) andallows solvingt-set agreement (but not (t− 1)-set agreement), a system with failure detectors of both classes can solve consensus for any value oft. More generally, the paper studies the failure detector classes,andΩz, and shows which reductions among these classes are possible and which are not. The paper also presents a message-passingΩk-basedk-set agreement protocol and shows thatΩkis not enough to solve (k− 1)-set agreement. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving thek-set agreement problem.