Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.