Document Open Access Logo

Coordination-Free Byzantine Replication with Minimal Communication Costs

Authors Jelle Hellings, Mohammad Sadoghi

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2020.17.pdf
  • Filesize: 0.65 MB
  • 20 pages

Document Identifiers

Author Details

Jelle Hellings
  • Exploratory Systems Lab, Department of Computer Science, University of California, Davis, Davis, CA 95616-8562, USA
Mohammad Sadoghi
  • Exploratory Systems Lab, Department of Computer Science, University of California, Davis, Davis, CA 95616-8562, USA

Cite As Get BibTex

Jelle Hellings and Mohammad Sadoghi. Coordination-Free Byzantine Replication with Minimal Communication Costs. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICDT.2020.17

Abstract

State-of-the-art fault-tolerant and federated data management systems rely on fully-replicated designs in which all participants have equivalent roles. Consequently, these systems have only limited scalability and are ill-suited for high-performance data management. As an alternative, we propose a hierarchical design in which a Byzantine cluster manages data, while an arbitrary number of learners can reliable learn these updates and use the corresponding data.
To realize our design, we propose the delayed-replication algorithm, an efficient solution to the Byzantine learner problem that is central to our design. The delayed-replication algorithm is coordination-free, scalable, and has minimal communication cost for all participants involved. In doing so, the delayed-broadcast algorithm opens the door to new high-performance fault-tolerant and federated data management systems. To illustrate this, we show that the delayed-replication algorithm is not only useful to support specialized learners, but can also be used to reduce the overall communication cost of permissioned blockchains and to improve their storage scalability.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Information systems → Distributed database transactions
Keywords
  • Byzantine learner
  • coordination-free checkpoint protocol
  • delayed-replication
  • information dispersal
  • consensus

Metrics

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

Supplementary Materials

