The introduction of the new multi-user linearly-separable distributed computing framework, has recently revealed how a parallel treatment of users can yield large parallelization gains with relatively low computation and communication costs. These gains stem from a new approach that converts the computing problem into a sparse matrix factorization problem; a matrix \(\mathbf{F}\) that describes the users' requests, is decomposed as \(\mathbf{F} = \mathbf{DE}\), where a \(γ\)-sparse \(\mathbf{E}\) defines the task allocation across \(N\) servers, and a \(δ\)-sparse \(\mathbf{D}\) defines the connectivity between \(N\) servers and \(K\) users as well as the decoding process. While this approach provides near-optimal performance, its linear nature has raised data secrecy concerns. We adopt an information-theoretic secrecy framework requiring that each user learns nothing more than its own requested function. Our main results provide (i) a necessary condition stating that for each user $k$ observing \(α_k\) server responses, the common randomness visible to that user must span a subspace of dimension greater than \(α_k-1\), and (ii) a necessary and sufficient condition requiring that removing from \(\mathbf{D}\) the columns corresponding to the servers observed by a user leaves a matrix of rank at least \(K-1\). Based on these conditions, we design a general, cost-preserving secrecy-enforcing transformation valid over both finite and real fields, obtained by appending to \(\mathbf{E}\) a basis of \(\mathrm{Null}(\mathbf{D})\) and carefully injecting shared randomness. This scheme preserves communication and computation costs, guarantees perfect information-theoretic secrecy over finite fields, and in the real case yields an explicit mutual-information bound that can be made arbitrarily small by increasing the variance of Gaussian common randomness.

International audience

This paper considers an $N$-server distributed computing setting with $K$ users requesting functions that are arbitrary multivariable polynomial evaluations of $L$ real (potentially non-linear) basis subfunctions, where each function output is raised to a bounded power. Our aim is to seek efficient task allocation and data communication techniques that reduce computation and communication costs. To this end, we take a tensor-theoretic approach, in which we represent the requested non-linearly decomposable functions using a properly designed tensor $\bar{\mathcal{F}}$, whose sparse decomposition into a tensor $\bar{\mathcal{E}}$ and a matrix $\mathbf{D}$ directly defines the task assignment, connectivity, and communication patterns. We design a lossless achievable scheme that integrates fixed-support SVD-based tensor factorization with multi-dimensional tiling of $\bar{\mathcal{E}}$ and $\mathbf{D}$, followed by a bipartite graph matching-based recursive assignment of tiles. This step transforms an overlapping decomposition into a disjoint one and reduces the resulting sum rank of the tiles, thereby decreasing the number of required servers. Under mild dimensionality conditions, we derive an explicit zero-error characterization of the achievable system rate $K/N$. Numerical simulations demonstrate the computational and communication savings over existing state-of-the-art matrix factorization approaches across a wide range of system parameters.

The work considers theN-server distributed computing scenario withKusers requesting functions that are linearly-decomposable over an arbitrary basis ofLreal (potentially non-linear) subfunctions. In our problem, the aim is for each user to receive their function outputs, allowing for reduced reconstruction error (distortion)$\epsilon $, 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 any given set ofKrequested functions — which is here represented by a coefficient matrix$\mathbf {F} \in \mathbb {R}^{K \times L}$— our problem is made equivalent to the open problem of sparse matrix factorization that seeks — for a given parameterT, representing the number of shots for each server — to minimize the reconstruction distortion$\frac {1}{KL}\|\mathbf {F} - \mathbf {D}\mathbf {E}\|^{2}_{F}$over all$\delta $-sparse and$\gamma $-sparse matrices$\mathbf {D}\in \mathbb {R}^{K \times NT}$and$\mathbf {E} \in \mathbb {R}^{NT \times L}$. With these matrices respectively defining which servers compute each subfunction, and which users connect to each server, we here design our$\mathbf {D},\mathbf {E}$by designing tessellated-based and SVD-based fixed support matrix factorization methods that first split F into properly sized and carefully positioned submatrices, which we then approximate and then decompose into properly designed submatrices of D and E. For the zero-error case and under basic dimensionality assumptions, the work reveals achievable computation-vs-communication corner points$(\gamma ,\delta)$which, for various cases, are proven optimal over a large class of$\mathbf {D},\mathbf {E}$by means of a novel tessellations-based converse. Subsequently, for largeN, and under basic statistical assumptions on F, the average achievable error$\epsilon $is concisely expressed using the incomplete first moment of the standard Marchenko-Pastur distribution, where this performance is shown to be optimal over a large class of D and E. In the end, the work also reveals that the overall achieved gains over baseline methods are unbounded.

In this paper, we investigate the problem of multi-user linearly decomposable function computation, where$N$servers help compute functions for$K$users, and where each such function can be expressed as a linear combination of$L$basis subfunctions. The process begins with each server computing some of the subfunctions, then broadcasting a linear combination of its computed outputs to a selected group of users, and finally having each user linearly combine its received data to recover its function. As it has become recently known, this problem can be translated into a matrix decomposition problem F = DE, where$\mathbf{F}\in\mathbf{GF}(q)^{K\times L}$describes the coefficients that define the users' demands, where$\mathbf{E}\in\mathbf{GF}(q)^{N\times L}$describes which subfunction each server computes and how it combines the computed outputs, and where$\mathbf{D}\in \mathbf{GF}(q)^{K\times N}$describes which servers each user receives data from and how it combines this data. Our interest here is in reducing the total number of subfunction computations across the servers (cumulative computational cost), as well as the worst-case load which can be a measure of computational delay. Our contribution consists of novel bounds on the two computing costs, where these bounds are linked here to the covering and packing radius of classical codes. One of our findings is that in certain cases, our distributed computing problem - and by extension our matrix decomposition problem - is treated optimally when F is decomposed into a parity check matrix D of a perfect code, and a matrix E which has columns as the coset leaders of this same code.

The multi-user linearly-separable distributed computing problem is considered here, in which N servers help to compute the real-valued functions requested by K users, where each function can be written as a linear combination of up to L (generally non-linear) subfunctions. Each server computes a fraction γ of the subfunctions, then communicates a function of its computed outputs to some of the users, and then each user collects its received data to recover its desired function. Our goal is to bound the ratio between the computation workload done by all servers over the number of datasets.To this end, we here reformulate the real-valued distributed computing problem into a matrix factorization problem and then into a basic sparse recovery problem, where sparsity implies computational savings. Building on this, we first give a simple probabilistic scheme for subfunction assignment, which allows us to upper bound the optimal normalized computation cost as $\gamma \leq \frac{K}{N}$ that a generally intractable ℓ0-minimization would give. To bypass the intractability of such optimal scheme, we show that if these optimal schemes enjoy $\gamma \leq - r\frac{K}{N}W_{ - 1}^{ - 1}\left( { - \frac{{2K}}{{eNr}}} \right)$ (where W−1(•) is the Lambert function and r calibrates the communication between servers and users), then they can actually be derived using a tractable Basis Pursuit ℓ1-minimization. This newly-revealed connection opens up the possibility of designing practical distributed computing algorithms by employing tools and methods from compressed sensing.

In this work, we explore the problem of multi-user linearly-separable distributed computation, where$N$servers help compute the desired functions (jobs) of$K$users, and where each desired function can be written as a linear combination of up to$L$(generally non-linear) subtasks (or sub-functions). Each server computes some of the subtasks, communicates a function of its computed outputs to some of the users, and then each user collects its received data to recover its desired function. We explore the computation and communication relationship between how many servers compute each subtask vs. how much data each user receives. For a matrix$\mathbf {F}$representing the linearly-separable form of the set of requested functions, our problem becomes equivalent to the open problem of sparse matrix factorization$\mathbf {F} = \mathbf {D}\mathbf {E}$over finite fields, where a sparse decoding matrix$\mathbf {D}$and encoding matrix$\mathbf {E}$imply reduced communication and computation costs respectively. This paper establishes a novel relationship between our distributed computing problem, matrix factorization, syndrome decoding and covering codes. To reduce the computation cost, the above$\mathbf {D}$is drawn from covering codes or from a here-introduced class of so- called ‘partial covering’ codes, whose study here yields computation cost results that we present. To then reduce the communication cost, these coding-theoretic properties are explored in the regime of codes that have low-density parity check matrices. The work reveals — first for the commonly used one-shot scenario — that in the limit of large$N$, the optimal normalized computation cost$\gamma \in (0,1)$is in the range$\gamma \in \left({H_{q}^{-1}\left({\frac {\log _{q}(L)}{N}}\right), H_{q}^{-1}(K/N)}\right)$— where$H_{q}$is the$q$-ary entropy function — and that this can be achieved with normalized communication cost that vanishes as$\sqrt {\log _{q}(N)}/N$. The above reveals an unbounded coding gain over the uncoded scenario, as well as reveals the role of a certain functional rate$\log _{q}(L)/N$and functional capacity$H_{q}(\gamma)$of the system. In the end, we also explore the multi-shot scenario, for which we derive bounds on the computation cost.

In this work, we investigate the problem of multi-user linearly separable function computation, where N servers help compute the desired functions (jobs) of K users. In this setting each desired function can be written as a linear combination of up to L (generally non-linear) sub-functions. Each server computes some of the sub-tasks, and communicates a linear combination of its computed outputs (files) in a single-shot to some of the users, then each user linearly combines its received data in order to recover its desired function. We explore the range of the optimal computation cost via establishing a novel relationship between our problem, syndrome decoding and covering codes. The work reveals that in the limit of large N, the optimal computation cost — in the form of the maximum fraction of all servers that must compute any subfunction — is lower bounded as $\gamma \geq H_q^{ - 1}\left( {\frac{{{{\log }_q}(L)}}{N}} \right)$, for any fixed logq(L)/N. The result reveals the role of the computational rate logq(L)/N, which cannot exceed what one might call the computational capacity Hq(γ) of the system.