A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
PODC ’24, June 17–21, 2024, Nantes, France
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155520 |
| _version_ | 1811006151146340352 |
|---|---|
| author | Ghaffari, Mohsen Trygub, Anton |
| author_facet | Ghaffari, Mohsen Trygub, Anton |
| author_sort | Ghaffari, Mohsen |
| collection | MIT |
| description | PODC ’24, June 17–21, 2024, Nantes, France |
| first_indexed | 2024-09-23T16:47:33Z |
| format | Article |
| id | mit-1721.1/155520 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:47:33Z |
| publishDate | 2024 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1555202024-09-08T04:24:45Z A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP Ghaffari, Mohsen Trygub, Anton PODC ’24, June 17–21, 2024, Nantes, France We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in Õ(n) rounds and each node is awake during only poly(log n) rounds. When a node is not awake, it performs no computations or communications and spends no energy. The general approach we take along the way to this result can be viewed as a novel adaptation of Dijkstra's classic approach to SSSP, which makes it suitable for the distributed setting. Notice that Dijkstra's algorithm itself is not efficient in the distributed setting due to its need for repeatedly computing the minimum-distance unvisited node in the entire network. Our adapted approach has other implications, as we outline next. As a step toward the above end-result, we obtain a simple deterministic algorithm for exact SSSP with near-optimal time and message complexities of Õ(n) and Õ(m), in which each edge communicates only poly(log n) messages. Therefore, one can simultaneously run n instances of it for n sources, using a simple random delay scheduling. That computes All Pairs Shortest Paths (APSP) in the near-optimal time complexity of Õ(n). This algorithm matches the complexity of the recent APSP algorithm of Bernstein and Nanongkai [STOC 2019] using a completely different method (and one that is more modular, in the sense that the SSSPs are solved independently). It also takes a step toward resolving the open problem on a deterministic Õ(n)-time APSP, as the only randomness used now is in the scheduling. 2024-07-09T16:21:23Z 2024-07-09T16:21:23Z 2024-06-17 2024-07-01T08:00:28Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0668-4 https://hdl.handle.net/1721.1/155520 Ghaffari, Mohsen and Trygub, Anton. 2024. "A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP." PUBLISHER_CC en 10.1145/3662158.3662812 Creative Commons Attribution-NoDerivs License https://creativecommons.org/licenses/by-nd/4.0/ The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Ghaffari, Mohsen Trygub, Anton A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP |
| title | A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP |
| title_full | A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP |
| title_fullStr | A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP |
| title_full_unstemmed | A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP |
| title_short | A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP |
| title_sort | near optimal low energy deterministic distributed sssp with ramifications on congestion and apsp |
| url | https://hdl.handle.net/1721.1/155520 |
| work_keys_str_mv | AT ghaffarimohsen anearoptimallowenergydeterministicdistributedssspwithramificationsoncongestionandapsp AT trygubanton anearoptimallowenergydeterministicdistributedssspwithramificationsoncongestionandapsp AT ghaffarimohsen nearoptimallowenergydeterministicdistributedssspwithramificationsoncongestionandapsp AT trygubanton nearoptimallowenergydeterministicdistributedssspwithramificationsoncongestionandapsp |