Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Distributed Computing
Published in: Distributed Computing 6/2022

10-03-2022

Asynchronous reconfiguration with Byzantine failures

Authors: Petr Kuznetsov, Andrei Tonkikh

Published in: Distributed Computing | Issue 6/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 Byzantine lattice agreement abstraction, and we discuss how to extend it to enable Byzantine fault-tolerant implementations of a large class of reconfigurable replicated services.
previous article Special issue on DISC 2020
next article Making Byzantine consensus live

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
T is a parameter of the scheme and can be set arbitrarily large (with a modest overhead). We believe that \(T = 2^{32}\) or \(T = 2^{64}\) should be sufficient for most applications.
 
2
We assume that anyone who knows the id of a process also knows its public key. For example, the public key can be directly embedded into the identifier.
 
3
Additional care is needed to prevent the “slow reader” attack. See Sect. 6 for more details.
 
4
Recall that, unlike an operation, a function can be computed locally, without communicating with other processes, and the result only depends on the function’s input.
 
5
The analogy for the number of verifiable input configurations in crash fault-tolerant systems is the number of reconfiguration requests. In the context of Byzantine fault-tolerant systems, we have to talk about the number of verifiable input configurations instead because a single Byzantine client can simulate an infinite sequence of requests.
 
6
Indeed, set \( curVals \) at each correct replica can only grow, and the replicas only sign messages with the same set of verifiable input values as \( curVals \) (see lines 75–76)
 
7
If either p or q eventually halts or becomes Byzantine, their local histories are not required to converge.
 
Literature
1.
Aguilera, M.K., Keidar, I., Malkhi, D., Martin, J.-P., Shraer, A., et al.: Reconfiguring replicated atomic storage: a tutorial. Bull. EATCS 102, 84–108 (2010)MathSciNetMATH
2.
3.
Alchieri, E., Bessani, A., Greve, F., da Silva Fraga, J: Efficient and modular consensus-free reconfiguration for fault-tolerant storage. In: OPODIS, pp. 26:1–26:17 (2017)
4.
Alvisi, L., Malkhi, D., Pierce, E., Reiter, M.K., Wright, R.N.: Dynamic byzantine quorum systems. In: Proceeding International Conference on Dependable Systems and Networks. DSN 2000, pp. 283–292. IEEE (2000)
5.
Aspnes, J., Attiya, H., Censor, K..: Max registers, counters, and monotone circuits. In: PODC, pp. 36–45 (2009)
6.
Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM (JACM) 42(1), 124–142 (1995)CrossRefMATH
7.
Attiya, H., Chung, H.C., Ellen, F., Kumar, S., Welch, J.L.: Emulating a shared register in a system that never stops changing. IEEE Trans. Parallel Distrib. Syst. 30(3), 44–559 (2019)CrossRefMATH
8.
Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib. Comput. 8(3), 121–132 (1995)CrossRefMATH
9.
Baldoni, R., Bonomi, S., Kermarrec, A.-M., Raynal, M.: Implementing a register in a dynamic distributed system. In: ICDCS, pp. 639–647 (2009)
10.
Bellare, M., Miner, S.K.: A forward-secure digital signature scheme. In: Annual International Cryptology Conference, pp. 431–448. Springer (1999)
11.
Boyen, X., Shacham, H., Shen, E., Waters, B.: Forward-secure signatures with untrusted update. In: Proceedings of the 13th ACM conference on Computer and communications security, pp. 191–200 (2006)
12.
Brewer, E.A.: Towards robust distributed systems (abstract). In: PODC, p. 7 (2000)
13.
Cachin, C., Guerraoui, R., Rodrigues, L.: Introduction to reliable and secure distributed programming. Springer (2011)
14.
15.
Douceur, J.R.: The sybil attack. In: International workshop on peer-to-peer systems, pp. 251–260. Springer (2002)
16.
Drijvers, M., Gorbunov, S., Neven, G., Wee, H..: Pixel: Multi-signatures for consensus. In: 29th USENIX Security Symposium (USENIX Security 20), August (2020)
17.
Faleiro, J., Rajamani, S., Rajan, K., Ramalingam, G., Vaswani, K.: Generalized lattice agreement. In: PODC, pp. 125–134 (2012)
18.
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM (JACM) 32(2), 374–382 (1985)MathSciNetCrossRefMATH
19.
Gafni, E.: Round-by-round fault detectors: unifying synchrony and asynchrony. In: PODC, pp. 143–152 (1998)
20.
Gafni, E., Malkhi, D.: Elastic configuration maintenance via a parsimonious speculating snapshot solution. In: DISC, pp. 140–153 (2015)
21.
Gifford, D.K.: Weighted voting for replicated data. In: SOSP, pp. 150–162 (1979)
22.
Gilbert, S., Lynch, N.: Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33(2), 51–59 (2002)
23.
Gilbert, S., Lynch, N.A., Shvartsman, A.A.: Rambo a robust, reconfigurable atomic memory service for dynamic networks. Distrib. Comput. 23(4), 225–272 (2010)CrossRefMATH
24.
Jehl, L., Vitenberg, R., Meling, H.: Smartmerge: a new approach to reconfiguration for atomic storage. In: DISC, pp. 154–169 (2015)
25.
Kermarrec, A.-M., Van Steen, M.: Gossiping in distributed systems. ACM SIGOPS Oper. Syst. Rev. 41(5), 2–7 (2007)
26.
27.
Kuznetsov, P., Rieutord, T., Tucci-Piergiovanni, S.: Reconfigurable lattice agreement and applications. In: OPODIS (2019)
28.
Kuznetsov, P., Tonkikh, A..: Asynchronous reconfiguration with byzantine failures. In: 34th International Symposium on Distributed Computing, DISC 2020, October 12–16, 2020, Virtual Conference, vol. 179 of LIPIcs, pp. 27:1–27:17 (2020)
29.
Lamport, L., Malkhi, D., Zhou, L.: Reconfiguring a state machine. SIGACT News 41(1), 63–73 (2010)CrossRef
30.
31.
Malkin, T., Micciancio, D., Miner, S.: Efficient generic forward-secure signatures with an unbounded number of time periods. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 400–417. Springer (2002)
32.
Martin, J.-P., Alvisi, L.: A framework for dynamic byzantine storage. In: International Conference on Dependable Systems and Networks, 2004, pp. 325–334. IEEE (2004)
33.
Shapiro, M., Preguiça, N.M., Baquero, C., Zawirski, M.: Conflict-free replicated data types. In: SSS, pp. 386–400 (2011)
34.
Spiegelman, A., Keidar, I.: 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, pp. 356–376 (2017)
35.
Spiegelman, A., Keidar, I., Malkhi, D.: Dynamic reconfiguration: abstraction and optimal asynchronous solution. In: DISC, pp. 40:1–40:15 (2017)
36.
Zheng, X., Hu, C., Garg, V.K.: Lattice agreement in message passing systems. In: DISC, pp. 41:1–41:17 (2018)
Metadata
Title
Asynchronous reconfiguration with Byzantine failures
Authors
Petr Kuznetsov
Andrei Tonkikh
Publication date
10-03-2022
Publisher
Springer Berlin Heidelberg
Published in
Distributed Computing / Issue 6/2022
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-022-00421-1

Other articles of this Issue 6/2022

Distributed Computing 6/2022 Go to the issue

EditorialNotes

Special issue on DISC 2020

OriginalPaper

Distributed computation with continual population growth

OriginalPaper

Linial for lists

OriginalPaper

Making Byzantine consensus live

Premium Partner

    Image Credits