PaperlayerView exact revision on arXiv

Source-linked AI summary

Throughput-Optimal Topology Design for Cross-Silo Federated Learning

Othmane Marfoq, Chuan Xu, Giovanni Neglia, Richard Vidal

arXiv:2010.12229v2cs.LGcs.DCcs.NImath.OC

TL;DR

Cross-silo federated learning can miss fast peer links when communication runs through an orchestrator. This paper uses max-plus systems to optimize topology throughput while accounting for network delays; its reported comparisons show faster training than STAR and MATCHA in the cited settings.

  • Problem

    In cross-silo federated learning, orchestrator-centered communication can ignore fast inter-silo links and make the orchestrator a potential congestion point.

    Source: §1 · p. 2

  • Method

    The paper uses max-plus linear systems to design cross-silo topologies that minimize communication-round duration, equivalently maximizing throughput.

    Source: §1 · p. 2

  • Results

    The RING is 9.4 times faster than STAR on Ebone and 1.5 to 6 times faster than MATCHA; speedups grow as access links slow.

    Source: §1 · p. 2, §4 · p. 8

  • Takeaways & Limitations

    Topology design based on system throughput is more promising than targeting the best spectral properties, as MATCHA(+) does.

    Source: §5 · p. 9

    The measured network quantities are assumed not to vary or to vary slowly, so topology recomputation is only occasional, if needed.

    Source: §2.2 · p. 4

Abstract

from arXiv · show

Federated learning usually employs a client-server architecture where an orchestrator iteratively aggregates model updates from remote clients and pushes them back a refined model. This approach may be inefficient in cross-silo settings, as close-by data silos with high-speed access links may exchange information faster than with the orchestrator, and the orchestrator may become a communication bottleneck. In this paper we define the problem of topology design for cross-silo federated learning using the theory of max-plus linear systems to compute the system throughput---number of communication rounds per time unit. We also propose practical algorithms that, under the knowledge of measurable network characteristics, find a topology with the largest throughput or with provable throughput guarantees. In realistic Internet networks with 10 Gbps access links for silos, our algorithms speed up training by a factor 9 and 1.5 in comparison to the master-slave architecture and to state-of-the-art MATCHA, respectively. Speedups are even larger with slower access links.

1 Introduction

Cross-silo silos can communicate quickly with nearby peers, while an orchestrator-centered topology may overlook those links and become congested. The paper designs communication topologies by modeling all major delay components and optimizing round throughput.

1 Introduction

  • Cross-silo silos have high-speed links and may exchange information faster with peers than with a distant orchestrator, making centralized communication potentially inefficient.The orchestrator may also become a congestion point.Source: §1 · p. 2
  • Topology design trades off faster convergence from greater connectivity against longer communication rounds, which can result from congestion.Prior convergence bounds may overestimate the first effect in practice, motivating this paper's focus on round duration.Source: §1 · p. 2
  • Max-plus linear systems guide topology design to minimize communication-round duration, equivalently maximizing the number of rounds completed per time unit.The proposed algorithms are optimal in some cases or provide guaranteed approximation factors; realistic-network speedups are larger with slower access links.Source: §1 · p. 2
  • Prior topology-design work considered access-link congestion or stragglers, while the paper models computation, link latency, transmission, and queueing delays together.The paper presents this as the first work, to its knowledge, to include all these components.Source: §1 · p. 2

2 Problem Formulation

The paper models synchronous federated training as local computation and communication over a selected overlay, then minimizes its cycle time using measurable network characteristics. The formulation defines link delays, throughput, and the minimal-cycle-time topology problem.

2.1 Machine Learning Training

  • The training objective weights each silo's loss by its relative-importance coefficient p_i; the paper uses p_i = 1, without affecting its analysis.The model is trained without sharing local datasets, using periodic model updates.Source: §2.1 · p. 3
  • DPASGD has each silo perform s mini-batch updates before sending its model over an overlay, with updates governed by a nonnegative consensus matrix.The paper's topology results also apply to synchronous iterative algorithms that alternate local computation and communication.Source: §2.1 · p. 3

2.2 Underlay, Connectivity graph, and Overlay

  • The underlay is the network infrastructure; the connectivity graph lists possible direct silo links, and the overlay selects the links used for exchanges.Link delays, latencies, and available bandwidths can be measured by probing; the model assumes these quantities are stable or change slowly.Source: §2.2 · pp. 3–4
  • A communication delay combines local computation, end-to-end latency and queueing, and model transmission time based on available bandwidth.The delay model assumes parallel uploads and downloads and negligible interference between messages in the core network.Source: §2.2 · p. 4

2.3 Time per Communication Round (Cycle Time)

  • The max-plus recurrence describes when each silo begins its next computation; the graph's average cycle time is common across silos, and its inverse is system throughput.For sufficiently many rounds, elapsed time grows approximately as cycle time multiplied by the round count.Source: §2.3 · pp. 4–5

2.4 Optimization Problem

  • Minimal Cycle Time seeks a strongly connected spanning subgraph of the connectivity graph with the lowest cycle time.Its input uses quantities available or measurable at the silos rather than detailed information about the underlay.Source: §2.4 · p. 5

3 Theoretical Results and Algorithms

The paper develops topology-design algorithms for edge- and node-capacitated networks, with optimality or approximation guarantees in specified settings. Some variants are NP-hard, motivating guaranteed approximations.

3 Theoretical Results and Algorithms

  • The paper's algorithm section presents topology-design methods with stated time complexities and guarantees, adapting existing algorithms in some cases.The section reports complexity results for Minimal Cycle Time.Source: §3 · p. 5

3.1 Edge-capacitated networks

  • For undirected overlays in edge-capacitated networks, a minimum-weight spanning tree solves Minimal Cycle Time by minimizing the average bidirectional link delays.Prim's algorithm finds this tree in O(|Ec| + |V| log |V|), suitable for networks with a few hundred nodes.Source: §3.1 · pp. 5–6
  • Even complete Euclidean edge-capacitated graphs have NP-hard Minimal Cycle Time, and directed overlays can have arbitrarily shorter cycle times than undirected ones.The NP-hardness result applies even when the overlay is required to be directed only by the problem's general setting; the cited proposition specifically establishes hardness for the stated complete Euclidean case.Source: §3.1 · p. 6
  • Christofides' algorithm gives a 3N-approximation for Minimal Cycle Time on edge-capacitated Euclidean graphs, producing ring topologies.The guarantee follows from a 1.5-approximation for the Travelling Salesman Problem and a 2N-approximation from TSP solutions to Minimal Cycle Time.Source: §3.1 · p. 6

3.2 Node-capacitated networks

  • With node-capacitated networks, access-link congestion can dominate delays, favoring overlays with small degrees.Minimal Cycle Time remains NP-hard even when the overlay must be undirected.Source: §3.2 · p. 6
  • Algorithm 1 is a 6-approximation for Minimal Cycle Time in the stated node-capacitated Euclidean setting.It combines existing approximation algorithms for bounded-degree minimum bottleneck spanning trees.Source: §3.2 · p. 6
  • For node-capacitated Euclidean graphs, Christofides' algorithm is a 3N-approximation for Minimal Cycle Time.The paper notes that the approximation factor carries over from the more general setting.Source: §3.2 · p. 6

4 Numerical Experiments

Experiments compare six overlays across real and synthetic network topologies and federated datasets, finding that throughput-oriented overlays often shorten training relative to STAR and MATCHA(+). Gains are especially large with slow access links, while communication-round differences are comparatively small.

4 Numerical Experiments

  • The evaluation spans three real and two synthetic network topologies, three LEAF datasets and iNaturalist, and six overlays including STAR, MATCHA(+), MST, δ-MBST, and RING.For the iNaturalist comparison, δ-MBST selects the same overlay as MST.Source: §4 · p. 7
  • 3.3–9.4× faster than STAR and 1.5–6× faster than MATCHA, the RING on Gaia and Ebone demonstrates substantial throughput gains over both baselines.The paper reports RING speedups from approximately 391/118 on Gaia to 902/95 on Ebone; Table 3 covers iNaturalist with 1 Gbps core and 10 Gbps access links.Source: Table 3 · p. 7, §4 · p. 8
  • RING requires at most 20% more communication rounds than STAR, yet retains almost the same relative training-time performance.The paper reports that round counts are weakly sensitive to topology; training time combines cycle time and rounds to convergence.Source: §4 · p. 8
  • The same qualitative overlay advantage appears across four datasets on AWS North America with 100 times slower access links.Figure 2 compares training loss by communication rounds and by wall-clock time.Source: §4 · p. 8, Figure 2 · p. 8
  • 72× faster than STAR and 5.6× faster than MATCHA+ at 100 Mbps access capacities, RING's throughput gains also translate into training-time gains.For homogeneous access links below 6 Gbps, RING has the largest throughput; the comparison is shown for iNaturalist on Géant.Source: §4 · pp. 8–9, Figure 3 · p. 9
  • With a fixed 10 Gbps access link at the star center, STAR performs better but remains twice slower than RING and only as fast as δ-MBST.In this heterogeneous setting, training-time differences emerge mainly between overlays with very close throughputs.Source: §4 · p. 9, Figure 3 · p. 9
  • As local computation steps s increase, computation time dominates and overlay throughputs become more similar; too many steps may degrade final-model quality, and tuning s remains open.The discussion relates this trend to iNaturalist throughput speedups on Exodus shown in Figure 4.Source: §4 · p. 9, Figure 4 · p. 9

5 Conclusions

The paper uses max-plus linear systems to design topology algorithms that maximize throughput and speed up cross-silo federated learning. Future work would add links without reducing throughput and optimize consensus-matrix weights.

5 Conclusions

  • Max-plus linear systems underpin topology-design algorithms that maximize throughput and can significantly speed up cross-silo federated learning.Source: §5 · p. 9
  • The approach is presented as more promising than choosing topologies for the best spectral properties, as MATCHA(+) does.Source: §5 · p. 9
  • Future work will explore adding links that improve connectivity without decreasing throughput and optimizing consensus-matrix weights.Source: §5 · p. 9
  • Appendix H.1 provides tables like Table 3 for different values of s.Source: §5 · p. 9

6 Broader Impact

The broader-impact section connects faster cross-silo federated learning with possible dataset sharing, while noting privacy and energy concerns. The appendix introduces graph terminology used later in the paper.

6 Broader Impact

  • Topology algorithms that speed up cross-silo federated learning may foster adoption and allow entities to share datasets otherwise unavailable for training.Source: §6 · p. 10
  • Federated learning keeps data localized, but distributed messages may still expose training or local-dataset characteristics to attacks [92].Encryption and differential privacy [1] may help prevent such attacks.Source: §6 · p. 10
  • Federated learning is less efficient than a highly optimized computing cluster and may increase energy costs through discontinuous local computing and long-distance message transmission.The authors say energy considerations have not been adequately explored, apart from a few mobile-device FL papers [42].Source: §6 · p. 10

A Graph Theory

  • The graph-theory appendix defines terms used later, including paths, cycles, spanning trees, minimum spanning trees, and cuts.Source: A Graph Theory · p. 17

B On STAR and MATCHA(+) Cycle Times

For slow homogeneous access links, the RING can substantially outperform STAR and MATCHA(+). The section explains cycle-time calculations for STAR and MATCHA(+), alongside assumptions for the RING comparison.

B On STAR and MATCHA(+) Cycle Times

C Directed Overlays may be Faster than Undirected Overlays

Directed overlays can have arbitrarily shorter cycle times than undirected overlays, while finding optimal directed overlays is NP-hard. The section also presents an approximation approach and supporting complexity results for minimal-cycle-time topology design.

C Directed Overlays may be Faster than Undirected Overlays

  • Directed overlays can have arbitrarily shorter cycle times than undirected overlays, even when underlay links are bidirectional with identical directional delays.The examples use an undirected underlay and compare its fastest undirected overlay with a directed ring.Source: C Directed Overlays may be Faster than… · p. 19

D Approximation Algorithm for MCT on Node-Capacitated Networks

  • For node-capacitated networks with complete connectivity, Algorithm 1 builds candidate undirected overlays and returns the one with the smallest cycle time.It considers a 2-MBST approximation and other δ-BST candidates for 3 ≤ δ ≤ N.Source: D Approximation Algorithm for MCT on… · p. 20

E.1 Proof of Proposition 3.1

  • The undirected-overlay result relies on the fact that an MCT solution set includes a spanning tree when the network is edge-capacitated.Source: §E.1 · p. 21
  • For edge-capacitated networks with an undirected overlay, a minimum-weight spanning tree solves MCT.Source: §E.1 · p. 21

E.2 Proof of Proposition 3.2

  • MCT is NP-hard even for a complete Euclidean edge-capacitated graph.The proof reduces Hamiltonian Cycle to MCT-DECISION.Source: §E.2 · pp. 22–23

E.3 Proof of Proposition 3.3

For Euclidean edge-capacitated networks, Christofides’ algorithm gives a 3N-approximation for MCT by applying its TSP guarantee. The proof first bounds an optimal TSP tour against the optimal MCT cycle time.

E.3 Proof of Proposition 3.3

  • 2N: the optimal TSP tour is within this multiplicative factor of the optimal MCT tour under the Euclidean assumption.The assumption requires symmetric delays satisfying the triangle inequality.Source: §E.3 · p. 23
  • The proof constructs closed walks from a minimal set of elementary circuits, then extracts a Hamiltonian cycle with no greater delay.The walks use the Euclidean graph’s completeness and triangle inequality.Source: §E.3 · pp. 23–24
  • 3N-approximation: Christofides’ algorithm solves MCT for edge-capacitated Euclidean connectivity graphs within this factor.The proof combines Christofides’ 1.5-approximation for TSP with a 2N bound relating TSP to MCT.Source: §E.3 · pp. 23–25
  • Christofides’ ring can be Ω(N)-suboptimal for MCT even on an Euclidean edge-capacitated graph.The example gives a ring cycle time at least N/4 times the optimal overlay’s cycle time.Source: §E.3 · p. 25

E.4 Proof of Proposition 3.4

MCT is NP-hard in node-capacitated networks even when the overlay must be undirected. The proof reduces the degree-constrained spanning tree decision problem to MCT-U-Decision.

E.4 Proof of Proposition 3.4

  • MCT-U-Decision asks whether a strongly connected connectivity graph has a strong spanning undirected overlay with cycle time at most τ0.Its input also includes model size and network and computation characteristics.Source: §E.4 · p. 25
  • NP-hard: MCT remains hard in node-capacitated networks when overlays are required to be undirected.The proof establishes this through a polynomial reduction from DCST.Source: §E.4 · pp. 25–26
  • The reduction maps each source vertex to two vertices and sets the MCT cycle-time threshold to k + 1.The constructed instance has a qualifying overlay exactly when the original graph has a spanning tree of maximum degree at most k.Source: §E.4 · p. 26

E.5 Proof of Proposition 3.5

The appendix proves approximation guarantees for MCT using spanning-tree and TSP constructions. The guarantees depend on network capacity and Euclidean-delay assumptions.

E.5 Proof of Proposition 3.5

  • The proof bounds the bottleneck of the modified bottleneck spanning tree by the optimal MCT cycle time for undirected overlays.It uses this relationship to connect the tree-based candidate to MCT.Source: §E.5 · p. 26
  • 6-approximation: Algorithm 1 approximates MCT for node-capacitated Euclidean networks under the stated upload-capacity condition.The proof uses an approximate bottleneck spanning tree and a Hamiltonian path candidate.Source: §E.5 · pp. 27–28

E.6 Proof of Proposition 3.6

  • 3N-approximation: Christofides’ algorithm approximates MCT for node-capacitated Euclidean networks.The proof transfers the TSP guarantee to MCT through the TSP-to-MCT bound.Source: §E.6 · p. 28

F Time Simulator

The time simulator reconstructs training wall-clock time from underlay, access-link, and computation characteristics. The evaluation considers real and synthetic network topologies with shortest-path routing.

