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.ITCS.2023.45
URN: urn:nbn:de:0030-drops-175485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17548/
Go to the corresponding LIPIcs Volume Portal

Dufoulon, Fabien ; Emek, Yuval ; Gelles, Ran

Beeping Shortest Paths via Hypergraph Bipartite Decomposition

pdf-format:
LIPIcs-ITCS-2023-45.pdf (0.8 MB)

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:1--45:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17548},
  URN =		{urn:nbn:de:0030-drops-175485},
  doi =		{10.4230/LIPIcs.ITCS.2023.45},
  annote =	{Keywords: Beeping Networks, Shortest Paths, Hypergraph Bipartite Decomposition}
}

Keywords: Beeping Networks, Shortest Paths, Hypergraph Bipartite Decomposition
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI