Fast Broadcast in Highly Connected Networks
SPAA ’24, June 17–21, 2024, Nantes, France
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM|SPAA '24: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155768 |
| _version_ | 1811082981387796480 |
|---|---|
| author | Chandra, Shashwat Chang, Yi-Jun Dory, Michal Ghaffari, Mohsen Leitersdorf, Dean |
| author_facet | Chandra, Shashwat Chang, Yi-Jun Dory, Michal Ghaffari, Mohsen Leitersdorf, Dean |
| author_sort | Chandra, Shashwat |
| collection | MIT |
| description | SPAA ’24, June 17–21, 2024, Nantes, France |
| first_indexed | 2024-09-23T12:16:29Z |
| format | Article |
| id | mit-1721.1/155768 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:16:29Z |
| publishDate | 2024 |
| publisher | ACM|SPAA '24: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures |
| record_format | dspace |
| spelling | mit-1721.1/1557682024-09-22T04:39:53Z Fast Broadcast in Highly Connected Networks Chandra, Shashwat Chang, Yi-Jun Dory, Michal Ghaffari, Mohsen Leitersdorf, Dean SPAA ’24, June 17–21, 2024, Nantes, France We revisit the classic broadcast problem, wherein we have k messages, each composed of O(log n) bits, distributed arbitrarily across a network. The objective is to broadcast these messages to all nodes in the network. In the distributed CONGEST model, a textbook algorithm solves this problem in O(D+k) rounds, where D is the diameter of the graph. While the O(D) term in the round complexity is unavoidable---given that Ω(D) rounds are necessary to solve broadcast in any graph ---it remains unclear whether the O(k) term is needed in all graphs. In cases where the minimum cut size is one, simply transmitting messages from one side of the cut to the other would require Ω(k) rounds. However, if the size of the minimum cut is larger, it may be possible to develop faster algorithms. This motivates the exploration of the broadcast problem in networks with high edge connectivity. In this work, we present a simple randomized distributed algorithm for performing k-message broadcast in O(((n+k)/λ)log n) rounds in any n-node simple graph with edge connectivity λ. When k = Ω(n), our algorithm is universally optimal, up to an O(log n) factor, as its complexity nearly matches an information-theoretic Ω(k/λ) lower bound that applies to all graphs, even when the network topology is known to the algorithm. The setting k = Ω(n) is particularly interesting because several fundamental problems can be reduced to broadcasting Ω(n) messages. Our broadcast algorithm finds several applications in distributed computing, enabling O(1)-approximation for all distances and (1+ε)-approximation for all cut sizes in ~O(n/λ) rounds. 2024-07-23T19:21:36Z 2024-07-23T19:21:36Z 2024-06-17 2024-07-01T07:53:03Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0416-1 https://hdl.handle.net/1721.1/155768 Chandra, Shashwat, Chang, Yi-Jun, Dory, Michal, Ghaffari, Mohsen and Leitersdorf, Dean. 2024. "Fast Broadcast in Highly Connected Networks." PUBLISHER_CC en 10.1145/3626183.3659959 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM|SPAA '24: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures Association for Computing Machinery |
| spellingShingle | Chandra, Shashwat Chang, Yi-Jun Dory, Michal Ghaffari, Mohsen Leitersdorf, Dean Fast Broadcast in Highly Connected Networks |
| title | Fast Broadcast in Highly Connected Networks |
| title_full | Fast Broadcast in Highly Connected Networks |
| title_fullStr | Fast Broadcast in Highly Connected Networks |
| title_full_unstemmed | Fast Broadcast in Highly Connected Networks |
| title_short | Fast Broadcast in Highly Connected Networks |
| title_sort | fast broadcast in highly connected networks |
| url | https://hdl.handle.net/1721.1/155768 |
| work_keys_str_mv | AT chandrashashwat fastbroadcastinhighlyconnectednetworks AT changyijun fastbroadcastinhighlyconnectednetworks AT dorymichal fastbroadcastinhighlyconnectednetworks AT ghaffarimohsen fastbroadcastinhighlyconnectednetworks AT leitersdorfdean fastbroadcastinhighlyconnectednetworks |