论文标题
$ n $流程中的$ k $达成协议
Reaching Agreement Among $k$ out of $n$ Processes
论文作者
论文摘要
在协议问题中，每个过程都有一个输入值，并且必须选择一个决策（输出）值。给定$ n \ geq 2 $流程和$ m \ geq 2 $可能的不同输入值，我们想设计一种协议算法，在存在$ t $崩溃失败的情况下，可以使尽可能多的流程确定其中一个流程的（相同）输入值。没有通信，当每个过程都简单地决定其输入值时，该过程的至少$ \ lceil（n-t）/m \ rceil $保证始终决定相同的值。我们可以在沟通方面做得更好吗？在某些情况下，例如，即使在单个崩溃失败的情况下，$ m = 2 $即使在确定性的异步系统中，答案也为负，在这种系统中，通过使用原子读/写寄存器或发送和接收消息，可以通过使用原子读/写寄存器进行通信。在其他情况下，答案是积极的。
In agreement problems, each process has an input value and must choose a decision (output) value. Given $n\geq 2$ processes and $m \geq 2$ possible different input values, we want to design an agreement algorithm that enables as many processes as possible to decide on the (same) input value of one of the processes, in the presence of $t$ crash failures. Without communication, when each process simply decides on its input value, at least $\lceil (n-t)/m \rceil$ of the processes are guaranteed to always decide on the same value. Can we do better with communication? For some cases, for example when $m=2$, even in the presence of a single crash failure, the answer is negative in a deterministic asynchronous system where communication is either by using atomic read/write registers or by sending and receiving messages. The answer is positive in other cases.
