Dufoulon, Fabien ;
Emek, Yuval ;
Gelles, Ran
Beeping Shortest Paths via Hypergraph Bipartite Decomposition
Abstract
Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in O(D log log n + log³ n) rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in O(D log² n + log³ n) rounds with high probability.
Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the hyperedge set of a hypergraph H = (V_H, E_H) into k = Θ (log² n) disjoint subsets F₁ ∪ ⋯ ∪ F_k = E_H such that the (sub)hypergraph (V_H, F_i) is bipartite in the sense that there exists a vertex subset U ⊆ V such that U ∩ e = 1 for every e ∈ F_i. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.
BibTeX  Entry
@InProceedings{dufoulon_et_al:LIPIcs.ITCS.2023.45,
author = {Dufoulon, Fabien and Emek, Yuval and Gelles, Ran},
title = {{Beeping Shortest Paths via Hypergraph Bipartite Decomposition}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {45:145:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17548},
URN = {urn:nbn:de:0030drops175485},
doi = {10.4230/LIPIcs.ITCS.2023.45},
annote = {Keywords: Beeping Networks, Shortest Paths, Hypergraph Bipartite Decomposition}
}
01.02.2023
Keywords: 

Beeping Networks, Shortest Paths, Hypergraph Bipartite Decomposition 
Seminar: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Issue date: 

2023 
Date of publication: 

01.02.2023 