On the road to the weakest failure detector for k-set agreement in message-passing systems
On the road to the weakest failure detector for k-set agreement in message-passing systems
复制标题
消息传递系统中 k 集协议的最弱故障检测器之路
DOI：
10.1016/j.tcs.2010.11.007
复制
发表时间：
2011
影响因子：
1.1
通讯作者：
M.Raynal
中科院分区：
文献类型：
--
作者：
F.Bonnet;M.Raynal
在k-集合一致性问题中，每个进程（在一个n个进程的集合中）提出一个值，并且必须以最多确定k个不同值的方式来确定所提出的值。虽然这个问题可以很容易地在异步系统中解决，当k>t时，容易发生t个进程崩溃，但当k≤t时，这个问题就无法解决了。几年来，人们一直在研究基于故障检测器的方法来规避这种不可能性。虽然最近已经发现了解决读写共享内存系统中k-集合一致性问题的最弱故障检测器类（PODC 2009），但在消息传递系统中情况不同，其中最弱故障检测器类仅在极端情况k=1（一致性）和k=n-1（集合一致性）下已知。本文提出了四个贡献，其目的是帮助铺平道路，发现最弱的故障检测器类的k-集协议的消息传递系统。这些贡献如下。(a)第一个是一个新的故障检测器类，记为k，即1= ×Ω（k=1时最弱的类），n−1=L（k=n−1时最弱的类）。(b)第二个是对故障检测器的结构的研究，表明故障检测器是两个故障检测器类的组合，故障检测器类是新的故障检测器类，故障检测器类是Ω k（它们分别推广了以前的“法定人数”和“最终领导者”故障检测器类）。(c)第三个贡献关注的是被证明是一个必要的要求（就失败的信息而言），以解决在消息传递系统中的k-集协议问题。(d)最后，最后一个贡献是一个基于n-1的算法，解决了（n-1）-集一致性问题。这个算法为我们提供了一个新的算法见解，可以解决异步消息传递系统中的（n-1）-集一致性问题。希望这些贡献将有助于发现消息传递系统中k集协议的最弱故障检测器类。
In the k-set agreement problem, each process (in a set of n processes) proposes a value and has to decide a proposed value in such a way that at most k different values are decided. While this problem can easily be solved in asynchronous systems prone to t process crashes when k>t, it cannot be solved when k≤t. For several years, the failure-detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the k-set agreement problem in read/write shared memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases k=1 (consensus) and k=n−1 (set agreement). This paper presents four contributions whose aim is to help pave the way to discover the weakest failure detector class for k-set agreement in message-passing systems. These contributions are the following. (a) The first is a new failure detector class, denoted Πk, that is such that Π1=Σ×Ω (the weakest class for k=1), and Πn−1=L (the weakest class for k=n−1). (b) The second is an investigation of the structure of Πkthat shows that Πkis the combination of two failure detector classes Σk(that is new) and Ωk(they generalize the previous “quorums” and “eventual leaders” failure detector classes, respectively). (c) The third contribution concerns Σkthat is shown to be a necessary requirement (as far as information on failure is concerned) to solve the k-set agreement problem in message-passing systems. (d) Finally, the last contribution is a Πn−1-based algorithm that solves the (n−1)-set agreement problem. This algorithm provides us with a new algorithmic insight on the way the (n−1)-set agreement problem can be solved in asynchronous message-passing systems. It is hoped that these contributions will help discover the weakest failure detector class for k-set agreement in message-passing systems.
登录
查看更多内容
同步集合协议：简明指南（包括新算法和未解决问题列表）
DOI：
10.1109/prdc.2006.59
发表时间：
2006
期刊：
2006 12th Pacific Rim International Symposium on Dependable Computing (PRDC'06)
影响因子：
--
作者：
M. Raynal;Corentin Travers
通讯作者：
Corentin Travers
基于(anti-Omegax ×Sigmaz)的k-Set一致性算法
DOI：
10.1007/978-3-642-17653-1_16
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Z. Bouzid;Corentin Travers
通讯作者：
Corentin Travers
原子对象实现的严格故障检测范围
DOI：
10.1145/1734213.1734216
发表时间：
2010
期刊：
J. ACM
影响因子：
--
作者：
C. Delporte;H. Fauconnier;R. Guerraoui
通讯作者：
R. Guerraoui
分享比同意更难
DOI：
10.1145/1400751.1400764
发表时间：
2008
期刊：
--
影响因子：
--
作者：
C. Delporte;H. Fauconnier;R. Guerraoui
通讯作者：
R. Guerraoui
具有有限精度故障检测器的 k 集协议
DOI：
10.1145/343477.343536
发表时间：
2000
期刊：
--
影响因子：
--
作者：
A. Mostéfaoui;M. Raynal
通讯作者：
M. Raynal