The Fault-Tolerant Cluster-Sending Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

The Fault-Tolerant Cluster-Sending Problem

  • Conference paper
  • First Online:
Foundations of Information and Knowledge Systems (FoIKS 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS))

Abstract

The emergence of blockchains is fueling the development of resilient data management systems that can deal with Byzantine failures due to crashes, bugs, or even malicious behavior. As traditional resilient systems lack the scalability required for modern data, several recent systems explored using sharding. Enabling these sharded designs requires two basic primitives: a primitive to reliably make decisions within a cluster and a primitive to reliably communicate between clusters. Unfortunately, such communication has not yet been formally studied.

In this work, we improve on this situation by formalizing the cluster-sending problem: the problem of sending a message from one resilient system to another in a fault-tolerant manner. We also establish lower bounds on the complexity of cluster-sending under both crashes and Byzantine failures. Finally, we present worst-case optimal cluster-sending protocols that meet these lower bounds in practical settings. As such, our work provides a strong foundation for the future development of sharded resilient data management systems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8007
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10009
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Example 1 showed that the impact of faulty replicas is minimal if we minimize the number of messages each replica exchanges. Let \(\mathbf {n}_{\mathcal {C}_1} > \mathbf {n}_{\mathcal {C}_2}\). If the number of messages sent to \(\mathbf {n}_{\mathcal {C}_2}\) is not a multiple of \(\mathbf {n}_{\mathcal {C}_2}\), then minimizing the number of messages received by each replica in \(\mathbf {n}_{\mathcal {C}_2}\) means that some replicas in \(\mathbf {n}_{\mathcal {C}_2}\) will receive one more message than others: each replica in \(\mathbf {n}_{\mathcal {C}_2}\) will receive at least \(q_1\) messages, while the term \(r_1 + \mathbf {f}_{\mathcal {C}_2} {\text {sgn}}r_1\) specifies the number of replicas in \(\mathbf {n}_{\mathcal {C}_2}\) that will receive \(q_1+1\) messages.

  2. 2.

    Tolerating Byzantine failures in an environment with replica signatures leads to an asymmetry between the sending cluster \(\mathcal {C}_1\), in which \(2\mathbf {f}_{\mathcal {C}_1} + 1\) replicas need to send, and the receiving cluster \(\mathcal {C}_2\), in which only \(\mathbf {f}_{\mathcal {C}_2}+1\) replicas need to receive. This asymmetry results in two distinct cases based on the relative cluster sizes.

