Common knowledge and consistent simultaneous coordination
Common knowledge and consistent simultaneous coordination
复制标题
共同知识和一致的同时协调
作者：
G. Neiger;M. Tuttle
摘要在同步分布式系统中，公共知识和并行性之间存在着非常密切的关系。几个著名的问题的分析，在常识方面，导致这些问题，包括可靠的广播，分布式共识，和theDistributed射击队的问题轮最优协议。这些问题要求正确的处理器以某种方式协调它们的动作，但不限制错误处理器的行为。然而，在处理器发生良性故障的系统中，要求故障处理器的操作与正确处理器的操作一致是合理的，假设它执行任何操作。我们认为问题需要一致的，同时协调。然后，我们分析这些问题的常识在几个故障模型。分析这些更强的问题需要更强的共同知识的定义，我们研究这两个定义之间的关系。在许多情况下，这两个定义实际上是等价的，并且对以前的解进行简单的修改可以得到这些问题的近似最优解。当定义不同，但是，我们表明，这样的问题无法解决，即使在无故障的执行。
SummaryThere is a very close relationship between common knowledge and simultaneity in synchronous distributed systems. The analysis of several well-known problems in terms of common knowledge has led to round-optimal protocols for these problems, includingReliable Broadcast, Distributed Consensus, and theDistributed Firing Squad problem. These problems require that the correct processors coordinate their actions in some way but place no restrictions on the behaviour of the faulty processors. In systems with benign processor failures, howrver, it is reasonable to require that the actions of a faulty processor be consistent with those of the correct processors, assuming it performs any action at all. We consider problems requiringconsistent, simultaneous coordination. We then analyze these problems in terms of common knowledge in several failure models. The analysis of these stronger problems requires a stronger definition of common knowledge, and we study the relationship between these two definitions. In many cases, the two definitions are actually equivalent, and simple modifications of previous solutions yield roundoptimal solutions to these problems. When the definitions differ, however, we show that such problems cannot be solved, even in failure-free executions.