Universally-optimal distributed algorithms for known topologies

Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions:

Authors

• Bernhard Haeupler
• David Wajc
• Goran Zuzic

Keywords

• Distributed Algorithms
• Shortcut Quality
• Shortcuts
• Universal Optimality
• Universal Lower Bounds