#  Optimal Moments on Redundancies in Noisy Parallel Computing Setup

Sahasrajit Sarmasarkar<EMAIL_ADDRESS>Stanford
UniversityUSA43017-6221 and  Harish Pillai<EMAIL_ADDRESS>Indian Institute
of Technology, BombayIndia

###### Abstract.

We consider the problem of job assignment where a master server aims to
compute some tasks and is provided a few child servers to compute under a
uniform straggling pattern where each server is equally likely to straggle. We
distribute tasks to the servers so that the master is able to receive most of
the tasks even if a significant number of child servers fail to communicate.
We first show that all balanced assignment schemes have the same expectation
on the number of distinct tasks received and then study the variance. The
variance or the second moment is a useful metric to study as there could be a
high variation in the number of distinct tasks received. We show constructions
using a generalization of “Balanced Incomplete Block Design”(BOSE, 1939;
Sprott, 1955) minimizes the variance, and constructions based on repetition
coding schemes attain the largest variance. Both minimum variance and maximum
variance attaining designs have their own use cases depending on whether the
master aims for a heavy-tailed or light-tailed distribution on the number of
distinct jobs. We further show the equivalence between job and server-based
assignment schemes when the number of jobs and child servers are equal.

Block Designs, Repetition Codes, Coding Theory, Straggler Mitigation and
Parallel Computing

##  1\. Introduction

A distributed computing framework where the computation is done on multiple
machines has been widely used for large-scale computations in (Azu, [n. d.];
AWS, [n. d.]; Goo, [n. d.]). This framework allows us to utilize the
computation resources and memory of multiple machines often referred to as
workers. Under a common and simple implementation of distributed computing,
the master server divides the computation tasks to multiple child servers
(workers). After each worker finishes its computation, it shares its results
with the master server. The master aggregates the results received from
different workers to finish its task.

However, in real noisy communication frameworks, a subset of servers (workers)
can be arbitrarily slow (often referred to as the stragglers) compared to the
rest of the workers. Lately, there has been work to mitigate the issue of
stragglers by introducing redundancies (Karakus et al., 2019; Aktas and
Soljanin, 2019; Joshi et al., 2017). Coding theoretic techniques have often
been used to introduce redundancies for straggler mitigation described
extensively in (Li and Avestimehr, 2020) and used to split the data and assign
different data parts to different servers. Distributed coding framework has
been used in gradient computation (Tandon et al., 2017), matrix-matrix
multiplication (Lee et al., 2017; Yu et al., 2017), polynomial computation (Yu
et al., 2019) and convolution coding(Dutta et al., 2017) using techniques from
coding theory namely MDS codes(Lee et al., 2017; Ferdinand and Draper, 2018),
LDPC codes(Maity et al., 2019) and rateless codes(Mallick et al., 2020). The
master server aggregates the computations transmitted by the non-straggling
workers to compute the desired result.

However, as happens typically in most modern cloud computing systems like
Amazon EC2, some servers can operate with a significantly high throughput
(Ananthanarayanan et al., 2013a; Zhang et al., 2013; Zhao et al., 2014).
Statistical knowledge of communication and computation latency of each server
can be used to design better assignment schemes and allocate the tasks more
efficiently as studied in(Wang et al., 2019a; Sun et al., 2019; Yang et al.,
2019).

On a side note, there may be several scenarios where it may not be possible to
split a computing task to multiple sub-parts, and job cloning is often used
for straggler mitigation in such scenarios as studied in (Chen et al., 2014;
Ananthanarayanan et al., 2013b; Joshi et al., 2015, 2017; Szajda et al.,
2005). This is also popular in cloud computing (Joshi et al., 2017; Wang et
al., 2015, 2014) where one task is assigned to multiple servers to combat the
stragglers to obtain a low compute time.

In this paper, we broadly study this problem of job assignment of multiple
cloned jobs to multiple servers treating each server with identical
communication latency where each server has a significant probability of
straggling. These assignment schemes may be particularly useful in framework
where there is high noise in the communication channel between the child
servers and master server.

##  2\. Related work

Block designs have been widely used in experiment design (Bose and Nair, 1939;
Addelman, 1969; Shieh and Jan, 2004) where experiment designs are grouped into
blocks and random treatments are applied to each block. Recently block designs
and its variants have been used to construct LDPC codes (Ammar et al., 2004),
gradient coding (Kadhe et al., 2019; Sakorikar and Wang, 2021) and error
correcting codes (Smith, 1968). The most common amongst these are 2-designs or
as often called balanced incomplete block designs (BIBDs), which are designs
where every pair of points occur together in the same number of blocks (Bose
and Nair, 1939; Colbourn and Dinitz, 2006). It has been shown that 2-designs
(if exist) uniquely attain A-, D- and E optimality for experiment design
(Kiefer, 1975; Kshirsagar, 1958), which was further generalized in (Yeh,
1986). However, our framework is different where we study variance on the
number of distinct tasks received at the the master and show that repetition
coding and a generalization of BIBDs can be utilized to attain the largest and
the least variance respectively.

In another direction, assignment policies of tasks to different servers under
a distributed server system have been studied, check (Semchedine et al., 2011)
for a survey on the same. Typically tasks arrive to a distributed server
system stochastically in real time and this system typically distributes the
tasks to various servers to minimise the response time as studied in
(Colajanni et al., 1998; Harchol-Balter, 2000; Harchol-Balter et al., 1999).
Recent observations show that the distribution of tasks follows a heavy-tailed
distribution (Crovella and Bestavros, 1997; Arlitt and Williamson, 1996;
Crovella et al., 1998; Williams et al., 2005), and designing assignment
policies suited for load balancing across servers becomes difficult. In many
cases, it may not be possible to recover the entire result but only partially
recover the result as studied in coding theory (Babu and Kumar, 2015; Korhonen
and Frossard, 2009). This setup has also been studied in distributed computing
setups where the aim is not to recover the exact result but an approximation
of the result suffices. This setup has been studied for matrix computation
(Ozfatura et al., 2021) and for gradient coding (Sarmasarkar et al., 2022;
Wang et al., 2019b). Our problem follows a similar setup where the master only
aims to recover a high fraction of the jobs as it may be difficult for the
server to recover all tasks in a noisy environment where a substantial
fraction of servers may straggle.

##  3\. Our contributions

In this paper, we study a setup where a master aims to compute $n$ jobs and
has $c$ identical servers to do the computations. In our model, the arrival
and assignment of tasks are not in real-time but instead, the set of tasks
(jobs) to be computed and the set of servers is given apriori. Jobs are
appropriately replicated and can be viewed as a way to mitigate the issue of
slow (straggling) workers. We study a homogeneous setup treating all the
servers as having identical computing and stochastic properties, that is,
balanced schemes with each server being assigned $k$ jobs and each job being
assigned to $r$ servers. We further assume that each server is equally likely
to straggle. We consider a setup where a non-straggling worker can
successfully transmit all tasks to the master as studied in (Tandon et al.,
2017; Joshi et al., 2017; Ozfatura et al., 2019). We aim to design coding
schemes where the master aims to maximise the number of computed distinct jobs
that are received. Towards this aim, we study the mean and variance of the
number of distinct jobs received in Section 5.

Our contributions can be described as follows.

a) We first show that when any set of $x$ servers is equally likely to
straggle, then for every balanced assignment, the expected number of completed
jobs that the master receives is the same (Theorem 1) and study the variance
of the number of jobs received within the class of balanced assignment
schemes.

b) Typically, assignment schemes with the largest variance may be useful for
systems where we aim to increase the likelihood of the master receiving a
large number (or all) of jobs (heavier mass at tails), and schemes with the
least variance may be useful for systems where one aims to reduce the
likelihood of the master receiving a small number of jobs (lighter mass at the
tails). This follows since every balanced assignment scheme has the same
expectation on the jobs received.

c) We show that certain special balanced assignments (called proximally
compact and stretched compact designs) when they exist, are guaranteed to
attain the least variance and largest variance respectively (Theorem 5 and
Theorem 8 in Section 6).

d) We show how our results generalise to the case where $x$ is sampled from a
distribution. This would imply that results on least variance and largest
variance would continue to hold when each worker is independently and equally
likely to straggle with probability $p$ (Theorems 1, 2 and 3 in Section 7).

e) Finally, we show that when the number of jobs equals the number of servers,
proximally compact job assignments and server assignments (replacing the roles
of jobs and servers) are identical and both of them attain the least variance
in Theorem 2 in Appendix A.

##  4\. Preliminaries and Notation

We consider a setup where a master has $n$ jobs to compute and has $c$ servers
to do the computations. We further assume a noisy scenario where only a
fraction of these servers are able to communicate back to the master.
Therefore, for increasing reliability, redundancies are introduced in the
setup by assigning each job to multiple servers. In this paper, we examine the
expectation and variance on the number of distinct completed jobs that the
master receives from the servers that were able to communicate, for various
assignment schemes. In particular, we study assignment schemes that achieve
certain desired variances on the number of received distinct jobs.

Given a set of $n$ jobs and $c$ servers, we study various assignments of jobs
to different servers by the master server. More formally, let us denote the
$n$ jobs by $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$ and $c$ servers by
$\mathcal{S}=\\{s_{1},s_{2},\ldots,s_{c}\\}$. Any assignment ($D$) of jobs in
$\mathcal{A}$ to servers in $\mathcal{S}$, can be equivalently represented by
a bipartite graph $\mathcal{G}_{D}$ where the nodes denote the jobs and the
servers. The edges of the graph exist between nodes representing job $a_{i}$
and server $s_{j}$ if job $a_{i}$ is assigned to server $s_{j}$. Alternately,
for a job assignment ${D}$, we can define an assignment matrix
$A_{{D}}\in\\{0,1\\}^{n\times c}$ as given below.

######  Definition 1.

(Construction of $A_{D}$): Given an assignment of jobs in $\mathcal{A}$ to
servers in $\mathcal{S}$, we define matrix $A_{D}\in\\{0,1\\}^{n\times c}$ as
follows. :

$\displaystyle{}A_{{D}}[i,j]$ $\displaystyle=1\text{ if job $a_{i}$ is
assigned to server $s_{j}$}$ (1) $\displaystyle=0\text{ otherwise}$

Observe that the matrix $A_{D}$ represents the adjacency matrix for the
bipartite graph $\mathcal{G}_{D}$.

We specifically study balanced assignment schemes where each server is
assigned the same number of jobs and each job is assigned to the same number
of servers. More formally, we define this as follows.

######  Definition 2.

(Balanced $(n,k,r,c)$ assignment): Given a set of $n$ jobs and $c$ servers, we
call an assignment scheme of jobs a balanced $(n,k,r,c)$ assignment if the
following conditions are satisfied.

  * •

Each server is assigned precisely $k$ distinct jobs to compute.

  * •

Each job is assigned to precisely $r$ distinct servers.

Note that this assignment scheme ensures that $n\times r=k\times c$.

We can equivalently define it in terms of matrix $A_{D}$ as follows.

######  Definition.

(Balanced $(n,k,r,c)$ assignment in terms of $A_{D}$): Given a set of $n$ jobs
and $c$ servers, we call the assignment scheme $D$ of jobs to servers a
balanced $(n,k,r,c)$ assignment if each row of $A_{D}$ sums up to $r$ and each
column sums up to $k$.

Let us look at an example of a balanced $(9,3,2,6)$ assignment scheme.

######  Example 0.

We describe a balanced assignment scheme with 9 jobs
$\\{a_{1},a_{2},\ldots,a_{9}\\}$ and 6 servers
$\\{s_{1},s_{2},\ldots,s_{6}\\}$ in Table 1. Note that each job is assigned to
precisely $2$ servers and each server has exactly 3 jobs to compute. The
assignment scheme is motivated from a cyclic assignment scheme.

Jobs Servers | $s_{1}$ | $s_{2}$ | $s_{3}$ | $s_{4}$ | $s_{5}$ | $s_{6}$
---|---|---|---|---|---|---
$a_{1}$ | 1 | 1 |  |  |  |
$a_{2}$ |  | 1 | 1 |  |  |
$a_{3}$ |  |  | 1 | 1 |  |
$a_{4}$ |  |  |  | 1 | 1 |
$a_{5}$ |  |  |  |  | 1 | 1
$a_{6}$ | 1 |  |  |  |  | 1
$a_{7}$ | 1 | 1 |  |  |  |
$a_{8}$ |  |  | 1 | 1 |  |
$a_{9}$ |  |  |  |  | 1 | 1
Table 1. Assignment of jobs to various servers in a balanced $(9,3,2,6)$
assignment scheme

##  5\. The Mean and the Variance

We consider the number of distinct jobs $d$ received at the master when only a
subset of $x$ servers manage to communicate with the master. We consider any
subset of $\mathcal{S}$ with cardinality $x$ to be equally likely be the set
of servers that communicates with the master. Note that with this definition,
if $\hat{S}\subseteq\mathcal{S}$ (with $|\hat{S}|=x$) is the subset of servers
that communicate with the master, then we can denote the number of distinct
jobs received $d=|\cup_{j\in\hat{S}}\text{supp}(A_{D}[:,j])|$ where
$\text{supp}(v)$ denotes the indices of the non-zero entries of the vector
$v$.

Now, consider the uniform distribution over all subsets of servers of
cardinality $x$ which we denote by $\mathfrak{D}_{\mathcal{S},x}$ i.e. a
sample from this distribution returns any subset of $\mathcal{S}$ of
cardinality $x$ with probability $\frac{1}{{{|\mathcal{S}|\choose x}}}$.

For a given assignment ${D}$ of jobs to servers, we denote the expectation of
the number of distinct completed jobs received by the master when any subset
of $x$ servers is able to communicate with master uniformly at random by
$\mathbbm{E}_{{D},x}[d]$ and the corresponding variance by
$\sigma_{{D},x}[d]$. The expectation and the variance on the number of
distinct received jobs $d$ may be written as

