Ami Paz (University of Vienna)
Title: A Topological Perspective on Distributed Network Algorithms
Abstract: More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In a recent work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in failure-free networks of arbitrary structure. I will give an overview of these techniques and results, and present implications to classical computational settings, such as the LOCAL model and dynamic networks.
Knowledge in distributed computing or topology will not be assumed. Based on a joint work with Armando Castañeda, Pierre Fraigniaud, Sergio Rajsbaum, Matthieu Roy, and Corentin Travers.
Kyrill Winkler (TU Wien)
Title: Topological characterization of consensus under general message adversaries
Abstract: We provide a characterization of consensus solvability in synchronous directed dynamic networks controlled by an arbitrary message adversary using point-set topology. Our work extends the approach introduced by Alpern and Schneider in 1985 by introducing a novel topology on the space of infinite executions, namely the minimum topology. It is induced by a distance function that focuses on the local view of the process that is the last to distinguish two executions. We present a connectivity property of the resulting topological space that provides necessary and sufficient topological conditions on the admissible graph sequences of a message adversary for solving consensus. We conclude by giving a non-topological characterization for the class of closed message adversaries and provide an example for a generic non-closed message adversary.
Short Bio: Kyrill Winkler obtained his doctorate in computer science from TU Wien in 2019. He was a visiting researcher at école polytechnique in Paris and currently works in the group of Ulrich Schmid as a university assistant at the institute of computer engineering at TU Wien. His main research interests include distributed algorithms, in particular the analysis of consensus and related problems in dynamic networks.
Hugo Rincon Galeana (TU Wien)
Title: A Topological View of Partitioning Arguments: Reducing k-Set Agreement to Consensus
Abstract: The objective of this paper is to understand the effect of partitioning in distributed computing models. In spite of being quite similar agreement problems, (deterministic) consensus (1-set agreement) and k-set agreement (for k > 1) require surprisingly different techniques for proving impossibilities. There is a widely applicable generic theorem, however, which allows to reduce the impossibility of k-set agreement to consensus in message-passing models that allow some partitioning. In this paper, we provide the topological representation of this theorem, which reveals how partitioning is reflected in the protocol complex: It turns out that this leads to a “color splitting” of the algorithm’s decision map, which separates the sub-complexes representing the partitioned processes. We also harvest a general advantage of topological results, which allowed us to carry over our findings to shared memory systems. We first demonstrate the utility of our reduction theorem by proving that d-set agreement cannot be solved in the d-solo asynchronous read-write model even when a single process may crash, not just in the wait-free case. Moreover, our new insights into the structure of protocol complexes gave us the idea for a simple proof of the fact that no partitioning argument can provide a valid impossibility proof for wait-free set agreement in the iterated immediate snapshot model: For any set of partition-compatible runs (which do not contain runs where all processes always have a complete view), we provide a way to construct a simple algorithm that solves set agreement.
