Distributed consensus in the presence of sectional faults
Distributed consensus in the presence of sectional faults
复制标题
存在分段故障时的分布式共识
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
C. Rangan
中科院分区：
文献类型：
--
作者：
S. Amitanand;I. Sanketh;K. Srinathan;V. Vaikuntanathan;C. Rangan
考虑一个<i> n </i>播放器的同步网络，每个网络都有本地输入。分布式共识的目标是，即使玩家的某些非平凡子集<i> frangy </i>，即使有效的输入之一。通过有效输入，我们的意思是任何非故障玩家的输入。现有的导致拜占庭协议文献以“全或全神不察病”的方式捕捉了错误玩家的行为。例如，（拜占庭）有缺陷的球员完全没有受限，并且可能与不同的玩家行为不同。这导致了可实现的断层耐受性的严重低估。在这项工作中，我们提出了一种故障模型，可大大改善故障容忍度的估计，并有助于更好地捕获现实生活中的情况。例如，如果两个（诚实）的玩家是同一LAN的一部分（本质上是广播网络），那么外部有缺陷的玩家不可能对这两个玩家的行为不同（尽管故障玩家可能会以“均等”行为这两个球员都有恶意！）。在我们的结果中，我们介绍了更通用的故障模型，可以捕获任何现有模型未捕获的实用场景。我们提供了可容忍的故障和当前有效方案以达成共识的完整表征。我们指出，本文的结果严格概括了耐断层的现有特征。例如，考虑一个由四个播放器组成的网络<i> p </i> <sub> 1 </sub>，<i> p </i> <sub> 2 </sub>，<i> p </i > <sub> 3 </sub>和<i> p </i> <sub> 4 </sub>，在拜占庭对手的损坏影响下，由对手结构给予<i> a </i> = {（<i> p </i> <sub> 1 </sub>，<i> p </i> <sub> 2 </sub>），（<i> p </i> <sub> 2 </sub>，<i> p </i> <sub> 3 </sub>），（<i> p </i> <sub> 4 </sub>）}。在这种情况下，协议是不可能的</i>，因为从<i> a </i>覆盖播放器集的三组。但是，从我们的结果中可以明显看出，在上述情况下的共识确实是可能的（并且仅当）播放器<i> p </i> <sub> 1 </sub>，<i> p </i > <sub> 3 </sub>和<i> p </i> <sub> 4 </sub>属于网络中的一个LAN！
Consider a synchronous network of <i>n</i> players, each with a local input. The goal of <i>distributed consensus</i> is to globally agree on one of the valid inputs even if some non-trivial subset of the players are <i>faulty</i>. By valid input, we mean the input of any non-faulty player. Extant results in Byzantine agreement literature capture the behaviour of faulty players in an "all-or-nothing" fashion. For instance, a (Byzantine) faulty player is completely unconstrained and could behave differently with different players. This leads to a gross underestimation of the achievable fault-tolerance. In this work, we propose a fault-model that considerably improves the estimation of fault-tolerance and helps capture real-life scenarios better. For instance, if two (honest) players were part of the same LAN (which is essentially a broadcast network), it is impossible for a external faulty player to behave differently with these two players (though the faulty player may behave with "equal" malice with both these players!). Among our results, we introduce the <i>sectional</i> fault-model that is more general and can capture practical scenarios not captured by any extant model. We provide a complete characterization of the tolerable faults and present efficient protocols to achieve consensus. We remark that the results of this paper strictly generalize the extant characterizations of fault-tolerance. For example, consider a network of four players <i>P</i><sub>1</sub>, <i>P</i><sub>2</sub>, <i>P</i><sub>3</sub> and <i>P</i><sub>4</sub>, under the corrupting influence of a Byzantine adversary given by the adversary structure <i>A</i> = {(<i>P</i><sub>1</sub>, <i>P</i><sub>2</sub>), (<i>P</i><sub>2</sub>, <i>P</i><sub>3</sub>), (<i>P</i><sub>4</sub>)}. Agreement is <i>impossible</i> in such a scenario, since the three sets from <i>A</i> cover the player set. However, it would be evident from our results that consensus in the above scenario was indeed possible if (and only if) the players <i>P</i><sub>1</sub>, <i>P</i><sub>3</sub> and <i>P</i><sub>4</sub> belonged to a single LAN in the network!