(2)
${}\mathbbm{E}_{D,x}[d]=\mathbbm{E}_{\hat{S}\sim\mathfrak{D}_{\mathcal{S},x}}\left[\left|\bigcup_{j\in\hat{S}}\text{supp}(A_{D}[:,j])\right|\right]\text{
and
}\sigma_{D,x}[d]=\sigma_{\hat{S}\sim\mathfrak{D}_{\mathcal{S},x}}\left[\left|\bigcup_{j\in\hat{S}}\text{supp}(A_{D}[:,j])\right|\right]$

Note that the randomness in this setup is only in the set of servers that can
communicate with the master. The assignment scheme has no randomness
associated with it.

Theorem 1 states that the expectation on the number of distinct jobs
$\mathbb{E}_{D,x}[d]$ is the same for every balanced $(n,k,r,c)$ assignment.
This expectation is a function of $n,k,r,c$ and $x$ and is independent of the
specific balanced assignment $D$ we choose. Throughout the remainder of this
paper, $\mathfrak{n}^{D}_{i,\hat{S}}$ denotes the number of servers in
$\hat{S}$ to which job $a_{i}$ is assigned under the assignment scheme $D$.
Observe that $\mathfrak{n}^{D}_{i,\hat{S}}$ can take any value from $0$ to
$r$.

######  Theorem 1.

Consider any balanced $(n,k,r,c)$ assignment $D$. The expectation of the
number of distinct completed jobs $d$ received by the master when any subset
of cardinality $x$ of the set of servers $\mathcal{S}$ is able to communicate
with the master with equal probability is the same for every balanced
$(n,k,r,c)$ assignment $D$ and is given by

(3) $\mathbbm{E}_{{D},x}[d]=n\cdot\left(1-\frac{{c-r\choose x}}{{c\choose
x}}\right)$

We present a proof sketch below. A detailed proof is presented in Appendix B.

###### Proof Sketch.

The number of distinct jobs $d$ received by the master when servers in a
subset $\hat{S}$ (with $|\hat{S}|=x$) is able to communicate with the master
is given by

(4)
${}d=\left|\bigcup_{j\in\hat{S}}\text{supp}(A_{D}[:,j])\right|=\left(k\times
x-\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}\right)$

Note that the term
$\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}$
excludes those jobs which have been received multiple times from various
servers present in $\hat{S}$.

(5)
$\displaystyle{}\mathbb{E}_{D,x}[d]=\frac{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(k\times
x-\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})}{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}1}{=}$ $\displaystyle k\times
x-\frac{n\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}}{{c\choose
x}}$

Observe that for every job $a_{i}$ in a balanced $(n,k,r,c)$ assignment, the
quantity
$\sum\limits_{\hat{S}\subset\mathcal{S},|\hat{S}|=x}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}$
is the same, i.e., this summation is independent of $i$. We now show that the
quantity
$\sum\limits_{\hat{S}\subset\mathcal{S},|\hat{S}|=x}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}$
for any specified $x$, is the same for every balanced $(n,k,r,c)$ distribution
${D}$. We compute this sum by counting the number of subsets
$\hat{S}\subset\mathcal{S}$ of cardinality $x$ which additionally satisfies
the constraint on $\mathfrak{n}^{D}_{i,\hat{S}}=t$ (i.e. job $a_{i}$ is
present in exactly $t$ servers from $\hat{S}$) for every $t$ from $2$ to $r$
(as these cases deal with the job $a_{i}$ appearing more than once in the
subset $\hat{S}$). Equation (46) follows from multiplying two binomial
expressions 111Detailed proof is presented in Appendix B and considering their
coefficients.

$\displaystyle{}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}{=}\sum\limits_{t=1}^{r-1}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x,\mathfrak{n}^{D}_{i,\hat{S}}=t+1\end{subarray}}t\overset{(a)}{=}$
$\displaystyle\sum\limits_{t=1}^{r-1}t{r\choose(t+1)}{(c-r)\choose(x-t-1)}$

(7)
${}\sum\limits_{t=1}^{r-1}t{r\choose(t+1)}{(c-r)\choose(x-t-1)}=r\times{{c-1\choose
x-1}}+{{c-r\choose x}}-{{c\choose x}}$

Combining equations (B), (B) and (46), we get the desired result.

∎

A few comments are in order here. Note that for $x=1$, the expectation (as
expected) is precisely $k$. Observe that for $x>c-r$, the expectation goes to
$n$. In other words, if the number of servers that successfully communicates
with the master is greater than $(c-r)$, then the master obtains at least one
copy of every job $a_{i}\in\mathcal{A}$. This follows since every job is
assigned to exactly $r$ servers and therefore for any job to be missed out,
the $r$ servers to which that specific job was assigned, should fail to
communicate with the master. Thus, if any job is missed out, then the number
of servers that manage to communicate with the master $x$ can at most be
$c-r$.

We now calculate the variance for the number of distinct jobs $d$ received at
the master for any balanced $(n,k,r,c)$ job assignment $D$. From the comments
in the previous paragraph, it is clear that $\sigma_{D,1}[d]=0$ for the case
$x=1$, since the master always receives precisely $k$ distinct jobs, if only
one server manages to communicate with the master. Similarly,
$\sigma_{D,x}[d]=0$ for $x>c-r$, as the master would receive all the $n$ jobs
if more than $c-r$ servers communicate (for the sake of completeness, we
formally calculate this in Corollary 1).

For calculating the variance on the number of distinct jobs $d$ received by
the master, observe

$\sigma_{D,x}(d)=\sigma_{D,x}\left(k\times
x-\sum\limits_{i}(\mathfrak{n}^{D}_{i,\hat{S}}-1\right)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})=\sigma_{D,x}\left(\sum\limits_{i}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}\right)$

The above follows since $\sigma(t-X)=\sigma(X)$ where $t$ is a constant and
$X$ is a random variable. We now make use of the definition
$\text{var}(X)=\mathbbm{E}[X^{2}]-(\mathbbm{E}[X])^{2}$. Therefore,

$\displaystyle{}\sigma_{D,x}\left(\sum\limits_{i}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}\right)=$
$\displaystyle\frac{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}{\left(\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}\right)}^{2}}{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}1}-\left(\frac{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};|\hat{S}|=x\end{subarray}}{(\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})}}{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}1}\right)^{2}$
$\displaystyle\overset{(a)}{=}\frac{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1})}{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}1}-\left(\frac{\sum\limits_{i=1}^{n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}{((\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})}}{{c\choose
x}}\right)^{2}$
$\displaystyle\overset{(b)}{=}\frac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}}{{c\choose
x}}-\left(\frac{n\sum\limits_{t=1}^{r-1}t{r\choose(t+1)}{(c-r)\choose(x-t-1)}}{{c\choose
x}}\right)^{2}$ (8)
$\displaystyle\overset{(c)}{=}\frac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}}{{c\choose
x}}-\left(\frac{n{{c-r\choose x}}}{{{c\choose
x}}}+n\times\left(\frac{rx}{c}-1\right)\right)^{2}$

In the above set of equations, $(a)$ follows from the identity
$(\sum\limits_{i}b_{i})^{2}=\sum\limits_{i}\sum\limits_{j}b_{i}b_{j}$. The
first term in $(b)$ is obtained by interchanging the order of summations,
whereas the second term comes from equation (B). Further, the second term in
$(c)$ follows using the equation (46) given in the proof of Theorem 1.

Observe that the second term in the final expression in equation (5) depends
only on $n,r,c$ and $x$ and is independent of the specific balanced
$(n,k,r,c)$ job assignment $D$. On the other hand, the first term in equation
(5) depends on the particular assignment $D$. We now consider the numerator of
the first term of equation (5) in more detail. We can break this expression
into two parts, where one part is dependent on just one index $i$ and the
other part is dependent on two distinct indices $i,j$. Thus,

$\displaystyle\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}$
(9) $\displaystyle=$ $\displaystyle 2\sum\limits_{1\leq i<j\leq
n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}$
(10) $\displaystyle\hskip 80.00012pt+\sum\limits_{1\leq i=j\leq
n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}$

In equation (5), the second term can be rewritten as $\sum\limits_{1\leq i\leq
n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}((\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})^{2}$.
For every job $a_{i}$, this expression calculates
$\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}((\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})^{2}$,
which is independent of the choice of the job $a_{i}$ in any balanced
$(n,k,r,c)$ assignment $D$. In fact, this second term of equation (5) is
independent of the choice of $D$ and it depends only on the values of $n,c,r$
and $x$. We can compute this sum by counting the number of subsets
$\hat{S}\subset\mathcal{S}$ of cardinality $x$ that additionally satisfy the
constraint $\mathfrak{n}^{D}_{i,\hat{S}}=t$ (i.e. job $a_{i}$ is present in
exactly $t$ servers from $\hat{S}$) for every $t$ from $2$ to $r$. Thus

(11) $\sum\limits_{1\leq i\leq
n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}((\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})^{2}=n\sum\limits_{t=1}^{r-1}t^{2}{r\choose(t+1)}{(c-r)\choose(x-t-1)}$

Note that the number of subsets $\hat{S}\subset\mathcal{S}$ of cardinality $x$
such that a particular job $a_{i}$ appears $t+1$ times in $\hat{S}$ is given
by ${r\choose(t+1)}{(c-r)\choose(x-t-1)}$. As
$\mathfrak{n}^{D}_{i,\hat{S}}=t+1$ for this particular $\hat{S}$, therefore
$((\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})^{2}=t^{2}$.
This explains the final expression in equation (11). A closed form expression
for the sum $\sum\limits_{t=1}^{r-1}t^{2}{r\choose(t+1)}{(c-r)\choose(x-t-1)}$
can be obtained by considering the following binomial expressions

(12)
${}r(r-1)y^{2}(1+y)^{r-2}-ry(1+y)^{r-1}-1+{(1+y)^{r}}=\sum_{t=1}^{r-1}t^{2}{{r\choose
t+1}}y^{t+1}$

(13) ${}(1+y)^{c-r}=\sum_{v=0}^{c-r}{{c-r\choose v}}y^{v}$

Multiplying equations (12) and (13), one obtains
$\sum\limits_{t=1}^{r-1}t^{2}{{r\choose t+1}}{{c-r\choose x-t-1}}$ to be the
coefficient of $y^{x}$ in
$r(r-1)y^{2}(1+y)^{c-2}-ry(1+y)^{c-1}-(1+y)^{c-r}+(1+y)^{c}$, thus,

(14) ${}\sum\limits_{t=1}^{r-1}t^{2}{{r\choose t+1}}{{c-r\choose
x-t-1}}=r(r-1){{c-2\choose x-2}}-r{{c-1\choose x-1}}-{{c-r\choose
x}}+{{c\choose x}}$

Finally, we analyse the first term in equation (5), viz., $\sum\limits_{1\leq
i<j\leq n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}$.
If a specific pair of jobs $a_{i},a_{j}$ appear $(\alpha+1)$ and $(\beta+1)$
times respectively in some subset $\hat{S}\subset\mathcal{S}$ of cardinality
$x$, then such a pair of jobs contribute $\alpha\beta$ towards this expression
that we are analysing. One needs to add up such contributions from every
distinct pair of jobs $(a_{i},a_{j})$ and every subset
$\hat{S}\subset\mathcal{S}$ of cardinality $x$ to get the final value of this
expression. The strategy that we adopt to compute this sum is as follows : we
find $\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}$
for any given pair of distinct jobs $(a_{i},a_{j})$. Observe that this
expression depends on how the pair of jobs $(a_{i},a_{j})$ are distributed
amongst the $c$ servers, which in turn depends on the particular balanced
$(n,k,r,c)$ job assignment $D$ that is under consideration. Now, given a
particular pair of jobs $(a_{i},a_{j})$, how they are farmed to the servers
can essentially differ only in the number of servers that are assigned both
the jobs $a_{i},a_{j}$ simultaneously. The number of servers that are
simultaneously assigned both the jobs $(a_{i},a_{j})$ can range from $0$ to
$r$. If a pair of jobs $(a_{i},a_{j})$ are assigned together to precisely $m$
servers (with $0\leq m\leq r$), then the sum
$\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}$
calculated for this particular pair of jobs is precisely equal to the
corresponding sum for every other pair of jobs that are assigned together to
precisely $m$ servers. We use the notation

(15) ${}g(m,x)=\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}$

to indicate this particular sum that arises from a pair of jobs $a_{i},a_{j}$
that are assigned together to precisely $m$ servers. We now show that the
values of $g(m,x)$ depends only on $c,r,m$ and $x$. We give the expression for
$g(0,x)$ in Lemma 2 and give a recursion to compute $g(m,x)$ in Lemma 3.

######  Lemma 0.

For a balanced $(n,k,r,c)$ assignment, the value of $g(0,x)$ is given by

(16) $\displaystyle{}g(0,x)=$ $\displaystyle r^{2}{{c-2\choose
x-2}}-2r{{c-1\choose x-1}}+{{c\choose x}}-2{{c-r\choose x}}+2r{{c-r-1\choose
x-1}}+{c-2r\choose x}$

######  Lemma 0.

For a balanced $(n,k,r,c)$ assignment, the values for $g(m,x)$ are related in
the following fashion

(17) ${}g(m+1,x)-g(m,x)={c-2\choose x-1}-2{c-r-1\choose x-1}+{c-2r+m\choose
x-1}$

We prove these Lemmas in Appendix E and F respectively using a careful
application of techniques from combinatorics.

Note that all the expressions for $g(m,x)$ depends on the values of $c,r,m$
and $x$ and is therefore independent of which balanced $(n,k,r,c)$ assignment
$D$ we choose. Observe further that the expression for $g(m+1,x)-g(m,x)$ is an
increasing function of $m$ when $x$ is fixed. This is clear from the fact that
only the last term in (17) depends on $m$. Of course, if $x\leq c-2r$, then we
can further conclude that $g(m+1,x)-g(m,x)$ is a strictly increasing function
of $m$.

