# Multi-Server Multi-Function Distributed Computation

Derya Malak, Mohammad Reza Deylam Salehi, Berksan Serbetci, and Petros Elia
Derya Malak, Mohammad Reza Deylam Salehi, and Petros Elia are with the Commun.
Systems Dept., EURECOM, Biot Sophia Antipolis, 06904 FRANCE (emails: {malak,
deylam, elia }@eurecom.fr). This work was conducted when B. Serbetci was a
Postdoctoral Researcher at EURECOM<EMAIL_ADDRESS>research was
partially supported by a Huawei France-funded Chair towards Future Wireless
Networks, and supported by the program “PEPR Networks of the Future” of France
2030. Co-funded by the European Union (ERC, SENSIBILITÉ, 101077361, and ERC-
PoC, LIGHT, 101101031). Views and opinions expressed are however those of the
author(s) only and do not necessarily reflect those of the European Union or
the European Research Council. Neither the European Union nor the granting
authority can be held responsible for them.

###### Abstract

The work here studies the communication cost for a multi-server multi-task
distributed computation framework, and does so for a broad class of functions
and data statistics. Considering the framework where a user seeks the
computation of multiple complex (conceivably non-linear) tasks from a set of
distributed servers, we establish communication cost upper bounds for a
variety of data statistics, function classes and data placements across the
servers. To do so, we proceed to apply, for the first time here, Körner’s
characteristic graph approach — which is known to capture the structural
properties of data and functions — to the promising framework of multi-server
multi-task distributed computing. Going beyond the general expressions, and in
order to offer clearer insight, we also consider the well-known scenario of
cyclic dataset placement and linearly separable functions over the binary
field, in which case our approach exhibits considerable gains over the state
of art. Similar gains are identified for the case of multi-linear functions.

###### Index Terms:

Distributed computation; linearly separable functions; non-linear functions;
functional compression; characteristic graph entropy; multi-server; multi-
function; skewed statistics; and data correlations.

##  I Introduction

Distributed computing plays an increasingly significant role in accelerating
the execution of computationally challenging and complex computational tasks.
This growth in influence is rooted in the innate capability of distributed
computing to parallelize computational loads across multiple servers. This
same parallelization renders distributed computing as an indispensable tool
for addressing a wide array of complex computational challenges, spanning
scientific simulations, extracting various spatial data distributions [1],
data-intensive analyses for cloud computing [2], machine learning [3], as well
as applications in various other fields such as computational fluid dynamics
[4], high-quality graphics for movie and game rendering [5], and a variety of
medical applications [6] to name just a few. In the center of this ever-
increasing presence of parallelized computing, stand modern parallel
processing techniques, such as MapReduce [7, 8, 9], and Spark [10, 11].

For distributed computing though to achieve the desirable parallelization
effect, there is an undeniable need for massive information exchange to-and-
from the various network nodes. Reducing this communication load is essential
for scalability [12, 13, 14, 15] in various topologies [16, 17, 18]. Central
to the effort to reduce communication costs, stand coding techniques such as
those found in [19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
34, 35, 36, 37], including gradient coding [21], and different variants of
coded distributed computing that nicely yield gains in reliability,
scalability, computation speed and cost-effectiveness [24]. Similar
communication-load aspects are often addressed via polynomial codes [38] which
can mitigate stragglers and enhance the recovery threshold, while MatDot
codes, devised in [32, 39] for secure distributed matrix multiplication, can
decrease the number of transmissions for distributed matrix multiplication.
This same emphasis in reducing communication costs is even more prominent in
works like [35, 36, 40, 39, 41, 42, 43, 44, 32, 45, 46, 47], which again focus
on distributed matrix multiplication. For example, focusing on a cyclic
dataset placement model, the work in [40] provided useful achievability
results, while the authors of [36] have characterized achievability and
converse bounds for secure distributed matrix multiplication. Furthermore, the
work in [35] found creative methods to exploit the correlation between the
entries of the matrix product in order to reduce the cost of communication.

###  I-A The multi-server multi-function distributed computing setting, and
the need for accounting for general non-linear functions

As computing requirements become increasingly challenging, distributed
computing models have also evolved to be increasingly complex. One such recent
model is the multi-server multi-function distributed computing model that
consists of a master node, a set of distributed servers, and a user demanding
the computation of multiple functions. The master contains the set of all
datasets and allocates them to the servers which are then responsible for
computing a set of specific subfunctions of datasets. This multi-server multi-
function setting was recently studied by Wan et al. in [40] for the class of
linearly separable functions, which nicely captures a wide range of real-world
tasks [7] such as convolution [42], the discrete Fourier transform [48] and a
variety of other cases as well. This same work bounded the communication cost,
employing linear encoding and linear decoding that leverage the structure of
requests.

At the same time though there is growing need to consider more general classes
of functions, including non-linear functions such as is often the case with
subfunctions that produce intermediate values in MapReduce operations [7], or
that relate to quantization [49], classification [50], and optimization [51].
Intense interest can also be identified in the aforementioned problem of
distributed matrix multiplication, which has been explored in a plethora of
works that include [36, 52, 53, 54, 46, 43], with a diverse focus that entails
secrecy [46, 54, 52], as well as precision and stragglers [36, 53, 14, 43] to
name a few. In addition to matrix multiplication, other important non-linear
function classes include sparse polynomial multiplication [55], permutation
invariant functions [56] — which often appear in multi-agent settings and have
applications in learning, combinatorics, and graph neural networks — as well
as nomographic functions [57, 58] which can appear in the context of sensor
networks and which have strong connections with interference exploitation and
lattice codes, as nicely revealed in [57, 58].

Our own work here is indeed motivated by this emerging need for distributed
computing of non-linear functions, and our goal is to now consider general
functions in the context of the multi-server, multi-function distributed
computing framework, while also capturing dataset statistics and correlations,
and while exploiting the structural properties of the (possibly non-linear)
functions requested by the user. To do so, we will go beyond the linear coding
approaches in [40, 59, 60], and will devise demand-based encoding-decoding
solutions. To do this, we will adopt — in the context of the multi-server
multi-function framework — the powerful tools from characteristic graphs,
which are specifically geared toward capturing both the statistical structure
of data as well as the properties of functions beyond the linear case. To help
the reader better understand our motivation and contribution, we proceed with
a brief discussion on data structure and characteristic graphs.

###  I-B Data correlation and structure

Crucial in reducing the communication bottleneck of distributed computing, is
an ability to capture the structure that appears in modern datasets. Indeed,
even before computing considerations come into play, capturing the general
structure of data has been crucial in reducing the communication load in
various scenarios such as those in the seminal work by Slepian-Wolf [61] and
Cover [62]. Similarly, when function computation is introduced, data structure
can be a key component. In the context of computing, we have seen the seminal
work by Körner and Marton [63] which focused on efficient compression of the
modulo $2$ sum of two statistically dependent sources, while Lalitha et al.
[64] explored linear combinations of multiple statistically dependent sources.
Furthermore, for general bivariate functions of correlated sources, when one
of the sources is available as side information, the work of Yamamoto [65]
generalized the pioneering work of Wyner and Ziv [66], to provide a rate-
distortion characterization for the function computation setting.

It is the case though that when the computational model becomes more involved
— as is the case in our multi-server multi-function scenario here — data may
often be treated as unstructured and independent [67, 40, 59, 68, 69]. This
naturally allows for crucial analytical tractability, but it may often ignore
the potential benefits of accounting for statistical skews and correlations in
data when aiming to reduce communication costs in distributed computing.
Furthermore, this comes at a time when more and more function computation
settings — such as in medical imaging analysis [70], data fusion and group
inferences [71], as well as predictive modeling for artificial intelligence
[72] — entail datasets with prominent dependencies and correlations. While
various works, such as by Körner-Marton [63], Han-Kobayashi [73], Yamamoto
[65], Alon-Orlitsky [74], Orlitsky-Roche [75], provide crucial breakthroughs
in exploiting data structure, to the best of our knowledge, _in the context of
fully distributed function computation_ , the structure in functions and data
has yet to be considered simultaneously.

###  I-C Characteristic graphs

To jointly account for this structure in both data and functions, we will draw
from the powerful literature on _Characteristic graphs_ , introduced by Körner
for source coding [76], and used in data compression [63, 74, 75, 77, 78, 79],
cryptography [80], image processing [81], and bioinformatics [82]. For
example, toward understanding the fundamental limits of distributed functional
compression, the work in [76] devised the graph entropy approach in order to
provide the best possible encoding rate of an information source with
vanishing error probability. This same approach, while capturing both function
structure and source structure, was presented for the case of one source, and
it is not directly applicable to the distributed computing setting. Similarly
the zero-error side information setting in [74] and the lossy encoding setting
in [75], [65] use Körner’s graph entropy [76] approach to capture both
function structure and source structure, but were again presented for the case
of one source. Similar focus can be found in the works in [74, 75, 77, 78,
80]. The same characteristic graph approach has been nicely used by Feizi and
Médard in [83] for the distributed computing setting, for a simple distributed
computing framework, and in the absence of considerations for data structure.

Characteristic graphs, which are used in fully distributed architectures to
compress information, can allow us to capture various data statistics and
correlations, various data placement arrangements, and various function types.
This versatility motivates us to employ characteristic graphs in our multi-
server, multi-function architecture for distributed computing of non-linear
functions.

###  I-D Contributions

In this paper, leveraging fundamental principles from source and functional
compression as well as graph theory, we study a general multi-server multi-
function distributed computing framework composed of a single user requesting
a set of functions, which are computed with the assistance of distributed
servers that have partial access to datasets. To achieve our goal, we consider
the use of Körner’s characteristic graph framework [76] in our multi-server
multi-function setting, and proceed to establish upper bounds on the
achievable sum-rates reflecting the setting’s communication requirements.

By extending, for the first time here, Körner’s characteristic graph framework
[76] to the new multi-server multi-function setting, we are able to reflect
the nature of the functions and data statistics, in order to allow each server
to build a codebook of encoding functions that determine the transmitted
information. Each server, using its own codebook, can transmit a function (or
a set of functions) of the subfunctions of the data available in its storage,
and to then provide the user with sufficient information for evaluating the
demanded functions. The codebooks allow for a substantial reduction in the
communication load.

The employed approach allows us to account for general dataset statistics,
correlations, dataset placement, and function classes, thus yielding gains
over the state of art [40], [61], as showcased in our examples for the case of
linearly separable functions in the presence of statistically skewed data, as
well as for the case of multi-linear functions where the gains are
particularly prominent, again under statistically skewed data. For this last
case of multi-linear functions, we provide an upper bound on the achievable
sum-rate (see Subsection IV-B), under a cyclic placement of data that reside
in the binary field. We also provide a generalization of some elements in
existing works on linearly separable functions [40, 59].

In the end, our work demonstrates the power of using characteristic graph-
based encoding for exploiting the structural properties of functions and data
in distributed computing, as well as provides insights into fundamental
compression limits, all for the broad scenario of multi-server, multi-function
distributed computation.

###  I-E Paper organization

The rest of this paper is structured as follows. Section II describes the
system model for the multi-server multi-function architecture, and Section III
details the main results on the communication cost or sum-rate bounds under
general dataset distributions and correlations, dataset placement models, and
general function classes requested by the user, over a field of characteristic
$q\geq 2$, through employing the characteristic graph approach, and contrasts
the sum-rate with relevant prior works, e.g., [40, 61]. Finally, we summarize
our key results and outline possible future directions in Section V. We
provide a primer for the key definitions and results on characteristic graphs
and their fundamental compression limits in Appendix A, and give proofs of our
main results in Appendix B.

Notation: We denote by $H(X)=\mathbb{E}[-\log P_{X}(X)]$ the Shannon entropy
of random variable $X$ drawn from distribution or probability mass function
(PMF) $P_{X}$. Let $P_{X_{1},X_{2}}$ be the joint PMF of two random variables
$X_{1}$ and $X_{2}$, where $X_{1}$ and $X_{2}$ are not necessarily independent
and identically distributed (i.i.d.), i.e., equivalently the joint PMF is not
in product form. The notation $X\sim{\rm Bern}(\epsilon)$ denotes that $X$ is
Bernoulli distributed with parameter $\epsilon\in[0,1]$. Let $h(\cdot)$ denote
the binary entropy function, and $H_{B}(B(n,\epsilon))$ denote the entropy of
a Binomial random variable of size $n\in\mathbb{N}$, with $\epsilon\in[0,1]$
modeling the success probability of each Boolean-valued outcome. The notation
$X_{\mathcal{S}}=\\{X_{i}\,:\,i\in\mathcal{S}\\}$ denotes a subset of servers
with indices $i\in\mathcal{S}$ for $\mathcal{S}\subseteq\Omega$. The notation
$\mathcal{S}^{c}=\Omega\backslash\mathcal{S}$ denotes the complement of
$\mathcal{S}$. We denote the probability of an event $A$ by $\mathbb{P}(A)$.
The notation $1_{x\in A}$ denotes the indicator function which takes the value
$1$ if $x\in A$, and $0$ otherwise. The notation $G_{X_{i}}$ denotes the
characteristic graph that server $i\in\Omega$ builds for computing
$F(X_{\Omega})$. The measures $H_{G_{X}}(X)$ and $H_{G_{X}}(X\,|\,Y)$ denote
the entropy of characteristic graph $G_{X}$, and the conditional graph entropy
for random variable $X$ given $Y$, respectively. The notation
$\mathcal{T}(N,K,K_{c},M,N_{r})$ shows the topology of the distributed system.
We note that $\mathcal{Z}_{i}$ denotes the indices of datasets stored in
$i\in\Omega$, and the notation
$K_{n}(\mathcal{S})=|\mathcal{Z}_{\mathcal{S}}|=\big{|}\bigcup\nolimits_{i\in\mathcal{S}}\mathcal{Z}_{i}\big{|}$
represents the cardinality of the datasets in the union of the sets in
$\mathcal{S}$ for a given subset $\mathcal{S}\subseteq\Omega$ of servers. We
also note that $[N]=\\{1,2,\dots,N\\}$, $N\in\mathbb{Z}^{+}$, and
$[a:b]=\\{a,a+1,\dots,b\\}$ for $a,b\in\mathbb{Z}^{+}$ such that $a<b$. We use
the convention $\mod{\\{b,a\\}}=a$ if $a$ divides $b$. We provide the notation
in Table I.

Distributed computation system-related definitions | Symbols
---|---
Number of distributed servers; set of distributed servers; capacity of a server |  $N$; $\Omega$; $M$
Set of datasets; dataset catalog size |  $\\{D_{k}\\}_{k\in[K]}$; $K=|\mathcal{K}|$
Subfunction $k\in\mathcal{Z}_{i}\subseteq[K]$ | $W_{k}=h_{k}(D_{k})$
The number of symbols in each $W_{k}$; blocklength |  $L$ ; $n$
Set of indices of datasets assigned to server $i\in\Omega$ such that $|\mathcal{Z}_{i}|\leq M$ | $\mathcal{Z}_{i}\subseteq[K]$
Set of subfunctions corresponding to a subset of servers with indices $i\in\mathcal{S}$ for $\mathcal{S}\subseteq\Omega$ | $X_{\mathcal{S}}=\\{X_{i}\,:\,i\in\mathcal{S}\\}$
Recovery threshold | $N_{r}$
Number of demanded functions by the user | $K_{c}$
Number of symbols per transmission of server $i\in\Omega$ | $T_{i}$
Topology of the multi-server multi-function distributed computing setting | $\mathcal{T}(N,K,K_{c},M,N_{r})$
Graph-theoretic definitions | Symbols
Characteristic graph that server $i$ builds for computing $F(X_{\Omega})$ |  $G_{X_{i}}$, $i\in\Omega$
Union of characteristic graphs that server $i$ builds for computing $\\{F_{j}(X_{\Omega})\\}_{j\in[K_{c}]}$ |  $G^{\cup}_{X_{i}}$, $i\in\Omega$
Maximal independent set (MIS); set of all MISs of $i\in\Omega$ |  $U_{1}$; $S(G_{X_{1}})$
A valid coloring of $G_{X_{i}}$ | $c_{G_{X_{i}}}$
$n$-th OR power graph; a valid coloring of the $n$-th OR power graph |  $G^{n}_{{\bf X}_{i}}$; $c_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i})$
Characteristic graph entropy of $X_{i}$ | $H_{G_{X_{i}}}(X_{i})$
Conditional characteristic graph entropy of $X_{i}$ such that $i\in\mathcal{S}$ given $X_{\mathcal{S}^{c}}$ | $H_{G_{X_{i}}}(X_{i}\,|\,X_{\mathcal{S}^{c}})$
TABLE I: Notation.

##  II System model

This section outlines our multi-server multi-function architecture and details
our main technical contributions, namely the communication cost for the
problem of distributed computing of general non-linear functions, and the cost
for special instances of the computation problem under some simplifying
assumptions on the dataset statistics, dataset correlations, placement, and
the structures of functions.

In the multi-server, multi-function distributed computation framework, the
master has access to the set of all datasets, and distributes the datasets
across the servers. The total number of servers is $N$, and each server has a
capacity of $M$. Communication from the master to the servers is allowed,
whereas the servers are distributed and cannot collaborate. The user requests
$K_{c}$ functions that could be non-linear. Given the dataset assignment to
the servers, any subset of $N_{r}$ servers is sufficient to compute the
functions requested. We denote by $\mathcal{T}(N,K,K_{c},M,N_{r})$ the
topology for the described multi-server multi-function distributed computing
setting, which we detail in the following.

###  II-A Datasets, subfunctions, and placement into distributed servers

There are $K$ datasets in total, each denoted by $D_{k}$, $k\in[K]$. Each
distributed server $i\in\Omega=[N]$ with a capacity of $M$ is assigned a
subset of datasets with indices $\mathcal{Z}_{i}\subseteq[K]$ such that
$|\mathcal{Z}_{i}|=M$, where the assignments possibly overlap.

