FOCS Conference 1989 Conference Paper
Solvability in Asynchronous Environments (Extended Abstract)
- Benny Chor
- Lior Moscovici
The authors present necessary and sufficient combinatorial conditions that determine membership in SM/sub t/ (respectively, MP/sub 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. >