Byzantine-tolerant Distributed Grow-only Sets: Specification and\n Applications

Abstract

In order to formalize Distributed Ledger Technologies and their\ninterconnections, a recent line of research work has formulated the notion of\nDistributed Ledger Object (DLO), which is a concurrent object that maintains a\ntotally ordered sequence of records, abstracting blockchains and distributed\nledgers. Through DLO, the Atomic Appends problem, intended as the need of a\nprimitive able to append multiple records to distinct ledgers in an atomic way,\nis studied as a basic interconnection problem among ledgers.\n In this work, we propose the Distributed Grow-only Set object (DSO), which\ninstead of maintaining a sequence of records, as in a DLO, maintains a set of\nrecords in an immutable way: only Add and Get operations are provided. This\nobject is inspired by the Grow-only Set (G-Set) data type which is part of the\nConflict-free Replicated Data Types. We formally specify the object and we\nprovide a consensus-free Byzantine-tolerant implementation that guarantees\neventual consistency. We then use our Byzantine-tolerant DSO (BDSO)\nimplementation to provide consensus-free algorithmic solutions to the Atomic\nAppends and Atomic Adds (the analogous problem of atomic appends applied on\nG-Sets) problems, as well as to construct consensus-free Single-Writer BDLOs.\nWe believe that the BDSO has applications beyond the above-mentioned problems.\n