Each server computes a set of subfunctions $W_{k}=h_{k}(D_{k})$ for
$k\in\mathcal{Z}_{i}\subseteq[K]$, $i\in\Omega$. Datasets
$\\{D_{k}\\}_{k\in[K]}$ could be dependent 111We note that exploiting the
temporal and spatial variation or dependence of data, it is possible to
decrease the communication cost.  across $\mathcal{K}$, so could
$\\{W_{k}\\}_{k\in[K]}$. We denote the number of symbols in each $W_{k}$ by
$L$, which equals the blocklength $n$. Let
$X_{i}=\\{W_{k}\\}_{k\in\mathcal{Z}_{i}}=W_{\mathcal{Z}_{i}}=\\{h_{k}(D_{k})\\}_{k\in\mathcal{Z}_{i}}$
denote the set of subfunctions of $i$-th server, $\mathcal{X}_{i}$ be the
alphabet of $X_{i}$, and $X_{\Omega}=(X_{1},X_{2},\dots,X_{N})$ be the set of
subfunctions of all servers. We denote by ${\bf
W}_{k}=W_{k1},W_{k2},\dots,W_{kn}$ and ${\bf
X}_{i}=X_{i1},X_{i2},\dots,X_{in}\in\mathbb{F}_{q}^{|\mathcal{Z}_{i}|\times
n}$, the length $n$ sequences of subfunction $W_{k}$, and of
$W_{\mathcal{Z}_{i}}$ assigned to server $i\in\Omega$.

###  II-B Cyclic dataset placement model, computation capacity, and recovery
threshold

We assume that the total number of datasets $K$ is divisible by the number of
servers $N$, i.e., $\frac{K}{N}\doteq\Delta\in\mathbb{Z}^{+}$. The dataset
placement on $N$ distributed servers is conducted in a circular or cyclic
manner, in the amount of $\Delta$ circular shifts between two consecutive
servers, where the shifts are to the right and the final entries are moved to
the first positions, if necessary. As a result of cyclic placement, any subset
of $N_{r}$ servers covers the set of all datasets to compute the requested
functions from the user. Given $N_{r}\in[N]$, each server has a storage size
or computation cost of $|\mathcal{Z}_{i}|=M=\Delta(N-N_{r}+1)$, and the amount
of dataset overlap between the consecutive servers is $\Delta(N-N_{r})$.

Hence, the set of indices assigned to server $i\in\Omega$ is given as follows:

$\displaystyle\mathcal{Z}_{i}=\bigcup_{r=0}^{\Delta-1}\left\\{\mod{\\{i,N\\}}+rN,\mod{\\{i+1,N\\}}+rN,\dots,\mod{\\{i+N-N_{r},N\\}}+rN\,\right\\},$
(1)

where $X_{i}=W_{\mathcal{Z}_{i}}$, $i\in\Omega$. As a result of (1), the
cardinality of the datasets assigned to each server meets the storage capacity
constraint $M$ with equality, i.e., $|\mathcal{Z}_{i}|=M$, for all
$i\in\Omega$.

###  II-C User demands and structure of the computation

We address the problem of distributed lossless compression of a set general
multi-variable functions
$F_{j}(X_{\Omega}):\mathcal{X}_{1}\times\mathcal{X}_{2}\dots\times\mathcal{X}_{N}\to\mathbb{F}_{q}$,
$j\in[K_{c}]$, requested by the user from the set of servers, where $K_{c}\geq
1$, and the functions are known by the servers and the user. More
specifically, the user, from a subset of distributed servers, aims to compute
in a lossless manner the following length $n$ sequence as $n$ tends to
infinity:

$\displaystyle F_{j}({\bf
X}_{\Omega})=\\{F_{j}(X_{1l},\,X_{2l},\dots,X_{Nl})\\}_{l=1}^{n}\,\,j\in[K_{c}]\
,$ (2)

where $F_{j}(X_{1l},\,X_{2l},\dots,X_{Nl})$ is the function outcome for the
$l$-th realization $l\in[n]$, given the length $n$ sequence. We note that the
representation in (2) is the most general form of a (conceivably non-linear)
multi-variate function, which encompasses the special cases of separable
functions, and linearly separable functions, which we discuss next.

In this work, the user seeks to compute functions that are separable to each
dataset. Each demanded function $f_{j}(\cdot)\in\mathbb{R}$, $j\in[K_{c}]$ is
a function of subfunctions $\\{W_{k}\\}_{k\in\mathcal{K}}$ such that
$W_{k}=h_{k}(D_{k})\in\mathbb{F}_{q}$, where $h_{k}$ is a general function
(could be linear or non-linear) of dataset $D_{k}$. Hence, using the relation
$X_{i}=W_{\mathcal{Z}_{i}}=\\{h_{k}(D_{k})\\}_{k\in\mathcal{Z}_{i}}$, each
demanded function $j\in[K_{c}]$ can be written in the following form:

$\displaystyle
f_{j}(W_{\mathcal{K}})=f_{j}(h_{1}(D_{1}),\dots,h_{K}(D_{K}))=F_{j}(\\{h_{k}(D_{k})\\}_{k\in\mathcal{Z}_{1}},\dots,\\{h_{k}(D_{k})\\}_{k\in\mathcal{Z}_{N}})=F_{j}(X_{\Omega})\
.$ (3)

In the special case of linearly separable functions222Special instances of the
linearly separable representation of subfunctions $\\{W_{k}\\}_{k}$ given in
(4) are linear functions of the datasets $\\{D_{k}\\}$ and are denoted by
$F_{j}=\sum_{k}\gamma_{jk}D_{k}$. [40], the demanded functions take the form:

$\displaystyle\\{F_{j}(X_{\Omega})\\}_{j\in[K_{c}]}=\begin{bmatrix}F_{1}&F_{2}&\ldots&F_{K_{c}}\end{bmatrix}^{\intercal}={\bf\Gamma}{\bf
W}\ ,$ (4)

where ${\bf
W}=\begin{bmatrix}W_{1}&W_{2}&\ldots&W_{K}\end{bmatrix}^{\intercal}\in\mathbb{F}_{q}^{K\times
1}$ is the subfunction vector, and the coefficient matrix
${\bf\Gamma}=\\{\gamma_{jk}\\}\in\mathbb{F}_{q}^{K_{c}\times K}$ is known to
the master node, servers, and the user. In other words,
$\\{F_{j}(X_{\Omega})\\}_{j\in[K_{c}]}$ is a set of linear maps from the
subfunctions $\\{W_{k}\\}_{k}$, where
$F_{j}(X_{\Omega})=\sum\nolimits_{k\in[K]}\gamma_{jk}\cdot W_{k}$. We do not
restrict $\\{F_{j}(X_{\Omega})\\}_{j\in[K_{c}]}$ to linearly separable
functions, i.e., it may hold that
$\\{F_{j}(X_{\Omega})\\}_{j\in[K_{c}]}\neq{\bf\Gamma}{\bf W}$.

###  II-D Communication cost for the characteristic graph-based computing
approach

To compute $\\{F_{j}({\bf X}_{\Omega})\\}_{j\in[K_{c}]}$, each server
$i\in\Omega$ constructs a characteristic graph, denoted by $G_{X_{i}}$, for
compressing $X_{i}$. More specifically, for asymptotic lossless computation of
the demanded functions, the server builds the $n$-th OR power $G^{n}_{{\bf
X}_{i}}$ of $G_{X_{i}}$ for compressing ${\bf X}_{i}$ to determine the
transmitted information. The minimal possible code rate achievable to
distinguish the edges of $G^{n}_{{\bf X}_{i}}$ as $n\to\infty$, is given the
_Characteristic graph entropy_ , $H_{G_{X_{i}}}(X_{i})$. For a primer on key
graph-theoretic concepts, characteristic graph-related definitions, and the
fundamental compression limits of characteristic graphs, we refer the reader
to [77], [80], [83]. In this work, we solely focus on the characterization of
the total communication cost from all servers to the user, i.e., the
achievable sum-rate, without accounting for the costs of communication between
the master and the servers, and of computations performed at the servers and
the user.

Each $i\in\Omega$ builds a mapping from ${\bf X}_{i}$ to a valid coloring of
$G^{n}_{{\bf X}_{i}}$, denoted by $c_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i})$. The
coloring $c_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i})$ specifies the color classes of
${\bf X}_{i}$ that form independent sets to distinguish the demanded function
outcomes. Given an encoding function $g_{i}$ that models the transmission of
server $i\in\Omega$ for computing $\\{F_{j}({\bf
X}_{\Omega})\\}_{j\in[K_{c}]}$, we denote by ${\bf Z}_{i}=g_{i}({\bf
X}_{i})=e_{X_{i}}(c_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i}))$ the color encoding
performed by server $i\in\Omega$ for ${\bf X}_{i}$. Hence, the communication
rate of server $i\in\Omega$, for a sufficiently large blocklength $n$, where
$T_{i}$ is the length for the color encoding performed at $i\in\Omega$, is

$\displaystyle\\!\\!R_{i}=\frac{T_{i}}{L}=\frac{H(e_{X_{i}}(c_{G^{n}_{{\bf
X}_{i}}}({\bf X}_{i})))}{n}\geq H_{G_{X_{i}}}(X_{i})\ ,\,\,i\in\Omega\ ,$ (5)

where the inequality follows from exploiting the achievability of
$H_{G_{X_{i}}}(X_{i})=\lim\limits_{n\to\infty}\frac{1}{n}H^{\chi}_{G^{n}_{{\bf
X}_{i}}}({\bf X}_{i})$, where $H^{\chi}_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i})$ is
the _chromatic entropy_ of the graph $G^{n}_{{\bf X}_{i}}$ [74], [76]. We
refer the reader to Appendix A-B for a detailed description of the notions of
chromatic and graph entropies (cf. (33) and (34), respectively).

For the multi-server multi-function distributed setup, using the
characteristic graph-based fundamental limit in (5), an achievable sum-rate
for asymptotic lossless computation is

$\displaystyle R_{\rm
ach}=\sum\limits_{i\in\Omega}R_{i}\leq\sum\limits_{i\in\Omega}H_{G_{X_{i}}}(X_{i})\
.$ (6)

We next provide our main results in Section III.

##  III Main results

In this section, we analyze the multi-server multi-function distributed
computing framework exploiting the characteristic graph-based approach in
[76]. In contrast to the previous research attempts in this direction, our
solution method is general, and it captures (i) general input statistics or
dataset distributions or the skew in data instead of assuming uniform
distributions, (ii) correlations across datasets, (iii) any dataset placement
model across servers, beyond the cyclic [40] or the Maddah-Ali and Niesen [84]
placements, and (iv) general function classes requested by the user, instead
of focusing on a particular function type (see e.g., [40, 68, 85]).

Subsequently, we will delve into specific function computation scenarios.
First, we will present our main result (Theorem 1) which is the most general
form that captures (i)-(iv). We then demonstrate (in Proposition 1) that the
celebrated result of Wan et al. [40, Theorem 2] can be obtained as a special
case of Theorem 1, given that: (i) the datasets are i.i.d. and uniform over
$q$-ary fields, (ii) the placement of datasets across servers is cyclic, and
(iii) the demanded functions are linearly separable, given as in (4). Under
correlated and identically distributed Bernoulli dataset model with a skewness
parameter $\epsilon\in(0,1)$ for datasets, we next present in Proposition 2,
the achievable sum rate for computing Boolean functions. Finally, in
Proposition 3, we analyze our characteristic graph-based approach for
evaluating multi-linear functions, a pertinent class of non-linear functions,
under the assumption of cyclic placement and i.i.d. Bernoulli distributed
datasets with parameter $\epsilon$, and derive an upper bound on the sum rate
needed. To gain insight into our analytical results and demonstrate the
savings in the total communication cost, we provide some numerical examples.

We next present our main theorem (Theorem 1) on the achievable communication
cost for the multi-server, multi-function topology, which holds for all input
statistics, under any correlation model across datasets, and for distributed
computing of all function classes requested by the user, regardless of the
data assignment over the servers’ caches. The key to capturing the structure
of general functions in Theorem 1 is the utilization of a characteristic
graph-based compression technique, as proposed by Körner in [76]. 333For a
more detailed description of characteristic graphs and their entropies, see
Appendix A-B.

######  Theorem 1.

(Achievable sum-rate using the characteristic graph approach for general
functions and distributions.) In the multi-server, multi-function distributed
computation model, denoted by $\mathcal{T}(N,K,K_{c},M,N_{r})$, under general
placement of datasets, and for a set of $K_{c}$ general functions
$\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$ requested by the user, and under
general jointly distributed dataset models, including non-uniform inputs and
allowing correlations across datasets, the characteristic graph-based
compression yields the following upper bound on the achievable communication
rate:

$\displaystyle R_{\rm
ach}\leq\sum\limits_{i=1}^{N_{r}}\,\min\limits_{Z_{i}=g_{i}(X_{i})\,:\,g_{i}\in\mathcal{C}_{i}}H_{G^{\cup}_{X_{i}}}(X_{i})\
,$ (7)

where

  * •

$G^{\cup}_{X_{i}}=\bigcup\limits_{j\in[K_{c}]}G_{X_{i},j}$ is the union
characteristic graph444We refer the reader to (36) (Appendix A-B) for the
definition of a union of characteristic graphs. that server $i\in\Omega$
builds for computing $\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$,

  * •

$\mathcal{C}_{i}\ni g_{i}$ denotes a codebook of functions that server
$i\in\Omega$ uses for computing $\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$,

  * •

each subfunction $W_{k}$, $k\in\mathcal{K}$ is defined over a $q$-ary field
such that the characteristic is at least $2$, and

  * •

$Z_{i}=g_{i}(X_{i})$ such that $g_{i}\in\mathcal{C}_{i}$ denotes the
transmitted information from server $i\in\Omega$.

###### Proof.

See Appendix B-A. ∎

Theorem 1 provides a general upper bound on the sum-rate for computing
functions for general dataset statistics and correlations, and the placement
model, and allows any function type, over a field of characteristic $q\geq 2$.
We note that in (7), the codebook $\mathcal{C}_{i}$ determines the structure
of the union characteristic graph $G^{\cup}_{X_{i}}$, which, in turn,
determines the distribution of $Z_{i}$. Therefore, the tightness of the rate
upper bound relies essentially on the codebook selection. We also note that it
is possible to analyze the computational complexity of building a
characteristic graph and computing the bound in (7) via evaluating the
complexity of the transmissions $Z_{i}$ determined by
$\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$ for a given $i\in\Omega$.
However, the current manuscript focuses primarily on the cost of
communication, and we leave the computational complexity analysis to future
work. Because (7) is not analytically tractable, in the following, we will
focus on special instances of Theorem 1, to gain insights into the effects of
input statistics, dataset correlations, and special function classes in
determining the total communication cost.

We next demonstrate that the achievable communication cost for the special
scenario of distributed linearly separable computation framework given in [40,
Theorem 2] is embedded by the characterization provided in Theorem 1. We next
showcase the achievable sum rate result for linearly separable functions.

######  Proposition 1.

(Achievable sum-rate using the characteristic graph approach for linearly
separable functions and i.i.d. subfunctions over $\mathbb{F}_{q}$.) In the
multi-server, multi-function distributed computation model, denoted by
$\mathcal{T}(N,K,K_{c},M,N_{r})$, under the cyclic placement of datasets,
where $\frac{K}{N}=\Delta\in\mathbb{Z}^{+}$, and for a set of $K_{c}$ linearly
separable functions, given as in (4), requested by the user, and given i.i.d.
uniformly distributed subfunctions over a field of characteristic $q\geq 2$,
the characteristic graph-based compression yields the following bound on the
achievable communication rate:

$\displaystyle R_{\rm ach}\leq\begin{cases}\min\\{K_{c},\Delta\\}N_{r}\ ,\quad
1\leq K_{c}\leq\Delta Nr\ ,\\\ \min\\{K_{c},K\\}\ ,\quad\Delta Nr<K_{c}\
.\end{cases}$ (8)

###### Proof.

See Appendix B-B. ∎

We note that Theorem 1 results in Proposition 1 when three conditions hold:
(i) the dataset placement across servers is cyclic following the rule in (1),
(ii) the subfunctions $W_{\mathcal{K}}$ are i.i.d. and uniform over
$\mathbb{F}_{q}$ (see (45) in Appendix B-B), and (iii) the codebook
$\mathcal{C}_{i}$ is restricted to linear combinations of subfunctions
$W_{\mathcal{K}}$, which yields that the independent sets of
$G^{\cup}_{X_{i}}$ satisfy a set of linear constraints555We detail these
linear constraints in Appendix B-B, where the set of linear equations given in
(46) is used to simplify the entropy $H_{G^{\cup}_{X_{i}}}(X_{i})$ of the
union characteristic graph $G^{\cup}_{X_{i}}$ via the expression given in (44)
for evaluating the upper bound given in (42) on the achievable sum rate for
computing the desired functions via exploiting the entropies of the union
characteristic graphs for each of the $N_{r}$ servers, given the recovery
threshold $N_{r}$. in the variables $\\{W_{k}\\}_{k\in\mathcal{Z}_{i}}$. Note
that the linear encoding and decoding approach for computing linearly
separable functions, proposed by Wan et al. in [40, Theorem 2], is valid over
a field of characteristic $q>3$. However, in Proposition 1, the characteristic
of $\mathbb{F}_{q}$ is at least $2$, i.e., $q\geq 2$, generalizing [40,
Theorem 2] to larger input alphabets.

Next, we aim to demonstrate the merits of the characteristic graph-based
compression in capturing dataset correlations within the multi-server, multi-
function distributed computation framework. More specifically, we restrict the
general input statistics in Theorem 1 such that the datasets are correlated
and identically distributed, where each subfunction follows a Bernoulli
distribution with the same parameter $\epsilon$, i.e., $W_{k}\sim{\rm
Bern}(\epsilon)$, with $\epsilon\in(0,1)$, and the user demands $K_{c}$
arbitrary Boolean functions regardless of the data assignment. Similarly to
Theorem 1, the following proposition (Proposition 2) holds for general
function types (Boolean) regardless of the data assignment.

######  Proposition 2.

(Achievable sum-rate using the characteristic graph approach for general
functions and identically distributed subfunctions over $\mathbb{F}_{2}$.) In
the multi-server multi-function distributed computing setting, denoted by
$\mathcal{T}(N,K,K_{c},M,N_{r})$, under the general placement of datasets, and
for a set of $K_{c}$ Boolean functions
$\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$ requested by the user, and given
identically distributed and correlated subfunctions with $W_{k}\sim{\rm
Bern}(\epsilon)$, $k\in[K]$, where $\epsilon\in(0,1)$, the characteristic
graph-based compression yields the following bound on the achievable
communication rate:

$\displaystyle R_{\rm
ach}\leq\sum\limits_{i=1}^{N_{r}}\,\min\limits_{Z_{i}=g_{i}(X_{i})\,:\,g_{i}\in\mathcal{C}_{i}}h(Z_{i})\
,$ (9)

where

  * •

$\mathcal{C}_{i}\ni g_{i}\,:\,\\{0,1\\}^{M}\to\\{0,1\\}$ denotes a codebook of
Boolean functions that server $i\in\Omega$ uses,

  * •

$Z_{i}=g_{i}(X_{i})$ such that $g_{i}\in\mathcal{C}_{i}$ denotes the
transmitted information from server $i\in\Omega$,

  * •

$G^{\cup}_{X_{i}}$ has two maximal independent sets (MISs), namely
$s_{0}(G^{\cup}_{X_{i}})$ and $s_{1}(G^{\cup}_{X_{i}})$, yielding $Z_{i}=0$
and $Z_{i}=1$, respectively, and

  * •

the probability that $W_{\mathcal{Z}_{i}}$ yields the function value $Z_{i}=1$
is given as

$\displaystyle\mathbb{P}(Z_{i}=1)=\mathbb{P}(W_{\mathcal{Z}_{i}}\in
s_{1}(G^{\cup}_{X_{i}}))\ ,\quad i\in\Omega\ .$ (10)

###### Proof.

See Appendix B-C. ∎

While admittedly the above approach (Proposition 2) may not directly offer
sufficient insight, it does employ the new machinery to offer a generality
that allows us to plug in any set of parameters to determine the achievable
performance.

Contrasting Propositions 1\- 2, which give the total communication costs for
computing linearly separable and Boolean functions, respectively, over
$\mathbb{F}_{2}$, Proposition 2, by exploiting the skew and correlations of
datasets indexed by $\mathcal{Z}_{i}$, as well as the functions’ structures
via the MISs $s_{0}(G^{\cup}_{X_{i}})$ and $s_{1}(G^{\cup}_{X_{i}})$ of server
$i\in\Omega$, demonstrates that harnessing the correlation across the datasets
can indeed reduce the total communication cost versus the setting in
Proposition 1, devised with the assumption of i.i.d. and uniformly distributed
subfunctions.

The prior works have focused on devising distributed computation frameworks
and exploring their communication costs for specific function classes. For
instance, in [63], Körner and Marton have restricted the computation to be the
binary sum function, and in [73], Han and Kobayashi have classified functions
into two categories depending on whether they can be computed at a sum rate
that is lower than that of [61]. Furthermore, the computation problem has been
studied for specific topologies, e.g., the side information setting in [74,
75]. Despite the existing efforts, see e.g., [63, 73, 74, 75], to the best of
our knowledge, for the given multi-server, multi-function distributed
computing scenario, there is still no general framework for determining the
fundamental limits of the total communication cost for computing general non-
linear functions. Indeed, for this setting, the most pertinent existing work
that applies to general non-linear functions and provides an upper bound on
the achievable sum rate is that of Slepian-Wolf [61]. On the other hand, the
upper bound on the achievable computation scheme presented in Theorem 1 can
provide savings in the communication cost over [61] for functions including
linearly separable functions and beyond. To that end, we exploit Theorem 1 to
determine an upper bound on the achievable sum-rate for distributed computing
of a multi-linear function in the form of

$\displaystyle f(W_{\mathcal{K}})=\prod\limits_{k\in[K]}W_{k}\ .$ (11)

Note that (11) is used in various scenarios, including distributed machine
learning, e.g., to reduce variance in noisy datasets via ensemble learning
[86] or weighted averaging [87], sensor network applications to aggregate
readings for improved data analysis [88], as well as distributed optimization
and financial modeling, where these functions play pivotal roles in
establishing global objectives and managing risk and return [89, 90].

Drawing on the utility of characteristic graphs in capturing the structures of
data and functions, as well as input statistics and correlations, and the
general result in Theorem 1, our next result, Proposition 3, demonstrates a
new upper bound on the achievable sum rate for computing _multi-linear
functions_ within the framework of multi-server and multi-function distributed
computing via exploiting conditional graph entropies.

######  Proposition 3.

(Achievable sum-rate using the characteristic graph approach for multi-linear
functions and i.i.d. subfunctions over $\mathbb{F}_{2}$.) In multi-server
multi-function distributed computing setting, denoted by
$\mathcal{T}(N,K,K_{c},M,N_{r})$, under the cyclic placement of datasets,
where $\frac{K}{N}=\Delta\in\mathbb{Z}^{+}$, and for computing the multi-
linear function ($K_{c}=1$), given as in (11), requested by the user, and
given i.i.d. uniformly distributed subfunctions $W_{k}\sim{\rm
Bern}(\epsilon)$, $k\in[K]$, for some $\epsilon\in(0,1)$, the characteristic
graph-based compression yields the following bound on the achievable
communication rate:

$\displaystyle R_{\rm
ach}\leq\frac{1-(\epsilon_{M})^{N^{*}}}{1-\epsilon_{M}}\cdot
h(\epsilon_{M})+(\epsilon_{M})^{N^{*}}\cdot\,1_{\Delta_{N}>0}\cdot\,h\big{(}\epsilon_{\xi_{N}}\big{)}\
,$ (12)

where

  * •

$\epsilon_{M}=\epsilon^{M}$ denotes the probability that the product of $M$
subfunctions, with $W_{k}\sim{\rm Bern}(\epsilon)$ being i.i.d. across
$k\in[K]$, taking the value one, i.e.,
$\mathbb{P}\Big{(}\prod\nolimits_{k\in\mathcal{S}\,:\,|\mathcal{S}|=M}W_{k}\Big{)}=\epsilon_{M}$,

  * •

the variable $N^{*}=\left\lfloor\frac{N}{N-N_{r}+1}\right\rfloor$ denotes the
minimum number of servers needed to compute $f(W_{\mathcal{K}})$, given as in
(11), where each of these servers computes a disjoint product of $M$
subfunctions, and

  * •

the variable $\Delta_{N}=N-N^{*}\cdot(N-N_{r}+1)$ represents whether an
additional server is needed to aid the computation, and if $\Delta_{N}\geq 1$,
then $\xi_{N}$ denotes the number of subfunctions to be computed by the
additional server, and similarly as above,
$\mathbb{P}\Big{(}\prod\nolimits_{k\in\mathcal{S}\,:\,|\mathcal{S}|={\xi_{N}}}W_{k}\Big{)}=\epsilon_{\xi_{N}}$.

###### Proof.

See Appendix B-D. ∎

We will next detail two numerical examples (Subsections IV-A-IV-B) to showcase
the achievable gains in the total communication cost for Proposition 2 and
Proposition 3, respectively.

##  IV Numerical Evaluations to Demonstrate the Achievable Gains

Given $\mathcal{T}(N,K,K_{c},M,N_{r})$, to gain insight into our analytical
results and demonstrate the savings in the total communication cost, we
provide some numerical examples. To demonstrate Proposition 2, in Subsection
IV-A, we focus on computing linearly separable functions, and in Subsection
IV-B (cf. Proposition 3), we focus on multi-linear functions, respectively.

To that end, to characterize the performance of our characteristic graph-based
approach for linearly separable functions, we denote by $\eta_{lin}$ the gain
of the sum-rate for the characteristic graph-based approach given in (9) over
the sum-rate of the distributed scheme of Wan et al. in [40], given in (8),
and by $\eta_{SW}$ the gain of the sum-rate in (9) over the sum-rate of the
fully distributed approach of Slepian-Wolf [61]. To capture general
statistics, i.e., dataset skewness and correlations, and make a fair
comparison, we adapt the transmission model of Wan et al. in [40] via
modifying the i.i.d. dataset assumption.

We next study an example scenario (Subsection IV-A) for computing a class of
linearly separable functions (4) over $\mathbb{F}_{2}$, where each of the
demanded functions takes the form
$f_{j}(W_{\mathcal{K}})=\sum\nolimits_{k\in[K]}\gamma_{jk}W_{k}\mod 2$,
$j\in[K_{c}]$, under a specific correlation model across subfunctions. More
specifically, when the subfunctions $W_{k}\sim{\rm Bern}(\epsilon)$ are
identically distributed and correlated across $k\in[K]$, and
$\Delta\in\mathbb{Z}^{+}$, we model the correlation across datasets (a)
exploiting the joint PMF model in [91, Theorem 1] and (b) for a joint PMF
described in Table II. Furthermore, we assume for $K_{c}>1$ that
${\bf\Gamma}=\\{\gamma_{jk}\\}\in\mathbb{F}_{2}^{K_{c}\times K}$ is full rank.
For the proposed setting, we next demonstrate the achievable gains
$\eta_{lin}$ of our proposed technique versus $\epsilon$ for computing (4), as
a function of skew, $\epsilon$, and correlation, $\rho$, of datasets,
$K_{c}\in[N_{r}]<K$, and other system parameters, and showcase the results via
Figures 1, 3, 4, and 5.

###  IV-A Example case: Distributed computing of linearly separable functions
over $\mathbb{F}_{2}$

We consider the computation of linearly separable functions given in (4) for
general topologies, with general $N$, $K$, $M$, $N_{r}$, $K_{c}$, over
$\mathbb{F}_{2}$, with an identical skew parameter $\epsilon\in[0,1]$ for each
subfunction, where $W_{k}\sim$Bern($\epsilon$), $k\in[K]$, using cyclic
placement as in (1), and incorporating the correlation between the
subfunctions, with the correlation coefficient denoted by $\rho$. We consider
three scenarios, as described next:

##### Scenario I. The number of demanded functions is $K_{c}=1$, where the
subfunctions could be uncorrelated or correlated.

This scenario is similar to the setting in [40] whereas different from [40]
which is valid over a field of characteristic $q>3$, we consider
$\mathbb{F}_{2}$, and in the case of correlations, i.e., when $\rho>0$, we
capture the correlations across the transmissions (evaluated from subfunctions
of datasets) from distributed servers, as detailed earlier in Section III. We
first assume that the subfunctions are not correlated, i.e., $\rho=0$, and
evaluate $\eta_{lin}$ for $f(W_{\mathcal{K}})=\sum\nolimits_{k\in[K]}W_{k}\mod
2$. The parameter of $f(W_{\mathcal{K}})$, i.e., the probability that
$f(W_{\mathcal{K}})$ takes the value $1$ can be computed using the recursive
relation:

$\displaystyle\mathbb{P}\Big{(}\sum\limits_{k\in\mathcal{S}\,:\,|\mathcal{S}|=l\leq
K}W_{k}\mod 2=1\Big{)}$
$\displaystyle=\sum\limits_{k\in\mathcal{S}\,:\,\,|\mathcal{S}|=l\leq K\
,\,k\,{\rm odd}}\mathbb{P}(B(K,\epsilon))=k)$
$\displaystyle=(1-\epsilon_{l-1})\cdot\epsilon+\epsilon_{l-1}\cdot(1-\epsilon)$
$\displaystyle\doteq\,\epsilon_{l}\ ,\quad 1<l\leq K\ ,$ (13)

where $B(K,\epsilon)$ is the binomial PMF, and $\epsilon_{l}$ is the
probability that the modulo $2$ sum of any $1<l\leq K$ subfunctions taking the
value one, with $W_{k}\sim{\rm Bern}(\epsilon)$ being i.i.d. across
$k\in\mathcal{S}$, with the convention $\epsilon_{1}=\epsilon$.

Given $N_{r}$, we denote by
$N^{*}=\left\lfloor\frac{N}{N-N_{r}+1}\right\rfloor$ the minimum number of
servers, corresponding to the subset $\mathcal{N}^{*}\subseteq\Omega$, needed
to compute $f(W_{\mathcal{K}})$, where each server, with a cache size of $M$,
computes a sum of $M$ subfunctions, where across these $N^{*}$ servers, the
sets of subfunctions are disjoint. Hence,
$\mathbb{P}\Big{(}\sum\nolimits_{k\in\mathcal{S}\,:\,|\mathcal{S}|=M}W_{k}\Big{)}=\epsilon_{M}$.
Furthermore, the variable $\Delta_{N}=N-N^{*}\cdot(N-N_{r}+1)$ represents
whether additional servers in addition to $N^{*}$ servers are needed to aid
the computation, and if $\Delta_{N}\geq 1$, then
$\Delta\cdot\Delta_{N}\doteq\xi_{N}$ denotes the number of subfunctions to be
computed by the set of additional servers, namely $\mathcal{I}^{*}\in\Omega$,
and similarly as above,
$\mathbb{P}\Big{(}\sum\nolimits_{k\in\mathcal{S}\,:\,|\mathcal{S}|={\xi_{N}}}W_{k}\Big{)}=\epsilon_{\xi_{N}}$,
which is obtained evaluating $\epsilon_{l}$ at $l=\xi_{N}$.

Adapting (8) for $\mathbb{F}_{2}$, we obtain the total communication cost
$R_{ach}(lin)$ for computing the linearly separable function
$f(W_{\mathcal{K}})=\sum\nolimits_{k\in[K]}W_{k}\mod 2$ as

$\displaystyle
R_{ach}(lin)=\sum\limits_{i=1}^{N_{r}}h\Big{(}\sum\limits_{k\in\mathcal{Z}_{i}}W_{k}\Big{)}=N_{r}\cdot
h(\epsilon_{M})\ .$ (14)

Using Proposition 2 and (IV-A), we derive the sum rate for distributed
lossless computing of $f(W_{\mathcal{K}})$ as

$\displaystyle\sum\limits_{i\in\Omega}R_{i}\leq N^{*}\cdot
h(\epsilon_{M})+1_{\Delta_{N}>0}\cdot h(\epsilon_{\xi_{N}})\ ,$ (15)

where the indicator function $1_{\Delta_{N}>0}$ captures the rate contribution
from the additional server, if any. Using (15), the gain $\eta_{lin}$ over the
linearly separable solution of [40] is presented as:

$\displaystyle\eta_{lin}=\frac{N_{r}\cdot h(\epsilon_{M})}{N^{*}\cdot
h(\epsilon_{M})+1_{\Delta_{N}>0}\cdot h(\epsilon_{\xi_{N}})}\ ,$ (16)

where $h(\epsilon_{\xi_{N}})$ represents the rate needed from the set of
additional servers $\mathcal{I}^{*}\in\Omega$, aiding the computation through
communicating the sum of the remaining subfunctions in the set
$\mathcal{C}\subseteq\mathcal{Z}_{\mathcal{I}^{*}}$, where the summation for
these remaining functions in
$\mathcal{C}\subseteq\mathcal{Z}_{\mathcal{I}^{*}}$ is denoted as
$\sum_{k\in\mathcal{C}\subseteq\mathcal{Z}_{\mathcal{I}^{*}}\ :\
k\notin\bigcup_{i\in\mathcal{N}^{*}}\mathcal{Z}_{i}\
,\,\,|\mathcal{C}|=\xi_{N}}W_{k}$, that cannot be captured by the set
$\mathcal{N}^{*}$.

Given $K_{c}=1$ for the given modulo $2$ sum function, we next incorporate the
correlation model in [91], for each $W_{k}$, identically distributed with
$W_{k}\sim{\rm Bern}(\epsilon)$, and correlation $\rho$ across any two
subfunctions. The formulation in [91] yields the following PMF for
$f(W_{\mathcal{K}})$:

$\displaystyle\mathbb{P}(f(W_{K})=y)$
$\displaystyle=\binom{K}{y}\epsilon^{y}(1-\epsilon)^{K-y}(1-\rho)\cdot 1_{y\in
A_{1}}$
$\displaystyle+\epsilon^{\frac{y}{K}}(1-\epsilon)^{\frac{K-y}{K}}\rho\cdot
1_{y\in A_{2}}\ ,\,y\in\\{0,\cdots,K\\}\ ,$ (17)

where $1_{y\in A_{1}}$ and $1_{y\in A_{2}}$ are indicator functions, where
${A_{1}}=\\{0,1,\cdots,K\\}$ and ${A_{2}}=\\{0,K\\}$.

We depict the behavior of our gain, $\eta_{lin}$, using the same topology
$\mathcal{T}(N,K,K_{c},M,N_{r})$ as in [40], with different system parameters
$(N,K,M,N_{r})$, under $\rho=0$ in Figure 1-(Left). As we increase both $N$
and $K$, along with the number of active servers, $N_{r}$, the gain,
$\eta_{lin}$, of the characteristic graph approach increases. This stems from
the characteristic graph approach, to compute functions $f(W_{\mathcal{K}})$
of $W_{\mathcal{K}}$ using $N^{*}$ servers. From Figure 1-(Right), it is
evident that by capturing correlations between the subfunctions, hence across
the servers’ caches, $\eta_{lin}$ grows more rapidly until it reaches the
maximum of (16), corresponding to $\eta_{lin}=\frac{N_{r}}{N^{*}}=10$,
attributed to full correlation (see, Figure 1-(Right)).

Figure 1: The gain $\eta_{lin}$ of the characteristic graph approach for
$K_{c}=1$, in Subsection IV-A (Scenario I). (Left) $\rho=0$ for various
distributed topologies. (Right) The correlation model given as (IV-A) for
$\mathcal{T}(30,30,1,11,20)$ with different $\epsilon$ values.

What we can also see is that for $\rho=0$, the gain rises with the increase of
$\epsilon$ and linearly grows with $\frac{N_{r}}{N^{*}}$. As $\rho$ increases
reaching its maximum at $\rho=1$, the gain is maximized, yielding the minimum
communication cost that can be achieved with our technique. Here, the gain
$\eta_{lin}$ is dictated by the topology and is given as
$\eta_{lin}=\frac{N_{r}}{N^{*}}$. This linear relation shows that this
specific topology can provide a very substantial reduction in the total
communication cost, as $\rho$ goes to $1$, over the state-of-the-art [40], as
shown in Figure 1-(Right) via the purple (solid) curve. Furthermore, one can
draw a comparison between the characteristic graph approach and the approach
in [61]. Here, we represent the gain as $\eta_{SW}$. It is noteworthy that the
sum rate of all servers using the coding approach of Slepian-Wolf [61] is
$R_{ach}(SW)=H(W_{\mathcal{K}})$. With $\rho=0$, this expression simplifies to
$R_{ach}(SW)=K\cdot H(W_{k})$, resulting again in a substantial reduction in
the communication cost as we see from $R_{ach}(lin)$ in (14) for the same
topology of the purple (solid) curve as shown in Figure 1-(Right).

##### Scenario II. The number of demanded functions is $K_{c}=2$, where the
subfunctions could be uncorrelated or correlated.

To gain insights into the behavior of $\eta_{lin}$, we consider an example
distributed computation model with $K=N=3$, $N_{r}=2$, where the subfunctions
$W_{1},\,W_{2},\,W_{3}$ are assigned to $X_{1}$, $X_{2}$ and $X_{3}$ in a
cyclic manner, with $h(W_{k})=\epsilon$, $k\in[3]$, and $K_{c}=2$ with
$f_{1}(W_{\mathcal{K}})=W_{2}$, and $f_{2}(W_{\mathcal{K}})=W_{2}+W_{3}$.

Given $N_{r}=2$, using the characteristic graph approach for individual
servers, an achievable compression scheme, for a given ordering $i$ and $j$ of
server transmissions, relies on first compressing of the characteristic graph
$G_{X_{i}}$ constructed by server $i\in\Omega$ that has no side information,
and then the conditional rate needed for compressing the colors of $G_{X_{j}}$
for any other server $j\in\Omega\backslash i$ via incorporating the side
information $Z_{i}=g_{i}(X_{i})$ obtained from server $i\in\Omega$. Thus,
contrasting the total communication cost associated with the possible
orderings, the minimum total communication cost $R_{ach}(G)$ can be
determined666We can generalize (18) to $N_{r}>2$, where, for a given ordering
of server transmissions, any consecutive server that transmits sees all
previous transmissions as side information and the best ordering that has the
minimum total communication cost, i.e., $R_{ach}(G)$.. The achievable sum rate
here takes the form

$\displaystyle
R_{ach}(G)=\min\\{H_{G_{X_{1}}}(X_{1})+H_{G_{X_{2}}}(X_{2}\,|\,Z_{1}),\quad
H_{G_{X_{2}}}(X_{2})+H_{G_{X_{1}}}(X_{1}\,|\,Z_{2})\\}\ .$ (18)

Figure 2: Colorings of graphs in Subsection IV-A (Scenario II). (Top Left-
Right) Characteristic graphs $G_{X_{1}}$ and $G_{X_{2}}$, respectively.
(Bottom Left-Right) The minimum conditional entropy colorings of $G_{X_{1}}$
given $c_{G_{X_{2}}}$, and $G_{X_{2}}$ given $c_{G_{X_{1}}}$, respectively.

Focusing on the characteristic graph approach, we illustrate how each server
builds its union characteristic graph for simultaneously computing $f_{1}$ and
$f_{2}$ according to (36) (as detailed in Appendix A-B1), in Figure 2. In
(18), the first term corresponds to $G_{X_{1}}=(V_{X_{1}},E_{X_{1}})$ where
$V_{X_{1}}=\\{0,1\\}^{2}$ is built using the support of $W_{1}$ and $W_{2}$,
and the edges $E_{X_{1}}$ are built based on the rule that
$(x_{1}^{1},x_{1}^{2})\in E_{X_{1}}$ if $F(x_{1}^{1},x_{2})\neq
F(x_{1}^{2},x_{2})$ for some $x_{2}\in V_{X_{2}}$, where, as we see here,
requires $2$ colors. Similarly, server $2$ constructs
$G_{X_{2}}=(V_{X_{2}},E_{X_{2}})$ given $Z_{1}$, where
$V_{X_{2}}=\\{0,1\\}^{2}$ using the support of $W_{2}$ and $W_{3}$, and where
$Z_{1}$ determines $f_{1}=W_{2}$, and hence, to compute $f_{2}=W_{2}+W_{3}$
given $f_{1}=W_{2}$, any two vertices taking values777Here,
$x_{2}^{1}=(w_{2}^{1},w_{3}^{1})$ and $x_{2}^{2}=(w_{2}^{2},w_{3}^{2})$
represent two different realizations of the pair of subfunctions $W_{2}$ and
$W_{3}$. $x_{2}^{1}=(w_{2}^{1},w_{3}^{1})\in V_{X_{2}}$ and
$x_{2}^{2}=(w_{2}^{2},w_{3}^{2})\in V_{X_{2}}$ are connected if $w_{3}^{1}\neq
w_{3}^{2}$. Hence, we require $2$ distinct colors for $G_{X_{2}}$. As a
result, the first term yields a sum rate of
$h(\epsilon)+h(\epsilon)=2h(\epsilon)$. Similarly, the second term of (18)
captures the impact of $G_{X_{2}}=(V_{X_{2}},E_{X_{2}})$, where server $2$
builds $G_{X_{2}}$ using the support of $W_{2}$ and $W_{3}$, and $G_{X_{2}}$
is a complete graph to distinguish all possible binary pairs to compute
$f_{1}$ and $f_{2}$, requiring $4$ different colors. Given $Z_{2}$, both
$f_{1}$ and $f_{2}$ are deterministic. Hence, given $Z_{2}$, $G_{X_{1}}$ has
no edges, which means that $H_{G_{X_{1}}}(X_{1}\,|\,Z_{2})=0$. As a result,
the ordering of server transmission given by the second term of (18) yields
the same sum rate of $2h(\epsilon)+0=2h(\epsilon)$. For this setting, the
minimum required rate is $R_{ach}(G)=2h(\epsilon)$, and the configuration
captured by the second term provides a lower recovery threshold of $N_{r}=1$
versus $N_{r}=2$ for the configurations of server transmissions given by the
first term (18). The different $N_{r}$ achieved by these two configurations is
also captured by Figure 2.

Alternatively, in the linearly separable approach [40], $N_{r}$ servers
transmit the requested function of the datasets stored in their caches. For
distributed computing of $f_{1}$ and $f_{2}$, servers $1$ and $2$ transmit at
rate $H(W_{2})=h(\epsilon)$, for computing $f_{1}$, and at rate
$H(W_{2}+W_{3})$, for function $f_{2}$. As a result, the achievable
communication cost is given by $R_{ach}(lin)=h(\epsilon)+h(W_{2}+W_{3})$.
Here, for a fair comparison, we update the model studied in [40] to capture
the correlation within each server without accounting for the correlation
across the servers.

Under this setting, for $\rho=0$, we see that the gain $\eta_{lin}$ of the
characteristic graph approach over the linearly separable solution of [40] for
computing $f_{1}$ and $f_{2}$ as a function of $\epsilon\in[0,1]$ takes the
form

$\displaystyle\eta_{lin}(\epsilon)$
$\displaystyle=\frac{h(\epsilon)+h(2\epsilon(1-\epsilon))}{2h(\epsilon)}\begin{cases}=1&,\,\,\epsilon=\\{\frac{1}{2}\\}\
,\\\ >1&,\,\,\epsilon\in[0,1]\backslash\\{\frac{1}{2}\\}\ ,\end{cases}$ (19)

where $\eta_{lin}(\epsilon)>1$ for $\epsilon\neq\frac{1}{2}$ follows from the
concavity of $h(\cdot)$ that yields the inequality
$h(2\epsilon(1-\epsilon))\geq h(\epsilon)$. Furthermore, $\eta_{lin}$
approaches $1.5$ as $\epsilon\to\\{0,1\\}$ (see Figure 3).

Figure 3: $\eta_{lin}$ in (19) versus $\epsilon$, for distributed computing of $f_{1}=W_{2}$ and $f_{2}=W_{2}+W_{3}$, where $K_{c}=2$, $N_{r}=2$, with $\rho=0$, in Subsection IV-A (Scenario II). $P_{W_{2},W_{3}}(W_{2},W_{3})$ | $W_{2}=0$ | $W_{2}=1$
---|---|---
$W_{3}=0$ | $(1-\epsilon)(1-p^{\prime})$ | $\epsilon p$
$W_{3}=1$ | $\epsilon p$ | $\epsilon(1-p)$
TABLE II: Joint PMF $P_{W_{2},W_{3}}$ of $W_{2}$ and $W_{3}$ with a crossover
parameter $p$, in Subsection IV-A (Scenario II).

We next examine the setting where the correlation coefficient $\rho$ is
nonzero, using the joint PMF $P_{W_{2},W_{3}}$, as depicted in Table II, of
the required subfunctions ($W_{2}$ and $W_{3}$) in computing $f_{1}$ and
$f_{2}$. This PMF describes the joint PMF corresponding to a binary non-
symmetric channel model, where the correlation coefficient between $W_{2}$ and
$W_{3}$ is $\rho=\frac{1-p}{1-\epsilon}$, and where $p^{\prime}=\frac{\epsilon
p}{1-\epsilon}$. Thus our gain here compared to the linearly separable
encoding and decoding approach of [40] is given as

$\displaystyle\eta_{lin}=\frac{H(W_{2})+H(W_{2}+W_{3})}{H(W_{2},W_{3})}=\frac{h(\epsilon)+h(2\epsilon
p)}{h(\epsilon)+(1-\epsilon)h\big{(}\frac{\epsilon
p}{1-\epsilon}\big{)}+\epsilon h(p)}\ .$ (20)

We consider now the correlation model in Table II, where coefficient $\rho$
rises in $\epsilon$ for a fixed $p$. In Figure 4-(Left), we illustrate the
behavior of $\eta_{lin}$, given by (20), for computing $f_{1}$ and $f_{2}$ for
$N_{r}=2$ as a function of $p$ and $\epsilon$, where for this setting, the
correlation coefficient $\rho$ is a decreasing function of $p$ and an
increasing function of $\epsilon$. We observe from (20) that the gain
$\eta_{lin}$ satisfies $\eta_{lin}\geq 1$ for all $\epsilon\in[0,1]$, which
monotonically increases in $p$ — and hence monotonically decreases in $\rho$
due to the relation $\rho=\frac{1-p}{1-\epsilon}$ — as a function of the
deviation of $\epsilon$ from $1/2$. For $\epsilon\in(0.5,1]$, $\eta_{lin}$
increases in $\epsilon$. For example, for $p=0.1$ then $\eta_{lin}(1)=1.28$,
as depicted by the green (solid) curve. Similarly, given $\epsilon\in[0,0.5)$,
decreasing $\epsilon$ results in $\eta_{lin}$ to exhibit a rising trend, e.g.,
for $p=0.9$ then $\eta_{lin}(0)=1.36$, as shown by the red (dash-dotted)
curve. As $p$ approaches one, $\eta_{lin}$ goes to $1.5$ as $\epsilon$ tends
to zero, which can be derived from (20). We here note that the gains are
generally smaller than in the previous set of comparisons as shown in Figure
3.

More generally, given a user request, consisting of $K_{c}=2$ linearly
separable functions (i.e., satisfying (4)), and after considering (20) beyond
$N_{r}=2$, we see that $\eta_{lin}$ is at most $N_{r}$ as $\rho$ approaches
one. We next use the joint PMF model used in obtaining (IV-A), where we
observe that
$f_{2}\sim((1-\epsilon)^{2}(1-\rho)+(1-\epsilon)\rho,\,2\epsilon(1-\epsilon)(1-\rho),\,\epsilon^{2}(1-\rho)+\epsilon\rho)$,
to see that the gain takes the form

$\displaystyle\eta_{lin}=\frac{h(\epsilon)+H(f_{2})}{h(\epsilon)+(1-\epsilon)h(\zeta_{1})+\epsilon
h(\zeta_{2})}\ ,$ (21)

where $\zeta_{1}=(1-\epsilon)(1-\rho)+\rho$, and
$\zeta_{2}=(1-\epsilon)(1-\rho)$. For this model, we illustrate $\eta_{lin}$
versus $\epsilon$ in Figure 4-(Right) for different $\rho$ values. Evaluating
(21), the peak achievable gain is attained when $\rho=1$ at
$f_{2}\sim((1-\epsilon),\,0,\,\epsilon)$, yielding
$H(W_{2}+W_{3})=h(\epsilon)$ and $H(W_{3}\,|\,W_{2})=(1-\epsilon)h(\rho)=0$,
and hence, a gain $\eta_{lin}=N_{r}=2$, as shown by the purple (solid) curve.
On the other hand, for $\rho=0$, we observe that
$f_{2}\sim((1-\epsilon)^{2},\,2\epsilon(1-\epsilon),\,\epsilon^{2})$, yielding
$H(W_{2}+W_{3})=h((1-\epsilon)^{2},\,2\epsilon(1-\epsilon),\,\epsilon^{2})=h(2\epsilon(1-\epsilon))+((1-\epsilon)^{2}+\epsilon^{2})h\Big{(}\frac{\epsilon^{2}}{\epsilon^{2}+(1-\epsilon)^{2}}\Big{)}$
and $H(W_{3}\,|\,W_{2})=(1-\epsilon)h(\epsilon)+\epsilon
h(\epsilon)=h(\epsilon)$, and hence, it can be shown that the gain is lower
bounded as $\eta_{lin}\geq 1.25$.

Figure 4: $\eta_{lin}$ versus $\epsilon$, for distributed computing of
$f_{1}=W_{2}$ and $f_{2}=W_{2}+W_{3}$, where $K_{c}=2$, $N_{r}=2$, in
Subsection IV-A, using different joint PMF models for $P_{W_{2},W_{3}}$
(Scenario II). (Left) $\eta_{lin}$ in (20) for the joint PMF in Table II, for
different values of $p$. (Right) $\eta_{lin}$ for the joint PMF in (IV-A), for
different values of $\rho$ .

##### Scenario III. The number of demanded functions is $K_{c}\in[N_{r}]$, and
the number of datasets is equal to the number of servers, i.e., $K=N$, where
the subfunctions are uncorrelated.

We now provide an achievable rate comparison between the approach in [40], and
our graph-based approach, as summarized by our Proposition 1 that generalizes
the result in [40, Theorem 2] to finite fields with characteristics $q\geq 2$,
for the case of $\rho=0$.

Here, to capture dataset skewness and make a fair comparison, we adapt the
transmission model of Wan et al. in [40] via modifying the i.i.d. dataset
assumption and taking into account the skewness incurred within each server in
determining the local computations
$\sum\nolimits_{k\in\mathcal{S}\,:\,|\mathcal{S}|=M}W_{k}$ at each server.

For the linearly separable model in (4) adapted to account for our setting,
exploiting the summation $\sum_{k\in\mathcal{Z}_{i}}W_{k}$, and $\epsilon_{M}$
given in (15), the communication cost for a general number of $K_{c}$ with
$\rho=0$ is expressed as:

$\displaystyle R_{ach}(lin)=N_{r}\cdot h(\epsilon_{M})\ .$ (22)

In (22), as $\epsilon$ approaches $0$ or $1$, then $h(\epsilon_{M})\to 0$.
Subsequently, the achievable communication cost for the characteristic graph
model can be determined as

$\displaystyle R_{ach}(G)=K_{c}\cdot{N^{*}}\cdot h(\epsilon)\ .$ (23)

To understand the behavior of
$\eta_{lin}=\frac{N_{r}}{K_{c}{N^{*}}}\cdot\frac{h(\epsilon_{M})}{h(\epsilon)}$,
knowing that $\frac{N_{r}}{K_{c}N^{*}}$ is a fixed parameter, we need to
examine the dynamic component $\frac{h(\epsilon_{M})}{h(\epsilon)}$.
Exploiting Schur concavity888A real-valued function
$f:\mathbb{R}^{n}\to\mathbb{R}$ is Schur concave if
$f(x_{1},x_{2},\cdots,x_{n})\leq f(y_{1},y_{2},\cdots,y_{n})$ holds whenever
$(x_{1},x_{2},\cdots,x_{n})$ majorizes $(y_{1},y_{2},\cdots,y_{n})$, i.e.,
$\sum_{i=1}^{k}x_{i}\geq\sum_{i=1}^{k}y_{i}$, for all $k\in[n]$ [92]. for the
binary entropy function, which tells us that
$h(\mathbb{E}[X])\geq\mathbb{E}[h(X)]$, we can see that as $\epsilon$
approaches $0$ or $1$, then

$\displaystyle\lim_{\epsilon\to\\{0,\,1\\}}\frac{h(\epsilon_{M})}{h(\epsilon)}\leq
M\ ,\quad M\in\mathbb{Z}^{+}\ ,$ (24)

where the inequality between the left and right-hand sides becomes loose as a
function of $M$. As a result, as $\epsilon$ approaches $0$ or $1$, then
$\eta_{lin}\approx M\cdot\frac{N_{r}}{K_{c}\cdot{N^{*}}}$, which follows from
exploiting (22), (23) and the achievability of the upper bound in (24). We
illustrate the upper bound on $\eta_{lin}$ in Figure 5, and demonstrate the
$\eta_{lin}$ behavior for $K_{c}$ demanded functions across various topologies
with circular dataset placement, namely for various $K=N$, i.e., when the
amount of circular shift between two consecutive servers is
$\Delta=\frac{K}{N}=1$ and the cache size is $M=N-N_{r}+1$, and for $\rho=0$
and $\epsilon\leq 1/2$. We focus only on plotting $\eta_{lin}$ for
$\epsilon\leq 1/2$, accounting for the symmetry of the entropy function.
Therefore, we only plot for $\epsilon\leq 1/2$. The multiplicative coefficient
$\frac{N_{r}}{K_{c}N^{*}}$ of $\eta_{lin}$ determines the growth, which is
depicted by the curves.

