Message Reduction in the Local Model is a Free Lunch
share
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 + ε) edges (for an arbitrarily small constant ε > 0) is constructed in a constant number of rounds sending O (n^1 + ε) 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 + ε) messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a log^Ω (1) n blow-up of the round complexity.
READ FULL TEXT