Article

Free access

A coding theorem for distributed computation

Authors:

Sridhar Rajagopalan,

Leonard SchulmanAuthors Info & Claims

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

Pages 790 - 799

https://doi.org/10.1145/195058.195462

Published: 23 May 1994 Publication History

PDF eReader

References

[1]

1#. Aleliunas. Randomized parallel communication. In Proceedings of the Symposium on the Principles of Distributed Systems., 1982, pages 60-72.

Digital Library

Google Scholar

[2]

T. M. Cover and j. A. Thomas. Elements of Information Theory. Wiley, 1991.

Digital Library

Google Scholar

[3]

R. L. Dobrushin and S. I. Ortyukov. Lower bound for the redundancy of self-correcting arrangements of unreliable functional elements. Prob. Inf. Trans., 13:59-65, 1977.

Google Scholar

[4]

R.L. Dobrushin and S. I. Ortyukov. Upper bound for the redundancy of self-correcting arrangements of unreliable functional elements. Prob. In/. Trans., 13:203-218, 1977.

Google Scholar

[5]

W. Evans and L. j. Schulman. Signal propagation, with application to a lower bound on the depth of noisy formulas. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 594-603, 1993.

Digital Library

Google Scholar

[6]

T. Feder. Reliable computation by networks in the presence of noise. IEEE Transactions on Information Theory, 35(3):569-571, May 1989.

Digital Library

Google Scholar

[7]

P. G#tcs. Reliable computation with cellular automata. J. Computer and System Sciences, 32:15-78, 1986.

Digital Library

Google Scholar

[8]

P. G#cs and J. Reif. A simple three-dimensional real-time reliable cellular array. J. Computer and System Sciences, 36:125-147, 1988.

Digital Library

Google Scholar

[9]

A. G#I. Lower bounds for the complexity of reliable boolean circuits with noisy gates. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 594-601, 1991.

Digital Library

Google Scholar

[10]

R. G. Gallager. Finding parity in a simple broadcast network. IEEE Trans. In}grin. Theory, 34(2):176-180, March 1988.

Crossref

Google Scholar

[11]

Lipton and Sedgewick. Lower bounds for VLSI. In Proceedings oj the 13th Annual Symposium on Theory oJ Computing, pages 300-307, 1981.

Digital Library

Google Scholar

[12]

L. Lov#sz. Communication complexity: A survey. In Korde et al, editor, Algorithms and Combinatorics. Springer- Verlag, 1990.

Google Scholar

[13]

M. Luby. On the parallel complexity of symmetric connection networks. U. Toronto CS Dept. Tech. Report # 214, 1988.

Google Scholar

[14]

C. Martel, R. Subramonian, and A. Park. Asynchronous PRAMs are (almost) as good as Synchronous PRAMs. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 590-599, 1990.

Digital Library

Google Scholar

[15]

N. Nisan Personal Communication.

Google Scholar

[16]

C. H. Papadimitriou and M. Sipser. Communication complexity. In Proceedings of the l#th Annual Symposium on Theory of Computing, pages 196-200, 1982.

Digital Library

Google Scholar

[17]

N. Pippenger. On networks of noisy gates. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 30-36, 1985.

Digital Library

Google Scholar

[18]

N. Pippenger. Reliable computation by formulas in the presence of noise. IEEE Transactions on Information Theory, 34(2):194-197, March 1988.

Crossref

Google Scholar

[19]

N. Pippenger. Invariance of complexity measures for networks with unreliable gates. J. A CM, 36:531-539, 1989.

Digital Library

Google Scholar

[20]

N. Pippenger, G. D. Stamoulis, and J. N. Tsitsiklis. On a lower bound for the redundancy of reliable networks with noisy gates. IEEE 7#cansactions on Information Theory, 37(3):639-643, 1991.

Google Scholar

[21]

A.G. Ranade. A Simpler Analysis of the Karp-Zhang Parallel Branch-and-Bound Method. University of Cali}ornia, TR, UCB/CSD 90/586, 1990.

Digital Library

Google Scholar

[22]

A.G. Ranade. How to emulate shared memory. JCSS, 42(3):307-326, June, 1991.

Digital Library

Google Scholar

[23]

1#. Reischuk and B. Schmeltz. Reliable computation with noisy circuits and decision trees- a general n log n lower bound. In Proceedings of the 3Pnd Annual Symposium on Foundations of Computer Science, pages 602-611, 1991.

Digital Library

Google Scholar

[24]

L. J. Schulman. Communication in the Presence of Noise. PhD thesis, Massachusetts Institute of Technology, 1992.

Digital Library

Google Scholar

[25]

L. J. Schulman. Communication on noisy channels: A coding theorem for computation. In Proceedings o.f the 33rd Annual Symposium on Foundations of Computer Science, pages 724-733, 1992.

Digital Library

Google Scholar

[26]

L. J. Schulmam Deterministic coding for interactive communication. In Proceedings of the 25th Annual Symposium on Theory of Computing, pages 747-756, 1993.

Digital Library

Google Scholar

[27]

C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379-423; 623-656, 1948.

Crossref

Google Scholar

[28]

M. C. Taylor. Reliable information storage in memories designed from unreliable components. Bell System Tech. J., 47(10) :2299-2337, 1968.

Google Scholar

[29]

C. D. Thompson. Area-time complexity for VLSI. In Proceedings of the 11th Annual Symposium on Theory o.f Computing, pages 81-88, 1979.

Digital Library

Google Scholar

[30]

A. L. Toom. Nonergodic multidimensional systems of automata. Problems Inform. Transmission, 10:239-246, 1974.

Google Scholar

[31]

A. L. Toom. Stable and attractive trajectories in multicomponent systems, in R. L. Dobrushin, editor, Multicomponent Systems, volume 6 of Adv. Probab., pages 549-575. Dekker, 1980.

