Information Transfer under Different Sets of Protocols
Joseph F. JáJá, V. Krishna Kumar, Janoš Šimon · SIAM Journal on Computing · 1984
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.