Choice coordination with limited failure

Abstract

The Choice Coordination Problem requires n asynchronous processes to reach a common choice of one out of k possible alternatives. Processes communicate via k shared variables. Up to t, t<n, of the processes may fail to operate by suddenly quitting the protocol. Rabin (1982) presented lower and upper bounds for the extreme case t=n-1. We present deterministic and randomized algorithms for arbitrary t using an alphabet of size O(t2). A semi-synchronous model is also studied. A reduction to a consensus problem proves the necessity to assume some powerful atomic shared-memory operations. © 1989 Springer-Verlag.