论文标题
另外两种算法，用于随机无签名的异步二进制拜占庭式共识，$ t <n/3 $和$ o（n^2）$消息和$ o（1）$（1）$圆形预期终止
Two More Algorithms for Randomized Signature-Free Asynchronous Binary Byzantine Consensus with $t < n/3$ and $O(n^2)$ Messages and $O(1)$ Round Expected Termination
论文作者
论文摘要
这项工作描述了基于[25]和[26]的算法，两种随机的，异步的，基于圆形的，基于圆形的二进制拜占庭式拜占庭有缺陷的共识算法。像[25]和[26]的算法一样，它们不使用签名，每回合使用$ o（n^2）$消息（其中每条消息由一个圆形数量和恒定的位数组成），可容忍多达三分之一的失败，并且预期终止了恒定的回合数。 第一个，例如[26]，使用弱的共同硬币（即可以在不同过程中以恒定概率返回不同值的硬币）来确保终止。该算法包括$ 5 $至$ 7 $ $的消息广播。描述了优化，将其降至$ 4 $至$ 5 $每轮的$ 5 $广播。相比之下，[26]包括$ 8 $至$ 12 $的消息广播。 第二种算法，例如[25]，都使用了完美的常见硬币（即，在所有非故障过程中返回相同值的硬币）来终止和正确性。与[25]不同，它不需要公平的调度程序来确保终止。此外，该算法包括第一轮的$ 2 $至$ 3 $的消息广播，下一轮的$ 1 $至$ 2 $广播，而[29]包括$ 2 $至$ 3 $每回合。
This work describes two randomized, asynchronous, round based, Binary Byzantine faulty tolerant consensus algorithms based on the algorithms of [25] and [26]. Like the algorithms of [25] and [26] they do not use signatures, use $O(n^2)$ messages per round (where each message is composed of a round number and a constant number of bits), tolerate up to one third failures, and have expected termination in constant number of rounds. The first, like [26], uses a weak common coin (i.e. one that can return different values at different processes with a constant probability) to ensure termination. The algorithm consists of $5$ to $7$ message broadcasts per round. An optimization is described that reduces this to $4$ to $5$ broadcasts per round for rounds following the first round. Comparatively, [26] consists of $8$ to $12$ message broadcasts per round. The second algorithm, like [25], uses a perfect common coin (i.e. one that returns the same value at all non-faulty processes) for both termination and correctness. Unlike [25], it does not require a fair scheduler to ensure termination. Furthermore, the algorithm consists of $2$ to $3$ message broadcasts for the first round and $1$ to $2$ broadcasts for the following rounds, while [29] consists of $2$ to $3$ broadcasts per round.
