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

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 noiselesschannel 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., oneway 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 890271. 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