2026-07-28T12:15:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13988 2024-03-06T10:31:22Z ddc:004 open_access

Byzantine-Tolerant Distributed Grow-Only Sets: Specification and Applications Cholvi, Vicent Fernández Anta, Antonio Georgiou, Chryssis Nicolaou, Nicolas Raynal, Michel Russo, Antonio Grow-only Sets Distributed Ledgers Blockchains Atomic appends In order to formalize Distributed Ledger Technologies and their interconnections, a recent line of research work has formulated the notion of Distributed Ledger Object (DLO), which is a concurrent object that maintains a totally ordered sequence of records, abstracting blockchains and distributed ledgers. Through DLO, the Atomic Appends problem, intended as the need of a primitive able to append multiple records to distinct ledgers in an atomic way, is studied as a basic interconnection problem among ledgers. In this work, we propose the Distributed Grow-only Set object (DSO), which instead of maintaining a sequence of records, as in a DLO, maintains a set of records in an immutable way: only Add and Get operations are provided. This object is inspired by the Grow-only Set (G-Set) data type which is part of the Conflict-free Replicated Data Types. We formally specify the object and we provide a consensus-free Byzantine-tolerant implementation that guarantees eventual consistency. We then use our Byzantine-tolerant DSO (BDSO) implementation to provide consensus-free algorithmic solutions to the Atomic Appends and Atomic Adds (the analogous problem of atomic appends applied on G-Sets) problems, as well as to construct consensus-free Single-Writer BDLOs. We believe that the BDSO has applications beyond the above-mentioned problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vicent Cholvi and Antonio Fernández Anta and Chryssis Georgiou and Nicolas Nicolaou and Michel Raynal and Antonio Russo 2021 Is Part Of OASIcs, Volume 92, 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.FAB.2021.2 urn:nbn:de:0030-drops-139883 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2021.2 eng https://creativecommons.org/licenses/by/4.0/legalcode