We now define $\mathfrak{m}^{D}(m)$ as the number of distinct pairs of jobs
$(a_{i},a_{j})$ with $1\leq i<j\leq n$ that are assigned together to precisely
$m$ servers in the balanced $(n,k,r,c)$ assignment $D$. One can formally
define this number for a specific balanced $(n,k,r,c)$ assignment $D$ using
the assignment matrix $A_{D}$ as

(18) ${}\mathfrak{m}^{D}(m)=\sum_{\begin{subarray}{c}(i_{1},i_{2})\\\ 1\leq
i_{1}<i_{2}\leq
n\end{subarray}}\mathbbm{1}_{\sum_{j=1}^{c}A_{D}[i_{1},j]A_{D}[i_{2},j]=m}$

Given a balanced $(n,k,r,c)$ assignment $D$, the numbers $\mathfrak{m}^{D}(m)$
have some additional properties

(19) $\sum_{m=0}^{r}\mathfrak{m}^{D}(m)={n\choose 2}$

(20) $\sum_{m=0}^{r}m\mathfrak{m}^{D}(m)=c{k\choose 2}$

Equation (19) follows from the fact that there are a total of $n$ jobs and
thus the total number of job pairs is given by ${{n\choose 2}}$. Equation (20)
follows from the fact that the number of pairs of jobs that are assigned
together to a fixed server $s_{i}$ is given by ${{k\choose 2}}$. Summing over
all the servers in $\mathcal{S}$ gives us the RHS in (20). Note that we count
each pair of jobs as many times as they appear together in a server and thus
we say $\sum_{m=0}^{r}m\mathfrak{m}^{D}(m)=c{k\choose 2}$.

Observe that the first term of equation (5) that we are evaluating can now be
rewritten as

(21) $\sum\limits_{1\leq i<j\leq
n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}=\sum_{m=0}^{r}\mathfrak{m}^{D}(m)g(m,x)$

Putting all of the discussion together, we therefore conclude the following
regarding evaluation of variance $\sigma_{D,x}(d)$ :

######  Theorem 4.

Consider any assignment $D$ amongst balanced $(n,k,r,c)$ assignments. The
variance on the number of distinct jobs $d$ $(\sigma_{D,x}(d))$ received by
the master when any subset of servers $\mathcal{S}$ of cardinality $x>1$ is
able to communicate to the master with equal probability, is equal to

(22)
${}\sigma_{{D},x}(d)=\frac{2\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)g(m,x)+T_{2}(n,r,c,x)}{{c\choose
x}}-\left(T_{1}(n,r,c,x)\right)^{2}\\\ $

where $T_{1}(n,r,c,x)=\frac{n{{c-r\choose x}}}{{{c\choose
x}}}+n\times(\frac{rx}{c}-1)$ and

(23) $\displaystyle T_{2}(n,r,c,x)=$ $\displaystyle
n\sum\limits_{t=1}^{r-1}t^{2}{r\choose(t+1)}{(c-r)\choose(x-t-1)}$ (24)
$\displaystyle=$ $\displaystyle n\left(r(r-1){{c-2\choose x-2}}-r{{c-1\choose
x-1}}-{{c-r\choose x}}+{{c\choose x}}\right)$

Thus, we have shown that while the mean of the number of received jobs $d$ is
the same for all balanced $(n,k,r,c)$ assignments, the variance of $d$ is
dependent on the frequency distribution of job pairs assigned to the same
server.

##  6\. Results on extreme variance based on $[\mathfrak{m}^{D}(m)]_{m=0}^{r}$

It is clear from the previous sections, that while all $(n,k,r,c)$ balanced
job assignments give the same mean, they display different variances based on
the values of $\mathfrak{m}^{D}(m)$ that arise in the respective job
assignments. Here $\mathfrak{m}^{D}(m)$ refers to number of pairs of distinct
jobs assigned together to precisely $m$ servers as defined in (18). We now
explore the range of variances that balanced $(n,k,r,c)$ job assignments can
attain.

######  Definition 2.

Given a balanced $(n,k,r,c)$ job assignment $D$, we define a shape vector
$h_{D}\in\mathbb{N}^{r+1}$ associated to the assignment $D$ as

(25)
${}h_{D}=[\mathfrak{m}^{D}(0),\mathfrak{m}^{D}(1),\ldots\mathfrak{m}^{D}(r)]^{T}$

Thus the shape vector lists the number of pairs of jobs that are assigned
together to $m$ servers, for $m=0,1,\cdots,r$ and is a vector of length $r+1$.
Clearly, the entries of $h_{D}$ are all non-negative integers. Two distinct
balanced $(n,k,r,c)$ job assignments $D_{1},D_{2}$ would have the same mean
and variance if and only if the corresponding shape vectors $h_{D_{1}}$ and
$h_{D_{2}}$ are the same.

We first characterize all possible candidate shape vectors in
$\mathbb{N}^{r+1}$.222In our notation, $\mathbb{N}$ is the set of all non-
negative integers including 0. Since the entries of the shape vectors are
$\mathfrak{m}^{D}(m)$ arising out of balanced $(n,k,r,c)$ job assignment, they
must satisfy equations (19) and (20). These can be rewritten as

(26) ${}\begin{bmatrix}1&1&1&\cdots&1\\\
0&1&2&\cdots&r\end{bmatrix}\begin{pmatrix}\mathfrak{m}^{D}(0)\\\
\mathfrak{m}^{D}(1)\\\ \vdots\\\
\mathfrak{m}^{D}(r)\end{pmatrix}=Hh_{D}=\begin{pmatrix}{n\choose 2}\\\
c{k\choose 2}\end{pmatrix}$

Here the matrix $H=\begin{bmatrix}1&1&1&\cdots&1\\\
0&1&2&\cdots&r\end{bmatrix}$. Thus, two possible shape vectors differ by a
vector in the kernel of the matrix $H$. Therefore, if one has a particular
balanced $(n,k,r,c)$ job assignment $D$ with the corresponding shape vector
$h_{D}$, then all other possible shape vectors can be characterized as vectors
$(h_{D}+v)\in\mathbb{N}^{r+1}$ where $v\in\ker H$. A basis for the kernel of
the matrix $H$ is given by the $r-1$ vectors

(27)
${}\left\\{h_{1},h_{2},h_{3},\cdots,h_{r-2},h_{r-1}\right\\}=\left\\{\begin{pmatrix}1\\\
-2\\\ 1\\\ 0\\\ \vdots\\\ 0\\\ 0\\\ 0\end{pmatrix},\begin{pmatrix}0\\\ 1\\\
-2\\\ 1\\\ \vdots\\\ 0\\\ 0\\\ 0\end{pmatrix},\begin{pmatrix}0\\\ 0\\\ 1\\\
-2\\\ \vdots\\\ 0\\\ 0\\\ 0\end{pmatrix},\cdots,\begin{pmatrix}0\\\ 0\\\ 0\\\
0\\\ \vdots\\\ -2\\\ 1\\\ 0\end{pmatrix},\begin{pmatrix}0\\\ 0\\\ 0\\\ 0\\\
\vdots\\\ 1\\\ -2\\\ 1\end{pmatrix}\right\\}$

Note that each of these basis vectors $h_{i}$ have only three nonzero entries.
We make use of these basis vectors in determining extremal values of variances
that a balanced $(n,k,r,c)$ job assignment can attain.

Based on the shape vectors, we now define certain special kinds of balanced
$(n,k,r,c)$ job assignments.

######  Definition 2.

A balanced $(n,k,r,c)$ assignment $D$ is compact if the corresponding shape
vector $h_{D}$ has at most two non-zero elements.

Under certain special conditions, there is a possibility that the shape vector
$h_{D}$ has only one nonzero entry. Of course, in this special case, every
possible pair of jobs is assigned together to $m$ servers, where
$m=\frac{ck(k-1)}{n(n-1)}=r\frac{k-1}{n-1}$. Clearly, the dependence of $m$ on
the values of $n,k,r$ forces such a possibility to be rare. So in general,
compact balanced $(n,k,r,c)$ job assignments have two nonzero entries.

######  Definition 2.

A balanced assignment $D$ is proximally compact if the shape vector $h_{D}$
has either exactly one nonzero entry or has exactly two consecutive nonzero
entries.

######  Lemma 1.

For proximally compact $(n,k,r,c)$ assignment $D$, we have
$\ell=\Bigl{\lfloor}\frac{r(k-1)}{n-1}\Bigr{\rfloor}$ where $\ell$ denotes the
index of the smallest non-zero entry in the shape vector $h_{D}$.

###### Proof.

For a proximally compact $(n,k,r,c)$ assignment $D$, if the shape vector has
only one nonzero entry, then $\mathfrak{m}^{D}(\ell)={n\choose 2}$. As the
total number of job pairs at the $c$ servers is $c{k\choose 2}$, therefore
using (20), we have $\ell=\frac{c{k\choose 2}}{{n\choose
2}}=\frac{r(k-1)}{n-1}$.

On the other hand, if a proximally compact $(n,k,r,c)$ assignment $D$, has a
shape vector with exactly two consecutive nonzero entries, then
$\mathfrak{m}^{D}(m)$ is zero for all $m\neq\ell,\ell+1$ for some $\ell$.
Using (19), we have $\mathfrak{m}^{D}(\ell+1)={{n\choose
2}}-\mathfrak{m}^{D}(\ell)$ and by (20), we get
$\ell(\mathfrak{m}^{D}(\ell))+(\ell+1)({{n\choose
2}}-\mathfrak{m}^{D}(\ell))=c{{k\choose 2}}$. Thus we can conclude that
$\ell{{n\choose 2}}\leq c{{k\choose 2}}$ and $(\ell+1){{n\choose
2}}>c{{k\choose 2}}$ (as $\mathfrak{m}^{D}(\ell)>0$) and therefore
$\ell=\Bigl{\lfloor}\frac{c.{{k\choose 2}}}{{{n\choose
2}}}\Bigr{\rfloor}=\Bigl{\lfloor}\frac{r(k-1)}{n-1}\Bigr{\rfloor}$. ∎

Given $n,k,r,c$ it is not clear whether a balanced $(n,k,r,c)$ job assignment
which is proximally compact exists. By Lemma 1, it is clear that there can be
only one shape vector in $\mathbb{N}^{r+1}$ that satisfies the condition of
proximal compactness. One can therefore conclude that there is at most only
one proximally compact balanced $(n,k,r,c)$ job assignment.

The special case of the shape vector having only one nonzero entry corresponds
to the case of balanced incomplete block designs (BIBD) (BOSE, 1939; Colbourn
and Dinitz, 2006). Balanced incomplete block designs is a very well studied
subject. For the sake of completeness, we give the definition of BIBD below.

######  Defintion 3.

(BIBD $(v,b,r,k,\lambda)$ scheme as in (Colbourn and Dinitz, 2006)) - A
balanced incomplete block design (BIBD) is a pair $(V,B)$ where V is a $v$-set
and B is a collection of $b$ $k$-sized subsets of $V$ (blocks) such that each
element of $V$ is contained in exactly $r$ blocks and any 2-subset of V is
contained in exactly $\lambda$ blocks.

Note that we can associate the set $V$ to the set of jobs $\mathcal{A}$. Thus
$v$ is the same as $n$ that we have employed so far. Each $k$ sized subset of
$V$ (or $\mathcal{A}$) can be identified to the set of jobs assigned to a
server. The number $r$ has the same interpretation as in our case. Since $B$
is a collection of $b$ $k$-sized sets, we can think of the number of servers
$c$ being equal to $b$. Finally $\lambda=\frac{r(k-1)}{n-1}$. Thus $(n,k,r,c)$
in our case is the same as $(v,b,r,k,\lambda)$ quoted in the definition of
BIBD above.

Even in cases where $n,k,r$ may lead to a $\lambda$ which is a positive
integer, it is not known whether a BIBD always exists. However, multiple
constructions of BIBD for various parameters have been described in (BOSE,
1939) using various techniques, like vector sub-spaces over finite fields etc.
The famous Bruck-Ryser-Chowla theorem in (Sprott, 1955) gives some necessary
conditions on $n,k,r$ that guarantees the existence of a BIBD.

Proximally compact assignments may be thought of as a generalization of BIBDs
that do not insist on a unique number $\lambda$, that represents the number of
servers to be shared by every pair of jobs. Instead proximally compact
assignments allow every pair of jobs to be assigned to either $\ell$ or
$\ell+1$ servers. As remarked earlier, Lemma 1 ensures that given $n,k,r,c$
there is a unique shape vector that can be constructed and therefore at most
only one proximally compact assignment can exist. We now provide an example of
a proximally compact assignment scheme that is not a BIBD.

######  Example 0.

Consider balanced $(9,3,3,9)$ assignment schemes. In this case,
$\frac{r(k-1)}{n-1}=\frac{3}{4}$ and so there is no BIBD possible. Further,
$\ell=0$ and the corresponding shape vector for a possible proximally compact
assignment should be $h_{D}=[9,27,0,0]^{T}$. We display an assignment scheme
in Table 2 whose shape vector is indeed $h_{D}$. Note that in this scheme, 27
pairs of jobs are assigned together to a server once and there are 9 pairs of
jobs that were never assigned together.

Jobs Servers | $s_{1}$ | $s_{2}$ | $s_{3}$ | $s_{4}$ | $s_{5}$ | $s_{6}$ | $s_{7}$ | $s_{8}$ | $s_{9}$
---|---|---|---|---|---|---|---|---|---
$a_{1}$ | 1 | 1 | 1 |  |  |  |  |  |
$a_{2}$ |  |  |  | 1 | 1 | 1 |  |  |
$a_{3}$ |  |  |  |  |  |  | 1 | 1 | 1
$a_{4}$ | 1 |  |  | 1 |  |  | 1 |  |
$a_{5}$ |  | 1 |  |  | 1 |  |  | 1 |
$a_{6}$ |  |  | 1 |  |  | 1 |  |  | 1
$a_{7}$ | 1 |  |  |  | 1 |  |  |  | 1
$a_{8}$ |  | 1 |  |  |  | 1 | 1 |  |
$a_{9}$ |  |  | 1 | 1 |  |  |  | 1 |
Table 2. Assignment of jobs to servers in a proximally minimally compact
$(9,3,3,9)$ assignment scheme

######  Theorem 5.

If a proximally compact balanced $(n,k,r,c)$ job assignment exists, then it
has the least variance amongst all balanced $(n,k,r,c)$ job assignments.

A proof sketch is presented below. A detailed proof is given in Appendix C.
Recall that in our notation $\mathbb{N}$ denotes the set of all non-negative
integers including 0.

###### Proof Sketch.

Let $h_{D}$ be the shape vector corresponding to the proximally compact
balanced $(n,k,r,c)$ job assignment. Thus $h_{D}(i)=0$ for all $i\leq\ell$ and
$i>\ell+2$ for $\ell$ as calculated in Lemma 1. Any balanced $(n,k,r,c)$ job
assignment $D_{1}$ would have a shape vector $h_{D}+v$ where $v\in\ker H$ with
matrix $H$ as defined in (26). Observe from the expression of variance in (22)
that it is only the term $\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)g(m,x)$ that
varies amongst the different balanced $(n,k,r,c)$ assignments. Thus it is
enough to show that for every permissible $v\in\ker H$ mentioned above,
$\sum\limits_{m=0}^{r}v(m+1)g(m,x)\geq 0$, in order to conclude that the
proximally compact balanced $(n,k,r,c)$ assignment has the least variance.

We therefore first characterize $v\in\ker H$ that may appear from some
balanced $(n,k,r,c)$ assignment. As both the shape vectors
$h_{D},h_{D}+v\in\mathbb{N}^{r+1}$, therefore $v(i)\geq 0$ for all
$i\neq\ell+1,\ell+2$. Further, as $v\in\ker H$, therefore
$\sum\limits_{i=1}^{r+1}v(i)=0$ and so if $v$ is a nonzero vector, then at
least one of $v(\ell+1),v(\ell+2)$ must be a negative integer. As $v\in\ker
H$, therefore $v$ can be expressed in terms of the basis vectors
$\left\\{h_{i}\right\\}$ listed in (27). Let
$v=\sum\limits_{i=1}^{r-1}\alpha_{i}h_{i}$ and we show 333A detailed proof
proving non-negativity of $\alpha_{i}$ is in Appendix C that all
$\alpha_{i}\in\mathbb{N}$.

As a result, we get

$\displaystyle\sum\limits_{m=0}^{r}v(m+1)g(m,x)=\sum\limits_{i=1}^{r-1}\alpha_{i}\left(g(i-1,x)-2g(i,x)+g(i+1,x)\right)$

By Lemma 3, we know that
$g(m+1,x)-g(m,x)={{c-2}\choose{x-1}}-2{{c-r-1}\choose{x-1}}+{{c-2r+m}\choose{x-1}}$
and therefore

(28) $\displaystyle g(i-1,x)-2g(i,x)+g(i+1,x)$ $\displaystyle=$
$\displaystyle\left(g(i+1,x)-g(i,x)\right)-\left(g(i,x)-g(i-1,x)\right)$
$\displaystyle=$
$\displaystyle{{c-2r+i}\choose{x-1}}-{{c-2r+i-1}\choose{x-1}}$
$\displaystyle=$
$\displaystyle\frac{x-1}{c-2r+i-x+1}{{c-2r+i-1}\choose{x-1}}\geq 0$

Thus we have

