The BG distributed simulation algorithm
We present a shared memory algorithm that allows a set of f + 1 processes to wait-free "simulate" a larger system of n processes, that may also exhibit up to f stopping failures. Applying this simulation algorithm to the k-set-agreement problem enables conversion of an arbitrary k-fault-tolerant n-process solution for the k-set-agreement problem into a wait-free k + 1-process solution for the same problem. Since the k + 1-process k-set-agreement problem has been shown to have no wait-free solution [5,18,26], this transformation implies that there is no k-fault-tolerant solution to the n-process k-set-agreement problem, for any n. More generally, the algorithm satisfies the requirements of a fault-tolerant distributed simulation. The distributed simulation implements a notion of fault-tolerant reducibility between decision problems. This paper defines these notions and gives examples of their application to fundamental distributed computing problems. The algorithm is presented and verified in terms of I/O automata. The presentation has a great deal of interesting modularity, expressed by I/O automaton composition and both forward and backward simulation relations. Composition is used to include a safe agreement module as a subroutine. Forward and backward simulation relations are used to view the algorithm as implementing a multi-try snapshot strategy. The main algorithm works in snapshot shared memory systems; a simple modification of the algorithm that works in read/write shared memory systems is also presented.
simulation fault-tolerance distributed computing set-agreement consensus