简单的超时共识

Question

有 n 个参与者，每个参与者都有一个超时，可以在达成共识之前或过程中随时触发。参与者处于可能发生分区和故障的分布式环境中。

所有参与者都可以从值 0 或 1（或 true/false）开始。如果任何参与者以 0 开始或任何参与者的超时在达成共识之前到期，则所有参与者必须决定 0。否则，所有参与者必须决定 1.

我已经经历了几次受启发或类似于 Ben-Or consensus protocol 的简单共识协议的迭代，但似乎找不到解决方案。

Ben-Or 协议与此设置之间的主要区别是：

1. 存在超时
2. 非随机化：如果有一个为零，那么所有的都应该为零。如果有任何超时，那么都应该决定为零。

此高度简化设置的示例（受 Ben-or 启发）：

x = True or False
while x or timeout not expired:
  broadcast report=True
  wait for all other participants' reports until timeout
  if all reports are True and received all reports:
    decide True
  otherwise
    decide False

要证明的关键事情：如果进程 p 决定 True，所有其他进程 q 决定 True

我可能在这里遗漏了一些关键的不可能性理论。任何想法将不胜感激。

Answer 1

随机化是 Ben-Or 在不可靠网络中避免确定性共识算法的 Fischer-Lynch-Paterson 不可能结果的方式。我认为 F–L–P 基本上适用于此设置，除非您每次都故意 运行 超时并且 return 到处都是 0。