Title :
Coding for distributed computation
Author :
Rajagopalan, Sridhar ; Schulman, Leonard J.
Author_Institution :
Princeton Univ., NJ, USA
Abstract :
We show that any distributed protocol which runs on a noiseless network in time T, can be simulated on an identical noisy network with a slow-down factor proportional to log(d+1), where d is the maximum degree in the network, and with exponentially small probability of error. On every channel of our network we implement communications using tree codes
Keywords :
codes; coding errors; error statistics; exponential distribution; protocols; telecommunication networks; distributed computation; distributed protocol; exponentially small error probability; noiseless network; noisy network; slow-down factor; tree codes; Channel capacity; Codes; Complexity theory; Computational efficiency; Computational modeling; Distributed computing; Mathematics; Protocols; Reliability theory; Space technology;
Conference_Titel :
Information Theory, 1995. Proceedings., 1995 IEEE International Symposium on
Conference_Location :
Whistler, BC
Print_ISBN :
0-7803-2453-6
DOI :
10.1109/ISIT.1995.550440
