The Library
Routing schemes for hybrid communication networks
Tools
Coy, Sam, Czumaj, Artur, Scheideler, Christian, Schneider, Philipp and Werthmann, Julian (2024) Routing schemes for hybrid communication networks. Theoretical Computer Science, 985 . 114352. doi:10.1016/j.tcs.2023.114352 ISSN 0304-3975.
|
PDF
WRAP-routing-schemes-hybrid-communication-networks-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1356Kb) | Preview |
Official URL: https://doi.org/10.1016/j.tcs.2023.114352
Abstract
We consider the problem of computing routing schemes in the HYBRID model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the HYBRID model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the HYBRID model. We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time O(|H|2+logn), label size O(logn), and size of routing tables O(|H|2⋅logn) where |H| is the number of “radio holes” in the network. Our work builds on recent work by Coy et al., who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Electronic data processing -- Distributed processing , Routing (Computer network management) , Computer algorithms | |||||||||||||||
Journal or Publication Title: | Theoretical Computer Science | |||||||||||||||
Publisher: | Elsevier Science BV | |||||||||||||||
ISSN: | 0304-3975 | |||||||||||||||
Official Date: | 21 February 2024 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 985 | |||||||||||||||
Article Number: | 114352 | |||||||||||||||
DOI: | 10.1016/j.tcs.2023.114352 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Copyright Holders: | ||||||||||||||||
Date of first compliant deposit: | 3 January 2024 | |||||||||||||||
Date of first compliant Open Access: | 4 January 2024 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year