Document Open Access Logo

Frugal Byzantine Computing

Authors Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, Igor Zablotchi

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.3.pdf
  • Filesize: 0.76 MB
  • 19 pages

Document Identifiers

Author Details

Marcos K. Aguilera
  • VMware Research, Palo Alto, CA, USA
Naama Ben-David
  • VMware Research, Palo Alto, CA, USA
Rachid Guerraoui
  • EPFL, Lausanne, Switzerland
Dalia Papuc
  • EPFL, Lausanne, Switzerland
Athanasios Xygkis
  • EPFL, Lausanne, Switzerland
Igor Zablotchi
  • MIT, Cambridge, MA, USA

Cite AsGet BibTex

Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi. Frugal Byzantine Computing. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.3

Abstract

Traditional techniques for handling Byzantine failures are expensive: digital signatures are too costly, while using 3f+1 replicas is uneconomical (f denotes the maximum number of Byzantine processes). We seek algorithms that reduce the number of replicas to 2f+1 and minimize the number of signatures. While the first goal can be achieved in the message-and-memory model, accomplishing the second goal simultaneously is challenging. We first address this challenge for the problem of broadcasting messages reliably. We study two variants of this problem, Consistent Broadcast and Reliable Broadcast, typically considered very close. Perhaps surprisingly, we establish a separation between them in terms of signatures required. In particular, we show that Consistent Broadcast requires at least 1 signature in some execution, while Reliable Broadcast requires O(n) signatures in some execution. We present matching upper bounds for both primitives within constant factors. We then turn to the problem of consensus and argue that this separation matters for solving consensus with Byzantine failures: we present a practical consensus algorithm that uses Consistent Broadcast as its main communication primitive. This algorithm works for n = 2f+1 and avoids signatures in the common case - properties that have not been simultaneously achieved previously. Overall, our work approaches Byzantine computing in a frugal manner and motivates the use of Consistent Broadcast - rather than Reliable Broadcast - as a key primitive for reaching agreement.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Distributed algorithms
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Reliable Broadcast
  • Consistent Broadcast
  • Consensus
  • Byzantine Failure
  • Message-and-memory

Metrics

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

Related Versions

