Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.7
URN: urn:nbn:de:0030-drops-113145
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11314/
Bitton, Shimon ; Emek, Yuval ; Izumi, Taisuke ; Kutten, Shay
Message Reduction in the LOCAL Model Is a Free Lunch
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{bitton_et_al:LIPIcs:2019:11314,
author = {Shimon Bitton and Yuval Emek and Taisuke Izumi and Shay Kutten},
title = {{Message Reduction in the LOCAL Model Is a Free Lunch}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-126-9},
ISSN = {1868-8969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11314},
URN = {urn:nbn:de:0030-drops-113145},
doi = {10.4230/LIPIcs.DISC.2019.7},
annote = {Keywords: distributed graph algorithms, spanner, LOCAL model, message complexity}
}
| Keywords: | distributed graph algorithms, spanner, LOCAL model, message complexity | |
| Seminar: | 33rd International Symposium on Distributed Computing (DISC 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 08.10.2019 |
