Power and limitations of hybrid communication networks

Media type: E-Book

Title: Power and limitations of hybrid communication networks

Contributor: Schneider, Philipp [Verfasser]; Kuhn, Fabian [Akademischer Betreuer]; Kuhn, Fabian [Sonstige]; Censor-Hillel, Keren [Sonstige]

Corporation: Albert-Ludwigs-Universität Freiburg, Algorithms and Complexity ; Albert-Ludwigs-Universität Freiburg, Fakultät für Angewandte Wissenschaften

imprint: Freiburg: Universität, 2023

Extent: Online-Ressource

Language: English

DOI: 10.6094/UNIFR/232804

Identifier:

Keywords: Verteiltes System ; Funknetz ; Routing ; Verteilter Algorithmus ; Netzwerkverwaltung ; Ad-hoc-Netz ; Rechnernetz ; Distributed Computing ; Computational Complexity ; Graph Algorithms ; (local)doctoralThesis

Origination:

University thesis: Dissertation, Universität Freiburg, 2023

Footnote:

Description: Abstract: Distributed computing addresses problems where the input is distributed over the nodes of a network. The challenge is to design protocols that minimize the communication among nodes in order to solve such a problem. The communication among nodes that can occur per unit of time -- also called a round -- is usually subject to throughput, range or connection limitations. This raises the question how hybrid communication networks, which combine different communication modes with specific strengths and weaknesses affect the complexity, i.e., the number of rounds required to solve distributed problems. This work focuses on distributed systems based on hybrid communication networks that admit two fundamentally different principles of communication. A local mode, where in each round each node can send large messages to its neighbors in a local network (a graph); and a global mode where each node is allotted limited bandwidth per round for communicating with any node in the network. This reflects, for instance, communication among mobile devices via high-performance, short ranged wireless local networks and long range, bandwidth restricted communication via a cellular network. We first consider the important problems of broadcasting and unicasting multiple messages in such hybrid networks, for which we develop efficient protocols. We demonstrate that these lead to efficient solutions for graph problems defined on the local network, for instance shortest path problems, where nodes must compute distances to others. An important application of shortest paths algorithms is the computation of routing schemes, which is a packet forwarding problem that prominently arises in the Internet. On one hand, we show that our algorithms solve the aforementioned problems significantly faster than if either mode is used in isolation, which demonstrates the power of combining the local and global communication modes. On the other hand, we show that despite their relative power, hybrid networks exhibit fundamental limitations by establishing lower bounds on the required number of rounds to solve distributed problems

Access State: Open Access

Search in field:

Recently searched for: