Byzantine Lattice Agreement in Synchronous Systems
Byzantine Lattice Agreement in Synchronous Systems
复制标题
同步系统中的拜占庭格子协议
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Vijay K. Garg
中科院分区：
文献类型：
--
作者：
Xiong Zheng;Vijay K. Garg
在本文中，我们研究了同步系统中的拜占庭晶体协议问题。碰撞故障模型中的晶格协议问题均已在同步和异步系统中研究，这导致了两个系统中当前最佳上限（log f）$ rounds。但是，对于拜占庭失败模型中的晶格一致性问题，很少有算法结果已知。该论文[Nowak等，Disc，2019年]首先给出了针对无周期晶格的晶格协议问题的算法，该晶格可容忍$ f <n/（h（x） + 1）$ byzantine press，其中$ n $是流程数，而$ h（x）$是输入晶格$ x $的高度。 Di等人的最新预印本。研究了异步系统中有效性条件略有修改的问题。他们通过将可靠的广播原始词作为第一步，并遵循类似的算法框架与崩溃失败模型中的算法相似的算法框架，呈现出$ O（f）$ roughs算法。在本文中，我们提出了同步系统中拜占庭晶格协议问题的三种算法。第一个算法花费$ min {3h（x） + 6,6sqrt {f} + 6}）$ rounds和$ o（n^2 min {h（x），sqrt {f}}）$ heess，其中$ h （x）$是输入晶格$ x $，$ n $的高度。第二个算法以$ 3LOG N + 3 $回合运行，并采用$ O（n^2 log N）$消息。第三算法需要$ 4 log f + 3 $回合，并采用$ o（n^2 log f）$消息。所有算法最多可以忍受$ f <frac {n} {3} $ byzantine Failures。
In this paper, we study the Byzantine lattice agreement problem in synchronous systems. The lattice agreement problem in crash failure model has been studied both in synchronous and asynchronous systems, which leads to the current best upper bound of $O(log f)$ rounds in both systems. However, very few algorithmic results are known for the lattice agreement problem in Byzantine failure model. The paper [Nowak et al., DISC, 2019] first gives an algorithm for a variant of the lattice agreement problem on cycle-free lattices that tolerates up to $f<n/(h(X) + 1)$ Byzantine faults, where $n$ is the number of processes and $h(X)$ is the height of the input lattice $X$. The recent preprint by Di et al. studies this problem with a slightly modified validity condition in asynchronous systems. They present a $O(f)$ rounds algorithm by using the reliable broadcast primitive as a first step and following the similar algorithmic framework as the algorithms in crash failure model. In this paper, we propose three algorithms for the Byzantine lattice agreement problem in synchronous systems. The first algorithm takes $min {3h(X) + 6,6sqrt{f} + 6})$ rounds and $O(n^2 min{h(X), sqrt{f}})$ messages, where $h(X)$ is the height of the input lattice $X$, $n$ is the total number of processes. The second algorithm runs in $3log n + 3$ rounds and takes $O(n^2 log n)$ messages. The third algorithm takes $4 log f + 3$ rounds and takes $O(n^2 log f)$ messages. All algorithms can tolerate up to $f<frac{n}{3}$ Byzantine failures.