research-article

Near-Optimal Scheduling of Distributed Algorithms

Author:

Mohsen GhaffariAuthors Info & Claims

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

Pages 3 - 12

https://doi.org/10.1145/2767386.2767417

Published: 21 July 2015 Publication History

Abstract

This paper studies the question of how to run many distributed algorithms, solving independent problems, together as fast as possible. Suppose that we want to run distributed algorithms A_1, ..., A_k in the CONGEST model, each taking at most $dilation$ rounds, and where for each network edge, at most $congestion$ messages need to go through it, in total over all these algorithms. A celebrated work of Leighton, Maggs, and Rao[Combinatorica 1994] shows that in the special case where each of these algorithms is simply a packet routing---that is, sending a message from a source to a destination along a given path---there is an $O(congestion+dilation)$ round schedule. Note that this bound is trivially optimal.

Generalizing the framework of LMR, we study scheduling general distributed algorithms and present two results: (a) an existential schedule-length lower bound of Ω(congestion + dilation log n/log log n) rounds, (b) a distributed algorithm that produces a near-optimal O(congestion + dilation log n) round schedule, after O(dilation log² n) rounds of pre-computation.

A key challenge in the latter result is to solve the problem with only private randomness, as globally-shared randomness simplifies it significantly. The technique we use for this problem is in fact more general, and it can be used to remove the assumption of having shared randomness from a broad range of distributed algorithms, at the cost of a slow down factor of O(log² n).

References

[1]

Lecture notes on Algorithmic Power Tools. http://www.ccs.neu.edu/home/rraj/Courses/7880/F09/Lectures/GeneralLLL_Apps.pdf. Accessed: 2015-02.

[2]

Lecture notes on Algorithmic Power Tools. http://www.ccs.neu.edu/home/rraj/Courses/7880/F09/Lectures/PacketRouting.pdf. Accessed: 2015-02.

[3]

Lecture notes on k-wise uniform (randomness) generators. http://pages.cs.wisc.edu/~dieter/Courses/2013s-CS880/Scribes/PDF/lecture04.pdf. Accessed: 2015-02.

[4]

Lecture notes on Randomized Algorithms and Probabilistic Analysis. http://courses.cs.washington.edu/courses/cse525/13sp/scribe/lec10.pdf. Accessed: 2015-02.

[5]

Lecture notes on Randomness and Computation. http://www.cs.berkeley.edu/~sinclair/cs271/n22.pdf. Accessed: 2015-02.

[6]

N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, 2004.

[7]

F. M. Auf~der Heide and B. Vöcking. Shortest-path routing in arbitrary networks. Journal of Algorithms, 31(1):105--131, 1999.

Digital Library

[8]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 184--193. IEEE, 1996.

Digital Library

[9]

Y. Bartal. Graph decomposition lemmas and their role in metric embedding methods. In Algorithms--ESA 2004, pages 89--97. Springer, 2004.

[10]

D. Bertsimas and D. Gamarnik. Asymptotically optimal algorithms for job shop scheduling and packet routing. Journal of Algorithms, 33(2):296--318, 1999.

Digital Library

[11]

G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. SIAM Journal on Computing, 34(2):358--372, 2005.

Digital Library

[12]

A. Das~Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363--372, 2011.

Digital Library

[13]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 448--455. ACM, 2003.

Digital Library

[14]

R. G. Gallager, P. A. Humblet, and P. M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and systems (TOPLAS), 5(1):66--77, 1983.

Digital Library

[15]

E. Gat and S. Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. In Electronic Colloquium on Computational Complexity (ECCC), volume~18, page 136, 2011.

[16]

M. Ghaffari and F. Kuhn. Distributed minimum cut approximation. In Proc.\ of the Int'l Symp. on Dist. Comp. (DISC), pages 1--15, 2013.

Digital Library

[17]

S. Goldwasser. Pseudo-deterministic algorithms. In STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), volume~14, pages 29--29. LIPIcs, 2012.

[18]

S. Holzer and R. Wattenhofer. Optimal distributed all pairs shortest paths and applications. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 355--364. ACM, 2012.

Digital Library

[19]

H. Klauck. A strong direct product theorem for disjointness. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 77--86. ACM, 2010.

Digital Library

[20]

S. Kutten and D. Peleg. Fast distributed construction of k-dominating sets and applications. In the Proc.\ of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 238--251, 1995.

Digital Library

[21]

J. R. Lee and A. Naor. Extending lipschitz functions via random metric partitions. Inventiones mathematicae, 160(1):59--95, 2005.

[22]

F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling in O(congestion+dilation) steps. Combinatorica, 14(2):167--186, 1994.

[23]

T. Leighton, B. Maggs, and A. W. Richa. Fast algorithms for finding O(congestion+dilation) packet routing schedules. Combinatorica, 19(3):375--401, 1999.

[24]

C. Lenzen and D. Peleg. Efficient distributed source detection with limited bandwidth. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 375--382. ACM, 2013.

Digital Library

[25]

N. A. Lynch. Distributed algorithms. Morgan Kaufmann, 1996.

Digital Library

[26]

J. Nesetril, E. Milková, and H. Nesetrilová. Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics, 233(1):3--36, 2001.

Digital Library

[27]

