Synchronous Byzantine Lattice Agreement in O(log(f) Rounds
Synchronous Byzantine Lattice Agreement in O(log(f) Rounds
复制标题
O(log(f) 轮中的同步拜占庭格子协议
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Leonardo Querzoni
中科院分区：
文献类型：
--
作者：
Giuseppe Antonio Di Luna;E. Anceaume;Silvia Bonomi;Leonardo Querzoni
在最初由Attiya等人提出的晶格协议（LA）问题中，一组进程必须决定一个晶格链。更准确地说，每一个正确的过程提出一个特定连接半格L的元素e，它必须确定一个包含e的值。并且，正确过程的任意一对pi， pj必须确定deci和decj两个可比较的值（例如deci≤decj或decj < deci）。在本文中，我们对同步情况提出了新的贡献。我们研究了具有不同唯一id的n个进程系统的常规消息传递模型中的问题。我们首先证明，当只有经过身份验证的通道可用时，如果f = n/3或更多进程是Byzantine，则问题无法解决。然后，我们提出了一种新的算法，该算法在具有签名的同步系统模型（即经过身份验证的消息模型）中工作，可以容忍多达f个拜占庭故障（其中f < n/3），并且在$mathcal{O}$ （log f）轮询中终止。我们讨论了如何在算法弹性（f < n/4）的代价下删除经过身份验证的消息。最后，我们提出了一个转换器，可以将任何同步的LA算法转换为同步的广义点阵协议算法。
In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. [1], a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element e of a certain join-semi lattice L and it has to decide on a value that contains e. Moreover, any pair pi, pj of correct processes has to decide two values deci and decj that are comparable (e.g., deci ≤ decj or decj < deci).In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of n processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if f = n/3 or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the authenticated message model), tolerates up to f byzantine failures (where f < n/3) and that terminates in $mathcal{O}$ (log f ) rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency (f < n/4). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.