Wednesday, October 19, 2016 - 12:00pm to 1:00pm
Location:8102 Gates & Hillman Centers
Speaker:GORAN ZUZIC, Ph.D. Student https://www.linkedin.com/in/goran-%C5%BEu%C5%BEi%C4%87-59658045
Solving optimization problems on large distributed system have been studied in great depth owing to their usefulness in internet protocols. Problems such as Minimum Spanning Tree and Min-Cut in this model have a long history of continuously improving algorithms and lower bounds. A model of particular interest is the one when all the nodes communicate in synchronous rounds with small,O(logn) sized, messages. However, it appeared that their development reached a stalemate when a matching upper and lower bound of Θ(diameter+n) was ascertained. Nevertheless, real-world graphs do not exhibit the strong lower bound properties and can typically be solved more efficiently. I will introduce the Shortcut framework that can be used to tackle the question. The framework allows us to easily reason and design otherwise fairly complex distributed algorithms. As an important consequence, the framework was used to construct the first sub-n -round protocol that works on several important graph classes, like planar and treewidth-bounded graphs. — Goran Zuzic is a second-year PhD student in CSD at CMU. He is advised by Bernhard Haeupler.