论文标题
在遗忘的消息对手下，在动态网络中共识的时间复杂性
Time Complexity of Consensus in Dynamic Networks Under Oblivious Message Adversaries
论文作者
论文摘要
共识是分布式计算中最基本的任务。本文研究了通过动态有向网络连接的一组过程的共识问题，其中计算和通信是锁定的同步，但受遗忘的消息对手的控制。在这个基本模型中，在可能的情况下，确定共识的解决性和设计共识算法，这是令人惊讶的困难。我们提出了一个明确的决策程序，以确定在给定对手下是否可以共识。反过来，这使我们能够首次研究该模型共识的时间复杂性。特别是，对于集中式决策程序以及解决分布式共识，我们为共识解决性提供了时间复杂性上限。我们将这些结果与时间复杂性下限进行补充。有趣的是，我们发现，在遗忘消息对手下达成共识的时间比将某些过程的输入值传播到所有其他过程的输入值的时间更长。
Consensus is a most fundamental task in distributed computing. This paper studies the consensus problem for a set of processes connected by a dynamic directed network, in which computation and communication is lock-step synchronous but controlled by an oblivious message adversary. In this basic model, determining consensus solvability and designing consensus algorithms in the case where it is possible, has been shown to be surprisingly difficult. We present an explicit decision procedure to determine if consensus is possible under a given adversary. This in turn enables us, for the first time, to study the time complexity of consensus in this model. In particular, we derive time complexity upper bounds for consensus solvability both for a centralized decision procedure as well as for solving distributed consensus. We complement these results with time complexity lower bounds. Intriguingly, we find that reaching consensus under an oblivious message adversary can take exponentially longer than broadcasting the input value of some process to all other processes.
