Lossless Tessellated Distributed Computing

The work considers the $N$-server distributed computing scenario with $K$ users requesting functions that are linearly-decomposable over an arbitrary basis of $L$ real (potentially non-linear) subfunctions, and the aim is to receive the function outputs with zero error, reduced computing cost ($\gamma$; the fraction of subfunctions each server must compute), and reduced communication cost ($\delta$; the fraction of users each server must connect to). For a matrix $F \in \mathbb{R}^{K \times L}$ representing the linearly-decomposable form of the $K$ requested functions, our problem is made equivalent to the open problem of zero-error sparse matrix factorization that seeks $F = DE$ over a special subset of $\gamma$-sparse and $\delta$-sparse $E \in \mathbb{R}^{N \times L}$ and $D \in \mathbb{R}^{K \times N}$ matrices that respectively define which servers compute each subfunction, and which users connect to each server. We here design an achievable scheme designing $\mathbf{E,D}$ by utilizing a fixed-support SVD-based matrix factorization method that first splits $F$ into properly sized and carefully positioned submatrices, and then decomposes these into properly designed submatrices of $\mathbf{D}$ and $\mathbf{E}$. For the zero-error case and under basic dimensionality and single-shot assumptions, this work reveals that the optimal number of servers can be upper-bounded as $N_{\text{opt}} \leq \min(\Delta,\Gamma)\lfloor K/\Delta \rfloor \lfloor L/\Gamma \rfloor + \min(\text{mod}(K,\Delta),\Gamma)\lfloor L/\Gamma \rfloor + \min(\text{mod}(L,\Gamma),\Delta)\lfloor K/\Delta \rfloor + \min(\text{mod}(K,\Delta),\text{mod}(L,\Gamma))$. In the special case, it reveals that the maximum possible ratio $K/N$ or the zero-error capacity of this system for any feasible single-shot scheme satisfying $\delta^{-1}, \gamma^{-1} \in \mathbb{N}$ is $C = \max(K/L\delta, \gamma)$.