The work considers the N-server distributed computing scenario with K users requesting functions that are arbitrary multi-variable polynomial evaluations of L real (potentially non-linear) basis subfunctions of a certain degree. Our aim is to reduce both the computational cost at the servers, as well as the load of communication between the servers and the users. To do so, we take a novel approach, which involves transforming our distributed computing problem into a sparse tensor factorization problemF =Ē ×1 D, where tensorF represents the requested non-linearly-decomposable jobs expressed as the mode-1 product between tensorĒ and matrix D, where D andĒ respectively define the communication and computational assignment, and where their sparsity respectively allows for reduced communication and computational costs. We here design an achievable scheme, designingĒ, D by utilizing novel fixed-support SVD-based tensor factorization methods that first splitF into properly sized and carefully positioned subtensors, and then decompose them into properly designed subtensors ofĒ and submatrices of D. For the zero-error case and under basic dimensionality assumptions, this work reveals a lower bound on the optimal rate K/N with a given communication and computational load.
Tessellated distributed computing of non-linearly separable functions
Submitted to Zenodo, January 2025
Type:
Conference
Date:
2025-01-22
Department:
Communication systems
Eurecom Ref:
8041
Copyright:
© EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Submitted to Zenodo, January 2025 and is available at : http://dx.doi.org/10.5281/zenodo.14726121
See also:
PERMALINK : https://www.eurecom.fr/publication/8041