Document Open Access Logo

Asynchronous Reconfiguration with Byzantine Failures

Authors Petr Kuznetsov, Andrei Tonkikh

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.27.pdf
  • Filesize: 0.53 MB
  • 17 pages

Document Identifiers

Author Details

Petr Kuznetsov
  • LTCI, Télécom Paris, Institut Polytechnique Paris, France
Andrei Tonkikh
  • National Research University Higher School of Economics, Saint-Petersburg, Russia

Cite AsGet BibTex

Petr Kuznetsov and Andrei Tonkikh. Asynchronous Reconfiguration with Byzantine Failures. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.27

Abstract

Replicated services are inherently vulnerable to failures and security breaches. In a long-running system, it is, therefore, indispensable to maintain a reconfiguration mechanism that would replace faulty replicas with correct ones. An important challenge is to enable reconfiguration without affecting the availability and consistency of the replicated data: the clients should be able to get correct service even when the set of service replicas is being updated. In this paper, we address the problem of reconfiguration in the presence of Byzantine failures: faulty replicas or clients may arbitrarily deviate from their expected behavior. We describe a generic technique for building asynchronous and Byzantine fault-tolerant reconfigurable objects: clients can manipulate the object data and issue reconfiguration calls without reaching consensus on the current configuration. With the help of forward-secure digital signatures, our solution makes sure that superseded and possibly compromised configurations are harmless, that slow clients cannot be fooled into reading stale data, and that Byzantine clients cannot cause a denial of service by flooding the system with reconfiguration requests. Our approach is modular and based on dynamic lattice agreement abstraction, and we discuss how to extend it to enable Byzantine fault-tolerant implementations of a large class of reconfigurable replicated services.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Reconfiguration
  • Asynchronous Models
  • Byzantine Faults

Metrics

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

Related Versions

References

  1. Marcos K Aguilera, Idit Keidar, Dahlia Malkhi, Jean-Philippe Martin, Alexander Shraer, et al. Reconfiguring replicated atomic storage: A tutorial. Bulletin of the EATCS, 102:84-108, 2010. Google Scholar
  2. Marcos Kawazoe Aguilera, Idit Keidar, Dahlia Malkhi, and Alexander Shraer. Dynamic atomic storage without consensus. J. ACM, 58(2):7:1-7:32, 2011. Google Scholar
  3. Eduardo Alchieri, Alysson Bessani, Fabíola Greve, and Joni da Silva Fraga. Efficient and modular consensus-free reconfiguration for fault-tolerant storage. In OPODIS, pages 26:1-26:17, 2017. Google Scholar
  4. Lorenzo Alvisi, Dahlia Malkhi, Evelyn Pierce, Michael K Reiter, and Rebecca N Wright. Dynamic byzantine quorum systems. In Proceeding International Conference on Dependable Systems and Networks. DSN 2000, pages 283-292. IEEE, 2000. Google Scholar
  5. James Aspnes, Hagit Attiya, and Keren Censor. Max registers, counters, and monotone circuits. In PODC, pages 36-45, 2009. Google Scholar
  6. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM (JACM), 42(1):124-142, 1995. Google Scholar
  7. Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, and Jennifer L. Welch. Emulating a shared register in a system that never stops changing. IEEE Trans. Parallel Distrib. Syst., 30(3):544-559, 2019. Google Scholar
  8. Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agreement. Distributed Comput., 8(3):121-132, 1995. Google Scholar
  9. Roberto Baldoni, Silvia Bonomi, Anne-Marie Kermarrec, and Michel Raynal. Implementing a register in a dynamic distributed system. In ICDCS, pages 639-647, 2009. Google Scholar
  10. Mihir Bellare and Sara K Miner. A forward-secure digital signature scheme. In Annual International Cryptology Conference, pages 431-448. Springer, 1999. Google Scholar
  11. Xavier Boyen, Hovav Shacham, Emily Shen, and Brent Waters. Forward-secure signatures with untrusted update. In Proceedings of the 13th ACM conference on Computer and communications security, pages 191-200, 2006. Google Scholar
  12. Eric A. Brewer. Towards robust distributed systems (abstract). In PODC, pages 7-, 2000. Google Scholar
  13. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011. Google Scholar
  14. Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key encryption scheme. Journal of Cryptology, 20(3):265-294, 2007. Google Scholar
  15. Manu Drijvers, Sergey Gorbunov, Gregory Neven, and Hoeteck Wee. Pixel: Multi-signatures for consensus. In 29th USENIX Security Symposium (USENIX Security 20), Boston, MA, August 2020. USENIX Association. URL: https://www.usenix.org/conference/usenixsecurity20/presentation/drijvers.
  16. Jose Faleiro, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam, and Kapil Vaswani. Generalized lattice agreement. In PODC, pages 125-134, 2012. Google Scholar
  17. 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
  18. Eli Gafni. Round-by-round fault detectors: Unifying synchrony and asynchrony. In PODC, pages 143-152, 1998. Google Scholar
  19. Eli Gafni and Dahlia Malkhi. Elastic configuration maintenance via a parsimonious speculating snapshot solution. In DISC, pages 140-153, 2015. Google Scholar
  20. David K. Gifford. Weighted voting for replicated data. In SOSP, pages 150-162, 1979. Google Scholar
  21. Seth Gilbert and Nancy Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):51-59, June 2002. Google Scholar
  22. Seth Gilbert, Nancy A Lynch, and Alexander A Shvartsman. Rambo: a robust, reconfigurable atomic memory service for dynamic networks. Distributed Computing, 23(4):225-272, 2010. Google Scholar
  23. Leander Jehl, Roman Vitenberg, and Hein Meling. Smartmerge: A new approach to reconfiguration for atomic storage. In DISC, pages 154-169, 2015. Google Scholar
  24. Anne-Marie Kermarrec and Maarten Van Steen. Gossiping in distributed systems. ACM SIGOPS operating systems review, 41(5):2-7, 2007. Google Scholar
  25. Saptaparni Kumar and Jennifer L. Welch. Byzantine-tolerant register in a system with continuous churn. CoRR, abs/1910.06716, 2019. URL: http://arxiv.org/abs/1910.06716.
  26. Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni. Reconfigurable lattice agreement and applications. In OPODIS, 2019. Google Scholar
  27. Petr Kuznetsov and Andrei Tonkikh. Asynchronous reconfiguration with byzantine failures. CoRR, abs/2005.13499, 2020. URL: https://arxiv.org/abs/2005.13499.
  28. Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. Reconfiguring a state machine. SIGACT News, 41(1):63-73, 2010. Google Scholar
  29. Dahlia Malkhi and Michael Reiter. Byzantine quorum systems. Distributed computing, 11(4):203-213, 1998. Google Scholar
  30. Tal Malkin, Daniele Micciancio, and Sara Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 400-417. Springer, 2002. Google Scholar
  31. J-P Martin and Lorenzo Alvisi. A framework for dynamic byzantine storage. In International Conference on Dependable Systems and Networks, 2004, pages 325-334. IEEE, 2004. Google Scholar
  32. Marc Shapiro, Nuno M. Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In SSS, pages 386-400, 2011. Google Scholar
  33. Alexander Spiegelman and Idit Keidar. On liveness of dynamic storage. In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers, pages 356-376, 2017. Google Scholar
  34. Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic reconfiguration: Abstraction and optimal asynchronous solution. In DISC, pages 40:1-40:15, 2017. 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