(29) $\displaystyle{}\sum\limits_{m=0}^{r}v(m+1)g(m,x)$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{r-1}\alpha_{i}\left(g(i-1,x)-2g(i,x)+g(i+1,x)\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{r-1}\frac{\alpha_{i}(x-1)}{c-2r+i-x+1}{{c-2r+i-1}\choose{x-1}}\geq
0$

As the above is true for every permissible $v\in\ker H$ such that $h_{D}+v$ is
a shape vector, therefore we conclude that proximally compact balanced
$(n,k,r,c)$ assignment has the least variance amongst all balanced $(n,k,r,c)$
assignments. ∎

The above theorem guarantees that if a proximally compact balanced $(n,k,r,c)$
assignment exists, then it has the least variance. Also note from (48) that
for the case $x=1$, the contribution due to every permissible $v\in\ker H$ is
zero and so all shape vectors give the same variance, which is zero. That is
consistent with what we have shown earlier. Similarly, note that for $x>c-r$,
every ${{c-2r+i-1}\choose{x-1}}$ is zero and therefore from (48) we can
conclude that every balanced $(n,k,r,c)$ assignment has the same variance when
one considers the cases of $x>c-r$.

We now provide an example of $(n,k,r,c)$ that does not have a proximally
compact assignment.

######  Example 0.

Consider balanced $(10,5,4,8)$ assignments. Here
$\frac{r(k-1)}{n-1}=\frac{16}{9}$ and so the shape vector must have at least
two nonzero entries. Moreover, $\ell=1$ and the corresponding shape vector for
a possible proximally compact assignment should be $h_{D}=[0,10,35,0,0]^{T}$.
We now show that an assignment with the shape vector $h_{D}$ does not exist.

As every job is assigned to $r=4$ servers, every job is involved in
$r(k-1)=16$ job pairs. Consider the job $a_{1}$ and let $x$ be the number of
other jobs with whom $a_{1}$ shares only one server. So $9-x$ jobs share two
servers each with $a_{1}$. Clearly $2(9-x)+x=16$ which implies that $x=2$. As
$a_{1}$ was an arbitrary choice, we can conclude that every job shares one
server with two other jobs and shares two servers with the other $7$ jobs.

Let $\mathfrak{G}=\left\\{a_{1},a_{2},a_{3},\cdots a_{i},a_{1}\right\\}$ be a
cycle of jobs such that each job shares only one server with the jobs that are
its predecessor and successor in $\mathfrak{G}$. One can now argue that the
only permissible lengths of these cycles can be either 5 or 10.444This follows
since there cannot exist a cycle of size 3 i.e. there cannot exist jobs $a,b$
and $c$ such that pairs $(a,b)$, $(b,c)$ and $(c,a)$ share a server each. Then
some more work proves that it is not possible to have an assignment with
$h_{D}=[0,10,35,0,0]^{T}$ The actual balanced $(10,5,4,8)$ assignments that
have shape vectors closest to $h_{D}$ have shape vectors $[1,8,36,0,0]^{T}$
and $[0,12,31,2,0]^{T}$ respectively.

We now define another class of compact assignments.

######  Definition 3.

A balanced assignment $D$ is stretched compact if the shape vector $h_{D}$ has
non-zero elements only in the first and the last entries.

If only the first and last entries of the shape vector $h_{D}$ are nonzero,
then by (26) it is clear that the last entry of the shape vector is
$\frac{c}{r}{k\choose 2}=\frac{n(k-1)}{2}$ and therefore the first entry of
the shape vector is $\frac{n(n-k)}{2}$. Of course, if $n$ is a odd number and
$k$ is even, then these calculated quantities are not integers and therefore
for such cases, there is no possibility of existence of a stretched compact
$(n,k,r,c)$ assignment. Even for the other cases, there is no guarantee that a
stretched compact $(n,k,r,c)$ assignment exists even though the shape vector
has integer entries.

######  Theorem 8.

If a stretched compact balanced $(n,k,r,c)$ job assignment exists, then it has
the largest variance amongst all balanced $(n,k,r,c)$ job assignments.

This proof goes along very similar lines to that of Theorem 5 and we prove in
Appendix D.

######  Example 0.

Let us revisit the earlier example of $(10,5,4,8)$ assignments. It is clear
that a shape vector corresponding to stretched compact assignment is
permissible, namely $h_{D}=[25,0,0,0,20]^{T}$. Such an assignment is indeed
possible. Divide the $10$ jobs into two sets of $5$ jobs. Assign each of these
sets of jobs to $4$ servers. That results in a total of $20$ pairs sharing $4$
servers each and the rest $25$ pairs consisting of a job each from the two
sets sharing no servers. This repetition assignment is a stretched compact
assignment and therefore has the largest variance amongst all possible
balanced $(10,5,4,8)$ assignments.

It is clear that this sort of repetition assignment where multiple servers
have the same set of jobs assigned is only possible if $k$ divides $n$. In
such a situation, one can subdivide the jobs into $\frac{n}{k}$ groups of $k$
jobs each. Each of these groups are repeated at $r$ servers, thus accounting
for $\frac{n}{k}r=c$ servers. Thus the number of job pairs that appear
together $r$ times is equal to $\frac{n}{k}{k\choose 2}=\frac{n(k-1)}{2}$. And
in all these cases, these repetition assignments would correspond to a
stretched compact assignment which has the largest variance amongst all
balanced $(n,k,r,c)$ assignments.

##  7\. Generalization where the number of servers that return ($x$) is random

We now look at a scenario where each of the $c$ servers is independently and
equally likely to communicate with the master with probability $p$. Note that
under this setup, the distribution of the number of servers $x$ that could
communicate is given by the binomial distribution $B(c,p)$. Observe that
conditioned on $x$, every subset of $x$ servers is equally likely to
communicate with the master. Under this setup, we can now state our results on
mean and variance on the number of distinct jobs received by the master.

######  Theorem 1.

Consider any balanced $(n,k,r,c)$ assignment $D$, where each server is
independently and equally likely to communicate with the master with
probability $p$. The expectation of the number of distinct completed jobs $d$
received is the same for every assignment $D$ amongst all balanced $(n,k,r,c)$
assignments and is given by

(30) $\mathbbm{E}_{D}[d]=n-n(1-p)^{r}$

and the variance is given by

(31) $\sigma_{D}(d)=\sum_{x=0}^{c}\sigma_{D,x}(d){{c\choose
x}}p^{x}(1-p)^{c-x}$

where $\sigma_{D,x}(d)$ is given by the expression in Equation (22).

###### Proof.

Observe that under this setup, the number of servers that communicates with
the master $x$ is be given by the binomial distribution $B(c,p)$. Also observe
that under this setup conditioned on $x$, any set of $x$ servers is equally
likely to communicate with the master.

We can thus say that

(32) $\displaystyle\mathbbm{E}_{D}[d]=$ $\displaystyle\mathbbm{E}_{x\sim
B(c,p)}\mathbbm{E}_{D,x}[d]$ (33)
$\displaystyle\overset{(a)}{=}\sum\limits_{x=0}^{c}n\left(1-\frac{{c-r\choose
x}}{{c\choose x}}\right){{c\choose x}}p^{x}(1-p)^{c-x}$ (34)
$\displaystyle=n-n(1-p)^{r}\sum\limits_{x=0}^{c}{{c-r\choose
x}}p^{x}(1-p)^{c-r-x}=n-n(1-p)^{r}$

Note $(a)$ follows from the expression of mean in Theorem 1. Using a very
similar technique, we can prove a result of $\sigma_{D}(d)$ as well. ∎

We can actually generalize some of our results in Theorem 5 and 8 for a more
generalized setup where the number of servers that return is not unique but is
sampled from some distribution $\mathcal{P}$. However, we ensure that the
subset $S_{1}$ is the set of servers that could communicate is equally likely
as the subset of servers $S_{2}$ that could communicate if $|S_{1}|=|S_{2}|$.
Formally, we study the setup where $x$ is sampled from a distribution
$\mathcal{P}$ and conditioned on $x$, any subset of $x$ servers is equally
likely to be the set of servers that could communicate with the master.

This precisely captures the case where every server is independently able to
communicate to the master with probability $p$, in which case $\mathcal{P}$
would be given by $B(c,p)$

######  Theorem 2.

Let us consider $x\sim\mathcal{P}$. Conditioned on $x$, we study the setup
where any set of $x$ servers is equally likely to communicate with the master.
Then the proximally compact assignment (if it exists) attains the least
variance on the number of distinct jobs received at master amongst all
balanced $(n,k,r,c)$ assignment schemes.

###### Proof.

Let us denote the number of distinct jobs when any set of $x$ servers return
uniformly at random by $d$. However, in our problem $x$ itself might be
sampled from a distribution $\mathcal{P}$. Let us denote the variance in this
set-up under this assignment of jobs to servers (say ${D}$) by
$\sigma_{{D},x\sim\mathcal{P}}(d)$.

Now using law of variances(Eve’s law), we can say that

$\sigma_{{D},x\sim\mathcal{P}}(d)=\mathbb{E}_{x\sim\mathcal{P}}[\sigma_{{D},x}(d)]+\sigma_{x\sim\mathcal{P}}[\mathbb{E}_{{D},x}(d)]$

Now consider assignments $D$ and ${D}_{1}$ such that assignment $D$ is a
proximally compact $(n,k,r,c)$ assignment scheme and assignment $D_{1}$ could
be any balanced $(n,k,r,c)$ assignment scheme.

However, we know from Theorem 5 that
$\sigma_{{D},x}(d)\leq\sigma_{{D}_{1},x}(d)$ for every $x$ if $D$ is a
proximally compact $(n,k,r,c)$ assignment scheme and assignment $D_{1}$ is any
other balanced $(n,k,r,c)$ assignment scheme.

We also know that $\mathbbm{E}_{{D},x}(d)=\mathbbm{E}_{{D}_{1},x}(d)$ from
Theorem 1. Combining the two properties, we get that
$\sigma_{{D},x\sim\mathcal{P}}(d)\leq\sigma_{{D}_{1},x\sim\mathcal{P}}(d)$
thus proving the theorem.

∎

Similarly, we can prove a result corresponding to that of Theorem 8 for this
setup.

######  Theorem 3.

Let us consider $x\sim\mathcal{P}$. Conditioned on $x$, if any set of $x$
servers is equally likely to communicate with the master, then the stretched
compact $(n,k,r,c)$ assignment scheme (if it exists) attains the largest
variance on the number of distinct jobs received at master amongst all
balanced $(n,k,r,c)$ assignment schemes.

##  8\. Conclusion

In this work, we study the mean and the variance of the number of distinct
jobs received at server under various assignment schemes and show that
assignment schemes based on the repetition coding and block designs attain the
largest and least variance respectively. However, it is not always known
whether such designs always exist and famous Bruck-Ryser-Chowla theorem in
(Sprott, 1955) just gives some necessary conditions. In future works, it would
be interesting to see if small modifications to designs are still close to
extremal variance in case they do not exist. Another direction of work could
be to extend results beyond the second moment to the $t^{th}$ moment and
investigate if constructions based on $t$-designs can attain extremal results.

##  9\. Acknowledgements

Most of this work was performed when SS was an undergraduate at Indian
Institute of Technology, Bombay. SS would like to thank Siddharth Chandak for
insightful discussions on Section 7.

## References

  * (1)
  * AWS ([n. d.]) [n. d.].  Distributed Computing AWS.  https://aws.amazon.com/what-is/distributed-computing/.
  * Goo ([n. d.]) [n. d.].  Distributed Computing Google Cloud.  https://cloud2data.com/distributed-computing-on-the-google-cloud-platform/.
  * Azu ([n. d.]) [n. d.].  Distributed Computing Microsoft Azure.  https://cloud2data.com/distributed-computing-in-microsoft-azure/.
  * Addelman (1969) Sidney Addelman. 1969\.  The generalized randomized block design.  _The American Statistician_ 23, 4 (1969), 35–36.
  * Aktas and Soljanin (2019) Mehmet Fatih Aktas and Emina Soljanin. 2019.  Straggler Mitigation at Scale.  _CoRR_ abs/1906.10664 (2019).  arXiv:1906.10664 http://arxiv.org/abs/1906.10664
  * Ammar et al. (2004) Bassem Ammar, Bahram Honary, Yu Kou, Jun Xu, and Shu Lin. 2004.  Construction of low-density parity-check codes based on balanced incomplete block designs.  _IEEE Transactions on information Theory_ 50, 6 (2004), 1257–1269.
  * Ananthanarayanan et al. (2013a) Ganesh Ananthanarayanan, Ali Ghodsi, Scott Shenker, and Ion Stoica. 2013a.  Effective Straggler Mitigation: Attack of the Clones. In _Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation_ (Lombard, IL) _(nsdi’13)_. USENIX Association, USA, 185–198.
  * Ananthanarayanan et al. (2013b) Ganesh Ananthanarayanan, Ali Ghodsi, Scott Shenker, and Ion Stoica. 2013b.  Effective straggler mitigation: Attack of the clones. In _10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)_. 185–198.
  * Arlitt and Williamson (1996) Martin F. Arlitt and Carey L. Williamson. 1996.  Web Server Workload Characterization: The Search for Invariants. In _Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems_ (Philadelphia, Pennsylvania, USA) _(SIGMETRICS ’96)_. Association for Computing Machinery, New York, NY, USA, 126–137.  https://doi.org/10.1145/233013.233034
  * Babu and Kumar (2015) Balaji Srinivasan Babu and P. Vijay Kumar. 2015.  On Partial Maximally-Recoverable and Maximally-Recoverable Codes.  _CoRR_ abs/1501.07130 (2015).  arXiv:1501.07130 http://arxiv.org/abs/1501.07130
  * BOSE (1939) R. C. BOSE. 1939\.  ON THE CONSTRUCTION OF BALANCED INCOMPLETE BLOCK DESIGNS.  _Annals of Eugenics_ 9, 4 (1939), 353–399.  https://doi.org/10.1111/j.1469-1809.1939.tb02219.x arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1469-1809.1939.tb02219.x
  * Bose and Nair (1939) Raj Chandra Bose and K Raghavan Nair. 1939.  Partially balanced incomplete block designs.  _Sankhyā: The Indian Journal of Statistics_ (1939), 337–372.
  * Chen et al. (2014) Shengbo Chen, Yin Sun, Longbo Huang, Prasun Sinha, Guanfeng Liang, Xin Liu, Ness B Shroff, et al. 2014\.  When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds. In _IEEE INFOCOM 2014-IEEE Conference on Computer Communications_. IEEE, 1042–1050.
  * Colajanni et al. (1998) Michele Colajanni, Philip S. Yu, and Daniel M Dias. 1998\.  Analysis of task assignment policies in scalable distributed Web-server systems.  _IEEE transactions on Parallel and Distributed Systems_ 9, 6 (1998), 585–600.
  * Colbourn and Dinitz (2006) Charles J. Colbourn and Jeffrey H. Dinitz. 2006.  _Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications)_.  Chapman & Hall/CRC.
  * Crovella and Bestavros (1997) M.E. Crovella and A. Bestavros. 1997.  Self-similarity in World Wide Web traffic: evidence and possible causes.  _IEEE/ACM Transactions on Networking_ 5, 6 (1997), 835–846.  https://doi.org/10.1109/90.650143
  * Crovella et al. (1998) Mark E Crovella, Murad S Taqqu, and Azer Bestavros. 1998\.  Heavy-tailed probability distributions in the World Wide Web.  _A practical guide to heavy tails_ 1 (1998), 3–26.
  * Dutta et al. (2017) S. Dutta, V. Cadambe, and P. Grover. 2017.  Coded convolution for parallel and distributed computing within a deadline. In _2017 IEEE International Symposium on Information Theory (ISIT)_. 2403–2407.  https://doi.org/10.1109/ISIT.2017.8006960
  * Ferdinand and Draper (2018) Nuwan Ferdinand and Stark C Draper. 2018.  Hierarchical coded computation. In _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 1620–1624.
  * Harchol-Balter (2000) Mor Harchol-Balter. 2000\.  Task assignment with unknown duration. In _Proceedings 20th IEEE international conference on distributed computing systems_. IEEE, 214–224.
  * Harchol-Balter et al. (1999) Mor Harchol-Balter, Mark E Crovella, and Cristina D Murta. 1999\.  On choosing a task assignment policy for a distributed server system.  _J. Parallel and Distrib. Comput._ 59, 2 (1999), 204–228.
  * Joshi et al. (2015) Gauri Joshi, Emina Soljanin, and Gregory Wornell. 2015\.  Queues with redundancy: Latency-cost analysis.  _ACM SIGMETRICS Performance Evaluation Review_ 43, 2 (2015), 54–56.
  * Joshi et al. (2017) Gauri Joshi, Emina Soljanin, and Gregory Wornell. 2017\.  Efficient Redundancy Techniques for Latency Reduction in Cloud Systems.  _ACM Trans. Model. Perform. Eval. Comput. Syst._ 2, 2, Article 12 (apr 2017), 30 pages.  https://doi.org/10.1145/3055281
  * Kadhe et al. (2019) Swanand Kadhe, O Ozan Koyluoglu, and Kannan Ramchandran. 2019\.  Gradient coding based on block designs for mitigating adversarial stragglers. In _2019 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2813–2817.
  * Karakus et al. (2019) Can Karakus, Yifan Sun, Suhas Diggavi, and Wotao Yin. 2019\.  Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning.  _Journal of Machine Learning Research_ 20, 72 (2019), 1–47.  http://jmlr.org/papers/v20/18-148.html
  * Kiefer (1975) J. Kiefer. 1975\.  Balanced Block Designs and Generalized Youden Designs, I. Construction (Patchwork).  _The Annals of Statistics_ 3, 1 (1975), 109 – 118.  https://doi.org/10.1214/aos/1176343002
  * Korhonen and Frossard (2009) Jari Korhonen and Pascal Frossard. 2009.  Flexible forward error correction codes with application to partial media data recovery.  _Signal Processing: Image Communication_ 24, 3 (2009), 229–242.  https://doi.org/10.1016/j.image.2008.12.005
  * Kshirsagar (1958) A. M. Kshirsagar. 1958\.  A Note on Incomplete Block Designs.  _The Annals of Mathematical Statistics_ 29, 3 (1958), 907–910.  http://www.jstor.org/stable/2237276
  * Lee et al. (2017) Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, and Kannan Ramchandran. 2017\.  Speeding up distributed machine learning using codes.  _IEEE Transactions on Information Theory_ 64, 3 (2017), 1514–1529.
  * Li and Avestimehr (2020) Songze Li and Salman Avestimehr. 2020.  Coded computing.  _Foundations and Trends® in Communications and Information Theory_ 17, 1 (2020).
  * Maity et al. (2019) Raj Kumar Maity, Ankit Singh Rawa, and Arya Mazumdar. 2019\.  Robust gradient descent via moment encoding and LDPC codes. In _2019 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2734–2738.
  * Mallick et al. (2020) Ankur Mallick, Malhar Chaudhari, Utsav Sheth, Ganesh Palanikumar, and Gauri Joshi. 2020\.  Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication. In _Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems_. 95–96.
  * Ozfatura et al. (2019) Emre Ozfatura, Deniz Gündüz, and Sennur Ulukus. 2019\.  Speeding Up Distributed Gradient Descent by Utilizing Non-persistent Stragglers. In _2019 IEEE International Symposium on Information Theory (ISIT)_. 2729–2733.  https://doi.org/10.1109/ISIT.2019.8849684
  * Ozfatura et al. (2021) Emre Ozfatura, Sennur Ulukus, and Deniz Gündüz. 2021\.  Coded distributed computing with partial recovery.  _IEEE Transactions on Information Theory_ 68, 3 (2021), 1945–1959.
  * Sakorikar and Wang (2021) Animesh Sakorikar and Lele Wang. 2021.  Variants on block design based gradient codes for adversarial stragglers. In _2021 11th International Symposium on Topics in Coding (ISTC)_. IEEE, 1–5.
  * Sarmasarkar et al. (2022) Sahasrajit Sarmasarkar, V Lalitha, and Nikhil Karamchandani. 2022\.  On gradient coding with partial recovery.  _IEEE Transactions on Communications_ 71, 2 (2022), 644–657.
  * Semchedine et al. (2011) Fouzi Semchedine, Louiza Bouallouche-Medjkoune, and Djamil Aissani. 2011\.  Task assignment policies in distributed server systems: A survey.  _Journal of network and Computer Applications_ 34, 4 (2011), 1123–1130.
  * Shieh and Jan (2004) Gwowen Shieh and Show-Li Jan. 2004.  The effectiveness of randomized complete block design.  _Statistica Neerlandica_ 58, 1 (2004), 111–124.
  * Smith (1968) KJC Smith. 1968\.  _An application of incomplete block designs to the construction of error-correcting codes_.  Technical Report. North Carolina State University. Dept. of Statistics.
  * Sprott (1955) D. A. Sprott. 1955\.  Balanced Incomplete Block Designs and Tactical Configurations.  _Ann. Math. Statist._ 26, 4 (12 1955), 752–758.  https://doi.org/10.1214/aoms/1177728433
  * Sun et al. (2019) Yuxuan Sun, Junlin Zhao, Sheng Zhou, and Deniz Gunduz. 2019\.  Heterogeneous Coded Computation across Heterogeneous Workers. In _2019 IEEE Global Communications Conference (GLOBECOM)_. 1–6.  https://doi.org/10.1109/GLOBECOM38437.2019.9014006
  * Szajda et al. (2005) Doug Szajda, Barry Lawson, and Jason Owen. 2005\.  Toward an Optimal Redundancy Strategy for Distributed Computations. In _2005 IEEE International Conference on Cluster Computing_. 1–11.  https://doi.org/10.1109/CLUSTR.2005.347045
  * Tandon et al. (2017) Rashish Tandon, Qi Lei, Alexandros G. Dimakis, and Nikos Karampatziakis. 2017.  Gradient Coding: Avoiding Stragglers in Distributed Learning. In _Proceedings of the 34th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 70)_ , Doina Precup and Yee Whye Teh (Eds.). PMLR, 3368–3376.  https://proceedings.mlr.press/v70/tandon17a.html
  * Wang et al. (2014) Da Wang, Gauri Joshi, and Gregory Wornell. 2014.  Efficient Task Replication for Fast Response Times in Parallel Computation.  _SIGMETRICS Perform. Eval. Rev._ 42, 1 (jun 2014), 599–600.  https://doi.org/10.1145/2637364.2592042
  * Wang et al. (2015) Da Wang, Gauri Joshi, and Gregory Wornell. 2015.  Using Straggler Replication to Reduce Latency in Large-Scale Parallel Computing.  _SIGMETRICS Perform. Eval. Rev._ 43, 3 (nov 2015), 7–11.  https://doi.org/10.1145/2847220.2847223
  * Wang et al. (2019a) Haozhao Wang, Song Guo, Bin Tang, Ruixuan Li, and Chengjie Li. 2019a.  Heterogeneity-aware Gradient Coding for Straggler Tolerance. In _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_. 555–564.  https://doi.org/10.1109/ICDCS.2019.00062
  * Wang et al. (2019b) Sinong Wang, Jiashang Liu, and Ness Shroff. 2019b.  Fundamental Limits of Approximate Gradient Coding.  _Proc. ACM Meas. Anal. Comput. Syst._ 3, 3, Article 52 (dec 2019), 22 pages.  https://doi.org/10.1145/3366700
  * Williams et al. (2005) Adepele Williams, Martin Arlitt, Carey Williamson, and Ken Barker. 2005.  Web workload characterization: Ten years later.  _Web content delivery_ (2005), 3–21.
  * Yang et al. (2019) Chien-Sheng Yang, Ramtin Pedarsani, and A. Salman Avestimehr. 2019\.  Timely-Throughput Optimal Coded Computing over Cloud Networks. In _Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing_ (Catania, Italy) _(Mobihoc ’19)_. Association for Computing Machinery, New York, NY, USA, 301–310.  https://doi.org/10.1145/3323679.3326528
  * Yeh (1986) Ching-Ming Yeh. 1986\.  Conditions for Universal Optimality of Block Designs.  _Biometrika_ 73, 3 (1986), 701–706.  http://www.jstor.org/stable/2336535
  * Yu et al. (2019) Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and Salman A Avestimehr. 2019.  Lagrange coded computing: Optimal design for resiliency, security, and privacy. In _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 1215–1225.
  * Yu et al. (2017) Qian Yu, Mohammad Ali Maddah-Ali, and A Salman Avestimehr. 2017\.  Polynomial codes: an optimal design for high-dimensional coded matrix multiplication. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_. 4406–4416.
  * Zhang et al. (2013) Qi Zhang, Mohamed Faten Zhani, Raouf Boutaba, and Joseph L. Hellerstein. 2013.  Harmony: Dynamic Heterogeneity-Aware Resource Provisioning in the Cloud. In _2013 IEEE 33rd International Conference on Distributed Computing Systems_. 510–519.  https://doi.org/10.1109/ICDCS.2013.28
  * Zhao et al. (2014) Xu Zhao, Ling Liu, Qi Zhang, and Xiaoshe Dong. 2014\.  Improving MapReduce Performance in a Heterogeneous Cloud: A Measurement Study. In _2014 IEEE 7th International Conference on Cloud Computing_. 400–407.  https://doi.org/10.1109/CLOUD.2014.61

##  Appendix A Assignment equivalence when number of servers equals number of
jobs

So far, we have been viewing the $(n,k,r,c)$ balanced assignment as a task of
assigning jobs to servers. Equivalently, one can also view the same balanced
assignment as assigning servers to jobs. Since every job is assigned to $r$
distinct servers, there is a total of ${r\choose 2}$ server pairs that can be
associated to each job. Like the shape vector $h_{D}$ that was built from
information about frequency of job-pairs at the servers in a given assignment,
one may build an equivalent shape vector based on frequency of server-pairs
that are associated to the jobs. Thus every server-pair can possibly be
associated to $m$ jobs, where $0\leq m\leq k$. Thus, the shape vector
corresponding to server assignment viewpoint would be a vector in
$\mathbb{N}^{k+1}$. One may now define compact balanced $(n,k,r,c)$ server
assignments as those balanced assignments that have server shape vector having
at most two nonzero entries. We may view proximally compact balanced
$(n,k,r,c)$ server assignment, through an analogous definition.

######  Definition 4.

Given a balanced $(n,k,r,c)$ assignment, we call it proximally compact
$(n,k,r,c)$ server assignment if for every pair of distinct servers $s_{i}$
and $s_{j}$ in $\mathcal{S}$, the number of jobs assigned to both $s_{i}$ and
$s_{j}$ simultaneously is exactly $\ell$ or $\ell+1$ for some integer $\ell$.

######  Lemma 2.

For any proximally compact $(n,k,r,c)$ server assignment, we must have
$\ell=\Bigl{\lfloor}\frac{n.{{r\choose 2}}}{{{c\choose 2}}}\Bigr{\rfloor}$

This lemma can be proved in a very similar way as that of Lemma 1.

We may observe that in general, proximally compact server assignment schemes
may not be proximally compact job assignment schemes. We demonstrate that with
an Example 1 below.

######  Example 0.

We now describe a proximally compact $(14,6,3,7)$ server assignment which is
not a proximally compact job assignment in Table 3. Note that in this scheme,
every pair of servers have exactly $2$ jobs in common and therefore proximally
compact server assignment. However, some pairs of jobs appear together in one
server like $(a_{1},a_{2})$, some pairs of jobs appear together in $2$ servers
like pairs of jobs $(a_{1},a_{8})$ and some pairs of jobs like
$(a_{3},a_{10})$ appear together in 3 servers and thus it is not proximally
compact job assignment.

Jobs Servers | $s_{1}$ | $s_{2}$ | $s_{3}$ | $s_{4}$ | $s_{5}$ | $s_{6}$ | $s_{7}$
---|---|---|---|---|---|---|---
$a_{1}$ |  | 1 |  | 1 |  | 1 |
$a_{2}$ | 1 |  |  | 1 | 1 |  |
$a_{3}$ |  |  | 1 | 1 |  |  | 1
$a_{4}$ | 1 | 1 | 1 |  |  |  |
$a_{5}$ |  | 1 |  |  | 1 |  | 1
$a_{6}$ | 1 |  |  |  |  | 1 | 1
$a_{7}$ |  |  | 1 |  | 1 | 1 |
$a_{8}$ | 1 |  |  | 1 |  | 1 |
$a_{9}$ |  | 1 |  | 1 | 1 |  |
$a_{10}$ |  |  | 1 | 1 |  |  | 1
$a_{11}$ | 1 | 1 | 1 |  |  |  |
$a_{12}$ | 1 |  |  |  | 1 |  | 1
$a_{13}$ |  | 1 |  |  |  | 1 | 1
$a_{14}$ |  |  | 1 |  | 1 | 1 |
Table 3. Assignment of jobs to various servers in a proximally compact
$(14,6,3,7)$ server assignment scheme

However, when $n=c$ our subsequent result shows that proximally compact server
assignment schemes and proximally compact job assignment schemes are
equivalent.

######  Theorem 2.

Amongst balanced $(n,k,k,n)$ assignments, every proximally compact $(n,k,k,n)$
job assignment is also a proximally compact server assignment and vice-versa.

To prove this theorem, we first prove Lemma 3.

We define a random variable $Y^{D}$ as follows for balanced $(n,k,r,c)$
assignment $D$ as the number of servers in which a pair of jobs chosen
uniformly at random occur together. Formally, we can say that

(35) ${}\mathbb{P}[Y^{D}=p]=\frac{\mathfrak{m}^{D}(p)}{{{n\choose
2}}}\text{for any integer $p\in[0,r]$}$

Observe that this is a valid distribution as
$\sum\limits_{p=0}^{r}\mathfrak{m}^{D}(p)={{n\choose 2}}$ in Equation (19).

######  Lemma 2.

For any balanced $(n,k,r,c)$ assignment $D$, the variance of $Y^{D}$ is
linearly proportional to the variance of distinct jobs $d$ received at master
when any 2 servers chosen uniformly at random return i.e. are able to
communicate their results to the master. We can also state it as follows.

(36) $\sigma_{D,2}(d)=\frac{{{n\choose 2}}\sigma(Y^{D})+\frac{\left(c{k\choose
2}\right)^{2}}{{n\choose 2}}+n\left({r\choose 2}\right)-c\left({k\choose
2}\right)}{{c\choose 2}}-\left(\frac{n{r\choose 2}}{{c\choose 2}}\right)^{2}$

Further for $n=c$, we can say that $\sigma(Y^{D})=\sigma_{D,2}(d)$

###### Proof.

Observe that
$g(0,x)=\sum\limits_{i=2}^{r+1}\sum\limits_{j=2}^{r+1}(i-1)(j-1){(c-2r)\choose(x-i-j)}{r\choose
i}{r\choose j}$ from equation (16) and therefore $g(0,2)=0$. Further, using
equation (17), we have $g(m+1,2)-g(m,2)=(c-2)-2(c-r-1)+(c-2r+m)=m$. Therefore,
$g(m,2)=1+2+\cdots+(m-1)=\frac{m(m-1)}{2}$.

Consider the numerator of first term in $\sigma_{D,x}(d)$ in equation (22)
which was shown to be
$2\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)g(m,x)+n\left(\sum\limits_{t=1}^{r-1}t^{2}{r\choose(t+1)}{(c-r)\choose(x-t-1)}\right)$.
Note that here we consider $x=2$ as we are considering the case when only two
servers communicate back to the master. So for $x=2$,

$\displaystyle
2\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)g(m,2)+n\left(\sum\limits_{t=1}^{k-1}t^{2}{r\choose(t+1)}{(c-r)\choose(2-t-1)}\right)=$
$\displaystyle\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)m(m-1)+n{r\choose 2}$
$\displaystyle\overset{(a)}{=}$
$\displaystyle\sum\limits_{m=0}^{r}m^{2}\mathfrak{m}^{D}(m)+n{r\choose
2}-c{k\choose 2}$

$(a)$ follows since $\sum\limits_{m=0}^{r}m\mathfrak{m}^{D}(m)=c{k\choose 2}$
in Equation (20).

Therefore,

(37) $\displaystyle{}\sigma_{D,2}(d)=$
$\displaystyle\frac{\sum\limits_{m=0}^{r}m^{2}\mathfrak{m}^{D}(m)+n{r\choose
2}-c{k\choose 2}}{{c\choose 2}}-\left(\frac{n{r\choose 2}}{{c\choose
2}}\right)^{2}$

Observe
$\mathbbm{E}[Y^{D}]=\frac{\sum_{m=0}^{r}m\mathfrak{m}^{D}(m)}{{{n\choose
2}}}=\frac{c{{k\choose 2}}}{{{n\choose 2}}}$ as
$\sum\limits_{m=0}^{r}m\mathfrak{m}^{D}(m)=c{k\choose 2}$ by equation (20) and
using the definition of $Y^{D}$ in Equation (35).

$\displaystyle{}\sigma(Y^{D})=$
$\displaystyle\mathbbm{E}[(Y^{D})^{2}]-(\mathbbm{E}[Y^{D}])^{2}$ (38)
$\displaystyle=$ $\displaystyle\frac{1}{{n\choose
2}}\sum_{m=0}^{r}m^{2}\mathfrak{m}^{D}(m)-\left(\frac{c{{k\choose
2}}}{{{n\choose 2}}}\right)^{2}$

Thus, using equations (A) and (37), we obtain the expression (36) in the
statement of the lemma. Further, when $n=c$, then $r=k$ and the two equations
(A) and (37) become equal. ∎

We now prove Theorem 2.

###### Proof.

Consider the set of balanced $(n,k,k,n)$ assignment schemes. Now recall
$Y^{D}$ denoted the number of servers where a pair of jobs chosen uniformly at
random occurs together and for $n=c$ and $k=r$, we have

(39) ${}\sigma_{D,2}(d)=\sigma(Y^{D}).$

Further $\mathbb{E}[Y^{D}]=\frac{n{{k\choose 2}}}{{{n\choose 2}}}$. Also,
observe from Theorem 1 (under $x=2,n=c$ and $k=r$ ) that

(40)
${}\mathbb{E}_{D,2}[d]=n\left(1-\frac{(n-k)(n-k-1)}{n(n-1)}\right)=\left(2k-n\frac{k(k-1)}{n(n-1)}\right)=\mathbb{E}_{D}[2k-Y^{D}]$

We first show that every proximally compact $(n,k,k,n)$ job assignment is also
a proximally compact server assignment scheme.

Suppose not and consider a balanced assignment scheme $D$ which is not a
proximally compact server assignment but is a proximally compact job
assignment. Now let us consider the scenario where $x=2$ (exactly 2 randomly
chosen servers) are able to communicate with the master. Now if $D$ is not a
proximally compact server assignment, then $d$ (the number of distinct jobs
received) can take at least two distinct integral values which are non-
consecutive, hence $2k-d$ also has a support of at least $2$ distinct non-
consecutive integral values. However the random variable $Y^{D}$ has a support
of at most 2 over two consecutive indices (since it is a proximally compact
job assignment). Now observe that random $2k-d$ and $Y^{D}$ have the same
expectation (shown above in Equation (40)). Therefore the variance of $2k-d$
is clearly more than that of $Y^{D}$ which contradicts equation (39).

Now we consider the reverse situation where a balanced assignment scheme is a
proximally compact server assignment but not proximally compact job
assignment. Again consider the scenario where $x=2$ (exactly 2 randomly chosen
servers) are able to communicate with the master. The number of distinct jobs
received at the master $d$ can take at most 2 consecutive values (as it is a
proximally compact server assignment) and therefore the random variable $2k-d$
has a support of at most 2 over two consecutive indices. Suppose the
assignment scheme is not proximally compact job assignment, $Y^{D}$ has a
support of at least 2 elements which are non consecutive. As the random
variables $Y^{D}$ and $2k-d$ have the same expectation according to (40),
hence the variance of $Y^{D}$ has to be clearly larger than that $2k-d$ which
is turn contradicts equation (39).

Thus, the set of proximally compact job assignments is identical to the set of
proximally compact server assignments. ∎

Thus, Theorem 2 ensures that when the number of servers equals the number of
jobs, proximally compact server assignment and proximally compact job
assignments minimise the variance of the number of distinct jobs received at
the server as shown in Theorem 2.

##  Appendix B Proof of Theorem 1

###### Proof.

The number of distinct jobs $d$ received by the master when servers in a
subset $\hat{S}$ (with $|\hat{S}|=x$) is able to communicate with the master
is given by

(41)
${}d=\left|\bigcup_{j\in\hat{S}}\text{supp}(A_{D}[:,j])\right|=\left(k\times
x-\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}\right)$

Note that the term
$\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}$
excludes those jobs which have been received multiple times from various
servers present in $\hat{S}$.

$\displaystyle{}\mathbb{E}_{D,x}[d]=\frac{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(k\times
x-\sum\limits_{i=1}^{n}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1})}{\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}1}{=}$ $\displaystyle k\times
x-\frac{\sum\limits_{i=1}^{n}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}}{{c\choose
x}}$ (42) $\displaystyle{=}$ $\displaystyle k\times
x-\frac{n\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}}{{c\choose
x}}$

Observe that for every job $a_{i}$ in a balanced $(n,k,r,c)$ assignment, the
quantity
$\sum\limits_{\hat{S}\subset\mathcal{S},|\hat{S}|=x}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}$
is the same, i.e., this summation is independent of $i$. We now show that the
quantity
$\sum\limits_{\hat{S}\subset\mathcal{S},|\hat{S}|=x}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}$
for any specified $x$, is the same for every balanced $(n,k,r,c)$ distribution
${D}$. We compute this sum by counting the number of subsets
$\hat{S}\subset\mathcal{S}$ of cardinality $x$ which additionally satisfies
the constraint on $\mathfrak{n}^{D}_{i,\hat{S}}=t$ (i.e. job $a_{i}$ is
present in exactly $t$ servers from $\hat{S}$) for every $t$ from $2$ to $r$
(as these cases deal with the job $a_{i}$ appearing more than once in the
subset $\hat{S}$).

$\displaystyle{}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}{=}\sum\limits_{t=1}^{r-1}\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x,\mathfrak{n}^{D}_{i,\hat{S}}=t+1\end{subarray}}t{=}\text{ }$
$\displaystyle\sum\limits_{t=1}^{r-1}t\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x,\mathfrak{n}^{D}_{i,\hat{S}}=t+1\end{subarray}}1$ (43)
$\displaystyle\overset{(a)}{=}$
$\displaystyle\sum\limits_{t=1}^{r-1}t{r\choose(t+1)}{(c-r)\choose(x-t-1)}$

The last equality $(a)$ comes from counting the number of subsets
$\hat{S}\subset\mathcal{S}$ of cardinality $x$ that contain precisely $t+1$
servers that were assigned the job $a_{i}$. Consider the following binomial
expressions

(44) ${}ry(1+y)^{r-1}+1-{(1+y)^{r}}=\sum\limits_{t=0}^{r-1}t{{r\choose
t+1}}y^{t+1}$

(45) ${}(1+y)^{c-r}=\sum\limits_{u=0}^{c-r}{{c-r\choose u}}y^{u}$

Multiplying equations (44) and (45), one observes that
$\sum\limits_{t=1}^{r-1}t{r\choose(t+1)}{(c-r)\choose(x-t-1)}$ is precisely
the coefficient of $y^{x}$ in $ry(1+y)^{c-1}+{(1+y)^{c-r}}-{(1+y)^{c}}$. Thus,

(46)
${}\sum\limits_{t=1}^{r-1}t{r\choose(t+1)}{(c-r)\choose(x-t-1)}=r\times{{c-1\choose
x-1}}+{{c-r\choose x}}-{{c\choose x}}$

Combining equations (B), (B) and (46), we get

$\mathbbm{E}_{D,x}[d]=k\times x-\frac{n\left(r\times{{c-1\choose
x-1}}+{{c-r\choose x}}-{{c\choose x}}\right)}{{{c\choose
x}}}=n\left(1-\frac{{{c-r\choose x}}}{{{c\choose x}}}\right)$

∎

##  Appendix C Proof of Theorem 5

###### Proof.

Let $h_{D}$ be the shape vector corresponding to the proximally compact
balanced $(n,k,r,c)$ job assignment. Thus $h_{D}(i)=0$ for all $i\leq\ell$ and
$i>\ell+2$ for $\ell$ as calculated in Lemma 1. Any balanced $(n,k,r,c)$ job
assignment $D_{1}$ would have a shape vector $h_{D}+v$ where $v\in\ker H$ with
matrix $H$ as defined in (26). Observe from the expression of variance in (22)
that it is only the term $\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)g(m,x)$ that
varies amongst the different balanced $(n,k,r,c)$ assignments. Thus it is
enough to show that for every permissible $v\in\ker H$ mentioned above,
$\sum\limits_{m=0}^{r}v(m+1)g(m,x)\geq 0$, in order to conclude that the
proximally compact balanced $(n,k,r,c)$ assignment has the least variance.

We therefore first characterize $v\in\ker H$ that may appear from some
balanced $(n,k,r,c)$ assignment. As both the shape vectors
$h_{D},h_{D}+v\in\mathbb{N}^{r+1}$, therefore $v(i)\geq 0$ for all
$i\neq\ell+1,\ell+2$. Further, as $v\in\ker H$, therefore
$\sum\limits_{i=1}^{r+1}v(i)=0$ and so if $v$ is a nonzero vector, then at
least one of $v(\ell+1),v(\ell+2)$ must be a negative integer. As $v\in\ker
H$, therefore $v$ can be expressed in terms of the basis vectors
$\left\\{h_{i}\right\\}$ listed in (27). Let
$v=\sum\limits_{i=1}^{r-1}\alpha_{i}h_{i}$. We now show that all
$\alpha_{i}\in\mathbb{N}$.

Consider the components of $v$ for $i\leq\ell$. Let $j$ be the smallest index
where $v(j)>0$ and $j\leq\ell$. Then one can inductively argue that
$\alpha_{i}=0$ for all $i<j$ by starting with $i=1$ as $v(i)=0$ for $i<j$.
Further, $\alpha_{j}=v(j)>0$. Now, $v(j+1)=\alpha_{j+1}-2\alpha_{j}\geq 0$
implies that $\alpha_{j+1}\geq 2\alpha_{j}$. Similarly,
$v(j+2)=\alpha_{j+2}-2\alpha_{j+1}+\alpha_{j}$, which implies
$\alpha_{j+2}\geq 2\alpha_{j+1}-\alpha_{j}\geq 3\alpha_{j}$ as $v(j+2)\geq 0$.
On the same lines, $\alpha_{j+3}\geq 2\alpha_{j+2}-\alpha_{j+1}\geq
2(2\alpha_{j+1}-\alpha_{j})-\alpha_{j+1}=3\alpha_{j+1}-2\alpha_{j}\geq
4\alpha_{j}$. Inductively, one can show that $\alpha_{j+k}\geq(k+1)\alpha_{j}$
for all $k\leq(\ell-j)$. Thus $\alpha_{i}\geq 0$ for all $1\leq i\leq\ell$.
This accounts for all $v(i)\geq 0$ for $i\leq\ell$.

Similarly, one can utilize $v(i)\geq 0$ for $i>\ell+2$ to conclude that
$\alpha_{i}\geq 0$ for $\ell+1\leq i\leq r-1$, by proceeding from the other
end. Let $j$ now be the largest index where $v(j)>0$ and $j>\ell+2$. If
$j<r+1$, then $v(r+1)=0$ forces $\alpha_{r-1}=0$. Once again, one can
inductively argue that $\alpha_{i}=0$ for $j-1\leq i\leq r-1$ as the
corresponding $v(i+2)=0$. Further, $\alpha_{j-2}=v(j)>0$. Now,
$v(j-1)=\alpha_{j-3}-2\alpha_{j-2}\geq 0$ implies that $\alpha_{j-3}\geq
2\alpha_{j-2}$. Using $v(j-2)\geq 0$, one obtains $\alpha_{j-4}\geq
2\alpha_{j-3}-\alpha_{j-2}\geq 3\alpha_{j-2}$. Reflecting the argument used
before, one can conclude that $\alpha_{j-2-k}\geq(k+1)\alpha_{j-2}$ for $0\leq
k\leq(j-\ell-3)$ and so $\alpha_{i}\geq 0$ for $\ell+1\leq i\leq r-1$. Thus
all $\alpha_{i}\in\mathbb{N}$.

As a result, we get

$\displaystyle\sum\limits_{m=0}^{r}v(m+1)g(m,x)=\sum\limits_{i=1}^{r-1}\alpha_{i}\left(g(i-1,x)-2g(i,x)+g(i+1,x)\right)$

By Lemma 3, we know that
$g(m+1,x)-g(m,x)={{c-2}\choose{x-1}}-2{{c-r-1}\choose{x-1}}+{{c-2r+m}\choose{x-1}}$
and therefore

(47) $\displaystyle g(i-1,x)-2g(i,x)+g(i+1,x)$ $\displaystyle=$ $\displaystyle
g(i+1,x)-g(i,x)-\left\\{g(i,x)-g(i-1,x)\right\\}$ $\displaystyle=$
$\displaystyle{{c-2r+i}\choose{x-1}}-{{c-2r+i-1}\choose{x-1}}$
$\displaystyle=$
$\displaystyle\frac{x-1}{c-2r+i-x+1}{{c-2r+i-1}\choose{x-1}}\geq 0$

Thus we have

