AF: Small: Distributed Optimization Beyond Worst Case Topologies

点击翻译按钮获取中文摘要

The modern computation and information processing systems shaping our world are ever increasing in scale and have become massively distributed. A fundamental understanding of distributed algorithms and optimization problems has in the past and inevitably will in the future lead to more efficient, more scalable, and overall vastly more powerful systems and applications with broad impacts on society. With this goal in mind, this project is developing an algorithmic toolbox for designing distributed optimization algorithms which drastically outperform state-of-the-art algorithms on non-worst-case topologies, common in practice. The project will also contribute greatly to the education and professional training of students in this critical field. The project plans to integrate research and education through curriculum development activities spanning graduate and undergraduate courses and provides initiatives and concrete steps taken by the project team to attract, excite, mentor, and support students from underrepresented groups.The shift towards massively distributed systems in practice has led to an increased interest and fast acceleration in our theoretical understanding of distributed optimization problems. However much of this work focuses on the algorithmic performance in worst-case topologies. Real world networks, however, do not always exhibit worst-case behavior and most networks of interest do not share the limiting bottleneck characteristics which dominate the current analyses of worst-case algorithms and their provable performance guarantees. In particular, there is no known barrier for ultra-fast polylogarithmic round distributed algorithms on any network of interest, while most current algorithms require Theta(sqrt(n)) rounds on any (such) topology, mostly because such a running time can be shown to be necessary on some practically irrelevant pathologically bad topologies. This almost exponential gap between worst-case-optimal Theta(sqrt(n)) algorithms and the ultra-fast performance which is likely possible in many, if not all, real-world settings motivates this project. This project provides a detailed program for designing instance-optimal distributed algorithms. Instance-optimal algorithms are competitive with the best algorithm on any given topology and thereby constitute the strongest possible form of algorithmically adjusting to non-worst-case topologies.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.