Fault-Tolerant Consensus with an Abstract MAC Layer
Fault-Tolerant Consensus with an Abstract MAC Layer
复制标题
DOI：
10.4230/lipics.disc.2018.38
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Calvin C. Newport;Peter Robinson
中科院分区：
文献类型：
--
作者：
Calvin C. Newport;Peter Robinson
在本文中，我们研究了无线系统中的容错分布式共识。更详细地说，我们产生了两个新的随机算法，解决了这个问题的抽象MAC层模型，它捕获了大多数无线MAC层提供的基本接口和通信保证。我们的算法适用于任何数量的故障，不需要预先了解网络参与者或网络大小，并保证在网络大小为多项式的广播数量后以高概率终止。我们的第一个算法满足标准协议属性，而我们的第二个交易更快的终止保证，以换取更宽松的协议属性，其中大多数节点同意相同的值。这些是第一个已知的容错共识算法，这个模型。除了我们的主要上限的结果，我们探索之间的差距差距的抽象MAC层和标准的异步消息传递模型证明容错共识是不可能的，在后者的情况下，关于网络参与者的信息，即使我们假设没有故障，允许随机的解决方案，并提供算法的网络大小的常数因子近似。
In this paper, we study fault-tolerant distributed consensus in wireless systems. In more detail, we produce two new randomized algorithms that solve this problem in the abstract MAC layer model, which captures the basic interface and communication guarantees provided by most wireless MAC layers. Our algorithms work for any number of failures, require no advance knowledge of the network participants or network size, and guarantee termination with high probability after a number of broadcasts that are polynomial in the network size. Our first algorithm satisfies the standard agreement property, while our second trades a faster termination guarantee in exchange for a looser agreement property in which most nodes agree on the same value. These are the first known fault-tolerant consensus algorithms for this model. In addition to our main upper bound results, we explore the gap between the abstract MAC layer and the standard asynchronous message passing model by proving fault-tolerant consensus is impossible in the latter in the absence of information regarding the network participants, even if we assume no faults, allow randomized solutions, and provide the algorithm a constant-factor approximation of the network size.