Coded Computing for Dynamic System via Cartesian Products

Abstract

Coded distributed computing (CDC) mitigates the Shuffle communication bottleneck through coded multicast, but existing schemes with predetermined worker populations do not directly adapt to worker arrivals and disconnections. To address these dynamics, we propose a dynamic CDC scheme that preserves surviving workers' caches and Reduce assignments while exploiting the storage brought by arriving clusters. The model accommodates general MapReduce tasks under a placement that is partly fixed and partly new. The scheme uses Cartesian products of cluster-wise placement delivery arrays (PDAs) for file placement. A delivery-aware greedy algorithm reassigns abandoned Reduce functions, and a Communication Array allows workers with no Reduce function to serve as coded transmitters. For arbitrary feasible disconnections, the scheme's exact communication load is derived. A converse bound under one-shot communication shows that, in the absence of disconnections, the scheme lies within a factor of 2 of the lower bound under these assumptions when new clusters arrive, and within a factor of 4 otherwise.

Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing
Parsa Moradi, Mohammad Ali Maddah-Ali
arXiv1 Sep 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
Multiple-Function Approximated Coded Computing: Constructions and Error Bounds
Rimpi Borah, Wilton Kim, J. Harshan +2
arXiv20 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
On k-limited domination: complexity and Cartesian products
Aleksandra Tepeh
arXiv1 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Basis Selection For Analog Coded Computing Under Differential Privacy Constraints
Aaditya Sharma, Rimpi Borah, J. Harshan
arXiv19 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
S_n-equivariant L-classes of Cartesian powers of Witt spaces and the Hodge index conjecture for symmetric products
Mohammadali Aligholi
arXiv2 Nov 2026PreprintCC BY 4.0Full textAlgebra & number theory Geometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@misc{li2026coded,
  title = {{Coded Computing for Dynamic System via Cartesian Products}},
  author = {Chenglin Li and Minquan Cheng and Youlong Wu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.39373},
  eprint = {2609.39373},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.39373},
}

RIS

TY  - UNPB
TI  - Coded Computing for Dynamic System via Cartesian Products
AU  - Chenglin Li
AU  - Minquan Cheng
AU  - Youlong Wu
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.39373
UR  - https://arxiv.org/abs/2609.39373
AB  - Coded distributed computing (CDC) mitigates the Shuffle communication bottleneck through coded multicast, but existing schemes with predetermined worker populations do not directly adapt to worker arrivals and disconnections. To address these dynamics, we propose a dynamic CDC scheme that preserves surviving workers' caches and Reduce assignments while exploiting the storage brought by arriving clusters. The model accommodates general MapReduce tasks under a placement that is partly fixed and partly new. The scheme uses Cartesian products of cluster-wise placement delivery arrays (PDAs) for file placement. A delivery-aware greedy algorithm reassigns abandoned Reduce functions, and a Communication Array allows workers with no Reduce function to serve as coded transmitters. For arbitrary feasible disconnections, the scheme's exact communication load is derived. A converse bound under one-shot communication shows that, in the absence of disconnections, the scheme lies within a factor of 2 of the lower bound under these assumptions when new clusters arrive, and within a factor of 4 otherwise.
ER  -

Abstract

Related

Cite