Metadata only
Datum
2021-12Typ
- Conference Paper
ETH Bibliographie
yes
Altmetrics
Abstract
The consensus number concept is used to determine the power of synchronization primitives in distributed systems. Recent work in the blockchain domain motivates shifting the attention to consensus number 1 objects, as it has been shown that transaction-based blockchains just need consensus number 1. In this paper we want to get a better understanding of such consensus number 1 objects. In particular, we study the necessary and sufficient conditions for determining the consensus number 1 objects. If an object has consensus number 1, then its operations must be either commutative or associative (necessary condition). On the other hand, if the operations are consistently commutative or overwriting, i.e., independent of the current state of the object, then the consensus number of the object is 1 (sufficient condition). We give an algorithm to implement such generic consensus number 1 objects using only read/write registers. This implies that read/write registers are universal enough to solve tasks, such as asset transfer of a cryptocurrency, among many others, in wait-free distributed systems for any number of processes. Mehr anzeigen
Publikationsstatus
publishedExterne Links
Buchtitel
2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)Seiten / Artikelnummer
Verlag
IEEEKonferenz
Thema
Consensus number; synchronization hierarchy; object implementation; read/write registersOrganisationseinheit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
ETH Bibliographie
yes
Altmetrics