Consensus is arguably one of the most important notions in distributed computing. Among asynchronous, randomized, and signature-free implementations, the protocols of Most\'efaoui et al. (PODC 2014 and JACM 2015) represent a landmark result, which has been extended later and taken up in practical systems. The protocols achieve optimal resilience and takes, in expectation, only a constant expected number of rounds of quadratic message complexity. Randomization is provided through a common-coin primitive. In traditional consensus protocols, all involved processes adhere to a global, symmetric failure model, typically only defined by bounds on the number of faulty processes. Motivated by applications to blockchains, however, more flexible trust assumptions have recently been considered. In particular, with asymmetric trust, a process is free to choose which other processes it trusts and which ones might collude against it. This paper revisits the optimal asynchronous protocol of Most\'efaoui et al. and shows how to realize it with asymmetric trust. The paper starts by pointing out in detail why some versions of this protocol may violate liveness. Then it proposes a fix for the protocol that does not affect its properties, but lets it regain the simplicity of its original version (PODC 2014). At the same time, the paper shows how to realize randomized signature-free asynchronous Byzantine consensus with asymmetric quorums. This results in an optimal consensus protocol with subjective, asymmetric trust and constant expected running time. It is suitable for applications to blockchains, for instance.
翻译:在分布式计算中,共识可以说是最重要的概念之一。在非同步、随机和无签名的执行中,Most\'efaoui et al.(PoDC 2014和JACM 2015)的议定书代表着一个里程碑式的结果,这一结果后来得到扩展,并在实际系统中被采纳。协议实现了最佳的复原力,并且预期只会得到一连串的四级信息的复杂性。随机化是通过一个普通的coin原始协议提供的。在传统的共识协议中,所有进程都包含一个全球性的、对称的失败模式,通常仅由错误过程数目的界限来界定。但是,最近,由于对阻塞链的合适应用(PoDC 2014 和 JACM 2015 ) 代表着一个里程碑式的里程碑式的信任假设,这是一个里程碑式的结果,后来,在不对称的信任下,一个进程可以自由选择它所信任的其他进程,并且人们可能会对此产生串联。 本文回顾了Most\'efaoui etality etality et etality etroom and al. show to to realfalfality trustation.