k-set agreement with limited accuracy failure detectors
k-set agreement with limited accuracy failure detectors
复制标题
具有有限精度故障检测器的 k 集协议
DOI：
10.1145/343477.343536
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
M. Raynal
中科院分区：
文献类型：
--
作者：
A. Mostéfaoui;M. Raynal
令不可靠的故障检测器的精度属性</italic> </italic>是数字<Italic> x </italic>可能无法怀疑正确过程的过程。我们在其中考虑<Italic> s <sudcrpt> x </subscrpt> </italic>和⋄<italic> s <s <subscrpt> x </subscrpt> </iTalic>在本文中等于<Italic> n </Italic>，过程总数）。
<italic> k </italic> - 集合协议问题概括了共识问题：每个正确的过程都必须以确定的值是提出的值的方式来决定一个值，并且决定的值的数量由<Italic> k </italic>。表明，当这些系统中没有解决方案ƒ≥<italic> k </italic>。
该论文认为配备有限的范围精度失效检测器的异步分布式系统研究<Italic> n </italic>，ƒ，<italic> k </italic>这些系统中的<Italic> k </iTalic> set协议问题，并提出了两个协议。斜体> s <subscrpt> x </subscrpt> </italic>。类<italic> s <subscrpt> x </subscrpt> </italic>实际上定义了该家族的家庭。 > max </italic>（<italic> k，max </italic> <sudcrpt>1≤<italic>α</italic>≤<italic> k </italic> k </italic> </subscrpt>（<italic> min </</</斜体>（<italic> n </italic> - <italic>α</italic> <Italic> <italic> n </italic>/（<italic>α</italic> + 1）斜体> +<italic> x </italic> -1））。配备故障检测器的异步分布式系统的一致性问题ε<italic> s <subscrpt> x </subscrpt> </italic>或⋄<italic> s <italic> s <sudcrpt> x </subscrpt> </italic>。
Let the <italic>scope</italic> of the accuracy property of an unreliable failure detector be the number <italic>x</italic> of processes that may not suspect a correct process. The scope notion gives rise to new classes of failure detectors among which we consider <italic>S<subscrpt>x</subscrpt></italic> and ⋄<italic>S<subscrpt>x</subscrpt></italic> in this paper (Usual failure detectors consider an implicit scope equal to <italic>n</italic>, the total number of processes).
The <italic>k</italic>-set agreement problem generalizes the consensus problem: each correct process has to decide a value in such a way that a decided value is a proposed value, and the number of decided values is bounded by <italic>k</italic>. There exist protocols that solve this problem in asynchronous distributed systems when ƒ < <italic>k</italic> (where ƒ is the maximum number of processes that may crash). Moreover, it has been shown that there is no solution in those systems when ƒ ≥ <italic>k</italic>.
The paper considers asynchronous distributed systems equipped with limited scope accuracy failure detectors. It studies conditions on <italic>n</italic>, ƒ, <italic>k</italic> and <italic>x</italic> that allow to solve the <italic>k</italic>-set agreement problem in those systems and presents two protocols. The first protocol solves the <italic>k</italic>-set agreement in asynchronous distributed systems augmented with a failure detector of the class <italic>S<subscrpt>x</subscrpt></italic>. It requires ƒ < <italic>k</italic> + <italic>x</italic> - 1. The second protocol works with any failure detector of the class ⋄<italic>S<subscrpt>x</subscrpt></italic>. It actually defines a family of protocols. This family allows to solve the <italic>k</italic>-set agreement problem when ƒ < <italic>max</italic>(<italic>k, max</italic><subscrpt>1≤<italic>α</italic>≤<italic>k</italic></subscrpt>(<italic>min</italic>(<italic>n</italic> - <italic>α</italic>⌊<italic>n</italic>/(<italic>α</italic> + 1)⌋, <italic>α</italic> +<italic>x</italic> - 1))). We conjecture that, when ƒ ≥ <italic>k</italic>, these conditions are necessary to solve the <italic>k</italic>-set agreement problem in asynchronous distributed systems equipped with failure detectors ε <italic>S<subscrpt>x</subscrpt></italic> or ⋄<italic>S<subscrpt>x</subscrpt></italic>, respectively.