EUVIMEDEUVIMED entdecken
Crossref

Byzantine-tolerant distributed grow-only sets: specification and applications

Vicent Cholvi, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou, Michel Raynal, Antonio Russo

Distributed Computing · 2026-06 · 39 (2)

DOI: 10.1007/s00446-025-00499-3 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Distributed Computing, online erschienen am 17.03.2026. Verfasst von Vicent Cholvi und 5 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben. Gefördert von: Ministerio de Ciencia, Innovación y Universidades / Agencia Estatal de Investigación, ERDF, A way of making Europe.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In order to formalize Distributed Ledger Technologies and their interconnections, recent research has introduced the concept of a Distributed Ledger Object (denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^L$$\end{document}), a concurrent abstraction that maintains a totally ordered sequence of records, capturing the essence of blockchains and distributed ledgers. In this work, we introduce the Distributed Grow-only Set object (denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^{GS}$$\end{document}), a novel abstraction that, unlike the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^L$$\end{document}, maintains an immutable set of records by supporting only Add and Get operations. This object is inspired by the Grow-only Set (G-Set) a well-known Conflict-free Replicated Data Type (CRDT). We formally define the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^{GS}$$\end{document} and present a Byzantine-tolerant, consensus-free implementation (denoted as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^{GS}_B$$\end{document}) that ensures eventual consistency. Building on this implementation, we propose consensus-free algorithmic solutions to two fundamental problems: the Atomic Appends problem, which concerns atomically appending multiple records to distinct ledgers, and the Atomic Adds problem, its counterpart in the context of G-Sets. Additionally, we show how the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^{GS}_B$$\end{document} can be leveraged to construct a consensus-free, Single-Writer Byzantine-tolerant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^L$$\end{document}. We argue that the applicability of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}^{GS}_B$$\end{document} extends well beyond these specific use cases, offering a lightweight and efficient foundation for a variety of distributed applications.

Förderung

  • Ministerio de Ciencia, Innovación y Universidades / Agencia Estatal de Investigación
  • ERDF, A way of making Europe

Zitieren

APA

Cholvi, V., Anta, A. F., Georgiou, C., Nicolaou, N., Raynal, M., & Russo, A. (2026). Byzantine-tolerant distributed grow-only sets: specification and applications. Distributed Computing, 39(2). https://doi.org/10.1007/s00446-025-00499-3

Vancouver

Cholvi V, Anta AF, Georgiou C, Nicolaou N, Raynal M, Russo A. Byzantine-tolerant distributed grow-only sets: specification and applications. Distributed Computing. 2026;39(2). doi:10.1007/s00446-025-00499-3

BibTeX
@article{Cholvi2026,
  author = {Cholvi, Vicent and Anta, Antonio Fernández and Georgiou, Chryssis and Nicolaou, Nicolas and Raynal, Michel and Russo, Antonio},
  title = {Byzantine-tolerant distributed grow-only sets: specification and applications},
  journal = {Distributed Computing},
  year = {2026},
  volume = {39},
  number = {2},
  doi = {10.1007/s00446-025-00499-3}
}
Kostenlos starten →