2026-07-24T03:28:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11314 2024-03-06T10:47:55Z ddc:004 open_access

Message Reduction in the LOCAL Model Is a Free Lunch Bitton, Shimon Emek, Yuval Izumi, Taisuke Kutten, Shay distributed graph algorithms spanner LOCAL model message complexity A new spanner construction algorithm is presented, working under the LOCAL model with unique edge IDs. Given an n-node communication graph, a spanner with a constant stretch and O(n^{1 + epsilon}) edges (for an arbitrarily small constant epsilon > 0) is constructed in a constant number of rounds sending O(n^{1 + epsilon}) messages whp. Consequently, we conclude that every t-round LOCAL algorithm can be transformed into an O(t)-round LOCAL algorithm that sends O(t * n^{1 + epsilon}) messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a log^{Omega (1)} n blow-up of the round complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shimon Bitton and Yuval Emek and Taisuke Izumi and Shay Kutten 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.7 urn:nbn:de:0030-drops-113145 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.7 eng https://creativecommons.org/licenses/by/3.0/legalcode