Combinatorial Arguments

Abstract

In this chapter, combinatorial and graph theoretic results are applied to obtain impossibility results. We begin, in Section 8.1, by proving that wait-free set consensus is unsolvable in an asynchronous shared memory system where processes communicate via registers. Then, in Section 8.2, we prove a lower bound on the number of steps required to perform an Update in a single-writer snapshot object implemented from single-writer registers. In both these proofs, counting is employed to show the existence of certain situations that an adversary can take advantage of to construct a bad execution.