Winkler, K. (2019). Characterization of consensus solvability under message adversaries [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2019.72069
We study characterizations of consensus solvability in dynamic networks controlled by an omniscient message adversary. This model assumes a system of n distributed agents, called processes, that execute a distributed algorithm and communicate by message passing in lockstep synchronous rounds. Communication in each round is subject to a message adversary, which determines which messages are successfully delivered and which are lost, encoded via a directed communication graph. In its most general form, the message adversary can be represented by the set of infinite sequences of communication graphs, one for each round, that it may generate. Perhaps our most important theoretical result are a precise topological characterization of consensus solvability for general message adversaries and a considerably less abstract combinatorial characterization for the important class of closed message adversaries, which encompasses most of the message adversary classes for which consensus solvability characterizations existed so far. Thanks to this, we are able to state for the first time in a precise and rigorous way exactly what is the crucial property of an arbitrary message adversary that permits a consensus solution algorithm. Our arguably most important practical result is an optimal algorithm for dynamic networks that guarantee only brief stability phases along with its correctness and optimality proof. This algorithm is relatively simple and might be used as a template for solving consensus in real systems that exhibit massive transient message loss.