Formalizing and Implementing Distributed Ledger Objects
Date
2018ISSN
0163-5700Source
ACM SIGACT NewsVolume
49Issue
2Google Scholar check
Metadata
Show full item recordAbstract
Despite the hype about blockchains and distributed ledgers, formal abstractions of these objects are scarce1. To face this issue, in this paper we provide a proper formulation of a distributed ledger object. In brief, we de ne a ledger object as a sequence of records, and we provide the operations and the properties that such an object should support. Implemen- tation of a ledger object on top of multiple (possibly geographically dispersed) computing devices gives rise to the distributed ledger object. In contrast to the centralized object, dis- tribution allows operations to be applied concurrently on the ledger, introducing challenges on the consistency of the ledger in each participant. We provide the de nitions of three well known consistency guarantees in terms of the operations supported by the ledger object: (1) atomic consistency (linearizability), (2) sequential consistency, and (3) eventual consistency. We then provide implementations of distributed ledgers on asynchronous message passing crash- prone systems using an Atomic Broadcast service, and show that they provide eventual, sequen- tial or atomic consistency semantics respectively. We conclude with a variation of the ledger the validated ledger which requires that each record in the ledger satis es a particular validation rule.