文章基本信息

标题：Byzantine Lattice Agreement in Synchronous Message Passing Systems
本地全文：下载
作者：Xiong Zheng ; Vijay Garg
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-16
DOI：10.4230/LIPIcs.DISC.2020.32
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We propose three algorithms for the Byzantine lattice agreement problem in synchronous systems. The first algorithm runs in min {3h(X) 6,6â^S{f_a} 6}) rounds and takes O(nÂ² min{h(X), â^S{f_a}}) messages, where h(X) is the height of the input lattice X, n is the total number of processes in the system, f is the maximum number of Byzantine processes such that n â¥ 3f 1 and f_a â¤ f is the actual number of Byzantine processes in an execution. The second algorithm takes 3log n 3 rounds and O(nÂ² log n) messages. The third algorithm takes 4 log f 3 rounds and O(nÂ² log f) messages. All algorithms can tolerate f < n/3 Byzantine failures. This is the first work for the Byzantine lattice agreement problem in synchronous systems which achieves logarithmic rounds. In our algorithms, we apply a slightly modified version of the Gradecast algorithm given by Feldman et al [Feldman and Micali, 1988] as a building block. If we use the Gradecast algorithm for authenticated setting given by Katz et al [Katz and Koo, 2006], we obtain algorithms for the Byzantine lattice agreement problem in authenticated settings and tolerate f < n/2 failures.
关键词：Lattice agreement; Byzantine Failure; Gradecast