research-article

A Scheme for Fast Parallel Communication

Author:

L. G. ValiantAuthors Info & Claims

SIAM Journal on Computing, Volume 11, Issue 2

Pages 350 - 361

https://doi.org/10.1137/0211027

Published: 01 May 1982 Publication History

Abstract

Consider $N = 2^n $ nodes connected by wires to make an n-dimensional binary cube. Suppose that initially the nodes contain one packet each addressed to distinct nodes of the cube. We show that there is a distributed randomized algorithm that can route every packet to its destination without two packets passing down the same wire at any one time, and finishes within time $O(\log N)$ with overwhelming probability for all such routing requests. Each packet carries with it $O(\log N)$ bits of bookkeeping information. No other communication among the nodes takes place.

The algorithm offers the only scheme known for realizing arbitrary permutations in a sparse N node network in $O(\log N)$ time and has evident applications in the design of general purpose parallel computers.

References

[1]

D. Angluin, L. G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. System Sci., 18 (1979), 155–193

Crossref

Google Scholar

[2]

K. E. Batcher, Sorting networks and their applications, AFIPS Spring Joint Comp. Conf., 32 (1968), 307–314

Google Scholar

[3]

V. E. Benes, Mathematical theory of connecting networks and telephone traffic, Mathematics in Science and Engineering, Vol. 17, Academic Press, New York, 1965xiv+319

Google Scholar

[4]

Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics, 23 (1952), 493–507

Crossref

Google Scholar

[5]

Wassily Hoeffding, On the distribution of the number of successes in independent trials, Ann. Math. Statist., 27 (1956), 713–721

Crossref

Google Scholar

[6]

G. Lev, N. Pippenger, L. G. Valiant, A fast parallel algorithm for routing in permutation networks, IEEE Trans. Comput., 30 (1981), 93–100

Digital Library

Google Scholar

[7]

Michael O. Rabin, J. F. Traub, Probabilistic algorithmsAlgorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), Academic Press, New York, 1976, 21–39

Google Scholar

[8]

H. J. Siegel, Interconnection networks for SIMD machines, Computer, (1979), 57–65, (June)

Digital Library

Google Scholar

[9]

R. Solovay, V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput., 6 (1977), 84–85

Digital Library

Google Scholar

[10]

Abraham Waksman, A permutation network, J. Assoc. Comput. Mach. 15 (1968), 159-163; corrigendum, ibid., 15 (1968), 340–

Digital Library

Google Scholar

[11]

L. G. Valiant, Experiments with a parallel communication scheme, Proc. 18th Allerton Conf. on Communication, Control and Computing, University of Illinois, 1980, 802–811, Oct. 8–10

Google Scholar

[12]

L. G. Valiant, G. J. Brebner, Universal Schemes for parallel communication, Proc. 13th ACM Symposium of Theory of Computing, 1981, 263–277

Google Scholar

Cited By

View all

Dillencourt MGoodrich MMitzenmacher M(2025)Leveraging parameterized Chernoff bounds for simplified algorithm analysesInformation Processing Letters10.1016/j.ipl.2024.106516187:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.ipl.2024.106516
Mellette WForencich AAthapathu RSnoeren APapen GPorter GSekar VYu MSeneviratne AVeitch D(2024)Realizing RotorNet: Toward Practical Microsecond Scale Optical NetworkingProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672273(392-414)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672273
Haeupler BPatel SRoeyskoe AStein CZuzic GMohar BShinkar IO'Donnell R(2024)Polylog-Competitive Deterministic Local Routing and SchedulingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649678(812-822)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649678
Show More Cited By

Index Terms

A Scheme for Fast Parallel Communication

Index terms have been assigned to the content through auto-classification.

Recommendations

Parallel algorithms with ultra-fast expected times
An O(log N) deterministic packet-routing scheme

A deterministic O(log N)-time algorithm for the problem of routing an aribitrary permutation on an N-processor bounded-degree network with bounded buffers is presented.

Unlike all previous deterministic solutions to this problem, our routing scheme does ...
Time-communication trade-offs for minimum spanning tree construction
ICDCN '17: Proceedings of the 18th International Conference on Distributed Computing and Networking

This paper concerns the problem of constructing a minimum spanning tree (MST) in a synchronous distributed network with n nodes, where each node knows only the identities of itself and its neighbors. We assume the CONGEST model where messages are of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 11, Issue 2

May 1982

208 pages

ISSN:0097-5397

DOI:10.1137/smjcat.1982.11.issue-2

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 May 1982

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dillencourt MGoodrich MMitzenmacher M(2025)Leveraging parameterized Chernoff bounds for simplified algorithm analysesInformation Processing Letters10.1016/j.ipl.2024.106516187:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.ipl.2024.106516
Mellette WForencich AAthapathu RSnoeren APapen GPorter GSekar VYu MSeneviratne AVeitch D(2024)Realizing RotorNet: Toward Practical Microsecond Scale Optical NetworkingProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672273(392-414)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672273
Haeupler BPatel SRoeyskoe AStein CZuzic GMohar BShinkar IO'Donnell R(2024)Polylog-Competitive Deterministic Local Routing and SchedulingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649678(812-822)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649678
Wilson TAmir DSaran NKleinberg RShrivastav VWeatherspoon HMohar BShinkar IO'Donnell R(2024)Breaking the VLB Barrier for Oblivious Reconfigurable NetworksProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649608(1865-1876)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649608
De Sensi DCosta Molero EDi Girolamo SVanbever LHoefler T(2024)CanaryFuture Generation Computer Systems10.1016/j.future.2023.10.010152:C(70-82)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.future.2023.10.010
Biryukov AFisch BHerold GKhovratovich DLeurent GNaya-Plasencia MWesolowski B(2024)Cryptanalysis of Algebraic Verifiable Delay FunctionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_14(457-490)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_14
Chitavisutthivong KSupittayapornpong SNamyar PZhang MYu MGovindan R(2023)Optimal Oblivious Routing With Concave Objectives for Structured NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2023.326463231:6(2669-2681)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TNET.2023.3264632
Dolev SKhankin D(2023)Random spanning trees for expanders, sparsifiers, and virtual network securityComputer Communications10.1016/j.comcom.2023.09.028212:C(21-34)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.comcom.2023.09.028
Reif JSen S(2023)Optimal randomized parallel algorithms for computational geometryAlgorithmica10.1007/BF017587537:1-6(91-117)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01758753
Feng GDong DLu YRauchwerger LCameron KNikolopoulos DPnevmatikatos D(2022)Optimized MPI collective algorithms for dragonfly topologyProceedings of the 36th ACM International Conference on Supercomputing10.1145/3524059.3532380(1-11)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1145/3524059.3532380
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Parallel algorithms with ultra-fast expected times

An O(log N) deterministic packet-routing scheme

Time-communication trade-offs for minimum spanning tree construction

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations