Optimal Dynamic Distributed MIS

תאריך: 
23/05/2017 - 14:00 - 15:00
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

מרצה: 
Keren Censor-Hillel
דוא"ל להרשמה: 
Affiliation: 
Computer Science Department, Technion I.I.T
מיקום: 
BIU Engineering Building 1103, Room 329