[Zurück]

H. Rincon Galeana, K. Winkler, U. Schmid, S. Rajsbaum:
"A Topological View of Partitioning Arguments: Reducing k-Set Agreement to Consensus";
Bericht für Institut für Computer Engineering E191-02; Berichts-Nr. TUW-281149, 2019.

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.

Algebraic topology, consensus, set agreement, partitioning arguments, shared memory

https://publik.tuwien.ac.at/files/publik_281149.pdf