Figure 5: $\eta_{lin}$ in a logarithmic scale versus $\epsilon$ for $K_{c}$
demanded functions for various values of $K_{c}$, with $\rho=0$ for different
topologies, as detailed in Subsection IV-A (Scenario III).

Thus we see that for a given topology $\mathcal{T}(N,K,K_{c},M,N_{r})$ with
$K_{c}$ demanded functions, for $\rho=0$, using (24), we see that $\eta_{lin}$
exponentially grows with term $1-\epsilon$ for $\epsilon\in[0,1/2]$999Here we
note that the behavior of $\eta_{lin}$ is symmetric around $\epsilon=1/2$.,
and very substantial reduction in the total communication cost is possible as
$\epsilon$ approaches $\\{0,1\\}$ as shown in Figure 5 by the blue (solid)
curve. The gain over [40, Theorem 2], $\eta_{lin}$, for a given topology,
changes proportionally to $\frac{N_{r}}{K_{c}N^{*}}$. The gain over [61],
$\eta_{SW}$, for $\rho=0$ linearly scales101010Incorporating the dataset skew
to Proposition 1 ([40, Theorem 2]), $R_{ach}(lin)$ is simplified to (22),
which from (24) can linearly grow in $M=N-N_{r}+1$ at high skew, explaining
the inferior performance of Proposition 1 over [61] as a function of the skew.
with $\frac{K}{K_{c}N^{*}}$. For instance, the gain for the blue (solid) curve
in Figure 5 is $\eta_{SW}=10$.

In general, other functions in $\mathbb{F}_{2}$, such as bitwise $AND$ and the
multi-linear function (see e.g., Proposition 3), are more skewed and have
lower entropies than linearly separable functions, and hence are easier to
compute. Therefore, the cost given in (23) can serve as an upper bound for the
communication costs of those more skewed functions in $\mathbb{F}_{2}$.

We have here provided insights into the achievable gains in communication cost
for several scenarios. We leave the study of $\eta_{lin}$ for more general
topologies $\mathcal{T}(N,K,K_{c},M,N_{r})$ and correlation models beyond
(IV-A) devised for linearly separable functions, and beyond the joint PMF
model in Table II, as future work.

Proposition 3 illustrates the power of the characteristic graph approach in
decreasing the communication cost for distributed computing of multi-linear
functions, given as in (11), compared to recovering the local computations
$\prod_{k\in\mathcal{S}\,:\,|\mathcal{S}|=M}W_{k}$ using [61]. We denote by
$\eta_{SW}$ the gain of the sum-rate for the graph entropy-based approach
given in (12) — using the conditional entropy-based sum-rate expression in
(B-D) — over the sum-rate of the fully distributed scheme of Slepian-Wolf [61]
for computing (11). For the proposed setting, we next showcase the achievable
gains $\eta_{SW}$ of Proposition 3 via an example and showcase the results via
Figure 6.

###  IV-B Distributed computation of $K$-multi-linear functions over
$\mathbb{F}_{2}$

We study the behaviors of $\eta_{SW}$ versus the skewness parameter $\epsilon$
for computing the multi-linear function given in (11) for i.i.d. uniform
$W_{k}\sim{\rm Bern}(\epsilon)$, $\epsilon\in[0,1/2]$ across $k\in[K]$, and
for a given $\mathcal{T}(N,K,K_{c},M,N_{r})$ with parameters $N$, $K$,
$M=\Delta(N-N_{r}+1)$, such that $N_{r}=N-1$, $K_{c}=1$, $\rho=0$, and the
number of replicates per dataset is $\frac{MN}{K}=2$. We use Proposition 3 to
determine the sum-rate upper bound, and illustrate the gains
$10\log_{10}(\eta_{SW})$ in decibels versus $\epsilon$ in Figure 6.

Figure 6: Gain $10\log_{10}(\eta_{SW})$ versus $\epsilon$ for computing (11),
where $K_{c}=1$, $\rho=0$, $N_{r}=N-1$. (Left) The set of parameters $N$, $K$,
and $M$ are indicated for each configuration. (Right) $10\log_{10}(\eta_{SW})$
versus $\epsilon$ to observe the effect of $N$ for a fixed total cache size
$MN$ and fixed $K$.

From the numerical results in Figure 6 (Left), we observe that the sum-rate
gain of the graph entropy-based approach versus the fully distributed approach
of [61], $\eta_{SW}$, could reach up to more than $10$-fold gain in
compression rate for uniform and up to $10^{6}$-fold for skewed data. The
results on $\eta_{SW}$ showcase that our proposed scheme can guarantee an
exponential rate reduction over [61] as a function of decreasing $\epsilon$.
Furthermore, the sum-rate gains scale linearly with the cache size $M$, which
scales with $K$ given $N_{r}=N-1$. Note that $\eta_{SW}$ diminishes with
increasing $N$ when $M$ and $\Delta$ are kept fixed. In Figure 6 (Right), for
$M\ll K$, a fixed total cache size $MN$, and hence fixed $K$, the gain
$\eta_{SW}$ for large $N$ and small $M$ is higher versus small $N$ and large
$M$, demonstrating the power of the graph-based approach as the topology
becomes more and more distributed.

##  V Conclusion

In this paper, we devised a distributed computation framework for general
function classes in multi-server, multi-function, single-user topologies.
Specifically, we analyzed the upper bounds for the communication cost for
computing in such topologies, exploiting Körner’s characteristic graph
entropy, by incorporating the structures in the dataset and functions, as well
as the dataset correlations. To showcase the achievable gains of our
framework, and perceive the roles of dataset statistics, correlations, and
function classes, we performed several experiments under cyclic dataset
placement over a field of characteristic two. Our numerical evaluations for
distributed computing of linearly separable functions, as demonstrated in
Subsection IV-A via three scenarios, indicate that by incorporating dataset
correlations and skew, it is possible to achieve a very substantial reduction
in the total communication cost over the state-of-the-art. Similarly, for
distributed computing of multi-linear functions, in Subsection IV-B, we
demonstrate a very substantial reduction in the total communication cost
versus the state-of-the-art. Our main results (Theorem 1 and Propositions 1,
2, and 3) and observations through the examples help us gain insights into
reducing the communication cost of distributed computation by taking into
account the structures of datasets (skew and correlations) and functions
(characteristic graphs).

Potential directions include providing a tighter achievability result for
Theorem 1 and devising a converse bound on the sum-rate. They involve
conducting experiments under the scheme of the coded scheme of Maddah-Ali and
Niesen detailed in [84] in order to capture the finer-grained granularity of
placement that can help tighten the achievable rates. They also involve,
beyond the special cases detailed in Propositions 1, 2, and 3, exploring the
achievable gains for a broader set of distributed computation scenarios, e.g.,
over-the-air computing, cluster computing, coded computing, distributed
gradient descent, or more generally, distributed optimization and learning,
and goal-oriented and semantic communication frameworks, that can be
reinforced by compression by capturing the skewness, correlations, and
placement of datasets, the structures of functions, and topology.

## Acknowledgments

The authors thank Prof. Kai Wan at the Huazhong University of Science and
Technology, Wuhan, China for interesting discussions.

##  Appendix A Technical Preliminary

Here, we detail the notion of characteristic graphs and their entropy in the
context of source compression. We recall that the below proofs use the
notation given in Section I-E.

###  A-A Distributed source compression, and communication cost

Given statistically dependent, finite-alphabet, i.i.d. random sequences ${\bf
X}_{1},\,{\bf X}_{2},\dots,{\bf X}_{N}$ where ${\bf
X}_{i}\in\mathbb{F}_{q}^{|\mathcal{Z}_{i}|\times n}$ for $i\in\Omega$, the
Slepian-Wolf theorem gives a theoretical lower bound for the lossless coding
rate of distributed servers, in the limit as $n$ goes to infinity. Denoting by
$R_{i}$ the encoding rate of server $i\in\Omega$, the sum-rate (or
communication cost) for distributed source compression is given by

$\displaystyle\sum\limits_{i\in\mathcal{S}}R_{i}\geq
H(X_{\mathcal{S}}\,|\,X_{\mathcal{S}^{c}}),\quad\mathcal{S}\subseteq\Omega\ ,$
(25)

where $\mathcal{S}$ denotes the indices of a subset of servers,
$\mathcal{S}^{c}=\Omega\backslash\mathcal{S}$ its complement, and
$X_{\mathcal{S}}=\\{X_{i},\,i\in\mathcal{S}\\}$.

We recall that in the case of distributed source compression, given by the
coding theorem of Slepian-Wolf [61], the encoder mappings specify the bin
indices for the server sequences ${\bf X}_{i}$. The bin index is such that
every bin of each n-vector ${\bf X}_{i}$ of server $i\in\Omega$ is randomly
drawn under the uniform distribution across the set
$\\{0,1,\dots,2^{nR_{i}}-1\\}$ of $2^{nR_{i}}$ bins. Transmission of server
$i\in\Omega$ is $e_{X_{i}}({\bf X}_{i})$, where $e_{X_{i}}:{\bf
X}_{i}\to\\{0,1,\dots,2^{nR_{i}}-1\\}$ is the encoding function of
$i\in\Omega$ onto bins. The total number of symbols in $e_{X_{i}}({\bf
X}_{i})$ is $T_{i}=H(e_{X_{i}}({\bf X}_{i}))$. This value corresponds to the
aggregate number of symbols in the transmitted subfunctions from the server.
Hence, the communication cost (rate) of $i\in\Omega$, for a sufficiently large
$n$, satisfies

$\displaystyle R_{i}=\frac{T_{i}}{L}=\frac{H(e_{X_{i}}({\bf X}_{i}))}{n}\geq
H(X_{i})\ ,$ (26)

where the cost can be further reduced via a more efficient mapping
$e_{X_{i}}({\bf X}_{i})$ if $W_{k}$, $k\in[K]$ are correlated.

###  A-B Characteristic graphs, distributed functional compression, and
communication cost

In this section, we provide a summary of key graph theoretic points devised by
Körner [76], and studied by Alon and Orlitsky [74], Orlitsky and Roche [75] to
understand the fundamental limits of distributed computation.

Let us consider the canonical scenario with two servers, storing $X_{1}$ and
$X_{2}$, respectively. The user requests a bivariate function
$F(X_{1},\,X_{2})$ that could be linearly separable or in general non-linear.
Associated with the source pair $(X_{1},X_{2})$ is a characteristic graph $G$,
as defined by Witsenhausen [93]. We denote by
$G_{X_{1}}=(V_{G_{X_{1}}},\,E_{G_{X_{1}}})$ the characteristic graph server
one builds (server two similarly builds $G_{X_{2}}$) for computing111111We
detail the compression problem for the simultaneous computation of a set of
requested functions in Appendix A-B1. $F(X_{1},\,X_{2})$, determined as a
function of $X_{1}$, $X_{2}$, and $F$, where $V_{G_{X_{1}}}=\mathcal{X}_{1}$
and an edge $(x_{1}^{1},x_{1}^{2})\in E_{G_{X_{1}}}$ if and only if there
exists a $x_{2}^{1}\in\mathcal{X}_{2}$ such that
$P_{X_{1},X_{2}}(x^{1}_{1},x^{1}_{2})\cdot
P_{X_{1},X_{2}}(x^{2}_{1},x^{1}_{2})>0$ and $F(x^{1}_{1},x^{1}_{2})\neq
F(x^{2}_{1},x^{1}_{2})$. Note that the idea of building $G_{X_{1}}$ can also
be generalized to multivariate functions, $F(X_{\Omega})$ where $\Omega=[N]$
for $N>2$ [83]. In this paper, we only consider vertex colorings. A valid
coloring of a graph $G_{X_{1}}$ is such that each vertex of $G_{X_{1}}$ is
assigned a color (code) such that adjacent vertices receive disjoint colors
(codes). Vertices that are not connected can be assigned to the same or
different colors. The chromatic number $\chi(G_{X_{1}})$ of a graph
$G_{X_{1}}$ is the minimum number of colors needed to have a valid coloring of
$G_{X_{1}}$ [77, 78, 80].

######  Definition 1.

(Characteristic graph entropy [76, 74].) Given a random variable $X_{1}$ with
characteristic graph $G_{X_{1}}=(V_{X_{1}},E_{X_{1}})$ for computing function
$f(X_{1},X_{2})$, the entropy of the characteristic graph is expressed as

$\displaystyle H_{G_{X_{1}}}(X_{1})=\min\limits_{X_{1}\in U_{1}\in
S(G_{X_{1}})}I(X_{1};U_{1})\ ,$ (27)

where $S(G_{X_{1}})$ is the set of all MISs of $G_{X_{1}}$, where an MIS is
not a subset of any other independent set, where an independent set of a graph
is a set of its vertices in which no two vertices are adjacent [94]. Notation
$X_{1}\in U_{1}\in S(G_{X_{1}})$ means that the minimization is over all
distributions $P_{U_{1},X_{1}}(u_{1},x_{1})$ such that
$P_{U_{1},X_{1}}(u_{1},x_{1})>0$ implies $x_{1}\in u_{1}$, where $U_{1}$ is an
MIS of $G_{x_{1}}$.

Similarly, the conditional graph entropy for $X_{1}$ with characteristic graph
$G_{X_{1}}$ for computing $f(X_{1},X_{2})$ given $X_{2}$ as side information
is defined in [75] using the notation $U_{1}-X_{1}-X_{2}$ that indicates a
Markov chain:

$\displaystyle H_{G_{X_{1}}}(X_{1}\,|\,X_{2})=\min\limits_{\overset{X_{1}\in
U_{1}\in S(G_{X_{1}})}{U_{1}-X_{1}-X_{2}}}I(X_{1};U_{1}\,|\,X_{2})\ .$ (28)

The Markov chain relation in (28) implies that
$H_{G_{X_{1}}}(X_{1}\,|\,X_{2})\leq H_{G_{X_{1}}}(X_{1})$ [95, Ch. 2]. In
(28), the goal is to determine the equivalence classes $U_{1}$ of
$x_{1}^{i}\in X_{1}$ that have the same function outcome $\forall
x_{2}^{1}\in\mathcal{X}_{2}$ such that
$P_{X_{1},X_{2}}(x_{1}^{i},x_{2}^{1})>0$. We next consider an example to
clarify the distinction between characteristic graph entropy,
$H_{G_{X_{1}}}(X_{1})$ and entropy of a conditional characteristic graph, or
conditional graph entropy, $H_{G_{X_{1}}}(X_{1}\,|\,X_{2})$.

######  Example 1.

(Characteristic graph entropy of ternary random variables [75, Examples 1-2].)
In this example, we first investigate the characteristic graph entropy
$H_{G_{X_{1}}}(X_{1})$ and the conditional graph entropy
$H_{G_{X_{1}}}(X_{1}\,|\,X_{2})$.

  1. 1.

Let $P_{X_{1}}$ be a uniform PMF over the set $\\{1,2,3\\}$. Assume that
$G_{X}$ has only one edge, i.e., $E_{X_{1}}=\\{(1,3)\\}$. Hence, the set of
MISs is given as $S(G_{X_{1}})=\\{\\{1,2\\},\\{2,3\\}\\}$.

To determine the entropy of a characteristic graph, i.e.,
$H_{G_{X_{1}}}(X_{1})$, from (27), our objective is to minimize
$I(X_{1};U_{1})$, which is a convex function of $\mathbb{P}(U_{1}\,|\,X_{1})$.
Hence, $I(X_{1};U_{1})$ is minimized when the conditional distribution of
$\mathbb{P}(U_{1}\,|\,X_{1})$ is selected as
$\mathbb{P}(U_{1}=\\{1,2\\}\,|\,X_{1}=1)=1$,
$\mathbb{P}(U_{1}=\\{2,3\\}\,|\,X_{1}=3)=1$, and
$\mathbb{P}(U_{1}=\\{1,2\\}\,|\,X_{1}=2)=\mathbb{P}(U_{1}=\\{2,3\\}\,|\,X_{1}=2)=1/2$.
As a result of this PMF, we have

$\displaystyle
H_{G_{X_{1}}}(X_{1})=H(U_{1})-H(U_{1}\,|\,X_{1})=1-\frac{1}{3}=\frac{2}{3}\ .$
(29)

  2. 2.

Let $P_{X_{1},X_{2}}$ be a uniform PMF over the set
$\\{(x_{1},x_{2}):\,x_{1},\,x_{2}\in\\{1,2,3\\},\,x_{1}\neq x_{2}\\}$ and
$E_{X_{1}}=\\{(1,3)\\}$. Note that $H(X_{1}|X_{2})=1$ given the joint PMF. To
determine the conditional characteristic graph entropy, i.e.,
$H_{G_{X_{1}}}(X_{1}\,|\,X_{2})$, using (28), our objective is to minimize
$I(X_{1};U_{1}|X_{2})$, which is convex in $\mathbb{P}(U_{1}\,|\,X_{1})$.
Hence, $I(X_{1};U_{1}\,|\,X_{2})$ is minimized when
$\mathbb{P}(U_{1}\,|\,X_{1})$ is selected as
$\mathbb{P}(U_{1}=\\{1,2\\}\,|\,X_{1}=1)=\mathbb{P}(U_{1}=\\{2,3\\}\,|\,X_{1}=3)=1$,
and
$\mathbb{P}(U_{1}=\\{1,2\\}\,|\,X_{1}=2)=\mathbb{P}(U_{1}=\\{2,3\\}\,|\,X_{1}=2)=1/2$.
Hence, we obtain

$\displaystyle H(U_{1}\,|\,X_{2})$
$\displaystyle=\frac{1}{3}H(U_{1}\,|\,X_{1}\in\\{2,3\\})+\frac{1}{3}H(U_{1}\,|\,X_{1}\in\\{1,3\\})+\frac{1}{3}H(U_{1}\,|\,X_{1}\in\\{1,2\\})$
$\displaystyle=\frac{1}{3}h\Big{(}\frac{1}{4}\Big{)}+\frac{1}{3}+\frac{1}{3}h\Big{(}\frac{1}{4}\Big{)}\
,$ (30)

which yields, using $U_{1}-X_{1}-X_{2}$, that

$\displaystyle H_{G_{X_{1}}}(X_{1}\,|\,X_{2})$
$\displaystyle=H(U_{1}\,|\,X_{2})-H(U_{1}\,|\,X_{1},\,X_{2})=H(U_{1}\,|\,X_{2})-H(U_{1}\,|\,X_{1})$
$\displaystyle=\Big{[}\frac{1}{3}h\Big{(}\frac{1}{4}\Big{)}+\frac{1}{3}+\frac{1}{3}h\Big{(}\frac{1}{4}\Big{)}\Big{]}-\frac{1}{3}=\frac{2}{3}h\Big{(}\frac{1}{4}\Big{)}\
.$ (31)

######  Definition 2.

(Chromatic entropy [74].) The chromatic entropy of a graph $G_{X_{1}}$ is
defined as

$\displaystyle
H^{\chi}_{G_{X_{1}}}(X_{1})=\min\limits_{c_{G_{X_{1}}}}H(c_{G_{X_{1}}}(X_{1})),$
(32)

where the minimization is over the set of colorings such that $c_{G_{X_{1}}}$
is a valid coloring of $G_{X_{1}}$.

Let $G^{n}_{{\bf X}_{1}}=(V_{X_{1}}^{n},E_{X_{1}}^{n})$ be the $n$-th OR power
of a graph $G_{X_{1}}$ for the source sequence ${\bf X}_{1}$ to compress
$F({\bf X}_{1},\,{\bf X}_{2})$. In this OR power graph,
$V_{X_{1}}^{n}=\mathcal{X}_{1}^{n}$ and $({\bf x}_{1}^{1},{\bf x}_{1}^{2})\in
E_{X_{1}}^{n}$, where ${\bf
x}_{1}^{1}=(x_{11}^{1},x_{12}^{1},\dots,x_{1n}^{1})$ and similarly for ${\bf
x}_{1}^{2}$, when there exists at least one coordinate $l\in[n]$ such that
$(x_{1l}^{1},x_{1l}^{2})\in E_{X_{1}}$. We denote a coloring of $G^{n}_{{\bf
X}_{1}}$ by $c_{{G^{n}_{{\bf X}_{1}}}}({\bf X}_{1})$. The encoding function at
server one is a mapping from ${\bf X}_{1}$ to the colors $c_{G^{n}_{{\bf
X}_{1}}}({\bf X}_{1})$ of the characteristic graph $G^{n}_{{\bf X}_{1}}$ for
computing $F({\bf X}_{1},\,{\bf X}_{2})$. In other words, $c_{G^{n}_{{\bf
X}_{1}}}({\bf X}_{1})$ specifies the color classes of ${\bf X}_{1}$ such that
each color class forms an independent set that induces the same function
outcome.

Using Definion 2, we can determine the chromatic entropy of graph $G^{n}_{{\bf
X}_{1}}$ as

$\displaystyle H^{\chi}_{G^{n}_{{\bf X}_{1}}}({\bf
X}_{1})=\min\limits_{c_{{G^{n}_{{\bf X}_{1}}}}}H(c_{{G^{n}_{{\bf
X}_{1}}}}({\bf X}_{1}))\ .$ (33)

In [76], Körner has shown the relation between the chromatic and graph
entropies, which we detail next.

######  Theorem 2.

(Chromatic entropy versus graph entropy [76].) The following relation holds
between the characteristic graph entropy and the chromatic entropy of graph
$G^{n}_{{\bf X}_{1}}$ in the limit of large $n$:

$\displaystyle H_{G_{X_{1}}}(X_{1})$
$\displaystyle=\lim\limits_{n\to\infty}\frac{1}{n}H^{\chi}_{G^{n}_{{\bf
X}_{1}}}({\bf X}_{1})\ .$ (34)

Similarly, from (33) and (34), the conditional graph entropy of $X_{1}$ given
$X_{2}$ is given as

$\displaystyle
H_{G_{X_{1}}}(X_{1}\,|\,X_{2})=\lim\limits_{n\to\infty}\,\,\min\limits_{c_{G^{n}_{{\bf
X}_{1}}},\,c_{G^{n}_{{\bf X}_{2}}}}\frac{1}{n}H(c_{G^{n}_{{\bf X}_{1}}}({\bf
X}_{1})\,|\,c_{G^{n}_{{\bf X}_{2}}}({\bf X}_{2}))\ .$ (35)

####  A-B1 A characteristic graph-based encoding framework for simultaneously
computing a set of functions

The user demands a set of functions
$\\{F_{j}(X_{\Omega})\\}_{j\in[K_{c}]}\in\mathbb{R}^{K_{c}}$ that are possibly
non-linear in the subfunctions. In our proposed framework, for the distributed
computing of these functions, we leverage characteristic graphs that can
capture the structure of subfunctions. To determine the achievable rate of
distributed lossless functional compression, we determine the colorings of
these graphs and evaluate the entropy of such colorings. In the case of
$K_{c}>1$ functions, let $G_{X_{i},j}=(V_{X_{i}},E_{X_{i},j})$ be the
characteristic graph that server $i\in\Omega$ builds for computing function
$j\in[K_{c}]$. The graphs $\\{G_{X_{i},j}\\}_{j\in[K_{c}]}$ are on the same
vertex set.

Union graphs for simultaneously computing a set of functions with side
information have been considered in [83], using _multi-functional
characteristic graphs_. A multi-functional characteristic graph is an OR
function of individual characteristic graphs for different functions [83,
Definition 45]. To that end, server $i\in\Omega$ creates a union of graphs on
the same set of vertices $V_{X_{i}}$ with a set of edges $E^{\cup}_{X_{i}}$,
which satisfy

$\displaystyle
G^{\cup}_{X_{i}}=\bigcup_{j\in[K_{c}]}G_{X_{i},j}=(V_{X_{i}},E^{\cup}_{X_{i}})\
,\quad E^{\cup}_{X_{i}}=\bigcup_{j\in[K_{c}]}E_{X_{i},j}\ .$ (36)

In other words, we need to distinguish the outcomes $x_{i}^{1}$ and
$x_{i}^{2}$ of server $X_{i}$ if there exists at least one function
$F_{j}(x_{\Omega}),\,j\in[K_{c}]$ out of $K_{c}$ functions such that
$F_{j}(x_{i}^{1},x_{\Omega\backslash_{i}}^{1})\neq
F_{j}(x_{i}^{2},x_{\Omega\backslash_{i}}^{1})$, for some
$P_{X_{\Omega}}(x_{i}^{1},x_{\Omega\backslash_{i}}^{1})\cdot
P_{X_{\Omega}}(x_{i}^{2},x_{\Omega\backslash_{i}}^{1})>0$ given
$x_{\Omega\backslash_{i}}^{1}\in X_{\Omega\backslash i}$. The server then
compresses the union $G^{\cup}_{X_{i}}$ by exploiting (33) and (34).

In the special case when the number of demanded functions $K_{c}$ is large (or
tends to infinity), such that the union of all subspaces spanned by the
independent sets of each $G_{X_{i},j}$, $j\in[K_{c}]$ is the same as the
subspace spanned by $\mathcal{X}_{i}$, MISs of $G^{\cup}_{X_{i}}$ in (36) for
server $i\in\Omega$ become singletons, rendering $G^{\cup}_{X_{i}}$ a complete
graph. In this case, the problem boils down to the paradigm of _distributed
source compression_ (see Appendix A-A).

####  A-B2 Distributed functional compression

The fundamental limit of functional compression has been given by Körner [76].
Given ${\bf X}_{i}\in\mathbb{F}_{q}^{|\mathcal{Z}_{i}|\times n}$ for server
$i\in\Omega$, the encoding function $e_{X_{i}}$ specifies MISs given by the
valid colorings $c_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i})$. Let the number of
symbols in ${\bf Z}_{i}=g_{i}({\bf X}_{i})=e_{X_{i}}(c_{G^{n}_{{\bf
X}_{i}}}({\bf X}_{i}))$ be $T_{i}$ for server $i\in\Omega$. Hence, the
communication cost of server $i$, as $n\to\infty$, is given by (5).

Defining $G_{X_{\mathcal{S}}}=[G_{X_{i}}]_{i\in\mathcal{S}}$ for a given
subset $\mathcal{S}\subseteq\Omega$ chosen to guarantee distributed
computation of $F(X_{\Omega})$, i.e., $|\mathcal{S}|\geq N_{r}$, the sum-rate
of servers for distributed lossless functional compression for computing
$F({\bf X}_{\Omega})=\\{F(X_{1l},\,X_{2l},\dots,X_{Nl})\\}_{l=1}^{n}$ equals

$\displaystyle R_{\rm ach}=\sum\limits_{i\in\mathcal{S}}R_{i}\geq
H_{G_{X_{\mathcal{S}}}}(X_{\mathcal{S}}\,|\,Z_{\mathcal{S}^{c}}),\quad\mathcal{S}\subseteq\Omega\
,$ (37)

where $H_{G_{X_{\mathcal{S}}}}(X_{\mathcal{S}})$ is the _joint graph entropy_
of $\mathcal{S}\subseteq\Omega$, and it is defined as [83, Definition 30]:

$\displaystyle
H_{G_{X_{\mathcal{S}}}}(X_{\mathcal{S}})=\lim\limits_{n\to\infty}\,\,\min\limits_{\big{\\{}c_{G^{n}_{{\bf
X}_{i}}}\big{\\}}_{i\in\mathcal{S}}}\frac{1}{n}H(c_{G^{n}_{{\bf X}_{i}}}({\bf
X}_{i}),\,i\in\mathcal{S})\ ,$ (38)

where $c_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i})$ is the coloring of the $n$-th
power graph $G^{n}_{{\bf X}_{i}}$ that $i\in\Omega$ builds for computing
$f({\bf X}_{\Omega})$ [83].

Similarly, exploiting [83, Definition 31], the _conditional graph entropy_ of
the servers is given as

$\displaystyle
H_{G_{X_{\mathcal{S}}}}(X_{\mathcal{S}}\,|\,Z_{\mathcal{S}^{c}})=\lim\limits_{n\to\infty}\,\,\min\limits_{\big{\\{}c_{G^{n}_{{\bf
X}_{i}}}\big{\\}}_{i\in\Omega}}\frac{1}{n}H(c_{G^{n}_{{\bf X}_{i}}}({\bf
X}_{i}),\,i\in\mathcal{S}\,|\,e_{X_{i}}(c_{G^{n}_{{\bf X}_{i}}}({\bf
X}_{i})),\,i\in\mathcal{S}^{c})\ .$ (39)

Using (36) we jointly capture the structures of the set of demanded functions.
Hence, this enables us to provide a refined communication cost model in (5)
versus the characterizations as a function of $K_{c}$, see e.g., [40, 69, 59].

##  Appendix B Proofs of Main Results

###  B-A Proof of Theorem 1

Consider the general topology, $\mathcal{T}(N,K,K_{c},M,N_{r})$, under general
placement of datasets, and for a set of $K_{c}$ general functions
$\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$ requested by the user, and under
general jointly distributed dataset models, including non-uniform inputs and
allowing correlations across datasets.

We note that server $i\in\Omega$ builds a characteristic graph121212The
characteristic graph-based approach is valid provided that each subfunction
$W_{k}$, $k\in\mathcal{K}$ contained in $X_{i}=W_{\mathcal{Z}_{i}}$ is defined
over a $q$-ary field such that $q\geq 2$, to ensure that the union graph
$G^{\cup}_{X_{i}}$, $i\in\Omega$ (or $G_{X_{i},j}$, $j\in[Kc]$ each) has more
than one vertex. $G_{X_{i},j}$ for distributed lossless computing of
$f_{j}(W_{\mathcal{K}})$, $j\in[K_{c}]$. Similarly, server $i\in\Omega$ builds
a union characteristic graph for computing
$\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$. We denote by
$G^{\cup}_{X_{i}}=(V_{X_{i}},E_{X_{i}})=\bigcup_{j\in[K_{c}]}G_{X_{i},j}$ the
union characteristic graph, given as in (36). In the description of
$G^{\cup}_{X_{i}}$, the set $V_{X_{i}}$ is the support set of $X_{i}$, i.e.,
$V_{X_{i}}=\mathcal{X}_{i}$, and $E_{X_{i}}$ is the union of edges, i.e.,
$E_{X_{i}}=\bigcup\nolimits_{j\in[K_{c}]}E_{X_{i},j}$, where $E_{X_{i},j}$
denotes the set of edges in $G_{X_{i},j}$, which is the characteristic graph
the server builds for distributed lossless computing $f_{j}(W_{\mathcal{K}})$
for a given function $j\in[K_{c}]$.

To compute the set of demanded functions
$\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$, we assume that server
$i\in\Omega$ can use a codebook of functions denoted by $\mathcal{C}_{i}$ such
that $\mathcal{C}_{i}\ni g_{i}$, where the user can compute its demanded
functions using the set of transmitted information
$\\{g_{i}(X_{i})\\}_{i\in\mathcal{S}}$ provided from any set of
$|\mathcal{S}|=N_{r}$ servers. More specifically, server $i\in\Omega$ chooses
a function $g_{i}\in\mathcal{C}_{i}$ to encode $X_{i}$. Note that $g_{i}$
represents, in the context of encoding characteristic graphs, the mapping from
$X_{i}$ to a valid coloring $c_{G_{X_{i}}}(X_{i})$. We denote by ${\bf
Z}_{i}=g_{i}({\bf X}_{i})=e_{X_{i}}(c_{G^{n}_{{\bf X}_{i}}}({\bf X}_{i}))$ the
color encoding performed by server $i\in\Omega$ for the length $n$ realization
of $X_{i}$, denoted by ${\bf X}_{i}$. For convenience, we use the following
shorthand notation to represent the transmitted information from the server:

$\displaystyle Z_{i}=g_{i}(X_{i})\ ,\quad i\in\Omega\ .$ (40)

Combining the notions of the union graph in (36) and the encodings of the
individual servers given in (40), the rate $R_{i}$ needed from server
$i\in\Omega$ for meeting the user demand is upper bounded by the cost of the
best encoding that minimizes the rate of information transmission from the
respective server. Equivalently,

$\displaystyle
R_{i}\geq\min\limits_{Z_{i}=g_{i}(X_{i})\,:\,g_{i}\in\mathcal{C}_{i}}H_{G^{\cup}_{X_{i}}}(X_{i})\
,$ (41)

where equality is achievable in (41). Because the user can recover the desired
functions using any set of $N_{r}$ servers, the achievable sum rate is upper
bounded by

$\displaystyle R_{\rm
ach}\leq\sum\limits_{i=1}^{N_{r}}\,\min\limits_{Z_{i}=g_{i}(X_{i})\,:\,g_{i}\in\mathcal{C}_{i}}H_{G^{\cup}_{X_{i}}}(X_{i})\
.$ (42)

###  B-B Proof of Proposition 1

For the multi-server, multi-function distributed computing architecture, this
proposition restricts the demand to be a set of linearly separable functions,
given as in (4). Given the recovery threshold $N_{r}$, it holds that

$\displaystyle R_{\rm
ach}\leq\sum\limits_{i=1}^{N_{r}}\,\min\limits_{Z_{i}=g_{i}(X_{i})\,:\,g_{i}\in\mathcal{C}_{i}}H_{G^{\cup}_{X_{i}}}(X_{i})$
$\displaystyle=\sum\limits_{i=1}^{N_{r}}\,\min\limits_{Z_{i}\,:\,g_{i}\in\mathcal{C}_{i}}\,\min\limits_{X_{i}\in
U_{i}\in S(G^{\cup}_{X_{i}})}I(X_{i};U_{i})$ (43)
$\displaystyle=\sum\limits_{i=1}^{N_{r}}\,\Big{[}H(W_{(i-1)\Delta+1}^{(i-1)\Delta+M})-H\Big{(}W_{(i-1)\Delta+1}^{(i-1)\Delta+M}\,\Big{|}\,Z_{i}\Big{)}\Big{]}$
(44)
$\displaystyle=\sum\limits_{i=1}^{N_{r}}\Big{[}M-\Big{(}M-H(Z_{i})\Big{)}\Big{]}=\sum\limits_{i=1}^{N_{r}}H(Z_{i})\
,$ (45)

where in (43), we used the identity
$H_{G^{\cup}_{X_{i}}}(X_{i})=\min\limits_{X_{i}\in U_{i}\in
S(G^{\cup}_{X_{i}})}I(X_{i};U_{i})$. Furthermore, if the codebook
$\mathcal{C}_{i}$ is restricted to linear combinations of subfunctions,
$Z_{i}$ is given by the following set of linear equations:

$\displaystyle
Z_{i}=g_{i}(X_{i})=\Big{\\{}\sum\limits_{k=(i-1)\Delta+1}^{(i-1)\Delta+M}\alpha_{k}^{(l)}W_{k}\
,\,l\in[K_{c}]\Big{\\}}\ .$ (46)

In other words, $Z_{i}$, $i\in[N_{r}]$, is a vector-valued function. Note that
each server contributes to determining the set of linearly separable functions
$\\{f_{j}(W_{\mathcal{K}})\ ,\ j\in[K_{c}]\\}$ of datasets, given as in (4),
in a distributed manner. Hence, each independent set $U_{i}\in
S(G^{\cup}_{X_{i}})$, with $S(G^{\cup}_{X_{i}})$ denoting the set of MISs of
$X_{i}$, of $X_{i}$ is captured by the linear functions of
$\\{W_{k}\\}_{k\in[(i-1)\Delta+1:(i-1)\Delta+M]}$, i.e., each $U_{i}\in
S(G^{\cup}_{X_{i}})$ is determined by (46). Hence, the user can recover the
requested functions by linearly combining the transmissions of the $N_{r}$
servers:

$\displaystyle
f_{j}(W_{\mathcal{K}})=\sum\limits_{i=1}^{N_{r}}\beta_{ji}Z_{i}=\sum\limits_{i=1}^{N_{r}}\beta_{ji}g_{i}(X_{i})=\sum\limits_{k=1}^{K}\gamma_{jk}W_{k}\
,\quad j\in[K_{c}]\ .$ (47)

In (44), we use the definition of mutual information,
$I(X_{i};U_{i})=H(X_{i})-H(X_{i}\,|\,U_{i})$, where given $i\in[N_{r}]$ and
$\Delta=\frac{K}{N}$, it holds under cyclic placement that

$\displaystyle
X_{i}=W_{(i-1)\Delta+1}^{(i-1)\Delta+M}=W_{(i-1)\Delta+1},W_{(i-1)\Delta+2},\dots,W_{(i-1)\Delta+M}\
,$ (48)

and $\alpha_{k}^{(l)}$ are the coefficients for computing function
$l\in[K_{c}]$. In (45), we used that $W_{k}$ is uniform over $\mathbb{F}_{q}$
and i.i.d. across $k\in[K]$, and rewrote the conditional entropy expression
such that

$\displaystyle
H\Big{(}W_{(i-1)\Delta+1}^{(i-1)\Delta+M}\,\Big{|}\,Z_{i}\,\Big{)}=H\Big{(}W_{(i-1)\Delta+1}^{(i-1)\Delta+M}\,,\,Z_{i}\,\Big{)}-H(Z_{i})\overset{(a)}{=}H\Big{(}W_{(i-1)\Delta+1}^{(i-1)\Delta+M}\Big{)}-H(Z_{i})\
,$ (49)

where $(a)$ follows from that $Z_{i}$ is a function of
$W_{(i-1)\Delta+1}^{(i-1)\Delta+M}$. For a given $l\in[K_{c}]$ and field size
$q$, the relation
$\sum\nolimits_{k=(i-1)\Delta+1}^{(i-1)\Delta+M}\alpha_{k}^{(l)}W_{k}$ ensures
that $G_{X_{i}}$ has $q$ independent sets where each such set $U_{i}$ contains
$q^{M-1}$ different values of $X_{i}$. Exploiting that $W_{k}$ is i.i.d. and
uniform over $\mathbb{F}_{q}$, each element of $Z_{i}$ is uniform over
$\mathbb{F}_{q}$. Hence, the achievable sum-rate is upper bounded by

$\displaystyle\sum\limits_{i=1}^{N_{r}}\,\min\limits_{Z_{i}\,:\,g_{i}\in\mathcal{C}_{i}}H_{G^{\cup}_{X_{i}}}(X_{i})\leq
K_{c}N_{r}\ .$ (50)

Exploiting the cyclic placement model, we can tighten the bound in (50). Note
that server $i=1$ can help recover $M$ subfunctions (at most, i.e., $M$
transmissions needed to recover $M$ subfunctions), and each of servers
$i\in[2:N_{r}]$ can help recover an additional $\Delta$ subfunctions (at most,
i.e., $\Delta$ transmissions needed to recover $\Delta$ subfunctions). Hence,
the set of servers $[N_{r}]$ suffices to provide $M+(Nr-1)\Delta=N\Delta=K$
subfunctions and reconstruct any desired function of $W_{\mathcal{K}}$. Due to
cyclic placement, each $W_{k}$ is stored in exactly $N-N_{r}+1$ servers. Now,
let us consider the following four scenarios:

(i) When $1\leq K_{c}<\Delta$, it is sufficient for each server to transmit
$K_{c}$ linearly independent combinations of their subfunctions. This leads to
resolving $K_{c}N_{r}$ linear combinations of $K$ subfunctions from $N_{r}$
servers that are sufficient to derive the demanded $K_{c}$ linear functions.
Because $K_{c}N_{r}<\Delta N_{r}$, there are
$K-K_{c}N_{r}>\Delta(N-N_{r})=M-\Delta$ unresolved linear combinations of $K$
subfunctions.

(ii) When $\Delta\leq K_{c}\leq\Delta N_{r}$, it is sufficient for each server
to transmit at most $\Delta$ linearly independent combinations of their
subfunctions. This leads to resolving $\Delta N_{r}$ linear combinations of
$K$ subfunctions and $\Delta(N-N_{r})=M-\Delta$ unresolved linear combinations
of $K$ subfunctions.

(iii) When $\Delta N_{r}<K_{c}\leq K$, each server needs to transmit at a rate
$\frac{K_{c}}{N_{r}}$ where $\frac{K_{c}}{N_{r}}>\Delta$ and
$\frac{K_{c}}{N_{r}}\leq\frac{K}{N_{r}}=\Delta\big{(}\frac{N_{r}+N-N_{r}}{N_{r}}\big{)}=\Delta+\Delta\big{(}\frac{N-N_{r}}{N_{r}}\big{)}$,
which gives the number of linearly independent combinations needed to meet the
demand. This yields a sum-rate of $K_{c}$. The subset of servers may need to
provide up to an additional $\Delta(N-N_{r})$ linear combinations, and
$\Delta\big{(}\frac{N-N_{r}}{N_{r}}\big{)}$ defines the maximum number of
additional linear combinations per server, i.e., the required number of
combinations when $K_{c}=K$.

(iv) When $K<K_{c}$, it is easy to note that since any $K$ linearly
independent equation in (47) suffices to recover $W_{\mathcal{K}}$, the sum-
rate $K$ is achievable.

From (i)-(iv), we obtain the following upper bound on the achievable sum-rate:

$\displaystyle\sum\limits_{i=1}^{N_{r}}\,\min\limits_{Z_{i}\,:\,g_{i}\in\mathcal{C}_{i}}H_{G^{\cup}_{X_{i}}}(X_{i})=\begin{cases}K_{c}N_{r}\
,\quad 1\leq K_{c}<\Delta\ ,\\\ \Delta N_{r}\ ,\quad\Delta\leq K_{c}\leq\Delta
Nr\ ,\\\ K_{c}\ ,\quad\Delta Nr<K_{c}\leq K\ ,\\\ K\ ,\quad K<K_{c}\
,\end{cases}$ (51)

where it is easy to note that (51) matches the communication cost in [40,
Theorem 2]. The i.i.d. distribution assumption for $W_{k}$, ensures that this
result holds for any $q\geq 2$.

###  B-C Proof of Proposition 2

Similarly as in Theorem 1, we let
$G^{\cup}_{X_{i}}=\bigcup_{j\in[K_{c}]}G_{X_{i},j}$ denote the union
characteristic graph that server $i\in\Omega$ builds for computing
$\\{f_{j}(W_{\mathcal{K}})\\}_{j\in[K_{c}]}$. Note that given
$W_{\mathcal{Z}_{i}}=W_{1+(i-1)\Delta},W_{1+(i-1)\Delta+1},\dots,W_{M+(i-1)\Delta}$,
the support set of server $i\in\Omega$ has a cardinality of
$\mathcal{X}_{i}=2^{M}$. Because the user demand is a collection of Boolean
functions, in this scenario, each server $i\in\Omega$ builds a graph with $2$
independent sets at most, denoted by $s_{0}(G^{\cup}_{X_{i}})$ and
$s_{1}(G^{\cup}_{X_{i}})$, yielding the function values $Z_{i}=0$ and
$Z_{i}=1$, respectively.

Given the recovery threshold $N_{r}$, any subset $\mathcal{S}$ of servers with
$|\mathcal{S}|=N_{r}$ stores the set $\mathcal{K}$, which is sufficient to
compute the demanded functions. Given server $i\in\Omega$, consider the set of
all $w_{\mathcal{Z}_{i}}\in W_{\mathcal{Z}_{i}}$ that satisfies

$\displaystyle
f(w_{\mathcal{Z}_{i}},w_{\mathcal{Z}_{\mathcal{S}}\backslash\mathcal{Z}_{i}})=1\
,\quad\forall
w_{\mathcal{Z}_{\mathcal{S}}\backslash\mathcal{Z}_{i}}\in\\{0,1\\}^{|\mathcal{K}\backslash\mathcal{Z}_{i}|}\
,$ (52)

where notation $w_{\mathcal{Z}_{\mathcal{S}}\backslash\mathcal{Z}_{i}}$
denotes the dataset values for the set of datasets stored in the subset of
servers $\mathcal{S}\backslash i$. Note in general that
$K_{n}(\mathcal{S})=|\mathcal{Z}_{\mathcal{S}}|=\big{|}\bigcup\nolimits_{i\in\mathcal{S}}\mathcal{Z}_{i}\big{|}$.
In the case of cyclic placement based on (1), out of the set of all datasets
$\mathcal{K}$, there are $\Delta$ datasets that belong exclusively to server
$i\in\Omega$. In this case, $|\mathcal{K}\backslash\mathcal{Z}_{i}|=K-\Delta$.

Note that (52) captures the independent set $s_{1}(G^{\cup}_{X_{i}})\ni
w_{\mathcal{Z}_{i}}$. Equivalently, the set of dataset values
$W_{\mathcal{Z}_{i}}$ that lands in $s_{1}(G^{\cup}_{X_{i}})$ of
$G^{\cup}_{X_{i}}$, yields $Z_{i}=1$. The transmitted information takes the
value $Z_{i}=1$ with a probability

$\displaystyle\mathbb{P}(Z_{i}=1)=\mathbb{P}(W_{\mathcal{Z}_{i}}\in
s_{1}(G^{\cup}_{X_{i}}))\ ,\quad i\in\Omega\ ,$ (53)

using which the upper bound on the achievable sum rate can be determined.

###  B-D Proof of Proposition 3

Recall that $W_{k}\sim{\rm Bern}(\epsilon)$ are i.i.d. across $k\in[K]$, and
each server has a capacity $M=\Delta(N-N_{r}+1)$. This means that given the
number of datasets $K$, each server can compute the product of
$\Delta(N-N_{r}+1)$ subfunctions and hence, the minimum number of servers to
evaluate the multi-linear function
$f(W_{\mathcal{K}})=\prod\nolimits_{k\in[K]}W_{k}$ is
$N^{*}=\left\lfloor\frac{N}{N-N_{r}+1}\right\rfloor$ such that given its
capacity $M=|\mathcal{Z}_{i}|$, each server can compute the product of a
disjoint set of $M$ subfunctions, i.e.,
$\prod\nolimits_{k\in\mathcal{Z}_{i}}W_{k}$, which operates at a rate of
$R_{i}\geq h(\epsilon_{M})$, $i\in\Omega$. Exploiting the characteristic graph
approach, we build $G_{X_{1}}=(V_{X_{1}}\,,\,E_{X_{1}})$ for $X_{1}$, with
respect to variables $X_{\Omega}\backslash X_{1}=X_{2},\dots,X_{N}$ and
$f(W_{\mathcal{K}})$, and similarly for other servers to characterize the sum-
rate for the computation by evaluating the entropy of each graph.

To evaluate the first term in (12), we choose a total of $N^{*}$ servers with
a disjoint set of subfunctions. We denote the selected set of servers by
$\mathcal{N}^{*}\subseteq\Omega$, and the collective computation rate of these
$N^{*}$ servers, as a function of the conditional graph entropies of these
servers, becomes

$\displaystyle\sum\limits_{i\in\mathcal{N}^{*}}R_{i}$
$\displaystyle\overset{(a)}{\leq}H_{G_{X_{i_{1}}}}(X_{i_{1}})+H_{G_{X_{i_{2}}}}(X_{i_{2}}\,|\,Z_{i_{1}})+\dots+H_{G_{X_{i_{N^{*}}}}}(X_{i_{N^{*}}}\,|\,Z_{i_{1}},Z_{i_{2}},\dots,Z_{i_{N^{*}-1}})$
$\displaystyle\overset{(b)}{=}h(\epsilon_{M})+\epsilon_{M}h(\epsilon_{M})+(\epsilon_{M})^{2}h(\epsilon_{M})+\cdots+(\epsilon_{M})^{N^{*}-1}h(\epsilon_{M})$
$\displaystyle\overset{(c)}{=}\frac{1-(\epsilon_{M})^{N^{*}}}{1-\epsilon_{M}}\cdot
h(\epsilon_{M})\ ,$ (54)

where $(a)$ follows from assuming
$\mathcal{S}=\\{i_{1},i_{2},\cdots,i_{N^{*}}\\}$ with no loss of generality,
and $(b)$ from that the rate of server $i_{l}\in\mathcal{S}$ is positive only
when
$\prod\nolimits_{i\in[i_{l-1}]}\prod\nolimits_{k\in\mathcal{Z}_{i}}W_{k}=1$,
which is true with probability $(\epsilon_{M})^{l-1}$. Finally, $(c)$ follows
from employing the sum of the terms in the geometric series, i.e.,
$\sum\nolimits_{l=0}^{N^{*}-1}(\epsilon_{M})^{l}=\frac{1-(\epsilon_{M})^{N^{*}}}{1-\epsilon_{M}}$.
131313While Proposition 3 uses the conditional graph entropies, the statements
of Theorem 1 and Proposition 1, and Proposition 2 do not take into account the
notion of conditional graph entropies. However, as indicated in Subsection
IV-A for computing linearly separable functions, and in Subsection IV-B for
computing multi-linear functions, respectively, we used the conditional
entropy-based sum rate in (B-D) to evaluate and illustrate the achievable
gains over [40] and [61].

In the case of $\Delta_{N}=N-N^{*}\cdot(N-N_{r}+1)>0$, the product of $K$
subfunctions cannot be determined by $N^{*}$ servers and we need additional
servers $\mathcal{I}^{*}\in\Omega$ to aid the computation and determine the
outcome of $f(W_{\mathcal{K}})$ by computing the product of the remaining
$\xi_{N}$ subfunctions. In other words, if $\Delta_{N}>0$ and
$\prod\nolimits_{i\in\mathcal{S}}\prod\nolimits_{k\in\mathcal{Z}_{i}}W_{k}=1$,
the $(N^{*}+1)$-th server determines the outcome of $f(W_{\mathcal{K}})$ by
computing the product of subfunctions $W_{k}\sim{\rm Bern}(\epsilon)$,
$k\in\big{[}N-\xi_{N}+1:N\big{]}$, that cannot be captured by the previous
$N^{*}$ servers. Hence, the additional rate, given by the second term in (12),
is given by the product of the term

$\displaystyle(\epsilon_{M})^{N^{*}}=\mathbb{P}\Big{(}\prod\limits_{i\in\mathcal{S}}\prod\limits_{k\in\mathcal{Z}_{i}}W_{k}=1\Big{)}\
,$ (55)

with $1_{\Delta_{N}>0}$, and $h\big{(}\epsilon_{\xi_{N}}\big{)}$. Combining
this rate term with (B-D), we prove the statement of the proposition.

