Solvability in asynchronous environments

The authors present necessary and sufficient combinatorial conditions that determine membership in SM_t (respectively, MP_t), the class of distributed decision tasks that are solvable in the shared memory (resp. message passing) model by a t-resilient randomized protocol, which never errs and works in the presence of a strong adversary. The sufficiency of the conditions is proved by designing protocols that are applicable to all tasks in the appropriate class. The computational complexity of the membership characterization is studied