Simulations and reductions for colorless tasks
Maurice P. Herlihy, Sergio Rajsbaum · 2012
If one model of computation can simulate another, then the existence (or non-existence) of an algorithm in the simulated model reduces to a related question about the simulating model. The BG-simulation algorithm uses this approach to prove that k-set agreement cannot be solved when t processes can crash, 1≤t≤k, by reduction to the wait-free case, where it is known that n+1 processes cannot solve n-set agreement, and similarly for any other colorless task. We give a definition, expressed in the language of combinatorial topology, for what it means for one model of distributed computation to simulate another with respect to the ability to solve colorless tasks. This definition is not linked to specific models or specific protocols. We show how to exploit elementary topological arguments to show when a simulation exists, without the need for an explicit construction. We use this approach to generalize the BG-simulation and to unify a number of simulation relations linking various models, some previously known, some not.