Schulman, Leonard J. (1994) Coding for distributed computation. In: Proceedings 1994 IEEEIMS Workshop on Information Theory and Statistics. IEEE , Piscataway, NJ, p. 28. ISBN 0780327616 http://resolver.caltech.edu/CaltechAUTHORS:20120223084134446

PDF
 Published Version
See Usage Policy. 76Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120223084134446
Abstract
The author describes analogous coding theorems for the more general, interactive, communications required in computation. In this case the bits transmitted in the protocol are not known to the processors in advance but are determined dynamically. First he shows that any interactive protocol of length T between two processors connected by a noiseless channel can be simulated, if the channel is noisy (a binary symmetric channel of capacity C), in time proportional to T 1/C, and with error probability exponentially small in T. He then shows that this result can be extended to arbitrary distributed network protocols. He shows that any distributed protocol which runs in time T on a network of degree d having noiseless communication channels, can, if the channels are in fact noisy, be simulated on that network in time proportional to T 1/C log d. The probability of failure of the protocol is exponentially small in T.
Item Type:  Book Section  

Related URLs: 
 
Additional Information:  © 1994 IEEE. Date of Current Version: 06 August 2002. Research supported by an NSF Mathematical Sciences Postdoctoral Fellowship.  
Funders: 
 
Other Numbering System: 
 
Record Number:  CaltechAUTHORS:20120223084134446  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20120223084134446  
Official Citation:  Schulman, L.J.; , "Coding for distributed computation," Information Theory and Statistics, 1994. Proceedings., 1994 IEEEIMS Workshop on , vol., no., pp.28, 2729 Oct 1994 doi: 10.1109/WITS.1994.513866 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=513866&isnumber=11344  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  29427  
Collection:  CaltechAUTHORS  
Deposited By:  Tony Diaz  
Deposited On:  23 Feb 2012 19:30  
Last Modified:  26 Dec 2012 14:52 
Repository Staff Only: item control page