References

  1. Al-Bassam, M., Sonnino, A., Bano, S., Hrycyszyn, D., Danezis, G.: Chainspace: a sharded smart contracts platform (2017). http://arxiv.org/abs/1708.03778

  2. Castro, M., Liskov, B.: Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst. 20(4), 398–461 (2002). https://doi.org/10.1145/571637.571640

    Article  Google Scholar 

  3. Dang, H., Dinh, T.T.A., Loghin, D., Chang, E.C., Lin, Q., Ooi, B.C.: Towards scaling blockchain systems via sharding. In: Proceedings of the 2019 International Conference on Management of Data. pp. 123–140. ACM (2019). https://doi.org/10.1145/3299869.3319889

  4. Dolev, D., Strong, H.R.: Authenticated algorithms for byzantine agreement. SIAM J. Comput. 12(4), 656–666 (1983). https://doi.org/10.1137/0212045

    Article  MathSciNet  MATH  Google Scholar 

  5. Gordon, W.J., Catalini, C.: Blockchain technology for healthcare: Facilitating the transition to patient-driven interoperability. Comput. Struct. Biotechnol. J. 16, 224–230 (2018). https://doi.org/10.1016/j.csbj.2018.06.003

    Article  Google Scholar 

  6. Gupta, S., Hellings, J., Sadoghi, M.: Fault-Tolerant distributed transactions on Blockchain. Synthesis Lectures on Data Management, Morgan & Claypool (2021). https://doi.org/10.1007/978-3-031-01877-0

  7. Gupta, S., Hellings, J., Sadoghi, M.: RCC: resilient concurrent consensus for high-throughput secure transaction processing. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 1392–1403. IEEE (2021). https://doi.org/10.1109/ICDE51399.2021.00124

  8. Gupta, S., Rahnama, S., Hellings, J., Sadoghi, M.: ResilientDB: global scale resilient blockchain fabric. Proc. VLDB Endow. 13(6), 868–883 (2020). https://doi.org/10.14778/3380750.3380757

  9. Gupta, S., Rahnama, S., Hellings, J., Sadoghi, M.: Proof-of-execution: reaching consensus through fault-tolerant speculation. In: Proceedings of the 24th International Conference on Extending Database Technology (EDBT), pp. 301–312. OpenProceedings.org (2021). https://doi.org/10.5441/002/edbt.2021.27

  10. Hellings, J., Sadoghi, M.: ByShard: sharding in a byzantine environment. Proc. VLDB Endow. 14(11), 2230–2243 (2021). https://doi.org/10.14778/3476249.3476275

  11. Herlihy, M.: Atomic cross-chain swaps. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. pp. 245–254. ACM (2018). https://doi.org/10.1145/3212734.3212736

  12. Herlihy, M., Liskov, B., Shrira, L.: Cross-chain deals and adversarial commerce. Proc. VLDB Endow. 13(2), 100–113 (2019). https://doi.org/10.14778/3364324.3364326

  13. Kamel Boulos, M.N., Wilson, J.T., Clauson, K.A.: Geospatial blockchain: promises, challenges, and scenarios in health and healthcare. Int. J. Health Geogr. 17(1), 1211–1220 (2018). https://doi.org/10.1186/s12942-018-0144-x

    Article  Google Scholar 

  14. Lao, L., Li, Z., Hou, S., Xiao, B., Guo, S., Yang, Y.: A survey of IoT applications in blockchain systems: architecture, consensus, and traffic modeling. ACM Comput. Surv. 53(1) (2020). https://doi.org/10.1145/3372136

  15. Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V.: Handbook of Applied Cryptography, 1st edn. CRC Press Inc., Boca Raton (1996)

    Google Scholar 

  16. Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system. https://bitcoin.org/en/bitcoin-paper

  17. Özsu, M.T., Valduriez, P.: Principles of Distributed Database Systems. (2020). https://doi.org/10.1007/978-3-030-26253-2

    Article  Google Scholar 

  18. Rejeb, A., Keogh, J.G., Zailani, S., Treiblmaier, H., Rejeb, K.: Blockchain technology in the food industry: a review of potentials, challenges and future research directions. Logistics 4(4) (2020). https://doi.org/10.3390/logistics4040027

  19. Shoup, V.: Practical threshold signatures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 207–220. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_15

    Chapter  Google Scholar 

  20. Treiblmaier, H., Beck, R. (eds.): Business Transformation Through Blockchain. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-98911-2

  21. Wood, G.: Ethereum: a secure decentralised generalised transaction ledger. https://gavwood.com/paper.pdf, EIP-150 revision

  22. Wu, M., Wang, K., Cai, X., Guo, S., Guo, M., Rong, C.: A comprehensive survey of blockchain: from theory to IoT applications and beyond. IEEE Internet Things J. 6(5), 8114–8154 (2019). https://doi.org/10.1109/JIOT.2019.2922538

    Article  Google Scholar 

  23. Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: HotStuff: BFT consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 347–356. ACM (2019). https://doi.org/10.1145/3293611.3331591

  24. Zakhary, V., Agrawal, D., El Abbadi, A.: Atomic commitment across blockchains. Proc. VLDB Endow. 13(9), 1319–1331 (2020). https://doi.org/10.14778/3397230.3397231

Download references

Author information

Authors and Affiliations

  1. McMaster University, 1280 Main St. W., Hamilton, ON, L8S 4L7, Canada

    Jelle Hellings

  2. Exploratory Systems Lab, Department of Computer Science, University of California, Davis, USA

    Mohammad Sadoghi

Authors
  1. Jelle Hellings
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammad Sadoghi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jelle Hellings .

Editor information

Editors and Affiliations

  1. Université d'Artois and CNRS, Lens, France

    Ivan Varzinczak

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hellings, J., Sadoghi, M. (2022). The Fault-Tolerant Cluster-Sending Problem. In: Varzinczak, I. (eds) Foundations of Information and Knowledge Systems. FoIKS 2022. Lecture Notes in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-031-11321-5_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-11321-5_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-11320-8

  • Online ISBN: 978-3-031-11321-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation