Document Open Access Logo

Byzantine Lattice Agreement in Synchronous Message Passing Systems

Authors Xiong Zheng, Vijay Garg

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.32.pdf
  • Filesize: 493 kB
  • 16 pages

Document Identifiers

Author Details

Xiong Zheng
  • Electrical and Computer Engineering, University of Texas at Austin, TX, USA
Vijay Garg
  • Electrical and Computer Engineering, University of Texas at Austin, TX, USA

Funding

  • Garg, Vijay: This work was supported in parts by the National Science Foundation Grants CNS-1812349, CNS-1563544, and the Cullen Trust Endowed Professorship.

Cite AsGet BibTex

Xiong Zheng and Vijay Garg. Byzantine Lattice Agreement in Synchronous Message Passing Systems. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.32

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Lattice agreement
  • Byzantine Failure
  • Gradecast

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM (JACM), 40(4):873-890, 1993. Google Scholar
  2. Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agreement. Distributed Computing, 8(3):121-132, 1995. Google Scholar
  3. Hagit Attiya and Ophir Rachman. Atomic snapshots in o (n log n) operations. SIAM Journal on Computing, 27(2):319-340, 1998. Google Scholar
  4. Michael Ben-Or, Danny Dolev, and Ezra N Hoch. Simple gradecast based algorithms. arXiv preprint arXiv:1007.1049, 2010. Google Scholar
  5. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  6. B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, Cambridge, UK, 1990. Google Scholar
  7. Giuseppe Antonio Di Luna, Emmanuelle Anceaume, Silvia Bonomi, and Leonardo Querzoni. Synchronous byzantine lattice agreement in 𝒪(log f) rounds. arXiv preprint arXiv:2001.02670, 2020. Google Scholar
  8. Giuseppe Antonio Di Luna, Emmanuelle Anceaume, and Leonardo Querzoni. Byzantine generalized lattice agreement. arXiv preprint arXiv:1910.05768, 2019. Google Scholar
  9. Jose M Faleiro, Sriram Rajamani, Kaushik Rajan, G Ramalingam, and Kapil Vaswani. Generalized lattice agreement. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 125-134. ACM, 2012. Google Scholar
  10. Paul Feldman and Silvio Micali. Optimal algorithms for Byzantine agreement. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 148-161. ACM, 1988. Google Scholar
  11. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382, 1985. Google Scholar
  12. Jonathan Katz and Chiu-Yuen Koo. On expected constant-round protocols for byzantine agreement. In Annual International Cryptology Conference, pages 445-462. Springer, 2006. Google Scholar
  13. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382-401, 1982. Google Scholar
  14. Marios Mavronicolasa. A bound on the rounds to reach lattice agreement. http://www.cs.ucy.ac.cy/ mavronic/pdf/lattice.pdf, 2018. Google Scholar
  15. Thomas Nowak and Joel Rybicki. Byzantine approximate agreement on graphs. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  16. Jan Skrzypczak, Florian Schintke, and Thorsten Schütt. Linearizable state machine replication of state-based crdts without logs. arXiv preprint arXiv:1905.08733, 2019. Google Scholar
  17. TK Srikanth and Sam Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80-94, 1987. Google Scholar
  18. Xiong Zheng and Vijay Garg. Byzantine lattice agreement in synchronous systems. arXiv preprint arXiv:1910.14141, 2019. Google Scholar
  19. Xiong Zheng and Vijay Garg. Byzantine lattice agreement in asynchronous systems. arXiv preprint arXiv:2002.06779, 2020. Google Scholar
  20. Xiong Zheng, Vijay K. Garg, and John Kaippallimalil. Linearizable Replicated State Machines With Lattice Agreement. In Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller, editors, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), volume 153 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1-29:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  21. Xiong Zheng, Changyong Hu, and Vijay K Garg. Lattice agreement in message passing systems. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact