Beeping Shortest Paths via Hypergraph Bipartite Decomposition
share
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 loglog n + log^3 n) rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in O (D log^2 n + log^3 n) rounds with high probability. The key technique behind the aforementioned schemes is a novel decomposition of hypergraphs into bipartite hypergraphs. Namely, we show how to partition the hyperedge set of a hypergraph H = (V_H, E_H) into k = Θ (log^2 n) disjoint subsets F_1 ∪⋯∪ 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 decomposition turns out to be instrumental in speeding up shortest path constructions under the beeping model.
READ FULL TEXT