Back to search

Cornell University

Algorithmic techniques for optimal collective communication

Abstract

dc:description.abstract

Improving the performance of collective communication---algorithms for coordinated data movement in distributed computing---becomes increasingly important as the use of large-scale machine learning clusters continues to grow. In this work, we introduce techniques for synthesizing optimal algorithms for collective communication for any given host and network topology. We provide a novel multicommodity flow-based approach that allows us to find provably optimal algorithms in terms of both latency and bandwidth utilization. Critical to our techniques are two important innovations: a conversion method from fluid solutions to discrete step-based solutions, and Mirrored Dantzig-Wolfe, which exploits the high degree of symmetry often present in communication networks. We complement our theoretical contributions with experimental results, demonstrating the practical efficacy of the constructed algorithms.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shapley, Richard
Chair dc:contributor.chair
  • Shmoys, David
Committee members dc:contributor.committeemember
  • Banerjee, Siddhartha
  • Williamson, David

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
17422614
Dc Identifier Other
ProQuest Submission ID: 15258
ProQuest Publication ID: 32171531

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shapley, Richard. Algorithmic techniques for optimal collective communication. Doctor of Philosophy thesis, Cornell University, 2025. https://hdl.handle.net/1813/120754