Robust and Scalable Distributed Ordering: Counting, Queueing and Agreement
OPEN ACCESS
Loading...
Author / Producer
Date
2020
Publication Type
Doctoral Thesis
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Any set of computing processes or participants interacting to achieve a common objective can be considered as a Distributed System. Arguably, the most important algorithms for designing such a system are related to ordering the system events identically for all the processes. This is also the
problem that many blockchain systems seek to address. Ideally, we want the algorithms to use minimal resources and scale well to a large number of processes or participants. We also want them to be robust against a multitude of failures such as unpredictable message delays and participants behaving maliciously. In this thesis, we discuss several fundamental distributed ordering problems and give algorithms with better scalability and robustness. For a multiprocessor system, we design an improved shared counter and also a concurrent queue. Our design works with concurrent unreliable processes that can crash at any time. We also propose a pair of new atomic instructions for a multiprocessor that have better scalability properties than the compare-and-swap instruction, which is widely supported by modern hardware. For a network of computers, we give a family of algorithms for distributed synchronization, which order concurrent requests to an exclusive resource that is shared over the network. These algorithms are not only simple but also efficient and only use a constant space per node. We also consider networks where potentially malicious or Byzantine participants can join the network and honest participants can leave over time. Such a dynamic setting is true for many blockchain systems that are used in practice. We give simple agreement protocols in such networks to totally order the events in the network.
Permanent link
Publication status
published
External links
Editor
Contributors
Examiner : Wattenhofer, Roger
Examiner : Gafni, Eli
Examiner : Guerraoui, Rachid
Book title
Journal / series
Volume
Pages / Article No.
Publisher
ETH Zurich
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Distributed algorithms; Consensus; concurrent data structures; Byzantine Agreement; Multiprocessor synchronization; Synchronization
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger