October 19, 2016

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 $n$ nodes communicate in synchronous rounds with small, $O(\log n)$ sized, messages. However, it appeared that their development reached a stalemate when a matching upper and lower bound of $\Theta(diameter + \sqrt{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-$\sqrt{n}$-round protocol that works on several important graph classes, like planar and treewidth-bounded graphs.