Synchronous Set Agreement: a Concise Guided Tour (including a new algorithm and a list of open problems)
Synchronous Set Agreement: a Concise Guided Tour (including a new algorithm and a list of open problems)
复制标题
同步集合协议：简明指南（包括新算法和未解决问题列表）
DOI：
10.1109/prdc.2006.59
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Corentin Travers
中科院分区：
文献类型：
--
作者：
M. Raynal;Corentin Travers
K-SET协议问题是分布式计算中遇到的协调问题的范式。参数k定义了我们感兴趣的协调度。（情况k = 1对应于众所周知的统一共识问题。）更确切地说，k-set协议问题考虑了由n个过程组成的系统，每个过程都提出了每个过程。值。它要求每个非故障流程都决定一个值，以使确定的值是提出的值，而决定的值不超过k个不同的值。本文访问了同步系统中的K-sten协议问题，其中最大的过程可能会遇到故障。探索了三个故障模型：碰撞故障模型，发送遗漏故障模型和一般遗漏故障模型。为每个模型提供了下限和协议。陈述了一般遗漏失败模型的开放问题。本文可以看作是一个简短的教程，其目的是使读者熟悉同步模型中的k-ster协议问题，并且故障严重程度增加。论文的一个重要关注点是简单性。除了调查味道外，呈现的几种结果和协议都是新的
The k-set agreement problem is a paradigm of coordination problems encountered in distributed computing. The parameter k defines the coordination degree we are interested in. (The case k=1 corresponds to the well-known uniform consensus problem.) More precisely, the k-set agreement problem considers a system made up of n processes where each process proposes a value. It requires that each non-faulty process decides a value such that a decided value is a proposed value, and no more than k different values are decided. This paper visits the k-set agreement problem in synchronous systems where up to t processes can experience failures. Three failure models are explored: the crash failure model, the send omission failure model, and the general omission failure model. Lower bounds and protocols are presented for each model. Open problems for the general omission failure model are stated. This paper can be seen as a short tutorial whose aim is to make the reader familiar with the k-set agreement problem in synchrony models with increasing fault severity. An important concern of the paper is simplicity. In addition to its survey flavor, several results and protocols that are presented are new