References

  1. 2ndQuadrant. Postgres-XL: Open source scalable SQL database cluster. URL: https://www.postgres-xl.org/.
  2. Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, and Julien Stern. Scalable Secure Storage When Half the System Is Faulty. Information and Computation, 174(2):203-213, 2002. URL: https://doi.org/10.1006/inco.2002.3148.
  3. Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, and Julien Stern. Addendum to "Scalable secure storage when half the system is faulty". Information and Computation, 205(7):1114-1116, 2007. URL: https://doi.org/10.1016/j.ic.2006.02.007.
  4. Yair Amir, Claudiu Danilov, Danny Dolev, Jonathan Kirsch, John Lane, Cristina Nita-Rotaru, Josh Olsen, and David Zage. Steward: Scaling Byzantine Fault-Tolerant Replication to Wide Area Networks. IEEE Transactions on Dependable and Secure Computing, 7(1):80-93, 2010. URL: https://doi.org/10.1109/TDSC.2008.53.
  5. Mohammad Javad Amiri, Divyakant Agrawal, and Amr El Abbadi. CAPER: A cross-application permissioned blockchain. Proceedings of the VLDB Endowment, 12(11):1385-1398, 2019. URL: https://doi.org/10.14778/3342263.3342275.
  6. Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolić, Sharon Weed Cocco, and Jason Yellick. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. In Proceedings of the Thirteenth EuroSys Conference, pages 30:1-30:15. ACM, 2018. URL: https://doi.org/10.1145/3190508.3190538.
  7. GSM Association. Blockchain for Development: Emerging Opportunities for Mobile, Identity and Aid, 2017. URL: https://www.gsma.com/mobilefordevelopment/wp-content/uploads/2017/12/Blockchain-for-Development.pdf.
  8. Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knežević, Vivien Quéma, and Marko Vukolić. The Next 700 BFT Protocols. ACM Transactions on Computer Systems, 32(4):12:1-12:45, 2015. URL: https://doi.org/10.1145/2658994.
  9. Pierre-Louis Aublin, Sonia Ben Mokhtar, and Vivien Quéma. RBFT: Redundant byzantine fault tolerance. In 2013 IEEE 33rd International Conference on Distributed Computing Systems, pages 297-306. IEEE, 2013. URL: https://doi.org/10.1109/ICDCS.2013.53.
  10. Christian Berger and Hans P. Reiser. Scaling Byzantine Consensus: A Broad Analysis. In Proceedings of the 2nd Workshop on Scalable and Resilient Infrastructures for Distributed Ledgers, SERIAL'18, pages 13-18. ACM, 2018. URL: https://doi.org/10.1145/3284764.3284767.
  11. Burkhard Blechschmidt. Blockchain in Europe: Closing the Strategy Gap. Technical report, Cognizant Consulting, 2018. URL: https://www.cognizant.com/whitepapers/blockchain-in-europe-closing-the-strategy-gap-codex3320.pdf.
  12. Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing, volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-1:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.1.
  13. Michael Casey, Jonah Crane, Gary Gensler, Simon Johnson, and Neha Narula. The Impact of Blockchain Technology on Finance: A Catalyst for Change. Technical report, International Center for Monetary and Banking Studies, 2018. URL: https://www.cimb.ch/uploads/1/1/5/4/115414161/geneva21_1.pdf.
  14. Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, pages 173-186. USENIX Association, 1999. Google Scholar
  15. Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Transactions on Computer Systems, 20(4):398-461, 2002. URL: https://doi.org/10.1145/571637.571640.
  16. Christie’s. Major Collection of the Fall Auction Season to be Recorded with Blockchain Technology, 2018. URL: https://www.christies.com/presscenter/pdf/9160/RELEASE_ChristiesxArtoryxEbsworth_9160_1.pdf.
  17. Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, pages 153-168. USENIX Association, 2009. Google Scholar
  18. Cindy Compert, Maurizio Luinetti, and Bertrand Portier. Blockchain and GDPR: How blockchain could address five areas associated with GDPR compliance. Technical report, IBM Security, 2018. URL: https://public.dhe.ibm.com/common/ssi/ecm/61/en/61014461usen/security-ibm-security-solutions-wg-white-paper-external-61014461usen-20180319.pdf.
  19. Oracle Corporation. Maximize Availability with Oracle Database 18c. URL: https://www.oracle.com/technetwork/database/availability/maximum-availability-wp-18c-4403435.pdf.
  20. Oracle Corporation. MySQL - MySQL 8.0 reference manual: 17 replication. URL: https://dev.mysql.com/doc/refman/8.0/en/replication.html.
  21. Alex de Vries. Bitcoin’s Growing Energy Problem. Joule, 2(5):801-805, 2018. URL: https://doi.org/10.1016/j.joule.2018.04.016.
  22. Microsoft Docs. SQL Server replication. URL: https://docs.microsoft.com/en-us/sql/relational-databases/replication/sql-server-replication.
  23. Wayne W. Eckerson. Data quality and the bottom line: Achieving Business Success through a Commitment to High Quality Data. Technical report, The Data Warehousing Institute, 101communications LLC., 2002. Google Scholar
  24. Muhammad El-Hindi, Carsten Binnig, Arvind Arasu, Donald Kossmann, and Ravi Ramamurthy. BlockchainDB: A shared database on blockchains. Proceedings of the VLDB Endowment, 12(11):1597-1609, 2019. URL: https://doi.org/10.14778/3342263.3342636.
  25. Muhammad El-Hindi, Martin Heyden, Carsten Binnig, Ravi Ramamurthy, Arvind Arasu, and Donald Kossmann. BlockchainDB - towards a shared database on blockchains. In Proceedings of the 2019 International Conference on Management of Data, pages 1905-1908. ACM, 2019. URL: https://doi.org/10.1145/3299869.3320237.
  26. The Apache Software Foundation. Apache Kafka: A distributed streaming platform. URL: https://kafka.apache.org/.
  27. Lan Ge, Christopher Brewster, Jacco Spek, Anton Smeenk, and Jan Top. Blockchain for agriculture and food: Findings from the pilot study. Technical report, Wageningen University, 2017. URL: https://www.wur.nl/nl/Publicatie-details.htm?publicationId=publication-way-353330323634.
  28. Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51-68. ACM, 2017. URL: https://doi.org/10.1145/3132747.3132757.
  29. William J. Gordon and Christian Catalini. Blockchain Technology for Healthcare: Facilitating the Transition to Patient-Driven Interoperability. Computational and Structural Biotechnology Journal, 16:224-230, 2018. URL: https://doi.org/10.1016/j.csbj.2018.06.003.
  30. Jim Gray. Notes on Data Base Operating Systems. In Operating Systems, An Advanced Course, pages 393-481. Springer-Verlag, 1978. URL: https://doi.org/10.1007/3-540-08755-9_9.
  31. Andy Greenberg. The Untold Story of NotPetya, the Most Devastating Cyberattack in History, 2018. URL: https://www.wired.com/story/notpetya-cyberattack-ukraine-russia-code-crashed-the-world/.
  32. The PostgreSQL Global Development Group. PostgreSQL documentation: Chapter 26. high availability, load balancing, and replication. URL: https://www.postgresql.org/docs/current/static/high-availability.html.
  33. Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: a scalable and decentralized trust infrastructure, 2019. URL: https://arxiv.org/abs/1804.01626.
  34. Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. Brief Announcement: Revisiting Consensus Protocols through Wait-Free Parallelization. In 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1-44:3. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.44.
  35. Suyash Gupta and Mohammad Sadoghi. Blockchain Transaction Processing, pages 1-11. Springer International Publishing, 2018. URL: https://doi.org/10.1007/978-3-319-63962-8_333-1.
  36. Suyash Gupta and Mohammad Sadoghi. EasyCommit: A non-blocking two-phase commit protocol. In Proceedings of the 21st International Conference on Extending Database Technology. Open Proceedings, 2018. URL: https://doi.org/10.5441/002/edbt.2018.15.
  37. Jelle Hellings and Mohammad Sadoghi. Brief Announcement: The Fault-Tolerant Cluster-Sending Problem. In 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1-45:3. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.45.
  38. Maurice Herlihy. Blockchains from a Distributed Computing Perspective. Communications of the ACM, 62(2):78-85, 2019. URL: https://doi.org/10.1145/3209623.
  39. Thomas N. Herzog, Fritz J. Scheuren, and William E. Winkler. Data Quality and Record Linkage Techniques. Springer New York, 2007. URL: https://doi.org/10.1007/0-387-69505-2.
  40. Matt Higginson, Johannes-Tobias Lorenz, Björn Münstermann, and Peter Braad Olesen. The promise of blockchain. Technical report, McKinsey&Company, 2017. URL: https://www.mckinsey.com/industries/financial-services/our-insights/the-promise-of-blockchain.
  41. Maged N. Kamel Boulos, James T. Wilson, and Kevin A. Clauson. Geospatial blockchain: promises, challenges, and scenarios in health and healthcare. International Journal of Health Geographics, 17(1):1211-1220, 2018. URL: https://doi.org/10.1186/s12942-018-0144-x.
  42. 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 Proceedings of the 7th ACM European Conference on Computer Systems, pages 295-308. ACM, 2012. URL: https://doi.org/10.1145/2168836.2168866.
  43. Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall/CRC, 2nd edition, 2014. Google Scholar
  44. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative byzantine fault tolerance. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, pages 45-58. ACM, 2007. URL: https://doi.org/10.1145/1294261.1294267.
  45. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative byzantine fault tolerance. ACM Transactions on Computer Systems, 27(4):7:1-7:39, 2009. URL: https://doi.org/10.1145/1658357.1658358.
  46. Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks (1976), 2(2):95-114, 1978. URL: https://doi.org/10.1016/0376-5075(78)90045-4.
  47. Leslie Lamport. Paxos Made Simple. ACM SIGACT News, Distributed Computing Column 5, 32(4):51-58, 2001. URL: https://doi.org/10.1145/568425.568433.
  48. Jian Liu, Wenting Li, Ghassan O. Karame, and N. Asokan. Scalable Byzantine Consensus via Hardware-Assisted Secret Sharing. IEEE Transactions on Computers, 68(1):139-151, 2019. URL: https://doi.org/10.1109/TC.2018.2860009.
  49. Jean-Philippe Martin and Lorenzo Alvisi. Fast Byzantine Consensus. IEEE Transactions on Dependable and Secure Computing, 3(3):202-215, 2006. URL: https://doi.org/10.1109/TDSC.2006.35.
  50. Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot. Handbook of Applied Cryptography. CRC Press, Inc., 1st edition, 1996. Google Scholar
  51. Ralph C. Merkle. A Digital Signature Based on a Conventional Encryption Function. In Advances in Cryptology - CRYPTO '87, pages 369-378. Springer Berlin Heidelberg, 1988. URL: https://doi.org/10.1007/3-540-48184-2_32.
  52. Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. URL: https://bitcoin.org/en/bitcoin-paper.
  53. Arvind Narayanan and Jeremy Clark. Bitcoin’s Academic Pedigree. Communications of the ACM, 60(12):36-45, 2017. URL: https://doi.org/10.1145/3132259.
  54. Senthil Nathan, Chander Govindarajan, Adarsh Saraf, Manish Sethi, and Praveen Jayachandran. Blockchain Meets Database: Design and Implementation of a Blockchain Relational Database. Proceedings of the VLDB Endowment, 12(11):1539-1552, 2019. URL: https://doi.org/10.14778/3342263.3342632.
  55. Faisal Nawab and Mohammad Sadoghi. Blockplane: A Global-Scale Byzantizing Middleware. In 35th International Conference on Data Engineering (ICDE), pages 124-135. IEEE, 2019. URL: https://doi.org/10.1109/ICDE.2019.00020.
  56. Dick O'Brie. Internet Security Threat Report: Ransomware 2017, An ISTR Special Report. Technical report, Symantec, 2017. URL: https://www.symantec.com/content/dam/symantec/docs/security-center/white-papers/istr-ransomware-2017-en.pdf.
  57. The Council of Economic Advisers. The Cost of Malicious Cyber Activity to the U.S. Economy. Technical report, Executive Office of the President of the United States, 2018. URL: https://www.whitehouse.gov/wp-content/uploads/2018/03/The-Cost-of-Malicious-Cyber-Activity-to-the-U.S.-Economy.pdf.
  58. National Audit Office. Investigation: WannaCry cyber attack and the NHS, 2018. URL: https://www.nao.org.uk/report/investigation-wannacry-cyber-attack-and-the-nhs/.
  59. Michael Okun. Byzantine Agreement, pages 255-259. Springer New York, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_60.
  60. M. Tamer Özsu and Patrick Valduriez. Principles of Distributed Database Systems. Springer New York, 3th edition, 2011. Google Scholar
  61. Michael Pisa and Matt Juden. Blockchain and Economic Development: Hype vs. Reality. Technical report, Center for Global Development, 2017. URL: https://www.cgdev.org/publication/blockchain-and-economic-development-hype-vs-reality.
  62. PwC. Blockchain - an opportunity for energy producers and consumers?, 2016. URL: https://www.pwc.com/gx/en/industries/energy-utilities-resources/publications/opportunity-for-energy-producers.html.
  63. Michael O. Rabin. Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance. Journal of the ACM, 36(2):335-348, 1989. URL: https://doi.org/10.1145/62044.62050.
  64. Thomas C. Redman. The Impact of Poor Data Quality on the Typical Enterprise. Communications of the ACM, 41(2):79-82, 1998. URL: https://doi.org/10.1145/269012.269025.
  65. Scott Ruoti, Ben Kaiser, Arkady Yerukhimovich, Jeremy Clark, and Robert Cunningham. Blockchain Technology: What is It Good For? Communications of the ACM, 63(1):46–-53, 2019. URL: https://doi.org/10.1145/3369752.
  66. Victor Shoup. Practical Threshold Signatures. In Advances in Cryptology - EUROCRYPT 2000, pages 207-220. Springer Berlin Heidelberg, 2000. URL: https://doi.org/10.1007/3-540-45539-6_15.
  67. Dale Skeen. A Quorum-Based Commit Protocol. Technical report, Cornell University, 1982. Google Scholar
  68. Symantec. Internet Security Threat Report, Volume 32, 2018. URL: https://www.symantec.com/content/dam/symantec/docs/reports/istr-23-2018-en.pdf.
  69. Gerard Tel. Introduction to Distributed Algorithms. Cambridge University Press, 2nd edition, 2001. Google Scholar
  70. Maarten van Steen and Andrew S. Tanenbaum. Distributed Systems. Maarten van Steen, 3th edition, 2017. URL: https://www.distributed-systems.net/.
  71. Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Verissimo. Efficient Byzantine Fault-Tolerance. IEEE Transactions on Computers, 62(1):16-30, 2013. URL: https://doi.org/10.1109/TC.2011.221.
  72. Harald Vranken. Sustainability of bitcoin and blockchains. Current Opinion in Environmental Sustainability, 28:1-9, 2017. URL: https://doi.org/10.1016/j.cosust.2017.04.011.
  73. Gavin Wood. Ethereum: a secure decentralised generalised transaction ledger. EIP-150 revision. URL: https://gavwood.com/paper.pdf.
  74. Yin Yang. LinBFT: Linear-communication byzantine fault tolerance for public blockchains, 2018. URL: https://arxiv.org/abs/1807.01829.
  75. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347-356. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331591.
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 About DROPS Imprint Privacy Contact