Information Transfer under Different Sets of Protocols

Abstract

We study four kinds of protocols in distributed computing. Besides the case of deterministic protocols, we consider random, nondeterministic and probabilistic models. We show a strict containment relationship with exponential gaps. We also explore in some depth the relationship between one-way and two-way communications. It is shown, for example, that the complexity classes of random one-way protocols and of deterministic two-way protocols are incomparable: exponential gaps exist in either direction. On the other hand there is no difference between the complexity of one-way and two-way communications in the nondeterministic case.