An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems
Maurice P. Herlihy, Sergio Rajsbaum, Mark R. Tuttle · Electronic Notes in Theoretical Computer Science · 2009
We present a unified, axiomatic approach to proving lower bounds for the k-set agreement problem in both synchronous and asynchronous message-passing models. The proof involves constructing the set of reachable states, proving that these states are highly connected, and then appealing to a well-known topological result that high connectivity implies that set agreement is impossible. We construct the set of reachable states in an iterative fashion using a round operator that we define, and our proof of connectivity is an inductive proof based on this iterative construction and simple properties of the round operator.