In agreement problems, each process has an input value and must choose the input of some process (possibly itself) as a decision 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 value 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.
翻译:在协议问题中,每个进程都有输入值, 并且必须选择某些进程( 可能本身) 的输入值为决定值。 鉴于$\geq 2$ 进程和$\geq 2$ 可能不同的输入值, 我们想要设计一个协议算法, 使尽可能多的进程能够在出现$t 崩溃失败的情况下决定相同价值。 没有通信, 当每个进程简单地决定其输入值时, 至少保证进程中的$\lcel (n- t)/m\rceil$ 总是决定相同的值 。 我们能更好地处理通信吗? 在有些情况下, 比如, $m=2$, 即使在出现一次崩溃故障的情况下, 答案是否定的, 在确定性的自动同步系统中, 通信要么使用原子读写登记册, 要么发送和接收信息。 答案在其他情况下是肯定的 。