(48) $\displaystyle{}\sum\limits_{m=0}^{r}v(m+1)g(m,x)$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{r-1}\alpha_{i}\left(g(i-1,x)-2g(i,x)+g(i+1,x)\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{r-1}\frac{\alpha_{i}(x-1)}{c-2r+i-x+1}{{c-2r+i-1}\choose{x-1}}\geq
0$

As the above is true for every permissible $v\in\ker H$ such that $h_{D}+v$ is
a shape vector, therefore we conclude that proximally compact balanced
$(n,k,r,c)$ assignment has the least variance amongst all balanced $(n,k,r,c)$
assignments. ∎

##  Appendix D Proof of Theorem 8

###### Proof.

Let $h_{D}$ be the shape vector corresponding to a stretched compact balanced
$(n,k,r,c)$ job assignment. Then $h_{D}(i)=0$ for all $i\neq 1,r+1$. Any
balanced $(n,k,r,c)$ job assignment $D_{1}$ has a shape vector $h_{D}+v$ where
$v\in\ker H$ with $H$ as defined in (26). Similar to the proof of Theorem 5,
we now characterize $v\in\ker H$ that can arise from some balanced $(n,k,r,c)$
assignment. Note that $v(i)\geq 0$ for all $i\neq 1,r+1$ and
$\sum\limits_{i=1}^{r+1}v(i)=0$. Hence $v(1)\leq 0$ and $v(r+1)\leq 0$. As
$v\in\ker H$, therefore $v=\sum\limits_{i=1}^{r-1}\alpha_{i}h_{i}$ where
$\left\\{h_{i}\right\\}$ is the basis for $\ker H$ as listed in (27).
Following the proof of Theorem 5, it is now enough to show that all
$\alpha_{i}\leq 0$ for any permissible nonzero vector $v\in\ker H$ since the
expression in (48) would then be rendered negative, thereby signalling a
decrease in the variance for all balanced $(n,k,r,c)$ assignments with shape
vector $h_{D}+v$.

Observe that as $v(1)\leq 0$, therefore $\alpha_{1}=v(1)\leq 0$. If $r=2$,
then $\ker H$ is one dimensional and therefore $v(1)=v(3)\leq 0$, while
$v(2)=-2v(1)\geq 0\geq v(1)$. If $r>2$, then as $v(2)\geq 0$ and
$v(2)=\alpha_{2}-2\alpha_{1}$, therefore $\alpha_{2}\geq 2\alpha_{1}$. Now if
$r=3$, then $\ker H$ is two dimensional and $\alpha_{2}=v(4)\leq 0$. Further,
$v(3)\geq 0$ implies $\alpha_{1}-2\alpha_{2}\geq 0$ and therefore
$\alpha_{1}\geq 2\alpha_{2}$. Thus again, for $r=3$, both
$\alpha_{1},\alpha_{2}$ are negative and their values are mutually bound by
the constraints $\frac{\alpha_{1}}{2}\geq\alpha_{2}\geq 2\alpha_{1}$ and
$\frac{\alpha_{2}}{2}\geq\alpha_{1}\geq 2\alpha_{2}$.

Now, we consider the cases of $r>3$. In this case, $v(3)\geq 0$ translates to
$2\alpha_{2}\leq\alpha_{1}+\alpha_{3}$. Therefore $4\alpha_{2}\leq
2\alpha_{1}+2\alpha_{3}\leq\alpha_{2}+2\alpha_{3}$ (by using the condition
obtained from $v(2)\geq 0$) which in turn translates to $3\alpha_{2}\leq
2\alpha_{3}$. From the condition $v(4)\geq 0$, we get
$2\alpha_{3}\leq\alpha_{2}+\alpha_{4}$ which can now be manipulated to
$6\alpha_{3}\leq 3\alpha_{2}+3\alpha_{4}\leq 2\alpha_{3}+3\alpha_{4}$ which
gives us $4\alpha_{3}\leq 3\alpha_{4}$. Following the steps mentioned above,
one can use the subsequent $v(k)\geq 0$ to show that
$k\alpha_{k-1}\leq(k-1)\alpha_{k}$ for $2\leq k\leq(r-1)$. Combining all these
inequalities, one gets
$\alpha_{1}\leq\frac{\alpha_{2}}{2}\leq\frac{\alpha_{3}}{3}\leq\cdots\leq\frac{\alpha_{k}}{k}\leq\cdots\leq\frac{\alpha_{r-1}}{r-1}\leq
0$. This proves that all the $\alpha_{i}\leq 0$. ∎

Interestingly, in the proof above, one could have started from the other end
and as already shown for the case $r=3$, one can get another set of
constraints
$\alpha_{r-1}\leq\frac{\alpha_{r-2}}{2}\leq\cdots\leq\frac{\alpha_{r-k}}{k}\leq\cdots\leq\frac{\alpha_{1}}{r-1}\leq
0$. These interwoven constraints restrict the possible values for the
$\alpha_{i}$ where $v=\sum\limits_{i=1}^{r-1}\alpha_{i}h_{i}$.

##  Appendix E Proof of Claim 2

###### Proof.

Consider a pair of jobs $(a_{i},a_{j})$ such that no server has been assigned
both $a_{i}$ and $a_{j}$ together. Therefore there are precisely $r$ servers
that have been assigned $a_{i}$ and not $a_{j}$. Another $r$ servers that are
assigned $a_{j}$ but not $a_{i}$ while the remaining $c-2r$ servers are
assigned neither $a_{i}$ nor $a_{j}$. Then

(49) $g(0,x)=\sum\limits_{\begin{subarray}{c}\hat{S}\subset\mathcal{S};\\\
|\hat{S}|=x\end{subarray}}(\mathfrak{n}^{D}_{i,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{i,\hat{S}}>1}(\mathfrak{n}^{D}_{j,\hat{S}}-1)\mathbbm{1}_{\mathfrak{n}^{D}_{j,\hat{S}}>1}=\sum_{t=2}^{r}\sum_{u=2}^{r}(t-1)(u-1){r\choose
t}{r\choose u}{c-2r\choose x-t-u}$

Clearly any subset of servers $\hat{S}\subset\mathcal{S}$ of cardinality $x$
that has at most only one instance of the job $a_{i}$ assigned amongst its
members does not contribute to the sum. Ditto for $a_{j}$. Therefore, one
needs to consider only those subsets $\hat{S}$ of servers that contain at
least two servers that are assigned $a_{i}$ and at least two servers that are
assigned $a_{j}$. In the final expression of equation (49), ${r\choose
t}{r\choose u}{c-2r\choose x-t-u}$ counts the number of subsets of servers
$\hat{S}$ of cardinality $x$ that contain $t$ servers assigned $a_{i}$, $u$
servers assigned $a_{j}$ and $x-t-u$ servers that have been assigned neither.
The summation limits ensure that there are at least $2$ servers assigned
$a_{i}$ and at least $2$ servers assigned $a_{j}$. The expression $(t-1)(u-1)$
is the contribution of each subset $\hat{S}$ that contains $t$ copies of
$a_{i}$ and $u$ copies of $a_{j}$ assigned to its members. A closed form
solution of the expression for $g(0,x)$ can be obtained by considering

(50) ${}ry(1+y)^{r-1}+1-(1+y)^{r}=\sum_{t=1}^{r}(t-1){{r\choose t}}y^{t}$

(51) ${}ry(1+y)^{r-1}+1-(1+y)^{r}=\sum_{u=1}^{r}(u-1){{r\choose u}}y^{u}$

(52) ${}(1+y)^{c-2r}=\sum_{v=0}^{c-2r}{{c-2r\choose v}}y^{v}$

Multiplying these three expressions (50), (51) and (52), we get
$\sum_{t=2}^{r}\sum_{u=2}^{r}(t-1)(u-1){{c-2r\choose x-t-u}}{{r\choose
t}}{{r\choose u}}$ to be the coefficient of $y^{x}$ in
$\left(ry(1+y)^{r-1}+1-(1+y)^{r}\right)^{2}(1+y)^{c-2r}$.

$\displaystyle\sum_{t=2}^{r}\sum_{u=2}^{r}(t-1)(u-1){{c-2r\choose
x-t-u}}{{r\choose t}}{{r\choose u}}$ (53) $\displaystyle=$ $\displaystyle
r^{2}{{c-2\choose x-2}}-2r{{c-1\choose x-1}}+{{c\choose x}}-2{{c-r\choose
x}}+2r{{c-r-1\choose x-1}}+{c-2r\choose x}$

∎

##  Appendix F Proof of Claim 3

###### Proof.

Let us consider a pair of jobs $(a_{i},a_{j})$ that have been assigned
together to precisely $m$ servers. Without loss of generality, let
$s_{1},s_{2},\cdots,s_{m}$ be the servers that are assigned both the jobs
$a_{i},a_{j}$. Let $s_{m+1},s_{m+2},\cdots,s_{r}$ be the servers that have
been assigned $a_{i}$ but not $a_{j}$. Assume servers
$s_{r+1},s_{r+2},\cdots,s_{2r-m}$ are the servers assigned $a_{j}$ but not
$a_{i}$. The last $c-2r+m$ servers $s_{2r-m+1},s_{2r-m+2},\cdots,s_{c}$ are
the ones that have not been assigned $a_{i}$ or $a_{j}$.

Let another pair of jobs $(a_{i_{1}},a_{j_{1}})$ be such that they have been
assigned together to precisely $m+1$ servers. We now consider a bijective map
$f:\mathcal{S}\rightarrow\mathcal{S}$ described in the following fashion. Let
$f(s_{\ell})$ for $1\leq\ell\leq m+1$ be servers that have been assigned both
the jobs $a_{i_{1}}$ and $a_{j_{1}}$. Let $f(s_{\ell})$ for $m+2\leq\ell\leq
r$ be servers that have been assigned $a_{i_{1}}$ but not $a_{j_{1}}$. Further
let $f(s_{\ell})$ for $r+2\leq\ell\leq 2r-m$ be servers that have been
assigned $a_{j_{1}}$ but not $a_{i_{1}}$. The rest of $f(s_{\ell})$ have not
been assigned $a_{i_{1}}$ or $a_{j_{1}}$. Thus there are two special servers,
namely $s_{m+1}$ (which does job $a_{i}$ but not $a_{j}$) and $s_{r+1}$ (which
does job $a_{j}$ but not $a_{i}$), and whose images $f(s_{m+1})$ (which does
both the jobs $a_{i_{1}}$ and $a_{j_{1}}$) and $f(s_{r+1})$ (which does
neither $a_{i_{1}}$ nor $a_{j_{1}}$) that we shall pay special attention to.

For any $\hat{S}\subset\mathcal{S}$ of cardinality $x$, let us compare its
contribution to the sum $g(m,x)$ with the contribution of $f(\hat{S})$ towards
$g(m+1,x)$. Clearly, if
$\hat{S}\subset\mathcal{S}\setminus\left\\{s_{m+1},s_{r+1}\right\\}$, then the
contribution of $\hat{S}$ towards $g(m,x)$ is exactly the same as the
contribution of $f(\hat{S})$ to $g(m+1,x)$. Similarly, if
$s_{m+1},s_{r+1}\in\hat{S}$, then contribution of $\hat{S}$ towards $g(m,x)$
and that of $f(\hat{S})$ towards $g(m+1,x)$ is exactly the same. Therefore it
suffices to only consider those subsets $\hat{S}$ of cardinality $x$ that
contain exactly one of the two special servers
$\left\\{s_{m+1},s_{r+1}\right\\}$ to evaluate the difference
$g(m+1,x)-g(m,x)$. Hence we look at subsets $\hat{S}$ that are formed by
taking either $s_{m+1}$ or $s_{r+1}$ along with
$\bar{S}\subset\mathcal{S}\setminus\left\\{s_{m+1},s_{r+1}\right\\}$ of
cardinality $x-1$.

Let $\bar{S}\subset\mathcal{S}\setminus\left\\{s_{m+1},s_{r+1}\right\\}$ of
cardinality $x-1$ contain $\alpha>0$ instances of job $a_{i}$ and $\beta>0$
instances of job $a_{j}$ assigned to its servers. Then
$\bar{S}\cup\\{s_{m+1}\\}$ contributes $\alpha(\beta-1)$ towards $g(m,x)$,
whereas $\bar{S}\cup\\{s_{r+1}\\}$ contributes $(\alpha-1)\beta$ towards
$g(m,x)$. At the same time, $f(\bar{S})\cup\\{f(s_{m+1})\\}$ contributes
$\alpha\beta$ towards $g(m+1,x)$, whereas $f(\bar{S})\cup\\{f(s_{r+1})\\}$
contributes $(\alpha-1)(\beta-1)$ towards $g(m+1,x)$. Thus, one can evaluate
the contribution of $\bar{S}$ towards the difference $g(m+1,x)-g(m,x)$ to be
$\alpha\beta+(\alpha-1)(\beta-1)-\alpha(\beta-1)-(\alpha-1)\beta=1$. So every
subset $\bar{S}\subset\mathcal{S}\setminus\\{s_{m+1},s_{r+1}\\}$ of
cardinality $x-1$, whose servers have at least one instance each of jobs
$a_{i}$ and $a_{j}$ assigned to them, contributes a net change of $1$ towards
the difference $g(m+1,x)-g(m,x)$. One needs to just count the number of
subsets $\bar{S}$ of cardinality $x-1$ that satisfy these conditions to find
$g(m+1,x)-g(m,x)$.

Total number of subsets of cardinality $x-1$ of the set
$\mathcal{S}\setminus\\{s_{m+1},s_{r+1}\\}$ is given by ${c-2\choose x-1}$. If
the subset $\bar{S}$ is one of the ${c-r-1\choose x-1}$ subsets chosen from
the servers $\\{s_{r+2},s_{r+3},\cdots s_{c}\\}$, then the job $a_{i}$ is not
assigned to any of its servers. Similarly, if $\bar{S}$ is one of the
${c-r-1\choose x-1}$ chosen from the servers
$\\{s_{m+2},s_{m+3},\cdots,s_{r}\\}\cup\\{s_{2r-m+1},s_{2r-m+2},\cdots,s_{c}\\}$,
then it does not have any instance of the job $a_{j}$ assigned to its servers.
As these subsets $\bar{S}$ do not contribute to the difference
$g(m+1,x)-g(m,x)$, their numbers have to be subtracted from ${c-2\choose
x-1}$. In the process,
$\bar{S}\subset\\{s_{2r-m+1},s_{2r-m+2},\cdots,s_{c}\\}$ have been subtracted
twice and therefore ${c-2r+m\choose x-1}$ needs to added back (inclusion-
exclusion principle), thereby giving

$g(m+1,x)-g(m,x)={c-2\choose x-1}-2{c-r-1\choose x-1}+{c-2r+m\choose x-1}$

∎

##  Appendix G Proof of Corollary 1

######  Corollary 1.

For $x>c-r$ , the expression of $\sigma_{D,x}(d)$ in Equation (22) in Theorem
4 goes to zero.

###### Proof.

Recall the expression of $\sigma_{D,x}(d)$ from Equation (22). Observe that
expression $g(m+1,x)-g(m,x)$ from Equation (17) would be ${{c-2\choose x-1}}$
for $x>c-r$ as the second and third term in equation (17) goes to zero since
$p\leq r$ and $x>c-r$.

(54) ${}g(m+1,x)-g(m,x)={{c-2\choose x-1}}$

Let us now compute $g(0,x)$ using the expression in (49) and (16) for $x>c-r$.

(55) ${}g(0,x)=\sum_{i=2}^{r+1}\sum_{j=2}^{r+1}(i-1)(j-1){{c-2r\choose
x-i-j}}=r^{2}{{c-2\choose x-2}}-2r{{c-1\choose x-1}}+{{c\choose x}}$

Thus, from equations (54) and (55), we get

(56) ${}g(m,x)=r^{2}{{c-2\choose x-2}}-2r{{c-1\choose x-1}}+{{c\choose
x}}+m\times{{c-2\choose x-1}}$

Since, $x>c-r$, we may claim that the term $T_{2}(n,k,r,c)$ in Equation (22)
in Thoerem 4 goes as follows.

(57)
${}T_{2}(n,k,r,c)=\sum\limits_{t=1}^{r-1}t^{2}{r\choose(t+1)}{(c-r)\choose(x-t-1)}=\left(r(r-1){{c-2\choose
x-2}}-r{{c-1\choose x-1}}+{{c\choose x}}\right)$

Also observe that since $x>c-r$ the term ${{c-r\choose x}}$ goes to zero,
hence not written in equation (14). Thus the numerator of the first term in
equation (22) in Thoerem 4 is given by (from equations (55) and (56) and (57))

$\displaystyle
2.\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)g(m,x)+n\sum\limits_{t=1}^{r-1}t^{2}{r\choose(t+1)}{(c-r)\choose(x-t-1)}$
$\displaystyle=$
$\displaystyle\sum\limits_{m=0}^{r}\Biggl{(}2\mathfrak{m}^{D}(m)\left(r^{2}{{c-2\choose
x-2}}-2r{{c-1\choose x-1}}+{{c\choose
x}}\right)+2m\mathfrak{m}^{D}(m){{c-2\choose x-1}}\Biggr{)}$
$\displaystyle\hskip 180.00027pt+n\left(r(r-1){{c-2\choose x-2}}-r{{c-1\choose
x-1}}+{{c\choose x}}\right)$
$\displaystyle\overset{(a)}{=}\left(r^{2}{{c-2\choose x-2}}-2r{{c-1\choose
x-1}}+{{c\choose x}}\right)n(n-1)+{{c-2\choose x-1}}ck(k-1)$
$\displaystyle\hskip 180.00027pt+n\left(r(r-1){{c-2\choose x-2}}-r{{c-1\choose
x-1}}+{{c\choose x}}\right)$ $\displaystyle\overset{(b)}{=}{{c-2\choose
x-2}}(nr(nr-1))+{{c-2\choose x-1}}ck(k-1)-{{c-1\choose
x-1}}(nr(2n-1))+n^{2}{{c\choose x}}$
$\displaystyle\overset{(c)}{=}{{c-2\choose x-2}}n^{2}r^{2}+{{c-2\choose
x-1}}ck^{2}-{{c-1\choose x-1}}(nr(2n))+n^{2}{{c\choose x}}$
$\displaystyle\overset{(d)}{=}{{c-1\choose x-1}}{nr\times kx}-{{c-1\choose
x-1}}(nr(2n))+n^{2}{{c\choose x}}$ $\displaystyle\overset{(e)}{=}{{c\choose
x}}\left(\left(\frac{nrx}{c}\right)^{2}-2n\left(\frac{nrx}{c}\right)+n^{2}\right)$
(58) $\displaystyle\overset{(f)}{=}{{c\choose
x}}\left(n\times\left(\frac{rx}{c}-1\right)\right)^{2}$

We now argue for each of the steps below.

  * •

$(a)$ follows since
$\sum\limits_{m=0}^{r}m\times\mathfrak{m}^{D}(m)=c{{k\choose 2}}$ and
$\sum\limits_{m=0}^{r}\mathfrak{m}^{D}(m)={{n\choose 2}}$ in Equations (19)
and (20)

  * •

$(b)$ follows by combining the coefficints of ${{c-2\choose x-2}}$,
${c-1\choose x-1}$ and ${c\choose x}$.

  * •

$(c)$ follows as $nr{{c-2\choose x-2}}+kc{{c-2\choose x-1}}=nr{{c-1\choose
x-1}}$. This can be explained by the fact that $n\times r=k\times c$.

  * •

$(d)$ follows from the following set of equalities

$\displaystyle{{c-2\choose x-2}}n^{2}r^{2}+{{c-2\choose x-1}}ck^{2}=$
$\displaystyle\frac{(c-1)!}{(x-2)!}{(c-x-1)!}\left(\frac{ck}{c-x}+\frac{k}{x-1}\right)$
$\displaystyle=$ $\displaystyle\frac{(c-1)!\times nr\times
kx(c-1)}{(x-2)!(c-x)(x-1)}=nr\times kx{{c-1\choose x-1}}$

  * •

$(e)$ and $(f)$ follow from the fact that $n\times r=k\times c$

Now, observe the second term of $\sigma_{D,x}(d)$ in equation (22) and we see
that $T_{1}(n,k,r,c)=n\times\left(\frac{rx}{c}-1\right)$ as $x>c-r$. Thus,
using equation (G), we can say that $\sigma_{D,x}(d)=0$ for $x>c-r$.

∎