Bridging the gap between theory and practice for distributed graph algorithms

弥合分布式图算法理论与实践之间的差距

• 批准号: 21KK0204
• 负责人: シュワルツマン グレゴリー
• 金额: $ 6.74万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Fund for the Promotion of Joint International Research (Fostering Joint International Research (A))
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022 至 2023
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21KK0204/
• 关键词: Theory; Networking; Graph algorithms

During my stay in Europe we achieved great progress in the project. On the practical side, we implemented many theory primitives (spanners, synchronizers, spanning trees) on P4 switches and checked their efficiency at handling failures in datacenter networks. The main problems we considered are clock synchronization and multicast. We show that using our techniques we can recover from failures considerably faster than other techniques.On the theory side we defined a theoretical model for distributed computation with bounded memory. We believe that this two way approach will greatly increase the communication between the theory and networking community.

我在欧洲逗留期间，我们的项目取得了很大进展。在实践方面，我们在P4交换机上实现了许多理论原语（spatial，同步器，生成树），并检查了它们在处理数据中心网络故障时的效率。我们考虑的主要问题是时钟同步和多播。我们表明，使用我们的技术，我们可以从故障中恢复得比其他technology.On的理论方面，我们定义了一个理论模型的分布式计算有界内存。我们相信，这种双向的方法将大大增加理论和网络社区之间的沟通。

项目成果

Mini-batch k-means terminates within O(d/ε) iterations

• DOI: 10.48550/arxiv.2304.00419
• 发表时间: 2023
• 期刊: ArXiv
• 作者: Gregory Schwartzman

Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs

低树宽图中的完全多项式时间分布式计算

• DOI: 10.1145/3490148.3538590
• 发表时间: 2022
• 期刊: Proc. of International Symposium on Parallelism in Algorithms and Architectures (SPAA)
• 作者: Izumi Taisuke;Kitamura Naoki;Naruse Takamasa;Schwartzman Gregory
• 通讯作者: Schwartzman Gregory