License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.32
URN: urn:nbn:de:0030-drops-131106
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13110/
Go to the corresponding LIPIcs Volume Portal

Zheng, Xiong ; Garg, Vijay

Byzantine Lattice Agreement in Synchronous Message Passing Systems

pdf-format:
LIPIcs-DISC-2020-32.pdf (0.5 MB)

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:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13110},
  URN =		{urn:nbn:de:0030-drops-131106},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI