论文标题
异步系统中的拜占庭晶格一致
Byzantine Lattice Agreement in Asynchronous Systems
论文作者
论文摘要
我们研究异步分布式消息传递系统中的拜占庭晶格协议（BLA）问题。在BLA问题中，每个过程都提出了一个来自联接半晶格的值，并且需要在晶格中输出一个值，以便尽管存在拜占庭式过程，但正确的过程的所有输出值都位于链上。我们为此问题提供了$ o（\ log f）$的圆形复杂性的算法，该复杂性可容忍$ f <\ frac {n} {5} $ byzantine Failures在没有数字签名的异步设置中，其中$ n $是$ n $是过程的数量。我们还展示了如何修改该算法以在身份验证的设置（即使用数字签名）中工作以耐受$ f <\ frac {n} {3} {3} $ byzantine Failures。
We study the Byzantine lattice agreement (BLA) problem in asynchronous distributed message passing systems. In the BLA problem, each process proposes a value from a join semi-lattice and needs to output a value also in the lattice such that all output values of correct processes lie on a chain despite the presence of Byzantine processes. We present an algorithm for this problem with round complexity of $O(\log f)$ which tolerates $f < \frac{n}{5}$ Byzantine failures in the asynchronous setting without digital signatures, where $n$ is the number of processes. We also show how this algorithm can be modified to work in the authenticated setting (i.e., with digital signatures) to tolerate $f < \frac{n}{3}$ Byzantine failures.
