A simple model of distributed computation that requires information exchange over a noisy channel is considered. A communication protocol is utilized that requires alternate bit exchanges between two processors. Interest in determining the communication complexity of this exchange is also shown. First, the case of a single public channel is considered and the number of bits that need to be exchanged between the processors to permit delta-accuracy in their goal is computed. For this computation, an error-detection-and-retransmission mechanism of error control, as well as an error-correction-and-retransmission mixture that are consistent with the logical protocol that governs this exchange are considered. Second, the case of the availability of an additional secret channel is considered and interest in determining the minimum number of bits that need to be exchanged over a secret channel in order to maintain epsilon-uncertainty about the computation for an eavesdropper on the public channel is shown. Various subcases under this case are considered and an upper bound on the number of secret bits when no error-control scheme is used is obtained.
