2022/10/13 by Fabien Dufoulon, Dufoulon, Fabien, Yuval Emek +3
Computer Science · Biochemistry, Genetics and Molecular Biology · #Complexity and Algorithms in Graphs #Stochastic Gradient Optimization Techniques #Advanced biosensing and bioanalysis techniques
paper · pdf · doi:10.48550/arxiv.2210.06882
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 + log3 n) rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in O (D log2 n + log3 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 (polynomially-large) hyperedge set of a hypergraph H = (VH, EH) into k = Θ(log2 n) disjoint subsets F1 ∪ ⋯ ∪ Fk = EH such that the (sub-)hypergraph (VH, Fi) is bipartite in the sense that there exists a vertex subset U ⊆ V such that |U ∩ e| = 1 for every e ∈ Fi. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.