Can I read Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model on EtoBox?

Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model by Chang, Yi-Jun; Hecht, Oren; Leitersdorf, Dean is a scholarly article available to read on EtoBox.

What is Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model about?

In theoretical computer science, it is a common practice to show existential lower bounds for problems, meaning there is a family of pathological inputs on which no algorithm can do better. However, most inputs of interest can be solved much more efficiently, giving rise to the notion of universally optimal algorithms, which run as fast as possible on every input. Questions on the existence of universally optimal algorithms were first raised by Garay, Kutten, and Peleg in FOCS '93. This research direction reemerged recently through a series of works, including the influential work of Haeupler, Wajc, and Zuzic in STOC '21, which resolves some of these decades-old questions in the supported CONGEST model. We work in the HYBRID distributed model, which analyzes networks combining both global and local communication. Much attention has recently been devoted to solving distance related problems, such as All-Pairs Shortest Paths (APSP) in HYBRID, culminating in a $\tilde \Theta(n^{1/2})$ round algorithm for exact APSP. However, by definition, every problem in HYBRID is solvable in $D$ (diameter) rounds, showing that it is far from universally optimal. We show the first universally optima

Author

Chang, Yi-Jun; Hecht, Oren; Leitersdorf, Dean

Published

2023

Language

EN