Metadata only
Date
2021-12Type
- Conference Paper
ETH Bibliography
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. Show more
Publication status
publishedExternal links
Book title
2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)Pages / Article No.
Publisher
IEEEEvent
Subject
Consensus number; synchronization hierarchy; object implementation; read/write registersOrganisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
More
Show all metadata
ETH Bibliography
yes
Altmetrics