References

  1. Marcos K Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg. Passing messages while sharing memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018. Google Scholar
  2. Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra Marathe, and Igor Zablotchi. The impact of RDMA on agreement. In ACM Symposium on Principles of Distributed Computing (PODC), pages 409-418, 2019. Google Scholar
  3. Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra J Marathe, Athanasios Xygkis, and Igor Zablotchi. Microsecond consensus for microsecond applications. In USENIX Symposium on Operating System Design and Implementation (OSDI), pages 599-616, 2020. Google Scholar
  4. Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi. Frugal Byzantine Computing. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.01330.
  5. Noga Alon, Michael Merritt, Omer Reingold, Gadi Taubenfeld, and Rebecca N Wright. Tight bounds for shared memory systems accessed by Byzantine processes. Distributed computing (DIST), 18(2), 2005. Google Scholar
  6. Hagit Attiya, Sweta Kumari, and Noa Schiller. Optimal resilience in systems that mix shared memory and message passing. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.10846.
  7. Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knežević, Vivien Quéma, and Marko Vukolić. The next 700 BFT protocols. ACM Transactions on Computer Systems (TOCS), 32(4), 2015. Google Scholar
  8. Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. Fast and robust memory reclamation for concurrent data structures. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 349-359, 2016. Google Scholar
  9. Naama Ben-David and Kartik Nayak. Brief announcement: Classifying trusted hardware via unidirectional communication. In ACM Symposium on Principles of Distributed Computing (PODC), 2021. Google Scholar
  10. Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 1983. Google Scholar
  11. Alysson Neves Bessani, Miguel Correia, Joni da Silva Fraga, and Lau Cheuk Lung. Sharing memory between Byzantine processes using policy-enforced tuple spaces. IEEE Transactions on Parallel and Distributed Systems, 20(3), 2009. Google Scholar
  12. Bitcoin Core Developers. Optimized C library for ECDSA signatures and secret/public key operations on curve secp256k1. URL: https://github.com/bitcoin-core/secp256k1.
  13. Zohir Bouzid, Damien Imbs, and Michel Raynal. A necessary condition for Byzantine k-set agreement. Information Processing Letters, 116(12), 2016. Google Scholar
  14. Gabriel Bracha. An asynchronous [(n-1)/3]-resilient consensus protocol. In ACM Symposium on Principles of Distributed Computing (PODC), pages 154-162, 1984. Google Scholar
  15. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2), 1987. Google Scholar
  16. Gabriel Bracha and Sam Toueg. Resilient consensus protocols. In Robert L. Probert, Nancy A. Lynch, and Nicola Santoro, editors, ACM Symposium on Principles of Distributed Computing (PODC), pages 12-26, 1983. Google Scholar
  17. Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM (JACM), 32(4), 1985. Google Scholar
  18. Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer, 2011. Google Scholar
  19. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference on Advances in Cryptology (CRYPTO), 2001. Google Scholar
  20. Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In USENIX Symposium on Operating System Design and Implementation (OSDI), 1999. Google Scholar
  21. Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398-461, 2002. URL: https://doi.org/10.1145/571637.571640.
  22. Certicom Research. Standards for efficient cryptography. https://www.secg.org/sec2-v2.pdf, 2010.
  23. Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM (JACM), 43(2), 1996. Google Scholar
  24. Byung-Gon Chun, Petros Maniatis, and Scott Shenker. Diverse replication for single-machine Byzantine-fault tolerance. In 2008 USENIX Annual Technical Conference, Boston, MA, USA, June 22-27, 2008. Proceedings, 2008. URL: http://www.usenix.org/events/usenix08/tech/full_papers/chun/chun.pdf.
  25. Byung-Gon Chun, Petros Maniatis, Scott Shenker, and John Kubiatowicz. Attested append-only memory: making adversaries stick to their word. In Proceedings of the 21st ACM Symposium on Operating Systems Principles 2007, SOSP 2007, Stevenson, Washington, USA, October 14-17, 2007, 2007. URL: https://doi.org/10.1145/1294261.1294280.
  26. Miguel Correia, Nuno Ferreira Neves, and Paulo Veríssimo. How to tolerate half less one Byzantine nodes in practical distributed systems. In 23rd International Symposium on Reliable Distributed Systems (SRDS 2004), 18-20 October 2004, Florianpolis, Brazil, 2004. URL: https://doi.org/10.1109/RELDIS.2004.1353018.
  27. Miguel Correia, Giuliana S Veronese, and Lau Cheuk Lung. Asynchronous Byzantine consensus with 2f+1 processes. In Proceedings of the 2010 ACM Symposium on Applied Computing, 2010. Google Scholar
  28. Dan Dobre and Neeraj Suri. One-step consensus with zero-degradation. In International Conference on Dependable Systems and Networks (DSN'06), 2006. Google Scholar
  29. Danny Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1):14-30, 1982. Google Scholar
  30. Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for Byzantine agreement. Journal of the ACM (JACM), 32(1):191-204, 1985. Google Scholar
  31. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2), 1988. Google Scholar
  32. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 1985. Google Scholar
  33. Vassos Hadzilacos, Xing Hu, and Sam Toueg. Optimal Register Construction in M&M Systems. In International Conference on Principles of Distributed Systems (OPODIS), volume 153, pages 28:1-28:16, 2020. Google Scholar
  34. Rüdiger Kapitza, Johannes Behl, Christian Cachin, Tobias Distler, Simon Kuhnle, Seyed Vahid Mohammadi, Wolfgang Schröder-Preikschat, and Klaus Stengel. CheapBFT: resource-efficient Byzantine fault tolerance. In European Conference on Computer Systems, Proceedings of the Seventh EuroSys Conference 2012, EuroSys '12, Bern, Switzerland, April 10-13, 2012, 2012. URL: https://doi.org/10.1145/2168836.2168866.
  35. Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults: preliminary version. ACM SIGACT News, 32(2), 2001. Google Scholar
  36. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: speculative Byzantine fault tolerance. In ACM Symposium on Operating Systems Principles (SOSP), 2007. Google Scholar
  37. Leslie Lamport. The weak Byzantine generals problem. Journal of the ACM (JACM), 30(3), 1983. Google Scholar
  38. Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2), 1998. Google Scholar
  39. Leslie Lamport. Fast Paxos. Distributed computing (DIST), 19(2), 2006. Google Scholar
  40. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3), 1982. Google Scholar
  41. linux-rdma. Rdma benchmarking utility. URL: https://github.com/linux-rdma/perftest.
  42. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996. Google Scholar
  43. Dahlia Malkhi, Michael Merritt, Michael K Reiter, and Gadi Taubenfeld. Objects shared by Byzantine processes. Distributed computing (DIST), 16(1), 2003. Google Scholar
  44. Mellanox. Network benchmarking utility. URL: https://github.com/Mellanox/sockperf.
  45. Achour Mostéfaoui, Moumen Hamouma, and Michel Raynal. Signature-free asynchronous Byzantine consensus with t < n/3 and o(n²) messages. In ACM Symposium on Principles of Distributed Computing (PODC), pages 2-9, 2014. Google Scholar
  46. Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2), 1980. Google Scholar
  47. Michel Raynal and Jiannong Cao. One for all and all for one: Scalable consensus in a hybrid communication model. In IEEE International Conference on Distributed Computing Systems (ICDCS), pages 464-471. IEEE, 2019. Google Scholar
  48. Michael K. Reiter. Secure agreement protocols: Reliable and atomic group multicast in Rampart. In Proceedings of the 2nd ACM Conference on Computer and Communications Security, pages 68–-80, 1994. URL: https://doi.org/10.1145/191177.191194.
  49. Blockchain hardware accelerator. https://www.xilinx.com/products/intellectual-property/1-175rk99.html. Accessed 2021-02-15.
  50. T. K. Srikanth and Sam Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed computing (DIST), 2(2):80-94, 1987. Google Scholar
  51. Shahar Timnat and Erez Petrank. A practical wait-free simulation for lock-free data structures. ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 49(8):357-368, 2014. Google Scholar
  52. Sam Toueg. Randomized Byzantine agreements. In ACM Symposium on Principles of Distributed Computing (PODC), pages 163-178, 1984. Google Scholar
  53. Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Veríssimo. Efficient Byzantine fault-tolerance. IEEE Trans. Computers, 62(1), 2013. URL: https://doi.org/10.1109/TC.2011.221.
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