Optimal Dynamic Distributed MIS

תאריך
-
Speaker
Keren Censor-Hillel
Place
BIU Engineering Building 1103, Room 329
Affiliation
Computer Science Department, Technion I.I.T
Abstract

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

תאריך עדכון אחרון : 04/12/2022