Optimal Dynamic Distributed MIS

Abstract: I will describe how we can exploit the locality of a maximal independent set (MIS) to the extreme, by showing how to update an MIS in a dynamic distributed setting within only a single adjustment in expectation. This holds for all changes: edge- and node- insertions and removals, gracefully and abruptly. The approach is surprisingly simple and is based on a novel analysis of the sequential random greedy algorithm.

No background in distributed computing will be assumed. The talk is based on joint work with Elad Haramaty and Zohar Karnin