Solvability in Asynchronous Environments (Extended Abstract)

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. >

Authors

• Benny Chor
• Lior Moscovici

Keywords

• Message passing
• Protocols
• Surface-mount technology
• Algorithms
• Computer science
• Read-write memory
• Writing
• Computer crashes
• Heart
• Law
• Asynchronous Environment
• Input Vector
• Output Vector
• Decision Task
• Local Computing
• Part Of The Input
• Part Of Output
• Correct Output
• Local Output
• Proof Sketch
• Shared Memory
• Consensus Calling