research-article

Optimal deterministic routing and sorting on the congested clique

Author:

Christoph LenzenAuthors Info & Claims

PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

Pages 42 - 50

https://doi.org/10.1145/2484239.2501983

Published: 22 July 2013 Publication History

Abstract

Consider a clique of n nodes, where in each synchronous round each pair of nodes can exchange O(log n) bits. We provide deterministic constant-time solutions for two problems in this model. The first is a routing problem where each node is source and destination of n messages of size O(log n). The second is a sorting problem where each node i is given n keys of size O(log n) and needs to receive the i^th batch of n keys according to the global order of the keys. The latter result also implies deterministic constant-round solutions for related problems such as selection or determining modes.

References

[1]

R. Cole, K. Ost, and S. Schirra. Edge-Coloring Bipartite Multigraphs in O(|E| log Δ) Time. Combinatorica, 21:5--12, 2001.

[2]

D. Dolev, C. Lenzen, and S. Peled. "Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting. In Proc. 26th Symposium on Distributed Computing (DISC), pages 195--209, 2012.

Digital Library

[3]

M. Elkin. An Unconditional Lower Bound on the Time-Approximation Tradeoff for the Minimum Spanning Tree Problem. SIAM Journal on Computing, 36(2):463--501, 2006.

Digital Library

[4]

S. Frischknecht, S. Holzer, and R. Wattenhofer. Networks Cannot Compute Their Diameter in Sublinear Time. In Proc. 23rd Symposium on Discrete Algorithms (SODA), pages 1150--1162, 2012.

Digital Library

[5]

M. T. Goodrich. Communication-Efficient Parallel Sorting. SIAM Journal on Computing, 29(2):416--432, Oct. 1999.

Digital Library

[6]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local Computation: Lower and Upper Bounds. Computing Research Repository, abs/1011.5470, 2010.

[7]

C. Lenzen and R. Wattenhofer. Tight Bounds for Parallel Randomized Load Balancing. In Proc. 43rd Symposium on Theory of Computing (STOC), pages 11--20, 2011.

Digital Library

[8]

N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193--201, 1992.

Digital Library

[9]

Z. Lotker, B. Patt-Shamir, and D. Peleg. Distributed MST for Constant Diameter Graphs. Distributed Computing, 18(6):453--460, 2006.

Digital Library

[10]

L. Lovász and M. D. Plummer. Matching Theory. American Mathematical Society, 2009. Reprint with corrections.

[11]

M. Naor. A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring. SIAM Journal on Discrete Mathematics, 4(3):409--412, 1991.

[12]

B. Patt-Shamir and M. Teplitsky. The Round Complexity of Distributed Sorting: Extended Abstract. In Proc. 30th Symposium on Principles of Distributed Computing (PODC), pages 249--256, 2011.

Digital Library

[13]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000.

Digital Library

[14]

D. Peleg and V. Rubinovich. Near-tight Lower Bound on the Time Complexity of Distributed MST Construction. SIAM Journal on Computing, 30:1427--1442, 2000.

Digital Library

[15]

A. D. Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed Verification and Hardness of Distributed Approximation. SIAM Journal on Computation, 41(5):1235--1265, 2012.

Cited By

Bui HChandra SChang YDory MLeitersdorf DKuznetsov PGelles ROlivetti D(2024)Improved All-Pairs Approximate Shortest Paths in Congested CliqueProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662804(391-400)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662804
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
Ghaffari MWang BMohar BShinkar IO'Donnell R(2024)Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time RoutabilityProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649627(1877-1888)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649627
Show More Cited By

Index Terms

Optimal deterministic routing and sorting on the congested clique

Recommendations

Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

We study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the well-studied Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these ...
Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-...
Optimal Time-Space Trade-Offs for Sorting
FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science

We study the fundamental problem of sorting in a sequential model of computation and in particular consider the time-space trade-off (product of time and space) for this problem.Beame has shown a lower bound of $\Omega(n^2)$ for this product leaving a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

July 2013

422 pages

ISBN:9781450320658

DOI:10.1145/2484239

General Chair:
Panagiota Fatourou
FORTH ICS & University of Crete, Greece
,
Program Chair:
Gadi Taubenfeld
IDC, Israel

Copyright © 2013 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '13

Sponsor:

PODC '13: ACM Symposium on Principles of Distributed Computing

July 22 - 24, 2013

Québec, Montréal, Canada

Acceptance Rates

PODC '13 Paper Acceptance Rate 37 of 145 submissions, 26%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

82
Total Citations
View Citations
525
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)3

Reflects downloads up to 11 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bui HChandra SChang YDory MLeitersdorf DKuznetsov PGelles ROlivetti D(2024)Improved All-Pairs Approximate Shortest Paths in Congested CliqueProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662804(391-400)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662804
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
Ghaffari MWang BMohar BShinkar IO'Donnell R(2024)Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time RoutabilityProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649627(1877-1888)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649627
Saikia P(2024)An O(1)-rounds Deterministic Distributed Approximation Algorithm for the Traveling Salesman Problem in Congested Clique2024 20th International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT)10.1109/DCOSS-IoT61029.2024.00034(179-186)Online publication date: 29-Apr-2024
https://doi.org/10.1109/DCOSS-IoT61029.2024.00034
Lingas A(2024)Boolean Matrix Multiplication for Highly Clustered Data on the Congested CliqueEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_4(45-58)Online publication date: 26-Aug-2024
https://doi.org/10.1007/978-3-031-69583-4_4
Biabani LPaz A(2024)k-Center Clustering in Distributed ModelsStructural Information and Communication Complexity10.1007/978-3-031-60603-8_5(83-100)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_5
Kerger PBernal Neira DGonzalez Izquierdo ZRieffel E(2023)Mind the O˜: Asymptotically Better, but Still Impractical, Quantum Distributed AlgorithmsAlgorithms10.3390/a1607033216:7(332)Online publication date: 11-Jul-2023
https://doi.org/10.3390/a16070332
Behnezhad SHajiaghayi MHarris D(2023)Exponentially Faster Massively Parallel Maximal MatchingJournal of the ACM10.1145/361736070:5(1-18)Online publication date: 11-Oct-2023
https://dl.acm.org/doi/10.1145/3617360
Forster Sde Vos TOshman RNolin AHalldorsson MBalliu A(2023)Brief Announcement: The Laplacian Paradigm in Deterministic Congested CliqueProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594577(75-78)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594577
Robinson POshman RNolin AHalldorsson MBalliu A(2023)Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594575(168-171)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594575
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten