Distance Computation in Distributed Networks

Michal Dory, Ph.D. Thesis Seminar
Wednesday, 24.6.2020, 14:30
Zoom Lecture: https://technion.zoom.us/j/99489358773
Prof. Keren Censor-Hillel

In this talk, I will describe a couple of results from my PhD thesis, that studies distributed algorithms for connectivity and distance related graph problems. I will focus on a recent line of work studying distance computation in the Congested Clique model of distributed computing. We design fast algorithms for the fundamental all-pairs shortest paths (APSP) and multi-source shortest paths (MSSP) problems. In particular, we show constant-factor approximation algorithms for weighted APSP and MSSP that take just poly-logarithmic time. Moreover, in unweighted graphs, we solve the same problems much faster, in just poly(loglogn) time. All previous algorithms require at least a polynomial number of rounds. Our main techniques are new distance tools we develop, based on sparse matrix multiplication, and a new fast construction of a near-additive emulator, a sparse graph that preserves the distances of the original graph up to a near-additive stretch. Based on joint works with Keren Censor-Hillel, Janne H Korhonen, Dean Leitersdorf, and Merav Parter.

Back to the index of events