arxiv: 2604.19399 · v1 · submitted 2026-04-21 · 💻 cs.LG · cs.DC

Recognition: unknown

Optimal Routing for Federated Learning over Dynamic Satellite Networks: Tractable or Not?

Yi Zhao , Di Yuan , Tao Deng , Suzhi Cao , Ying Dong

Authors on Pith no claims yet

Pith reviewed 2026-05-10 03:18 UTC · model grok-4.3

classification 💻 cs.LG cs.DC

keywords federated learningsatellite networksrouting optimizationtractability analysisNP-hardnessin-orbit communicationdynamic networksmodel distribution

0 comments

The pith

Routing optimization for in-orbit federated learning is polynomial-time solvable in some settings and NP-hard in others, with proofs for each variant.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies routing decisions needed when satellites serve as clients in federated learning and must exchange models over changing multi-hop links. Communication occurs in two phases: the server sends the current global model outward, then clients return their updated local models. For each combination of settings, such as the number of models involved, whether flows can be split across paths, unicast versus multicast delivery, and whether clients can be selected, the authors prove either that an optimal routing plan can be found by an efficient algorithm or that the problem is computationally hard. A reader would care because the distinction decides whether satellite networks can use exact routing in practice or must accept approximations and heuristics.

Core claim

For global model distribution, the routing problem is polynomial-time solvable or NP-hard depending on the number of models, the objective function, and the routing scheme (unicast versus multicast, splittable versus unsplittable flow). For local model collection, the same distinction holds based on the number of models, client selection rules, and flow splittability. Rigorous proofs establish the exact boundary between the two regimes for every listed combination.

What carries the argument

The case-by-case tractability classification of routing problems, parameterized by flow splittability, multicast support, client selection, and number of models, which separates those admitting efficient optimal algorithms from those that are NP-hard.

If this is right

Efficient algorithms for the tractable cases can be implemented directly in satellite federated learning systems.
Complexity insights for the intractable cases indicate where approximation or heuristic methods are unavoidable.
The classification supplies a systematic basis for choosing routing configurations when designing or evaluating in-orbit learning deployments.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same boundary analysis could apply to routing in other time-varying networks that support distributed model training, such as drone fleets.
Designers might deliberately favor network topologies or client-selection rules that land in the polynomial-time regime when possible.
Hybrid solvers could invoke exact methods on small instances and switch to approximations once network size exceeds a proven threshold.

Load-bearing premise

The proofs assume idealized models of satellite movement and exactly two communication phases per federated learning round.

What would settle it

Running a candidate polynomial algorithm on successively larger networks for a case labeled polynomial, or exhibiting a small instance that violates the claimed polynomial bound for a case labeled NP-hard.

Figures

Figures reproduced from arXiv: 2604.19399 by Di Yuan, Suzhi Cao, Tao Deng, Ying Dong, Yi Zhao.

**Figure 2.** Figure 2: Examples of multipath transmission and multicast [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: An example of TVG, where i§k represents the copy of satellite i in snapshot k. TVG is a concept for representing time-dynamic graph structure, frequently used for modeling satellite networks [24]– [27]. Typically, a TVG is composed by a sequence of connected snapshots, and each snapshot is a static network topology, illustrated in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

**Figure 4.** Figure 4: Examples of routing solutions for the downloading phase, under different options of: 1) unicast or multicast, 2) [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗

**Figure 5.** Figure 5: Examples of routing solutions for the uploading [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗

**Figure 7.** Figure 7: An illustration of expanded topology of intersnapshot arcs and the unit flow cost for solving 1-UF-WS. in this paper are given in Table II. The tractability results under unicast for the downloading phase are shown in Table III. A. Tractable Problem Variants Theorem 1. 1-UF-WS is solvable in polynomial time. Proof. To prepare for the proof, we introduce an expanded topology for the inter-snapshot links of… view at source ↗

**Figure 8.** Figure 8: An illustration of reduction from 3SAT to 1-SF-WS. [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗

**Figure 9.** Figure 9: An illustration of reduction from 3SAT to 2-UF [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗

**Figure 10.** Figure 10: An illustration of reduction from 3SAT to 2-UF [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗

**Figure 11.** Figure 11: An illustration of reduction from MVC to 1-SF-CS. [PITH_FULL_IMAGE:figures/full_fig_p013_11.png] view at source ↗

read the original abstract

Federated learning (FL) is a key paradigm for distributed model learning across decentralized data sources. Communication in each FL round typically consists of two phases: (i) distributing the global model from a server to clients, and (ii) collecting updated local models from clients to the server for aggregation. This paper focuses on a type of FL where communication between a client and the server is relay-based over dynamic networks, making routing optimization essential. A typical scenario is in-orbit FL, where satellites act as clients and communicate with a server (which can be a satellite, ground station, or aerial platform) via multi-hop inter-satellite links. This paper presents a comprehensive tractability analysis of routing optimization for in-orbit FL under different settings. For global model distribution, these include the number of models, the objective function, and routing schemes (unicast versus multicast, and splittable versus unsplittable flow). For local model collection, the settings consider the number of models, client selection, and flow splittability. For each case, we rigorously prove whether the global optimum is obtainable in polynomial time or the problem is NP-hard. Together, our analysis draws clear boundaries between tractable and intractable regimes for a broad spectrum of routing problems for in-orbit FL. For tractable cases, the derived efficient algorithms are directly applicable in practice. For intractable cases, we provide fundamental insights into their inherent complexity. These contributions fill a critical yet unexplored research gap, laying a foundation for principled routing design, evaluation, and deployment in satellite-based FL or similar distributed learning systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper maps out polynomial-time vs NP-hard cases for routing in satellite federated learning with a systematic case analysis.

read the letter

This paper's main result is a case-by-case breakdown showing which routing optimization problems for federated learning over dynamic satellite networks are solvable in polynomial time and which are NP-hard. They handle global model distribution under different numbers of models, objectives, unicast/multicast, and flow splittability, and local model collection with client selection and flow types. What they do well is apply standard complexity analysis to these specific FL routing variants in the satellite setting. The two-phase communication model is used consistently, and the analysis covers a wide range of practical settings that hadn't been classified before. This gives useful boundaries for when exact solutions are feasible. The soft spots are limited. Their model of satellite networks and FL phases is reasonable but simplified, so real orbital dynamics or additional constraints could change things in practice. The abstract promises rigorous proofs, and no inconsistencies appear in the setup, but without the full reductions it's tough to be 100% sure on every edge case. This work is for researchers in satellite communications and federated learning who care about algorithmic tractability. It would be worth bringing to a reading group focused on network optimization or distributed systems. It deserves peer review because it provides concrete, applicable insights without overreaching.

Referee Report

0 major / 3 minor

Summary. The paper claims to present a comprehensive tractability analysis of routing optimization for federated learning in dynamic satellite networks, with a focus on in-orbit scenarios. It analyzes the global model distribution phase under settings like number of models, objective function, unicast/multicast, and splittable/unsplittable flows, and the local model collection phase considering number of models, client selection, and flow splittability. For each case, it provides rigorous proofs determining if the global optimum is obtainable in polynomial time or if the problem is NP-hard.

Significance. If the proofs hold, this work is significant for establishing boundaries between tractable and intractable routing problems in satellite-based federated learning. It provides efficient algorithms for tractable cases that are directly applicable in practice and fundamental insights into complexity for intractable cases. This fills a critical gap in the literature at the intersection of distributed learning and satellite networking, aiding principled design and deployment. The case-by-case application of standard complexity-theoretic tools to the two-phase FL structure is a clear strength.

minor comments (3)

The abstract could benefit from a brief mention of the specific satellite network model assumptions, such as orbital dynamics or link stability, to better contextualize the results for readers unfamiliar with the domain.
Consider adding a summary table that lists all analyzed cases along with their tractability results (P or NP-hard) for quick reference and to strengthen the 'clear boundaries' claim.
Ensure that all notation used in the complexity proofs (e.g., for flow splittability or multicast schemes) is consistently defined and introduced early, perhaps in a dedicated preliminaries section.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript and the recommendation for minor revision. The referee's summary accurately reflects the scope of our tractability analysis for routing optimization in in-orbit federated learning.

read point-by-point responses

Referee: No specific major comments were listed in the report beyond the overall summary and recommendation.

Authors: We appreciate the recognition that the proofs establish clear boundaries between tractable and intractable cases, with efficient algorithms for the former and complexity insights for the latter. Since no particular issues or required changes were identified, we see no need for substantive revisions at this stage. Any minor editorial adjustments requested by the editor will be incorporated in the next version. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper formulates routing optimization problems for federated learning over dynamic satellite networks under explicitly enumerated settings (number of models, unicast/multicast, splittable/unsplittable flows, client selection, etc.) and then applies standard complexity-theoretic techniques to prove polynomial-time solvability or NP-hardness on a case-by-case basis. No step reduces a claimed result to a fitted parameter, self-referential definition, or load-bearing self-citation; the tractability classifications rest on independent reductions and algorithms whose correctness is established directly from the problem statements rather than from prior outputs of the same work. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper applies standard complexity analysis techniques to the described FL routing problems without introducing new free parameters or invented entities.

axioms (1)

domain assumption Standard assumptions of network flow models and NP-hardness reductions for dynamic multi-hop satellite links
Required to define the routing problems and prove their complexity status.

pith-pipeline@v0.9.0 · 5591 in / 1118 out tokens · 29954 ms · 2026-05-10T03:18:15.777716+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 4 canonical work pages · 2 internal anchors

[1]

Communication-Efficient Learning of Deep Networks from Decentralized Data,

B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” inProceedings of the 20th International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, A. Singh and J. Zhu, Eds., vol. 54. PMLR, 20–22 Apr 2017, pp. 1273–1282. [...

2017
[2]

A survey on federated learning,

C. Zhang, Y . Xie, H. Bai, B. Yu, W. Li, and Y . Gao, “A survey on federated learning,”Knowledge-Based Systems, vol. 216, p. 106775, 2021. [Online]. Available: https://www.sciencedirect.com/ science/article/pii/S0950705121000381

2021
[3]

Federated learning over wireless networks: Convergence analysis and resource allocation,

C. T. Dinh, N. H. Tran, M. N. H. Nguyen, C. S. Hong, W. Bao, A. Y . Zomaya, and V . Gramoli, “Federated learning over wireless networks: Convergence analysis and resource allocation,”IEEE/ACM Transactions on Networking, vol. 29, no. 1, pp. 398–409, 2021

2021
[4]

Client selection in federated learning: Principles, challenges, and opportunities,

L. Fu, H. Zhang, G. Gao, M. Zhang, and X. Liu, “Client selection in federated learning: Principles, challenges, and opportunities,”IEEE Internet of Things Journal, vol. 10, no. 24, pp. 21 811–21 819, 2023

2023
[5]

Leader federated learning optimization using deep reinforcement learning for distributed satellite edge intelligence,

H. Zhang, H. Zhao, R. Liu, X. Gao, and S. Xu, “Leader federated learning optimization using deep reinforcement learning for distributed satellite edge intelligence,”IEEE Transactions on Services Computing, vol. 17, no. 5, pp. 2544–2557, 2024

2024
[6]

FedTrack: A collaborative target tracking framework based on adaptive federated learning,

Y . Pan, C. Zhu, L. Luo, Y . Liu, and Z. Cheng, “FedTrack: A collaborative target tracking framework based on adaptive federated learning,”IEEE Transactions on Vehicular Technology, vol. 73, no. 9, pp. 13 868–13 882, 2024

2024
[7]

Federated learning for mobility applications,

M. Gecer and B. Garbinato, “Federated learning for mobility applications,”ACM Comput. Surv., vol. 56, no. 5, Jan. 2024. [Online]. Available: https://doi.org/10.1145/3637868

work page doi:10.1145/3637868 2024
[8]

FedHC: A Hierarchical Clustered Federated Learning Framework for Satellite Networks

Z. Liu, Z. Shen, P. Zhou, Q. Zheng, and J. Jin, “FedHC: A hierarchical clustered federated learning framework for satellite networks,” 2025. [Online]. Available: https://arxiv.org/abs/2502.12783

work page internal anchor Pith review Pith/arXiv arXiv 2025
[9]

Satellite federated edge learning: Architecture design and convergence analysis,

Y . Shi, L. Zeng, J. Zhu, Y . Zhou, C. Jiang, and K. B. Letaief, “Satellite federated edge learning: Architecture design and convergence analysis,” IEEE Transactions on Wireless Communications, vol. 23, no. 10, pp. 15 212–15 229, 2024

2024
[10]

Federated learning in satellite constellations,

B. Matthiesen, N. Razmi, I. Leyva-Mayorga, A. Dekorsy, and P. Popovski, “Federated learning in satellite constellations,”IEEE Net- work, vol. 38, no. 2, pp. 232–239, 2024

2024
[11]

FedSN: A federated learning framework over heterogeneous LEO satellite net- works,

Z. Lin, Z. Chen, Z. Fang, X. Chen, X. Wang, and Y . Gao, “FedSN: A federated learning framework over heterogeneous LEO satellite net- works,”IEEE Transactions on Mobile Computing, vol. 24, no. 3, pp. 1293–1307, 2025

2025
[12]

A survey on satellite networks with federated learning to analyze data or manage resource,

J. Oh, D. Lee, T. P. Truong, D. Hur, S. Hong, and S. Cho, “A survey on satellite networks with federated learning to analyze data or manage resource,” in2025 International Conference on Artificial Intelligence in Information and Communication (ICAIIC), 2025, pp. 0022–0027

2025
[13]

Segment routing architecture,

C. Filsfils, S. Previdi, L. Ginsberg, B. Decraene, S. Litkowski, and R. Shakir, “Segment routing architecture,” RFC 8402, July 2018. [Online]. Available: https://www.rfc-editor.org/info/rfc8402

2018
[14]

Segment routing for traffic engi- neering and effective recovery in low-earth orbit satellite constellations,

S. Zhang, X. Li, and K. L. Yeung, “Segment routing for traffic engi- neering and effective recovery in low-earth orbit satellite constellations,” Digital Communications and Networks, vol. 10, no. 3, pp. 706–715, 2024

2024
[15]

Software defined multicast using segment routing in LEO satellite networks,

M. Hu, M. Xiao, Y . Hu, C. Cai, T. Deng, and K. Peng, “Software defined multicast using segment routing in LEO satellite networks,” IEEE Transactions on Mobile Computing, vol. 23, no. 1, pp. 835–849, 2022

2022
[16]

Connectivity and inference problems for temporal networks,

D. Kempe, J. Kleinberg, and A. Kumar, “Connectivity and inference problems for temporal networks,”Journal of Computer and System Sciences, vol. 64, no. 4, pp. 820–842, 2002. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0022000002918295

2002
[17]

Time- varying graphs and dynamic networks,

A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro, “Time- varying graphs and dynamic networks,” 2012. [Online]. Available: https://arxiv.org/abs/1012.0009

work page arXiv 2012
[18]

A review of client selection methods in federated learning,

S. Mayhoub and T. M. Shami, “A review of client selection methods in federated learning,”Archives of Computational Methods in Engineering, vol. 31, no. 2, pp. 1129–1152, 2024

2024
[19]

Client selection in federated learning: Convergence analysis and power-of-choice selection strategies,

Y . J. Cho, J. Wang, and G. Joshi, “Client selection in federated learning: Convergence analysis and power-of-choice selection strategies,” 2020

2020
[20]

Client selection in nonconvex federated learning: Improved convergence analysis for optimal unbiased sampling strategy,

L.-C. Wang, Y . Guo, T. Lin, and X. Tang, “Client selection in nonconvex federated learning: Improved convergence analysis for optimal unbiased sampling strategy,” 2022

2022
[21]

Distilling the Knowledge in a Neural Network

G. Hinton, O. Vinyals, and J. Dean, “Distilling the knowledge in a neural network,”arXiv preprint arXiv:1503.02531, 2015

work page internal anchor Pith review Pith/arXiv arXiv 2015
[22]

Distributed distillation for on- device learning,

I. Bistritz, A. Mann, and N. Bambos, “Distributed distillation for on- device learning,”Advances in Neural Information Processing Systems, vol. 33, pp. 22 593–22 604, 2020

2020
[23]

A comprehensive survey on segment routing traffic engineering,

D. Wu and L. Cui, “A comprehensive survey on segment routing traffic engineering,”Digital Communications and Networks, vol. 9, no. 4, pp. 990–1008, 2023

2023
[24]

Application of time-varying graph theory over the space information networks,

T. Zhang, J. Li, H. Li, S. Zhang, P. Wang, and H. Shen, “Application of time-varying graph theory over the space information networks,”IEEE Network, vol. 34, no. 2, pp. 179–185, 2020

2020
[25]

Improving the snapshot routing performance through reassigning the inter-satellite links,

Z. Tang, Z. Feng, W. Han, W. Yu, B. Zhao, and C. Wu, “Improving the snapshot routing performance through reassigning the inter-satellite links,” in2015 IEEE Conference on Computer Communications Work- shops (INFOCOM WKSHPS), 2015, pp. 97–98

2015
[26]

Dynamic routings in satellite networks: An overview,

X. Cao, Y . Li, X. Xiong, and J. Wang, “Dynamic routings in satellite networks: An overview,”Sensors, vol. 22, no. 12, 2022. [Online]. Available: https://www.mdpi.com/1424-8220/22/12/4552

2022
[27]

Time-varying topology model for dynamic routing in LEO satellite constellation networks,

Z. Han, C. Xu, G. Zhao, S. Wang, K. Cheng, and S. Yu, “Time-varying topology model for dynamic routing in LEO satellite constellation networks,”IEEE Transactions on Vehicular Technology, vol. 72, no. 3, pp. 3440–3454, 2023

2023
[28]

D.-Z. Du, P. M. Pardalos, X. Hu, and W. Wu,Introduction to Combi- natorial Optimization. Springer, 2022

2022
[29]

M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company, 1979

1979
[30]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin,Network Flows: Theory, Algorithms, and Applications. Prentice hall, 1993

1993
[31]

Routing of multipoint connections,

B. Waxman, “Routing of multipoint connections,”IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1617–1622, 1988

1988
[32]

Winter, F

P. Winter, F. Hwang, and D. Richard,The Steiner Tree Problem. North- Holland, 1992

1992
[33]

Optimum branchings,

J. Edmonds, “Optimum branchings,”Journal of Research of the National Bureau of Standards Section B, vol. 71B, no. 4, pp. 233–240, 1967

1967
[34]

The directed subgraph homeo- morphism problem,

S. Fortune, Hopcroft, and J. Wyllie, “The directed subgraph homeo- morphism problem,”Journal of Theoretical Computer Science, vol. 10, no. 2, pp. 111–121, 1980

1980