Agreement algorithms in directed dynamic networks / by Manfred Schwarz
Verfasser / Verfasserin Schwarz, Manfred
Begutachter / BegutachterinSchmid, Ulrich
ErschienenWien, 2018
Umfangxv, 110 Seiten : Diagramme
HochschulschriftTechnische Universität Wien, Dissertation, 2018
Zusammenfassung in deutscher Sprache
Schlagwörter (EN)Agreement algorithms / Distributed systems / Consensus / Directed dynamic networks
URNurn:nbn:at:at-ubtuw:1-113538 Persistent Identifier (URN)
 Das Werk ist frei verfügbar
Agreement algorithms in directed dynamic networks [1.28 mb]
Zusammenfassung (Englisch)

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.

Das PDF-Dokument wurde 22 mal heruntergeladen.