Abstract
We propose three algorithms for the Byzantine lattice agreement problem in synchronous systems. The first algorithm runs in min {3h(X) + 6,6√{f_a} + 6}) rounds and takes O(n² min{h(X), √{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.
BibTeX  Entry
@InProceedings{zheng_et_al:LIPIcs:2020:13110,
author = {Xiong Zheng and Vijay Garg},
title = {{Byzantine Lattice Agreement in Synchronous Message Passing Systems}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {32:132:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771689},
ISSN = {18688969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13110},
URN = {urn:nbn:de:0030drops131106},
doi = {10.4230/LIPIcs.DISC.2020.32},
annote = {Keywords: Lattice agreement, Byzantine Failure, Gradecast}
}
Keywords: 

Lattice agreement, Byzantine Failure, Gradecast 
Collection: 

34th International Symposium on Distributed Computing (DISC 2020) 
Issue Date: 

2020 
Date of publication: 

07.10.2020 