Google Scholar

[32]

A. L. Toom. Estimates for the measures describing the behavior of stochastic systems with local interaction. In Kryukov Dobrushin and Toom, editors, Int'.eractive Markov Processes and Their Application to the Mathematical Modelling o} Biological Systems. Acad. Sci. USSR, 1982.

Google Scholar

[33]

B. S. Tsirel'son. Reliable information storage in a system of locally interacting unreliable elements. In Interacting Markov Processes in Biology, volume 653 of Lecture Notes in Mathematics. Springer-Verlag, 1978.

Google Scholar

[34]

j. von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In C. E. Shannon and J. McCarthy, editors, Automata S,iudies. Princeton University Press, 1956.

Google Scholar

[35]

A. C. Yao. Some complexity questions related to distributive computing. In Proceedings of the 11th Annual Symposium on Theory of Computing, pages 209-213, 1979.

Digital Library

Google Scholar

[36]

A. C. Yao. The entropic limitations on VLSI computations. In Proceedings of the 13th Annual Symposium on Theory of Computing, pages 308-311, 1981.

Digital Library

Google Scholar

Cited By

View all

Ling YScarlett J(2024)Optimal 1-bit Error Exponent for 2-Hop Relaying With Binary-Input ChannelsIEEE Transactions on Information Theory10.1109/TIT.2024.340735470:11(7599-7615)Online publication date: Nov-2024
https://doi.org/10.1109/TIT.2024.3407354
Ling YScarlett J(2024)Maxflow-Based Bounds for Low-Rate Information Propagation Over Noisy NetworksIEEE Transactions on Information Theory10.1109/TIT.2023.333593370:6(3840-3854)Online publication date: Jun-2024
https://doi.org/10.1109/TIT.2023.3335933
Domanovitz EKhina APhilosof TKochman Y(2024)Information Velocity of Cascaded Gaussian Channels With FeedbackIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2024.34163105(554-569)Online publication date: 2024
https://doi.org/10.1109/JSAIT.2024.3416310
Show More Cited By

Index Terms

A coding theorem for distributed computation

Recommendations

Distributed Space-Frequency Coding over Broadband Relay Channels
Part 2

Designing diversity achieving schemes over the wireless broadband fading relay channels is crucial to achieve higher diversity gains. These gains are achieved by exploiting the multipath (frequency) and cooperative diversities to combat the fading ...
Rate-adaptive codes for distributed source coding
Special section: Distributed source coding

Source coding with correlated decoder side information is considered. We impose the practical constraint that the encoder be unaware of even the statistical dependencies between source and side information. Two classes of rate-adaptive distributed ...
An efficient adaptive distributed space-time coding scheme for cooperative relaying

A non-regenerative dual-hop wireless system based on distributed Alamouti space-time coding is considered. It is assumed that each relay retransmits an appropriately scaled space-time coded version of its received signal. The main goal of this paper is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

May 1994

822 pages

ISBN:0897916638

DOI:10.1145/195058

Chairmen:
F. Tom Leighton
Massachusetts Institue of Technology, Cambridge
,
Michael Goodrich
Johns Hopkins Univ., Baltimore, MD

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC94

Sponsor:

SIGACT

STOC94: Symposium on Theory of Computing

May 23 - 25, 1994

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
1,164
Total Downloads

Downloads (Last 12 months)478
Downloads (Last 6 weeks)16

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ling YScarlett J(2024)Optimal 1-bit Error Exponent for 2-Hop Relaying With Binary-Input ChannelsIEEE Transactions on Information Theory10.1109/TIT.2024.340735470:11(7599-7615)Online publication date: Nov-2024
https://doi.org/10.1109/TIT.2024.3407354
Ling YScarlett J(2024)Maxflow-Based Bounds for Low-Rate Information Propagation Over Noisy NetworksIEEE Transactions on Information Theory10.1109/TIT.2023.333593370:6(3840-3854)Online publication date: Jun-2024
https://doi.org/10.1109/TIT.2023.3335933
Domanovitz EKhina APhilosof TKochman Y(2024)Information Velocity of Cascaded Gaussian Channels With FeedbackIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2024.34163105(554-569)Online publication date: 2024
https://doi.org/10.1109/JSAIT.2024.3416310
Mukherjee MGelles R(2024)Information Exchange is Harder with Noise at Source2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619523(3285-3290)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619523
Aggarwal MMukherjee M(2024)Improved Bounds on the Interactive Capacity via Error Pattern Analysis2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619345(2975-2980)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619345
Mukherjee MGelles R(2024)Computation in Server-Assisted Noisy Networks2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619253(3297-3301)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619253
Domanovitz EKhina APhilosof TKochman Y(2024)Information Velocity of Cascaded AWGN Channels with Feedback2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619138(499-504)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619138
Fischer OParter MOshman RNolin AHalldorsson MBalliu A(2023)Distributed CONGEST Algorithms against Mobile AdversariesProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594578(262-273)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594578
Ling YScarlett J(2023)Multi-Bit Relaying Over a Tandem of ChannelsIEEE Transactions on Information Theory10.1109/TIT.2023.324782969:6(3511-3524)Online publication date: Jun-2023
https://doi.org/10.1109/TIT.2023.3247829
Censor-Hillel KCohen SGelles RSela G(2023)Distributed computations in fully-defective networksDistributed Computing10.1007/s00446-023-00452-236:4(501-528)Online publication date: 19-Jun-2023
https://doi.org/10.1007/s00446-023-00452-2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Distributed Space-Frequency Coding over Broadband Relay Channels

Rate-adaptive codes for distributed source coding

An efficient adaptive distributed space-time coding scheme for cooperative relaying