Agreement algorithms in directed dynamic networks

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.