On Sparsity Awareness in Distributed Computations
Keren Censor-Hillel, Dean Leitersdorf, Volodymyr Polosukhin · 2021
We extract a core principle that underlies seemingly different fundamental distributed settings, which is that sparsity awareness may induce faster algorithms for core problems in these settings. To leverage this, we establish a new framework by developing an intermediate auxiliary model which is weak enough to be successfully simulated in the classic congest model given low mixing time, as well as in the recently introduced hybrid model. We prove that despite imposing harsh restrictions, this artificial model allows balancing massive data transfers with a maximal utilization of bandwidth. We then exemplify the power we gain from our methods, by deriving fast shortest-paths algorithms which greatly improve upon the state-of-the-art.