Round- and message-optimal distributed graph algorithms

DOI10.1145/3212734.3212737MaRDI QIDQ5197673zbMATH OpenOpenAlexWikidataFDO

Authors Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.05127

zbMATH Keywords

Congestdistributed graph algorithmslow-congestion shortcutspart-wise aggregation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Abstract: Distributed graph algorithms that separately optimize for either the number of rounds used or the total number of messages sent have been studied extensively. However, algorithms simultaneously efficient with respect to both measures have been elusive. For example, only very recently was it shown that for Minimum Spanning Tree (MST), an optimal message and round complexity is achievable (up to polylog terms) by a single algorithm in the CONGEST model of communication. In this paper we provide algorithms that are simultaneously round- and message-optimal for a number of well-studied distributed optimization problems. Our main result is such a distributed algorithm for the fundamental primitive of computing simple functions over each part of a graph partition. From this algorithm we derive round- and message-optimal algorithms for multiple problems, including MST, Approximate Min-Cut and Approximate Single Source Shortest Paths, among others. On general graphs all of our algorithms achieve worst-case optimal $ildeO(D+sqrtn)$ round complexity and $ildeO(m)$ message complexity. Furthermore, our algorithms require an optimal $ildeO(D)$ rounds and $ildeO(n)$ messages on planar, genus-bounded, treewidth-bounded and pathwidth-bounded graphs.

Recommendations

• Distributed MST and broadcast with fewer messages, and faster gossiping

Cited in

(18)

• Optimal distributed algorithms in unlabeled tori and chordal rings
• Latency, capacity, and distributed minimum spanning trees
• Low-congestion shortcut and graph parameters
• Low-congestion shortcuts without embedding
• Distributed computing of efficient routing schemes in generalized chordal graphs
• A Class of Optimal Structures for Node Computations in Message Passing Algorithms
• Distributed MST and broadcast with fewer messages, and faster gossiping
• Time-message trade-offs in distributed algorithms
• Minor excluded network families admit fast distributed algorithms
• Distributed algorithms for planar networks. I: Planar embedding
• A novel pseudo‐polynomial approach for shortest path problems
• A note on the message complexity of Cidon's distributed depth-first search algorithm
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Singularly optimal randomized leader election
• Distributed planar reachability in nearly optimal time
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Near-optimal schedules for simultaneous multicasts
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions

This page was built for publication: Round- and message-optimal distributed graph algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197673)