## References

  * [1] C. Yang, H. Wu, Q. Huang, Z. Li, and J. Li, “Using spatial principles to optimize distributed computing for enabling the physical science discoveries,” _Proc., Natl. Acad. Sci. U.S.A._ , vol. 108, no. 14, pp. 5498–5503, Apr. 2011.
  * [2] J. Shamsi, M. A. Khojaye, and M. A. Qasmi, “Data-intensive cloud computing: Requirements, expectations, challenges, and solutions,” _J. Grid Comput._ , vol. 11, no. 2, pp. 281–310, Jun. 2013.
  * [3] H. Yang, T. Ding, and X. Yuan, “Federated learning with lossy distributed source coding: Analysis and optimization,” _IEEE Trans. Commun._ , vol. 71, no. 8, pp. 4561–4576, May 2023.
  * [4] G. Gan, “Evaluation of room air distribution systems using computational fluid dynamics,” _Energy Build._ , vol. 23, no. 2, pp. 83–93, Dec. 1995.
  * [5] Y. Gao, L. Wang, and J. Zhou, “Cost-efficient and quality of experience-aware provisioning of virtual machines for multiplayer cloud gaming in geographically distributed data centers,” _IEEE Access_ , vol. 7, pp. 142 574–142 585, Sep. 2019.
  * [6] C. Lushbough and V. Brendel, “An overview of the bioextract server: a distributed, web-based system for genomic analysis,” in _Proc., Adv. Comput. Biol._ New York, NY: Springer, Jan. 2010, pp. 361–369.
  * [7] J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” _Commun. ACM_ , vol. 51, no. 1, pp. 107–113, Jan. 2008.
  * [8] K. Grolinger, M. Hayes, W. A. Higashino, A. L’Heureux, D. S. Allison, and M. A. Capretz, “Challenges for MapReduce in big data,” in _Proc., IEEE World Congress Serv._ , Anchorage, AK, USA, Jun. 2014, pp. 182–189.
  * [9] M. A. Al-Khasawneh, S. M. Shamsuddin, S. Hasan, and A. A. Bakar, “MapReduce a comprehensive review,” in _Proc., Inter. Smart Comput. Elec. Enter._ , Shah Alam, Malaysia, Jul. 2018, pp. 1–6.
  * [10] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster computing with working sets,” in _Proc., USENIX HotTop Cloud Comp. Works._ , Boston, MA, USA, Jun. 2010.
  * [11] A. Khumoyun, Y. Cui, and L. Hanku, “Spark based distributed deep learning framework for big data applications,” in _Proc., Int. Inform. Sci. Commun. Tech._ , Tashkent, Uzbekistan, Nov. 2016, pp. 1–5.
  * [12] A.-C. Orgerie, M. D. d. Assuncao, and L. Lefevre, “A survey on techniques for improving the energy efficiency of large-scale distributed systems,” _ACM Comput. Surv._ , vol. 46, no. 4, pp. 1–31, Mar. 2014.
  * [13] R. Keralapura, G. Cormode, and J. Ramamirtham, “Communication-efficient distributed monitoring of thresholded counts,” in _Proc., ACM SIGMOD Int. Conf. Management of Data_ , New York, NY, USA, Jun. 2006, p. 289–300.
  * [14] W. Li, Z. Chen, Z. Wang, S. A. Jafar, and H. Jafarkhani, “Flexible constructions for distributed matrix multiplication,” in _Proc., IEEE Int. Symp. Inf. Theory_ , Melbourne, Australia, Jul. 2021, pp. 1576–1581.
  * [15] Y. Liu, F. R. Yu, X. Li, H. Ji, and V. C. Leung, “Distributed resource allocation and computation offloading in fog and cloud networks with non-orthogonal multiple access,” _IEEE Trans. Veh. Tech._ , vol. 67, no. 12, pp. 12 137–12 151, Sep. 2018.
  * [16] M. Noormohammadpour and C. S. Raghavendra, “Datacenter traffic control: Understanding techniques and tradeoffs,” _IEEE Commun. Surv. Tutor._ , vol. 20, no. 2, pp. 1492–1525, Dec. 2017.
  * [17] N. Shivaratri, P. Krueger, and M. Singhal, “Load distributing for locally distributed systems,” _Computer_ , vol. 25, no. 12, pp. 33–44, Dec. 1992\.
  * [18] A. Bestavros, “Demand-based document dissemination to reduce traffic and balance load in distributed information systems,” in _Proc., IEEE Symp. Parallel Distrib. Process._ , San Antonio, Texas, USA, Oct. 1995, pp. 338–345.
  * [19] A. Reisizadeh, S. Prakash, R. Pedarsani, and A. S. Avestimehr, “Tree gradient coding,” in _Proc., IEEE Int. Symp. Inf. Theory_ , Paris, France, Jul. 2019, pp. 2808–2812.
  * [20] E. Ozfatura, D. Gündüz, and S. Ulukus, “Gradient coding with clustering and multi-message communication,” in _Proc., IEEE Data Science Wksh._ , Minneapolis, MN, USA, Jun. 2019, pp. 42–46.
  * [21] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding: Avoiding stragglers in distributed learning,” in _Proc., Int. Conf. Machine Learn._ Sydney, Australia: PMLR, Jul. 2017.
  * [22] M. Ye and E. Abbe, “Communication-computation efficient gradient coding,” in _Proc., Int. Conf. Machine Learning_. Stockholm, Sweden: PMLR, Jul. 2018, pp. 5610–5619.
  * [23] W. Halbawi, N. Azizan, F. Salehi, and B. Hassibi, “Improving distributed gradient descent using reed-solomon codes,” in _Proc., IEEE Int. Symp. Inf. Theory_ , Vail, Colorado, USA, Jun. 2018, pp. 2027–2031.
  * [24] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” in _Proc., IEEE Int. Symp. Inf. Theory_ , Istanbul, Türkiye, July 2013, pp. 1077–1081.
  * [25] N. Karamchandani, U. Niesen, M. A. Maddah-Ali, and S. N. Diggavi, “Hierarchical coded caching,” _IEEE Trans. Info Theory_ , vol. 62, no. 6, pp. 3212–3229, Jun. 2016.
  * [26] S. Li, S. Supittayapornpong, M. A. Maddah-Ali, and S. Avestimehr, “Coded terasort,” in _Proc. IEEE Int. Parallel Distrib. Process. Symp. Works._ , Lake Buena Vista, FL, USA, May 2017.
  * [27] S. Li, M. A. Maddah-Ali, Q. Yu, and A. S. Avestimehr, “A fundamental tradeoff between computation and communication in distributed computing,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 1, pp. 109–128, Sep. 2017.
  * [28] ——, “A fundamental tradeoff between computation and communication in distributed computing,” _IEEE Trans. Inf. Theory_ , vol. 64, pp. 109–128, Jan. 2018.
  * [29] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 2, pp. 1281–96, Feb. 2018.
  * [30] N. Naderializadeh, M. A. Maddah-Ali, and A. S. Avestimehr, “Fundamental limits of cache-aided interference management,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 5, pp. 3092–107, May 2017.
  * [31] A. M. Subramaniam, A. Heidarzadeh, and K. R. Narayanan, “Collaborative decoding of polynomial codes for distributed computation,” in _Proc., IEEE Inf. Theory Wksh._ , Visby, Sweden, Aug. 2019, pp. 1–5.
  * [32] S. Dutta, M. Fahim, F. Haddadpour, H. Jeong, V. Cadambe, and P. Grover, “On the optimal recovery threshold of coded matrix multiplication,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 1, pp. 278–301, Jul. 2019.
  * [33] R. Yosibash and R. Zamir, “Frame codes for distributed coded computation,” in _Proc., Int. Symp. Topics Coding_ , Montreal, QC, Canada, Aug. 2021, pp. 1–5.
  * [34] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 9, pp. 4539–51, Sep. 2010.
  * [35] K. Wan, H. Sun, M. Ji, D. Tuninetti, and G. Caire, “Cache-aided matrix multiplication retrieval,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 7, pp. 4301–4319, Mar. 2022.
  * [36] Z. Jia and S. A. Jafar, “On the capacity of secure distributed batch matrix multiplication,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 11, pp. 7420–7437, Sep. 2021.
  * [37] M. Soleymani, H. Mahdavifar, and A. S. Avestimehr, “Analog lagrange coded computing,” _IEEE J. Sel. Areas Inf. Theory_ , vol. 2, no. 1, pp. 283–295, Feb. 2021.
  * [38] Q. Yu, M. A. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,” in _Proc., Adv. Neural Inf. Process. Syst._ , Long Beach, CA, USA, Dec. 2017, pp. 4403–4413.
  * [39] H. H. López, G. L. Matthews, and D. Valvo, “Secure MatDot codes: a secure, distributed matrix multiplication scheme,” in _Proc., IEEE Inf. Theory Wksh._ , Mumbai, India, Nov. 2022, pp. 149–154.
  * [40] K. Wan, H. Sun, M. Ji, and G. Caire, “Distributed linearly separable computation,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 2, pp. 1259–1278, Nov. 2021.
  * [41] J. Zhu, S. Li, and J. Li, “Information-theoretically private matrix multiplication from MDS-coded storage,” _IEEE Trans. Inf. Forensics and Secur._ , vol. 18, pp. 1680–1695, Feb. 2023.
  * [42] A. B. Das, A. Ramamoorthy, and N. Vaswani, “Efficient and robust distributed matrix computations via convolutional coding,” _IEEE Trans. Inf. Theory._ , vol. 67, no. 9, pp. 6266–6282, Jul. 2021.
  * [43] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding,” _IEEE Trans. Inf. Theory._ , vol. 66, no. 3, pp. 1920–1933, Jan. 2020.
  * [44] A. Fawzi, M. Balog, A. Huang, T. Hubert, B. Romera-Paredes, M. Barekatain, A. Novikov, F. J. R Ruiz, J. Schrittwieser, G. Swirszcz _et al._ , “Discovering faster matrix multiplication algorithms with reinforcement learning,” _Nature_ , vol. 610, no. 7930, pp. 47–53, Oct. 2022.
  * [45] M. Aliasgari, O. Simeone, and J. Kliewer, “Private and secure distributed matrix multiplication with flexible communication load,” _IEEE Trans. Inf. Forensics Secur._ , vol. 15, pp. 2722–2734, Feb. 2020.
  * [46] R. G. D’Oliveira, S. El Rouayheb, D. Heinlein, and D. Karpuk, “Notes on communication and computation in secure distributed matrix multiplication,” in _Proc., IEEE Conf. Commun. and Netw. Secur._ , virtual, Jun. 2020, pp. 1–6.
  * [47] K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 8, pp. 5227–5239, Jul. 2011.
  * [48] E. Cancès and G. Friesecke, _Density Functional Theory: Modeling, Mathematical Analysis, Computational Methods, and Applications_ , 1st ed. Springer Nature, Jul. 2023.
  * [49] O. A. Hanna, Y. H. Ezzeldin, T. Sadjadpour, C. Fragouli, and S. Diggavi, “On distributed quantization for classification,” _IEEE J. Sel. Areas Inf. Theory_ , vol. 1, no. 1, pp. 237–249, Apr. 2020.
  * [50] P. Luo, H. Xiong, K. Lü, and Z. Shi, “Distributed classification in peer-to-peer networks,” in _Proc., ACM SIGKDD Int. Conf. Knowl. Discov. Data Min._ , San Jose, CA, Aug. 2007, pp. 968–976.
  * [51] C. Karakus, Y. Sun, S. Diggavi, and W. Yin, “Straggler mitigation in distributed optimization through data encoding,” in _Proc., Adv. Neural Inform. Process. Syst._ , Long Beach, CA, Dec. 2017, pp. 5434–5442.
  * [52] Z. Jia and S. A. Jafar, “Cross subspace alignment codes for coded distributed batch computation,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 5, pp. 2821–2846, Mar. 2021.
  * [53] J. Wang, Z. Jia, and S. A. Jafar, “Price of precision in coded distributed matrix multiplication: A dimensional analysis,” in _Proc., IEEE Inf. Theory Wksh._ , Kanazawa, Japan, Oct. 2021, pp. 1–6.
  * [54] W.-T. Chang and R. Tandon, “On the capacity of secure distributed matrix multiplication,” in _Proc., IEEE Global Commun. Conf._ , Abu Dhabi, United Arab Emirates, Dec. 2018, pp. 1–6.
  * [55] M. Monagan and R. Pearce, “Parallel sparse polynomial multiplication using heaps,” in _Proc. Int. Symp. Symb. Algebr._ , New York, NY, USA, Jun. 2009, pp. 263–270.
  * [56] C. D. Hsu, H. Jeong, G. J. Pappas, and P. Chaudhari, “Scalable reinforcement learning policies for multi-agent control,” in _Proc., IEEE Int. Conf. Intell. Robots Syst._ , Prague, Czech, Sep. 2021, pp. 4785–4791.
  * [57] M. Goldenbaum, H. Boche, and S. Stańczak, “Nomographic functions: Efficient computation in clustered gaussian sensor networks,” _IEEE Trans. Wirel. Commun._ , vol. 14, no. 4, pp. 2093–2105, Dec. 2014.
  * [58] ——, “Harnessing interference for analog function computation in wireless sensor networks,” _IEEE Trans. Signal Process._ , vol. 61, no. 20, pp. 4893–4906, Jul. 2013.
  * [59] W. Huang, K. Wan, H. Sun, M. Ji, R. C. Qiu, and G. Caire, “Fundamental limits of distributed linearly separable computation under cyclic assignment,” in _Proc., IEEE Int. Symp. Inf. Theory_ , Taipei, Taiwan, Jun. 2023.
  * [60] K. Wan, H. Sun, M. Ji, and G. Caire, “On secure distributed linearly separable computation,” _IEEE J. Sel. Areas Commun._ , vol. 40, no. 3, pp. 912–926, Jan. 2022.
  * [61] D. Slepian and J. K. Wolf, “Noiseless coding of correlated information sources,” _IEEE Trans. Inf. Theory_ , vol. 19, no. 4, pp. 471–480, Jul. 1973\.
  * [62] T. Cover, “A proof of the data compression theorem of slepian and wolf for ergodic sources (corresp.),” _IEEE Trans. Inf. Theory_ , vol. 21, no. 2, pp. 226–228, Mar. 1975.
  * [63] J. Korner and K. Marton, “How to encode the modulo-two sum of binary sources (corresp.),” _IEEE Trans. Inf. Theory_ , vol. 25, no. 2, pp. 219–221, Mar. 1979.
  * [64] V. Lalitha, N. Prakash, K. Vinodh, P. V. Kumar, and S. S. Pradhan, “Linear coding schemes for the distributed computation of subspaces,” _IEEE J. Sel. Areas Commun._ , vol. 31, no. 4, pp. 678–690, Mar. 2013.
  * [65] H. Yamamoto, “Wyner-Ziv theory for a general function of the correlated sources,” _IEEE Trans. Inf. Theory_ , vol. 28, pp. 803–807, Sep. 1982.
  * [66] A. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,” _IEEE Trans. Inf. Theoy_ , vol. 22, no. 1, pp. 1–10, Jan. 1976.
  * [67] K. Wan, H. Sun, M. Ji, D. Tuninetti, and G. Caire, “Cache-aided general linear function retrieval,” _Entropy_ , vol. 23, no. 1, p. 25, Dec. 2020.
  * [68] A. Khalesi and P. Elia, “Multi-user linearly-separable distributed computing,” _IEEE. Trans. Inf. Theory_ , vol. 69, no. 10, pp. 6314–6339, Jun. 2023.
  * [69] K. Wan, H. Sun, M. Ji, and G. Caire, “On the tradeoff between computation and communication costs for distributed linearly separable computation,” _IEEE Trans. Commun._ , vol. 69, no. 11, pp. 7390–7405, Aug. 2021.
  * [70] B. J. Erickson, P. Korfiatis, Z. Akkus, and T. L. Kline, “Machine learning for medical imaging,” _Radiographics_ , vol. 37, no. 2, pp. 505–515, Mar. 2017\.
  * [71] N. M. Correa, T. Adali, Y.-O. Li, and V. D. Calhoun, “Canonical correlation analysis for data fusion and group inferences,” _IEEE Signal Process. Mag._ , vol. 27, no. 4, pp. 39–50, Jun. 2010.
  * [72] G. Kant and K. S. Sangwan, “Predictive modeling for power consumption in machining using artificial intelligence techniques,” _Procedia CIRP_ , vol. 26, no. 1, pp. 403–407, Jan. 2015.
  * [73] T. Han and K. Kobayashi, “A dichotomy of functions F(X, Y) of correlated sources (X, Y),” _IEEE Trans. Inf. Theory_ , vol. 33, no. 1, pp. 69–76, Jan. 1987.
  * [74] N. Alon and A. Orlitsky, “Source coding and graph entropies,” _IEEE Trans. Inf. Theory_ , vol. 42, no. 5, pp. 1329–39, Sep. 1996.
  * [75] A. Orlitsky and J. R. Roche, “Coding for computing,” _IEEE Trans. Inf. Theory_ , vol. 47, no. 3, pp. 903–17, Mar. 2001.
  * [76] J. Körner, “Coding of an information source having ambiguous alphabet and the entropy of graphs,” in _Proc., Prague Conf. Inf. Theory_ , Prague, Czech, Sep. 1973.
  * [77] D. Malak, “Fractional graph coloring for functional compression with side information,” in _Proc., IEEE Inf. Theory Wksh. (ITW)_ , Mumbai, India, Nov. 2022.
  * [78] ——, “Weighted graph coloring for quantized computing,” in _Proc., IEEE Int. Symp. Inf. Theory_ , Taipei, Taiwan, Jun. 2023, pp. 2290–2295.
  * [79] N. Charpenay, M. Le Treust, and A. Roumy, “Complementary graph entropy, and product, and disjoint union of graphs,” in _Proc., IEEE Int. Symp. Inf. Theory_ , Taipei, Taiwan, Jun. 2023, pp. 2446–2451.
  * [80] M. R. Deylam Salehi and D. Malak, “An achievable low complexity encoding scheme for coloring cyclic graphs,” in _Proc., Annu. Allerton Conf. Commun. Control Comput._ , Monticello, IL, USA, Sep. 2023, pp. 1–8.
  * [81] T. Maugey, M. Rizkallah, N. Mahmoudian Bidgoli, A. Roumy, and C. Guillemot, “Graph spectral 3D image compression,” _Graph. Spec. Image. Proc._ , pp. 105–128, Aug. 2021.
  * [82] J. L. Sevilla, V. Segura, A. Podhorski, E. Guruceaga, J. M. Mato, L. A. Martinez-Cruz, F. J. Corrales, and A. Rubio, “Correlation between gene expression and GO semantic similarity,” _IEEE/ACM Trans. Comput. Biol. Bioinf._ , vol. 2, no. 4, pp. 330–338, Nov. 2005.
  * [83] S. Feizi and M. Médard, “On network functional compression,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 9, pp. 5387–401, Sep. 2014.
  * [84] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 5, pp. 2856–67, May 2014.
  * [85] D. Mosk-Aoyama and D. Shah, “Fast distributed algorithms for computing separable functions,” _IEEE. Trans. Info. Theory_ , vol. 54, no. 7, pp. 2997–3007, Jun. 2008.
  * [86] G. Kaur, “A comparison of two hybrid ensemble techniques for network anomaly detection in spark distributed environment,” _J. Inform. Secur. Appl._ , vol. 55, no. 102601, Dec. 2020.
  * [87] J. Chen, J. Li, R. Huang, K. Yue, Z. Chen, and W. Li, “Federated learning for bearing fault diagnosis with dynamic weighted averaging,” in _Proc., Int. Conf. Sensing, Meas. & Data Analytics AI_, Nanjing, China, Oct. 2021, pp. 1–6.
  * [88] J. Zhao, R. Govindan, and D. Estrin, “Computing aggregates for monitoring wireless sensor networks,” in _Proc., IEEE Int. Workshop Sens. Netw. Protocols Appl._ , Anchorage, AK, USA, May. 2003, pp. 139–148.
  * [89] P. Giselsson and A. Rantzer, _Large-scale and distributed optimization: An introduction_ , 1st ed. Springer, 2018, vol. 2227.
  * [90] S. Kavadias and R. O. Chao, _Resource allocation and new product development portfolio management_ , 1st ed. Elsevier/Butterworth-Heinemann, Oxford, UK, Nov. 2007.
  * [91] C. A. R. Diniz, M. H. Tutia, and J. G. Leite, “Bayesian analysis of a correlated binomial model,” _Braz. J. Probab. Stat._ , vol. 24, no. 1, p. 68–77, Mar. 2010.
  * [92] P. J. Boland, F. Proschan, and Y. Tong, “Some majorization inequalities for functions of exchangeable random variables,” _Lect. Not.-Mono. Ser._ , pp. 85–91, Jan. 1990.
  * [93] H. Witsenhausen, “The zero-error side information problem and chromatic numbers (corresp.).” _IEEE Trans. Inf. Theory_ , vol. 22, no. 5, pp. 592–593, Sep. 1976.
  * [94] J. W. Moon and L. Moser, “On cliques in graphs,” _Israel J. Math._ , vol. 3, no. 1, pp. 23–28, Mar. 1965.
  * [95] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 2nd ed. New York, NY: USA: John Wiley & Sons, Dec. 1991.