Document Open Access Logo

Byzantine Lattice Agreement in Asynchronous Systems

Authors Xiong Zheng, Vijay Garg

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.4.pdf
  • Filesize: 0.5 MB
  • 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 Asynchronous Systems. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.4

Abstract

We study the Byzantine lattice agreement (BLA) problem in asynchronous distributed message passing systems. In the BLA problem, each process proposes a value from a join semi-lattice and needs to output a value also in the lattice such that all output values of correct processes lie on a chain despite the presence of Byzantine processes. We present an algorithm for this problem with round complexity of O(log f) which tolerates f < n/5 Byzantine failures in the asynchronous setting without digital signatures, where n is the number of processes. This is the first algorithm which has logarithmic round complexity for this problem in asynchronous setting. Before our work, Di Luna et al give an algorithm for this problem which takes O(f) rounds and tolerates f < n/3 Byzantine failures. We also show how this algorithm can be modified to work in the authenticated setting (i.e., with digital signatures) to tolerate f < n/3 Byzantine failures.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Byzantine Lattice Agreement
  • Asynchronous

Metrics

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

Related Versions

References

  1. Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agreement. Distributed Computing, 8(3):121-132, 1995. Google Scholar
  2. Hagit Attiya and Ophir Rachman. Atomic snapshots in o (n log n) operations. SIAM Journal on Computing, 27(2):319-340, 1998. Google Scholar
  3. Martin Biely, Zarko Milosevic, Nuno Santos, and Andre Schiper. S-paxos: Offloading the leader for high throughput state machine replication. In 2012 IEEE 31st Symposium on Reliable Distributed Systems, pages 111-120. IEEE, 2012. Google Scholar
  4. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  5. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Inf. Comput., 105(1):132-158, 1993. Google Scholar
  6. Soma Chaudhuri, Maurice Herlihy, Nancy A Lynch, and Mark R Tuttle. Tight bounds for k-set agreement. Journal of the ACM (JACM), 47(5):912-943, 2000. 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. Danny Dolev and H Raymond Strong. Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983. Google Scholar
  10. 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
  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. Maurice Herlihy, Sergio Rajsbaum, and Mark R Tuttle. Unifying synchronous and asynchronous message-passing models. In Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pages 133-142, 1998. Google Scholar
  13. Marios Mavronicolasa. A bound on the rounds to reach lattice agreement. http://www.cs.ucy.ac.cy/ mavronic/pdf/lattice.pdf, 2018. Google Scholar
  14. 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
  15. Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2):228-234, 1980. Google Scholar
  16. Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In Symposium on Self-Stabilizing Systems, pages 386-400. Springer, 2011. Google Scholar
  17. 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
  18. Xiong Zheng and Vijay K Garg. Byzantine lattice agreement in synchronous systems. In 34nd International Symposium on Distributed Computing (DISC 2020), 2020. Google Scholar
  19. 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
  20. 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