License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.28
URN: urn:nbn:de:0030-drops-172198
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17219/
Kuhn, Fabian ;
Schneider, Philipp
Routing Schemes and Distance Oracles in the Hybrid Model
Abstract
The HYBRID model was introduced as a means for theoretical study of distributed networks that use various communication modes. Conceptually, it is a synchronous message passing model with a local communication mode, where in each round each node can send large messages to all its neighbors in a local network (a graph), and a global communication mode, where each node is allotted limited (polylogarithmic) bandwidth per round to communicate with any node in the network.
Prior work has often focused on shortest paths problems in the local network, as their global nature makes these an interesting case study how combining communication modes in the HYBRID model can overcome the individual lower bounds of either mode. In this work we consider a similar problem, namely computation of distance oracles and routing schemes. In the former, all nodes have to compute local tables, which allows them to look up the distance (estimates) to any target node in the local network when provided with the label of the target. In the latter, it suffices that nodes give the next node on an (approximately) shortest path to the target.
Our goal is to compute these local tables as fast as possible with labels as small as possible. We show that this can be done exactly in Õ(n^{1/3}) communication rounds and labels of size Θ(n^{2/3}) bits. For constant stretch approximations we achieve labels of size O(log n) in the same time. Further, as our main technical contribution, we provide computational lower bounds for a variety of problem parameters. For instance, we show that computing solutions with stretch below a certain constant takes Ω̃(n^{1/3}) rounds even for labels of size O(n^{2/3}).
BibTeX - Entry
@InProceedings{kuhn_et_al:LIPIcs.DISC.2022.28,
author = {Kuhn, Fabian and Schneider, Philipp},
title = {{Routing Schemes and Distance Oracles in the Hybrid Model}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {28:1--28:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-255-6},
ISSN = {1868-8969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17219},
URN = {urn:nbn:de:0030-drops-172198},
doi = {10.4230/LIPIcs.DISC.2022.28},
annote = {Keywords: Distributed Computing, Graph Algorithms, Complexity Analysis}
}
|
Keywords: |
|
Distributed Computing, Graph Algorithms, Complexity Analysis |
|
Collection: |
|
36th International Symposium on Distributed Computing (DISC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
17.10.2022 |
