Title: Agreement algorithms in directed dynamic networks
Language: English
Authors: Schwarz, Manfred 
Qualification level: Doctoral
Advisor: Schmid, Ulrich  
Issue Date: 2018
Number of Pages: 110
Qualification level: Doctoral
Abstract: 
This dissertation explores algorithmic solutions for some prominent agreement problems in the field of distributed computing. Such problems are interesting as they are the basis for many practical distributed systems. Agreement problems include clock synchronization, symmetry breaking or solving coordination problems where participants with conflicting inputs have to agree on a common output. Whereas most of the existing work studies systems where the failure assumption is a crash of one or more participants, this thesis focuses on synchronous dynamic networks with communication failures controlled by a message adversary. With the emergence of wireless systems, ad-hoc networks and sensor networks, systems consisting of large, possibly unknown, number of network nodes connected by undirected network links become ubiquitous. Results include optimal solutions for the consensus problem, a gracefully degrading solution for the more general k-set agreement problem, and lower bounds for the asymptotic consensus problem. The thesis closes with relating synchronous systems subject to message adversaries to asynchronous systems with failure detectors, which inspired the use of a suitable definition of message adversary simulations.
Keywords: Agreement algorithms; Distributed systems; Consensus; Directed dynamic networks
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-113538
http://hdl.handle.net/20.500.12708/7199
Library ID: AC15078077
Organisation: E191 - Institut für Computer Engineering 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

25
checked on Aug 18, 2021

Download(s)

56
checked on Aug 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.