Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes
Abstract
We study the (K,N,S,M,Kc) distributed linearly separable computation (DLSC) setting, where a master employs N workers with a per-worker computation load of M to recover Kc deterministic linear combinations of K messages in the presence of up to S stragglers. We propose a DLSC framework based on nested cyclic codes that achieves M=K/N(S+Kc). For sufficiently large K, we establish the matching converse M≥K/N(S+Kc), proving the asymptotic computation load optimality of the proposed framework. By instantiating cyclic locally recoverable codes (LRCs) as base codes in the framework, the master can recover the desired Kc linear combinations by contacting fewer than N−S workers under many straggler scenarios. This essentially softens the straggler threshold without increasing the computation load or communication cost. Finally, we extend the construction to reduce the per-worker communication load by a factor of m, while achieving an asymptotically optimal computation load of M=K/N(S+mKc).
Related
- Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices
- A Parallel Adaptive Proximal ADMM for Linearly Constrained Separable Composite Optimization Problems
- Consensus-based optimization for linearly separable functions
- Fast Computation of Nested Cross-Validation for Penalized Regression
- Privacy-Constrained Function Computation in Distributed Databases
BibTeX
@misc{mathew2026deterministic,
title = {{Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes}},
author = {Anu Mathew and M. Nikhil Krishnan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18184},
eprint = {2610.18184},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18184},
}
RIS
TY - UNPB
TI - Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes
AU - Anu Mathew
AU - M. Nikhil Krishnan
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18184
UR - https://arxiv.org/abs/2610.18184
AB - We study the (K,N,S,M,K_c) distributed linearly separable computation (DLSC) setting, where a master employs N workers with a per-worker computation load of M to recover K_c deterministic linear combinations of K messages in the presence of up to S stragglers. We propose a DLSC framework based on nested cyclic codes that achieves M=K/N(S+K_c). For sufficiently large K, we establish the matching converse M≥K/N(S+K_c), proving the asymptotic computation load optimality of the proposed framework. By instantiating cyclic locally recoverable codes (LRCs) as base codes in the framework, the master can recover the desired K_c linear combinations by contacting fewer than N−S workers under many straggler scenarios. This essentially softens the straggler threshold without increasing the computation load or communication cost. Finally, we extend the construction to reduce the per-worker communication load by a factor of m, while achieving an asymptotically optimal computation load of M=K/N(S+mK_c).
ER -