The modern computation and information processing systems shaping our world have become massively distributed and a fundamental understanding of distributed lorithmics has never been more important. This shift towards distributed systems has resulted in increased interest and fast acceleration in our theoretical understanding of distributed optimization problems. At the same time, extremely general lower bound suncovered that any distributed optimization requires Θ(√n) rounds on some worst-case network topology, even if the diameter of the network is small. Many fundamental optimization problems, including MST, shortest paths, and cut/flow problems, now have "optimal" algorithms matching this worst-case performance bound. Real-world networks, however, are never worst-case and no network of interest shares the limiting bottleneck characteristics of the lower bound topology. In fact, there is no known barrier for ultra-fast polylogarithmic-round distributed algorithms on any network of interest.

In this thesis, we develop a theoretical understanding of when it is possible o go below the Θ(√n) bound. Our results include:

1. We show that planar networks, genus-bounded networks, and tree width-bounded networks admit Õ(D) round algorithms, where D is the network diameter. Similarly, we show that minor-free networks, a wide family subsuming all of the above, admit Õ(D2) round algorithms. Moreover, we give a single (uniform) and simple algorithm that works on all of these network classes by introducing a new framework called tree-restricted shortcuts. Prior to our work, only the planar network result was known and was significantly more complicated compared to ours.

2. We resolve the following 25-year-old open problem asked by Garay, Kutten, and Peleg: "What network topology parameters determine the complexity of distributed optimization?" We show that a previously studied parameter, the general shortcuts of best congestion+dilation, characterizes the complexity of distributed optimization for every network topology. In particular, this includes showing the first known non-trivial unconditional lower bound that is universal (i.e., applies to all graphs) and constructively matching that bound in the distributed known-topology setting.

191 pages

Thesis Committee:
Bernhard Haeupler (Chair)
Anupam Gupta
Gary L. Miller
Keren Censor-Hillel (Technion)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu