Byzantine-tolerant distributed grow-only sets: specification and applications
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.
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}
}
EUVIMED