CaltechAUTHORS
  A Caltech Library Service

Coding for interactive communication

Schulman, Leonard J. (1996) Coding for interactive communication. IEEE Transactions on Information Theory, 42 (6). pp. 1745-1756. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit96

[img]
Preview
PDF
See Usage Policy.

188Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit96

Abstract

Let the input to a computation problem be split between two processors connected by a communication link; and let an interactive protocol π be known by which, on any input, the processors can solve the problem using no more than T transmissions of bits between them, provided the channel is noiseless in each direction. We study the following question: if in fact the channel is noisy, what is the effect upon the number of transmissions needed in order to solve the computation problem reliably? Technologically this concern is motivated by the increasing importance of communication as a resource in computing, and by the tradeoff in communications equipment between bandwidth, reliability, and expense. We treat a model with random channel noise. We describe a deterministic method for simulating noiseless-channel protocols on noisy channels, with only a constant slowdown. This is an analog for general, interactive protocols of Shannon's coding theorem, which deals only with data transmission, i.e., one-way protocols. We cannot use Shannon's block coding method because the bits exchanged in the protocol are determined only one at a time, dynamically, in the course of the interaction. Instead, we describe a simulation protocol using a new kind of code, explicit tree codes.


Item Type:Article
Additional Information:© Copyright 1996 IEEE. Reprinted with permission. Manuscript received March 1, 1995; revised April 10, 1996. This research was conducted at MIT (see [26], [27] for preliminary presentations and related work) and at the University of California at Berkeley (see [28]). This work was supported at MIT under an ONR graduate fellowship, an MIT Applied Mathematics graduate fellowship, and under Grants NSF 8912586 CCR and AFOSR 89-0271. At Berkeley, this work was supported by NSF under a postdoctoral fellowship. The author wishes to thank his advisor M. Sipser whose oversight and encouragement in the early stages of this work were invaluable. For consultations and comments, the author also wishes to thank D. Abramovich, M. Blum, P. Elias, W. Evans, R. Gallager, W. Goddard, 0. Goldreich, M. Karchmer, R. Karp, C. Kenyon, D. Kleitman, M. Klugennan, N. Linial, M. Luby, M. Naor, Y. Peres, N. Pippenger, Y. Rabani, S. Rajagopalan, A. Sutherland, U. Vazirani, B. Velickovic, and D. Zuckerman. Finally, the author wishes to thank the Associate Editor, R. Cruz, and the anonymous referees, whose careful comments substantially improved the paper.
Subject Keywords:Interactive communication, coding theorem, tree code, distributed computing, reliable communication, error correction
Record Number:CaltechAUTHORS:SCHUieeetit96
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit96
Alternative URL:http://dx.doi.org/10.1109/18.556671
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6329
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:01 Dec 2006
Last Modified:26 Dec 2012 09:20

Repository Staff Only: item control page