Sharing is harder than agreeing
Sharing is harder than agreeing
复制标题
分享比同意更难
DOI：
10.1145/1400751.1400764
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Guerraoui
中科院分区：
文献类型：
--
作者：
C. Delporte;H. Fauconnier;R. Guerraoui
分布式计算理论最著名的成果之一是，在通过共享内存寄存器进行通信的 n 个进程的异步系统中，不可能解决集合一致性问题，即进程需要在其 n 个初始值中决定最多 n-1 个值。简而言之，结果表明寄存器抽象太弱，无法实现既定协议。
本文探讨了消息传递系统中这些抽象之间的关系，其中寄存器不是给定的物理设备，而是本身由通过消息传递进行通信的进程实现。我们表明，也许令人惊讶的是，关于进程故障的信息对于实现由两个特定进程共享的寄存器是必要和充分的，但对于实现设定的协议来说不是必需的。
我们稍后通过考虑 k 集一致性（其中进程可以决定最多 k 个值）并将其与 2k 进程的任何特定子集共享的寄存器进行比较来概括此结果。我们证明
对于 1 ≤ k ≤ n/2，(a) 足以实现 2k 个进程共享的寄存器的任何故障信息也足以实现 (n-k) 组一致，但 (b) 足以实现 (n-k) 组一致的故障信息不足以实现 2k 进程共享的寄存器。我们还证明 (c) 对于 2k 个进程共享的寄存器来说足够的故障信息对于 ((n-k)-1) 集一致性来说是不够的。
One of the most celebrated results of the theory of distributed computing is the impossibility, in an asynchronous system of n processes that communicate through shared memory registers, to solve the set agreement problem where the processes need to decide on up to n-1 among their n initial values. In short, the result indicates that the register abstraction is too weak to implement the set agreement one.
This paper explores the relation between these abstractions in a message passing system where a register is not a given physical device but is rather itself implemented by processes communicating through message passing. We show that, maybe surprisingly, the information about process failures that is necessary and sufficient to implement a register shared by two particular processes is sufficient but not necessary to implement set agreement.
We later generalize this result by considering k-set agreement, where the processes can decide on up to k values, and comparing it with a register shared by any particular subset of 2k processes. We prove
that, for 1 ≤ k ≤ n/2, (a) any failure information that is sufficient to implement a register shared by 2k processes is sufficient to implement (n-k)-set agreement but (b) a failure information that is sufficient for (n-k)-set agreement is not sufficient for a register shared by 2k processes. We also prove that (c) a failure information that is sufficient for a register shared by 2k processes is not sufficient for ((n-k)-1)-set agreement.