F Time Simulator

  • The simulator computes when each silo starts its kth computation for a given overlay, using complete knowledge of underlay and access-link capacities.It reconstructs message delays from physical-link capacities and the message size.Source: F Time Simulator · p. 29
  • Message delay combines path latency and transmission delay, the latter depending on the path’s minimum available bandwidth.The simulator estimates latency as 0.0085 × distance in kilometers + 4 milliseconds.Source: F Time Simulator · p. 29
  • The simulator also includes computation time as the number of local steps multiplied by each node’s time per step.This term is s × Tc(i).Source: F Time Simulator · p. 29

G.1 Networks and Communication model

  • The evaluation uses three real and two synthetic topologies, with 11–87 nodes; Gaia spans four continents.The assumed routing uses shortest paths with geographical distance, equivalently latency, as link cost.Source: §G.1 · p. 30

G.2 Datasets and Models

The appendix documents the datasets, models, implementation settings, and additional experiments used to evaluate overlays. Across the explored scenarios, RING converges faster in wall-clock time than MATCHA+ and STAR, though some test metrics worsen over time.

G.2 Datasets and Models

  • Experiments use datasets spanning sentiment analysis, language modeling, image classification, and character recognition, including LEAF benchmarks and iNaturalist.The iNaturalist subset uses images from 80 popular species; local data are split between random assignment and assignment to the geographically closest silo.Source: §G.2 · pp. 30–31

G.3 Implementation Details

  • Implementation details specify network-dependent optimizers and learning rates, dataset-specific batch sizes, and MATCHA variants initialized from either the connectivity graph or underlay.MATCHA+ starts from the underlay and generally outperformed MATCHA, so its results are shown.Source: §G.3 · pp. 32–33

H.1 Effect of the number of local steps

  • Tables 6 and 7 report iNaturalist training over five networks with 1 Gbps core and 10 Gbps access links, using five and ten local computation steps, respectively.Training-time thresholds vary by network and local-step setting.Source: §H.1 · p. 34, Table 6 · p. 34, Table 7 · p. 34

H.2 Full results for training every dataset on AWS North America

  • Figures 11–14 provide training and test loss and accuracy against communication rounds and wall-clock time for four datasets on AWS North America.The reported datasets are Shakespeare, FEMNIST, Sentiment140, and iNaturalist.Source: §H.2 · p. 34, Figure 11 · p. 35, Figure 12 · p. 35

H.3 Exploring other scenarios

  • Across representative scenarios, RING converges faster in wall-clock time than MATCHA+ and STAR, though some test metrics later worsen, possibly from overfitting.The appendix covers five underlays, six overlays, four datasets, and three local-step settings, but not all 360 possible combinations.Source: §H.3 · p. 34

H.4 Training on Full-iNaturalist dataset

The appendix evaluates the method on Full-iNaturalist and examines model performance across underlays and MATCHA communication-budget choices. RING achieves the best throughput on Full-iNaturalist and is faster than MATCHA in most reported comparisons.

H.4 Training on Full-iNaturalist dataset

  • Full-iNaturalist contains 450,000 images across 8,142 classes, and the experiments fine-tune an ImageNet-pretrained ResNet-50.The class distribution is highly skewed; the dataset is split into 80% training and 20% testing data.Source: §H.4 · p. 39
  • RING always achieves the best throughput among six overlays when training ResNet-50 on Full-iNaturalist across networks with 1 Gbps core and access links.The table uses one local computation step.Source: §H.4 · p. 40, Table 9 · p. 41

H.5 Dependence of model performance on underlays

  • With data-size-weighted loss on STAR, ResNet-18 reaches 46%–48% test accuracy across five underlays, unlike the differing performances under the unweighted objective.The paper attributes the earlier differences to optimizing the mean of local functions, which changes the optimization problem when silo counts differ.Source: §H.5 · p. 40, Figure 26 · p. 41

H.6 Effect of Cb in MATCHA

  • RING remains faster than MATCHA by 1.08× with 10 Gbps access links and 3.29× with 100 Mbps access links, even when MATCHA uses Cb = 0.2.The authors report RING outperforming MATCHA except on Géant, including additional MATCHA experiments over the tested topologies.Source: §H.6 · p. 41, Table 10 · p. 41

Related papers

Loading 2010.12229v2…