R. Ostrovsky and Y. Rabani. Universal O(congestion+dilation+log1+ε n) local control packet switching algorithms. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 644--653. ACM, 1997.

Digital Library

[28]

B. Peis and A. Wiese. Universal packet routing with arbitrary bandwidths and transit times. In Integer Programming and Combinatoral Optimization, pages 362--375. Springer, 2011.

Digital Library

[29]

D. Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

[30]

Y. Rabani and É. Tardos. Distributed packet switching in arbitrary networks. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 366--375. ACM, 1996.

Digital Library

[31]

R. Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763--803, 1998.

Digital Library

[32]

T. Rothvoß. A simpler proof for O(congestion+dilation) packet routing. In Integer Programming and Combinatorial Optimization, pages 336--348. Springer, 2013.

Digital Library

[33]

C. Scheideler. Universal routing strategies for interconnection networks, volume 1390. Springer, 1998.

Digital Library

[34]

J. P. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223--250, 1995.

Digital Library

[35]

D. M. Topkis. Concurrent broadcast for information dissemination. Software Engineering, IEEE Transactions on, (10):1107--1112, 1985.

Digital Library

[36]

A. Wiese. Packet Routing and Scheduling. Cuvillier, 2011.

Cited By

Ghaffari MTrygub AKuznetsov PGelles ROlivetti D(2024)A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSPProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662812(401-411)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662812
Chang YHuang SSu HKuznetsov PGelles ROlivetti D(2024)Deterministic Expander Routing: Faster and More VersatileProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662797(194-204)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662797
Chandra SChang YDory MGhaffari MLeitersdorf DAgrawal KPetrank E(2024)Fast Broadcast in Highly Connected NetworksProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659959(331-343)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659959
Show More Cited By

Index Terms

Near-Optimal Scheduling of Distributed Algorithms
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

On the Use of Randomness in Local Distributed Graph Algorithms
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
We attempt to better understand randomization in local distributed graph algorithms by exploring how randomness is used and what we can gain from it:
- We first ask the question of how much randomness is needed to obtain efficient randomized algorithms. ...
Sublinear Message Bounds for Randomized Agreement
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

This paper focuses on understanding the message complexity of randomized agreement in synchronous distributed networks. We focus on the so-called implicit agreement problem where each node starts with an input value (0 or 1) and at the end one or more ...
Near-Optimal Scheduling in the Congested Clique
Structural Information and Communication Complexity
Abstract
This paper provides three nearly-optimal algorithms for scheduling t jobs in the $CLIQUE$ model. First, we present a deterministic scheduling algorithm that runs in $O (Global Congestion + dilation)$ rounds for jobs that are sufficiently efficient in ... $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

July 2015

508 pages

ISBN:9781450336178

DOI:10.1145/2767386

General Chair:
Chryssis Georgiou
University of Cyprus, Cyprus
,
Program Chair:
Paul G. Spirakis
University of Liverpool, UK & CTI, Greece

Copyright © 2015 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 the author(s) 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: 21 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

AFOSR
NSF
Simon's Institute for the Theory of Computing

Conference

PODC '15

Sponsor:

PODC '15: ACM Symposium on Principles of Distributed Computing

July 21 - 23, 2015

Donostia-San Sebastián, Spain

Acceptance Rates

PODC '15 Paper Acceptance Rate 45 of 191 submissions, 24%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
697
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghaffari MTrygub AKuznetsov PGelles ROlivetti D(2024)A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSPProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662812(401-411)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662812
Chang YHuang SSu HKuznetsov PGelles ROlivetti D(2024)Deterministic Expander Routing: Faster and More VersatileProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662797(194-204)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662797
Chandra SChang YDory MGhaffari MLeitersdorf DAgrawal KPetrank E(2024)Fast Broadcast in Highly Connected NetworksProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659959(331-343)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659959
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
Bodwin GParter M(2023)Restorable Shortest Path Tiebreaking for Edge-Faulty GraphsJournal of the ACM10.1145/360354270:5(1-24)Online publication date: 11-Oct-2023
https://doi.org/10.1145/3603542
Jiang YMukhopadhyay SSaha BServedio R(2023)Finding a Small Vertex Cut on Distributed NetworksProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585201(1791-1801)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585201
Parter M(2023)Secure Computation Meets Distributed Universal Optimality2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00144(2336-2368)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00144
Parter MPetruschka A(2023)Near-optimal distributed computation of small vertex cutsDistributed Computing10.1007/s00446-023-00455-z37:2(67-88)Online publication date: 14-Jul-2023
https://doi.org/10.1007/s00446-023-00455-z
Anagnostides ILenzen CHaeupler BZuzic GGouleakis T(2023)Almost universally optimal distributed Laplacian solvers via low-congestion shortcutsDistributed Computing10.1007/s00446-023-00454-036:4(475-499)Online publication date: 31-Jul-2023
https://doi.org/10.1007/s00446-023-00454-0
Eden TFiat NFischer OKuhn FOshman R(2022)Sublinear-time distributed algorithms for detecting small cliques and even cyclesDistributed Computing10.1007/s00446-021-00409-335:3(207-234)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s00446-021-00409-3
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.

Media

Figures

Other

Tables

View Table of Contents