#  FedGS: Federated Graph-based Sampling with Arbitrary Client Availability

Zheng Wang,1 Xiaoliang Fan, 1,111Corresponding Author Jianzhong Qi, 2 Haibing
Jin,1 Peizhen Yang, 1
Siqi Shen,1 Cheng Wang1

###### Abstract

While federated learning has shown strong results in optimizing a machine
learning model without direct access to the original data, its performance may
be hindered by intermittent client availability which slows down the
convergence and biases the final learned model. There are significant
challenges to achieve both stable and bias-free training under arbitrary
client availability. To address these challenges, we propose a framework named
Federated Graph-based Sampling (FedGS), to stabilize the global model update
and mitigate the long-term bias given arbitrary client availability
simultaneously. First, we model the data correlations of clients with a Data-
Distribution-Dependency Graph (3DG) that helps keep the sampled clients data
apart from each other, which is theoretically shown to improve the
approximation to the optimal model update. Second, constrained by the far-
distance in data distribution of the sampled clients, we further minimize the
variance of the numbers of times that the clients are sampled, to mitigate
long-term bias. To validate the effectiveness of FedGS, we conduct experiments
on three datasets under a comprehensive set of seven client availability
modes. Our experimental results confirm FedGS’s advantage in both enabling a
fair client-sampling scheme and improving the model performance under
arbitrary client availability. Our code is available at
https://github.com/WwZzz/FedGS.

## Introduction

Federated learning (FL) enables various data owners to collaboratively train a
model without sharing their own data (McMahan et al. 2017). In a FL system,
there is a server that broadcasts a global model to clients and then
aggregates the local models from them to update the global model. Such a
distributed optimization may cause prohibitive communication costs due to the
unavailability of clients (Gu et al. 2021).

As an early solution to this problem, (McMahan et al. 2017) propose to
uniformly sample a random subset of clients without replacement to join the
training process.

Figure 1:  An motivating example: there are significant challenging to achieve
both stable model updates and bias-free training with the intermittent client
availability in FL.

(Li et al. 2020) sample clients in proportion to their data sizes with
replacement to obtain an unbiased estimator of update. More recently, some
works take the client availability into account when sampling clients (Yan et
al. 2020; Gu et al. 2021; Balakrishnan et al. 2021; Cho, Wang, and Joshi 2020;
Huang et al. 2020). They show that selecting clients without considering
whether the clients are active will lead to unbounded waiting times and poor
responding rates. As a result, they sample only the active clients to
guarantee immediate client availability (Gu et al. 2021; Cho, Wang, and Joshi
2020). For example, in Fig. 1, the server will not sample the inactive Client
$A$ and Client $B$ at Round ${t-1}$.

However, enabling both stable model updates and bias-free training under
_arbitrary client availability_ (i.e., without any assumption on when each
client will become available) poses significant challenges which have not been
addressed. On one hand, the model is improved on the data distributions of the
sampled clients at each round, which might lead to the detriment of the data
specificity of non-sampled clients (Fraboni et al. 2021). For example, in Fig.
1, fair-selection (Huang et al. 2020) tries to guarantee the least sampled
times for each client (and hence it is “fair”). While mitigating the long-term
bias, it will ignore the data of the red type at Round $t+1$, since it only
considers the balance of the sampled frequency of clients. This fails to
observe the data heterogeneity across the clients and leads to instability of
the model update due to the absence of the gradients computed on the “red”
data. On the other hand, the global models trained by FL may also be biased
towards clients with higher availability in a long run. Also in Fig. 1, the
MDSample (Li et al. 2020) and Variance-Reduce (Fraboni et al. 2021;
Balakrishnan et al. 2021) methods, which do not consider the difference in
client availability, introduce bias towards the clients with higher
availability (i.e. Client $A$ is overlooked at Round $t+1$ regardless of not
sampled in the previous rounds). In summary, there are significant challenges
to address two competitive issues (i.e. stable model updates and bias-free
training) that limit the FL training performance under the arbitrary client
availability.

To address the issues above, we propose a novel FL framework named _Fed erated
Graph-based Sampling_ (FedGS) to tackle the arbitrary client availability
problem. We first model the data correlations of clients with a Data-
Distribution-Dependency Graph (3DG) that helps keep the sampled clients data
far from each other. We further minimize the variance of the numbers of times
that the clients are sampled to mitigate long-term bias. Extensive experiments
on three datasets under different client availability modes confirm FedGS’s
advantage in both enabling a fair client-sampling scheme and improving the
model performance under arbitrary client availability.

The contributions of this work are summarized as follow:

  * •

We propose FedGS that could both stabilize the model update and mitigate long-
term bias under arbitrary client availability. To the best of our knowledge,
this is the first work that tackles the two issues simultaneously.

  * •

We propose the data correlations of clients with a Data-Distribution-
Dependency Graph (3DG), which helps keep sampled clients apart from each
other, and is also dedicate to mitigate long-term bias.

  * •

We design a comprehensive set of seven client availability modes, on which we
evaluate the effectiveness of FedGS on three datasets. We observe that FedGS
outperforms existing methods in both client-selection fairness and model
performance.

## Background and Problem Formulation

Given $N$ clients where the $k$th client has a local data size of $n_{k}$ and
a local objective function $F_{k}(\cdot)$, we study the standard FL
optimization problem as:

$\displaystyle\min_{\theta}F(\theta)=$
$\displaystyle\sum_{k=1}^{N}\frac{n_{k}}{n}F_{k}(\theta)$ (1)

where $\theta$ is the shared model parameter and $n=\sum_{k=1}^{N}n_{k}$ is
the total data size. A common approach to optimize this objective is to
iteratively broadcast the global model (i.e., its learned parameter values)
$\theta^{t}$ to all clients at each training round $t$ and aggregate local
models $\\{\theta^{t+1}_{1},...,\theta^{t+1}_{N}\\}$ that are locally trained
by clients using SGD with fixed steps:

$\displaystyle\theta^{t+1}=\sum_{k=1}^{N}\frac{n_{k}}{n}\theta^{t+1}_{k}$ (2)

When the number of clients is large, it is infeasible to update $\theta^{t+1}$
with $\theta^{t+1}_{k}$ from each client $k$, due to communication
constraints. Sampling a random client subset $S_{t}\subset[N]$ to obtain an
estimator of the full model update at each round becomes an attractive in this
case, which is shown to enjoy convergence guarantee when the following
unbiasedness condition is met (Li et al. 2019; Fraboni et al. 2021):

$\displaystyle\mathbb{E}_{S_{t}}\left[\theta^{t+1}\right]=\sum_{k=1}^{N}\frac{n_{k}}{n}\theta^{t+1}_{k}$
(3)

Further, Fraboni et al. and Balakrishnan et al. propose to reduce the variance
of the estimator as follows to enable faster and more stable training:

$\displaystyle Var(\nabla F_{\theta})$ $\displaystyle=\|Var(\nabla
F_{\theta})\|_{1}$ (4) $\displaystyle=\mathbb{E}_{t}{\|\nabla
F_{\theta^{t}}-\mathbb{E}[\nabla F_{\theta^{t}}]\|_{2}^{2}}$ (5)

However, the effectiveness of these variance-reducing methods is still limited
by the long-term bias caused by the arbitrary client availability as discussed
earlier.

### Mitigating long-term bias

We first propose an objective that could mitigate the long-term bias without
any assumption on the client availability. We denote the set of available
clients at the round $t$ as $A_{t}\subseteq[N]$. Then, sampled clients should
satisfy $S_{t}\subseteq A_{t}$ and $|S_{t}|\leq M$, where $M$ is the maximum
sample size limited by the server’s capacity. To mitigate the impact of
unexpected client availability on the sampled subset from a long-term view, we
sample clients by minimizing the variance of the sampling counts of clients
(i.e., the numbers of times that the clients are sampled after $t$ rounds).
Let the sampling counts of $N$ clients after $t$ rounds be
$\mathbb{v}^{t}=\left[v_{1}^{t},...,v_{N}^{t}\right]$ where
$v_{k}^{t}=\sum_{\tau=1}^{t}{\mathbb{I}(k\in
S_{\tau})}=v_{k}^{t-1}+\mathbb{I}(k\in S_{t})$. Then, the variance of the
client sampling counts after round $t$ is:

$\displaystyle
Var(\mathbb{v}^{t})=\frac{1}{N-1}\sum_{k=1}^{N}(v_{k}^{t}-\bar{v}^{t})^{2}$
(6)
$\displaystyle=\frac{1}{N-1}\sum_{k=1}^{N}\left(v_{k}^{t-1}+\mathbb{I}(k\in
S_{t})-(\bar{v}^{t-1}+M/N)\right)^{2}$ (7)

As discussed earlier, only balancing participating rates for clients may
introduce large variance of model updates that slows down the model
convergence (Fraboni et al. 2021). To enable a stable training, we introduce
low-variance model updates as a constraint on the feasible space when
minimizing the variance of sampling counts of the clients. We thus formulate
our sampling optimization problem as:

$\displaystyle\min_{|S_{t}|\leq M,S_{t}\subseteq A_{t}}Var(\mathbb{v}^{t})$
(8) $\displaystyle\text{s.t.}\quad\quad Var(\nabla
F_{S_{t}}(\theta^{t}))\leq\sigma^{2}$ (9)

where $\sigma^{2}\geq 0$ is a coefficient that allows to search for a trade-
off between the two objectives of stable model updates and balanced client
sampling counts. When $\sigma^{2}\rightarrow\infty$, the optimal solution will
select the currently available clients with the lowest sampling counts. On the
other hand, a small $\sigma^{2}$ will limit the sampled clients to those with
adequately small variance of the corresponding model updates.

## Methodology

This section presents our solutions to the optimization problem above (Eq. 8
and 9). The main challenge lies in converting the constraint on the variance
of the global model update into a solvable one. For this purpose, we utilize
the data similarity between clients to increase the data diversity of the
sampled subset.

Figure 2: An example of two types of local data distributions: (a) a simple
cluster; and (b) a complex cluster.

### Variance Reduction Based On 3DG

Before illustrating our method, we briefly review previous works that address
the Gradient Variance Reduction problem in FL. Li et al. add an proximal term
to the local objectives to prevent the model from overfitting on the local
data. Karimireddy et al. use control variate to dynamically correct the biased
updates during local training. These two methods can avoid large model update
variance by debiasing the local training procedure, which is orthogonal to the
sampling strategy. Fraboni et al. group the clients into $M$ clusters and then
sample clients from these clusters without replacement to increase the chance
for each client to be selected while still promising the unbiasedness of the
model updates. Similarly, Balakrishnan et al. approximates the full model
updates by enlarging the diversity of the selected client set, which is done
by minimizing a relaxed upper bound of the difference between the optimal full
update and the approximated one. Such a relaxation aims to achieve that for
each client $k\in[N]$ there exists an adequately similar client $i\in S_{t}$
in the sampled subset.

The existing methods work well when there are obvious clusters of clients
based on their local data distributions in Fig. 2(a). However, when the local
data distributions are too complex to cluster like Fig. 2(b), clustering the
clients cannot accurately capture the implicit data correlations between
clients, which may lead to performance degradation. Meanwhile, minimizing the
relaxed upper is not the only means to enlarge the diversity of the sampled
clients. We can achieve the same purpose without such minimization.

To better describe the correlations among clients’ local data distributions,
we model the local data distribution similarities with a Data-Distribution-
Dependency Graph (3DG) instead of grouping the clients into discrete clusters,
as shown in Fig. 3. Then, we show that keeping a large average shortest-path
distance between the sampled nodes (i.e. clients) on the 3DG helps approximate
the full model update. Intuitively, encouraging the sampled nodes to spread as
far as possible helps differentiate the sampled local data distributions,
which brings a higher probability to yield good balanced approximations for
the full model update. This is proven as Theorem 1.

######  Theorem 1.

Suppose that there are $C$ types of data (i.e., $C$ types of labels) over all
datasets, where each data type’s ratio is $p_{i}$ such that the dataset can be
represented by the vector
$\mathbb{p}^{*}=[p_{1}^{*},...,p_{C}^{*}],\mathbb{1}^{\top}\mathbb{p}^{*}=1$.
Without losing generality, consider $\mathbb{p}^{*}$ to be uniformly
distributed in the simplex in $\mathbb{R}^{C}$, the number of local updates to
be $1$, and 3DG is a complete graph. A larger distance of sampled clients on
the 3DG leads to a more approximate full model update.

###### Proof.

See Appendix A. ∎

Although the proof is based on that 3DG is a complete graph, we empirically
show that keeping the clients far away from each others on the 3DG can benefit
FL training even when this assumption is broken.

Figure 3: A visualized example of the oracle 3DG generated on CIFAR10
partitioned by 20 clients and each of them owns data with only two labels. The
different color means the ratio of corresponding labels in their local
dataset.

### Construction of 3DG in FL

Now we discuss how to construct the 3DG. A straightforward approach is to
directly calculate the distance (e.g., KL divergence) between different local
data distributions, which is infeasible in FL because the clients do not share
their local data. Without loss of generality, we assume that there is a
feature vector $\mathbb{u}_{k}\in\mathbb{R}^{d}$ that can well represent the
information about the local data distribution of each client $c_{k}$. We argue
that this is achievable in practice. For example, training an ML model for
tasks of supervised learning (e.g., classification) usually face severe data
heterogeneity in FL, where there may exist label skewness in clients’ local
data (e.g. each client only owns data with a subset of labels). In this case,
the label distribution vectors (i.e. the number of items of each label) can
well reflect the bias of each client’s local data. Once given the feature
vectors $\mathbb{U}=[\mathbb{u}_{1},\mathbb{u}_{2},...,\mathbb{u}_{N}]$, we
can easily calculate the similarity between any two clients $c_{i}$ and
$c_{j}$ with a similarity function
$f_{sim}:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow[0,1]$ as:

$\displaystyle\mathbb{V}=[V_{ij}]_{N\times
N},V_{ij}=f_{sim}(\mathbb{u}_{i},\mathbb{u}_{j})$ (10)

Then, the similarity matrix $\mathbb{V}$ can be converted into an adjacent
matrix $\mathbb{R}$ for the 3DG over the clients for the 3DG over the clients
by:

$\displaystyle\begin{split}R_{ij}=\left\\{\begin{array}[]{ll}0,&i=j\\\
e^{-V_{ij}/\sigma^{2}}&i\neq j,V_{ij}\geq\epsilon\\\ \infty,&i\neq
j,V_{ij}<\epsilon\end{array}\right.\end{split}$

where $\epsilon>0$ is a positive threshold used to control the sparsity of the
adjacent matrix and $\sigma$ controls the diversity of the edge weight. A
large value of $\sigma$ will lead to small difference between the edge
weights.

The feature vector $\mathbb{u}_{k}$ can also leak sensitive information about
the clients, and it may not be exposed to the other clients or the server. It
is necessary for the server to obtain the similarities between clients in
privacy-preserving manner to reconstruct or accurately approximate the _oracle
3DG_ (i.e., the 3DG corresponding to the true features $\mathbb{U}$). To
achieve this goal, we present two methods that can help the server construct
the 3DG.

The first is to use techniques based on Secure Scalar Product Protocols (SSPP)
(Wang et al. 2009; Shundong, Mengyu, and Wenting 2021), which aims to compute
the dot product of private vectors of parties. We argue that any existing
solutions of SSPP can be used to reconstruct the similarity matrix
$\mathbb{V}$ of clients in our settings, and we detail one of the existing
solutions for scalar product protocal (Du and Zhan 2002) with a discussion on
how to adapt it to build the 3DG in the Appendix D.

Although the SSPP-based methods can construct the oracle 3DG without any
error, it cannot be adapted to the case where the feature vectors are
difficult or impossible to obtain. In addition, the SSPP-based method only
applies when the similarity function $f_{sim}$ is a simple dot product.

We propose a second method that computes the similarity between clients based
on their uploaded model parameters. Given the locally trained models
$\theta_{i}^{t+1}$ and $\theta_{j}^{t+1}$, a straightforward way to calculate
the similarity between the two clients is to compute the cosine similarity of
their model updates (Xu and Lyu 2020; Xu et al. 2021)

$\displaystyle
V_{ij}=\max(\frac{\Delta\theta_{i}^{t\top}\Delta\theta_{j}^{t}}{\|\Delta\theta_{i}^{t}\|\|\Delta\theta_{j}^{t}\|},0)$
(11)

where $\Delta\theta_{i}^{t\top}=\theta_{i}^{t+1}-\theta^{t}$. However, since
the model parameters’ update is usually of extremely high dimensions but low
rank (Azam et al. 2021), the direct cos similarity may contain too much noise,
causing inaccuracy when constructing the 3DG. Motivated by (Baek et al. 2022),
we instead compute the functional similarity based on the model parameters to
overcome the problem above. We first feed a batch of random Gaussian noise
$\epsilon\sim\mathcal{N}(\mu,\Sigma)$ to all the locally trained models, where
$\mu$ and $\Sigma$ are respectively the mean and covariance of a small
validation dataset owned by the server (Zhao et al. 2018). Then, we take the
average of the $l$th layer’s network embedding on this batch for each client
to obtain $e_{i}$, and we compute the similarity as:

$\displaystyle
e_{i}=\theta_{i}(\epsilon)[l],V_{ij}=\max(\frac{e_{i}^{\top}e_{j}}{\|e_{i}\|\|e_{j}\|},0)$
(12)

where we set $l$ as the output layer in practice.

Another concerning issue is that the server may not have access to all the
clients’ feature vectors during the initial phase. As a result, the adjacent
matrix of clients may need to be dynamically built and polished round by
round. Nevertheless, we emphasize that we are not trying to answer how to
optimally capture the correlations between clients’ local data distributions
in FL. Instead, we aim at showing that the topological correlations of
clients’ local data can be utilized to improve the training process of FL, and
we key how to build the optimal 3DG for as our future work.

For convenience, we simply assume that all the clients are available at the
initial phase, by which the server can obtain the 3DG just before training
starts. We empirically show the effectiveness of the approximated 3DG in Sec.
4.4.

### FedGS

We now present our proposed Federated Graph-based Sampling (FedGS) method. As
mentioned in Sec. 3.1, we bound the variance of the global model update at
each round by keeping a larger average shortest-path distance between each
pair of sampled clients. Given a 3DG, we first use the Floyd–Warshall
algorithm to compute the shortest-path distance matrix
$\mathbb{H}=[h_{ij}]_{N\times N}$ for all pairs of clients. Let
$s_{k}^{t}\in\\{0,1\\}$ be a binary variable, where $s_{k}^{t}=1$ means client
$c_{k}$ is selected to participate training round $t$ and $s_{k}^{t}=0$
otherwise. Then, the sampling result in round $t$ can be
$\mathbb{s}_{t}=[s_{1}^{t},...,s_{N}^{t}]\in\\{0,1\\}^{N}$, where the average
shortest-path distance between sampled clients is written as:

$\displaystyle g(S_{t})=\frac{2}{N(N-1)}\sum_{i,j\in S_{t},i\neq
j}h_{ij}s_{i}^{t}s_{j}^{t}=\frac{\mathbb{s}_{t}^{\top}{\mathbb{H}}\mathbb{s}_{t}}{N(N-1)}$
(13)

Accordingly, we replace the constraint in Equation (9) with
$g(S_{t})\geq\alpha$, and we convert this constraint into a penalty term added
into the objective. After rewriting the equation (8) to be a maximization
problem based on $s_{t}$, we obtain:

$\displaystyle\max_{\mathbb{s}_{t}\leq\mathbb{a}^{t},s_{k}^{t}\in\\{0,1\\}}\frac{\alpha\mathbb{s}_{t}^{\top}{\mathbb{H}}\mathbb{s}_{t}}{N(N-1)}-\frac{1}{N-1}\mathbb{z}^{\top}\mathbb{s}_{t}$
(14) $\displaystyle\text{s.t.
}\quad\quad\mathbb{1}^{\top}\mathbb{s}_{t}=min(M,|A_{t}|)$ (15)

where $z_{k}=2(v_{k}^{t-1}-\bar{v}^{t-1}-M/N)+1$,
$\mathbb{a}^{t}=\\{a_{1}^{t},...,a_{N}^{t}\\}\in\\{0,1\\}^{N}$ and
$a_{k}^{t}=1$ means client $c_{k}$ is available in round $t$. Note that
$s_{k}^{t}=0$ for the clients unavailable clients in round $t$ and
$s_{k}^{t2}=s_{k}^{t}$. Thus, Equation (14) can be reduced to:

$\displaystyle\max_{\tilde{s}_{k}^{t}\in\\{0,1\\}}\mathbb{\tilde{s}}_{t}^{\top}\left(\frac{\alpha}{N}\tilde{\mathbb{H}}-\textbf{diag}(\tilde{\mathbb{z}})\right)\mathbb{\tilde{s}}_{t}$
(16) $\displaystyle\text{s.t.
}\quad\mathbb{1}^{\top}\mathbb{\tilde{s}}_{t}=min(M,|A_{t}|)$ (17)

$\mathbb{\tilde{s}}_{t}=[s_{i1}^{t},...,s_{i|A_{t}|}^{t}]\in\\{0,1\\}^{|A_{t}|}$
and $s_{ij}^{t}=1$ represents that the $j$th client in the available set is
selected. $\tilde{\mathbb{z}}\in\mathbb{R}^{|A_{t}|}$ and
$\tilde{\mathbb{H}}\in\mathbb{R}^{|A_{t}|\times|A_{t}|}$ also only contains
the element where the corresponding clients are available in round $t$.

This rewritten problem is a constrained mixed integer quadratic problem, which
is a variety of an NP-hard problem, p-dispersion (Pisinger 1999), with a non-
zero diagonal. We optimize it to select clients within a fixed upper bound of
wall-clock time. We empirically show that a local optimal can already bring
non-trivial improvement when the client availability varies.

#### Aggregation Weight.

Instead of directly averaging the uploaded model parameters like (Balakrishnan
et al. 2021; Li et al. 2020), We normalize the ratio of the local data size of
selected clients as weights of the model aggregation:

$\displaystyle\theta^{t+1}=\sum_{k\in S_{t}}\frac{n_{k}}{\sum_{i\in
S_{t}}n_{i}}\theta^{t+1}_{k}$ (18)

We argue that this is reasonable in our sampling scheme. Firstly, FedGS forces
to balance the sampling counts of all the clients regardless of their
availability. Thus, for convenience, we simply assume that all the clients
will be uniformly sampled with the same frequency $\frac{MT_{c}}{N}$ in every
$T_{c}$ rounds, and that the size of the set of available clients $|A_{t}|$ is
always larger than the sample size limit $M$ in each round $t$. By treating
the frequency $\frac{MT_{c}}{N}/T_{c}=M/N$ as the probability of each client
being selected without replacement in each round $T_{0}+\tau$, $(\tau\leq
T_{c})$, we obtain:

$\displaystyle\mathbb{E}_{S_{t}}[\theta_{t+1}]$
$\displaystyle=\mathbb{E}_{S_{t}}\left[\frac{M}{N}\sum_{k=1}^{N}\frac{n_{k}}{n_{k}+\sigma(S_{t},k)}\theta^{t+1}_{k}\right]$
(19)
$\displaystyle=\frac{M}{N}\sum_{k=1}^{N}\frac{n_{k}}{n_{k}+\sigma_{k}}\theta^{t+1}_{k}$
(20)

where
$\sigma_{k}=\mathbb{E}_{S_{t}}[\sigma(S_{t},k)]=\mathbb{E}_{S_{t}}[\sum_{j\in
S_{t},j\neq k}n_{j}]=\frac{M-1}{N-1}(n-n_{k})$. Therefore, the expected
updated model of the next round follows:

$\displaystyle\mathbb{E}_{S_{t}}[\theta_{t+1}]$
$\displaystyle=\frac{M}{N}\sum_{k=1}^{N}\frac{n_{k}}{n_{k}+\frac{M-1}{N-1}(n-n_{k})}\theta^{t+1}_{k}$
(21)
$\displaystyle=\sum_{k=1}^{N}\frac{n_{k}}{n}\frac{1}{1+\frac{1}{M}\frac{N-M}{N-1}\frac{n_{k}-\bar{n}}{\bar{n}}}\theta^{t+1}_{k}$
(22) $\displaystyle=\sum_{k=1}^{N}\frac{n_{k}}{n}\gamma_{k}\theta^{t+1}_{k}$
(23)

From Equation (22), we see that the degree of data imbalance will impact the
unbiasedness of the estimation. When the data size is balanced as
$n_{k}=\bar{n},\forall k\in[N]$, the estimation is unbiased since
$\gamma_{k}=1,\forall k\in[N]$. If the data size is imbalanced, the degree of
data imbalance will only have a controllable influence on the unbiasedness
with the ratio of each client’s local data’s size to the average data size
$\frac{\|n_{k}-\bar{n}\|}{\bar{n}}$. This impact can be immediately reduced by
increasing the number of sampled clients $M$ at each round.

The analysis above is based on the assumption that our proposed FedGS can well
approximate the results obtained by uniform sampling without replacement in
ideal settings. Generally speaking, a small $Var(\mathbb{v}^{t})$ will limit
the difference between the sampling counts, which is also empirically verified
by our experimental results. The pseudo codes in Algorithm 1 summarizes the
main steps of FedGS.

Algorithm 1 Federated Graph-Based Sampling

Input:The global model $\theta$, the feature matrix of clients’ data
distribution $\mathbb{U}$, the maximum wall-clock time of the solver
$\tau_{max}$, the sizes of clients’ local data $n_{k}$, the number of local
updating steps $E$, and the learning rate $\eta_{t}$

1: Initialize the global model parameters $\theta_{0}$ and the sampling counts
of clients $\mathbb{v}^{0}=[0,...,0]\in\mathbb{N}^{N}$.

2: Create the 3DG $\mathbb{G}$ based on the techniques in Sec. 3.2.

3: Compute the shortest-path distance of each pair of nodes on 3DG by Floyd
Algorithm to obtain $\mathbb{H}$.

4: for communication round $t=0,1,...,T-1$ do

5: The server checks the set of available clients $A_{t}$.

6: The server uses $\mathbb{v}^{t}$ and $\mathbb{H}$ to solve equation (16)
within the maximum wall-clock time $\tau_{max}$ to obtain the sampled client
set $S_{t}\subseteq A_{t}$

7: The server broadcasts the model $\theta^{t}$ to clients in $S_{t}$.

8: for each client $k\in S_{t}$ do

9: for each iteration $i=0,1,...,E-1$ do

10: $\theta_{k,i+1}^{t}\leftarrow\theta_{k,i}^{t}-\eta_{t}\nabla
F_{k}(\theta_{k,i}^{t})$

11: end for

12: Client $k$ send the model parameters $\theta_{k}^{t+1}=\theta_{k,E}^{t}$
to the server.

13: end for

14: The server aggregates the received local model parameters
$\theta^{t+1}=\sum_{k\in S_{t}}\frac{n_{k}}{\sum_{i\in
S_{t}}n_{i}}\theta^{t+1}_{k}$

15: The server updates the sampling counts of clients
$\mathbb{v}^{t+1}[k]\leftarrow\mathbb{v}^{t}[k]+\mathbb{I}(k\in S_{t})$

16: end for

Name | Description | Dependency | Active Rate
---|---|---|---
Time | Data | Other
IDeaL | Full client availability | - | - | - | $1$
MoreDataFirst (Ours) | More data, higher availability | - | data size $n_{k}$ | - | $\frac{n_{k}^{\beta}}{\max_{i}n_{i}^{\beta}}$
LessDataFirst (Ours) | Less data, higher availability | - | data size $n_{k}$ | - | $\frac{n_{k}^{-\beta}}{\max_{i}n_{i}^{-\beta}}$
YMaxFirst (Gu et al. 2021) | Larger value of label, higher availability | - | value of label set $\\{y_{ki}\\}$ | - | $\beta\frac{\min_{i}\\{y_{ki}\\}}{\max_{c,j}\\{y_{cj}\\}}+(1-\beta)$
YCycle (Ours) | Periodic availability with label values | round $t$ | value of label set $\\{y_{ki}\\}$ | - | $\beta\mathbb{I}\left(\cup_{y_{ki}}\frac{1+(t\%T_{p})}{T_{p}}\in[\frac{y_{ki}}{num_{Y}},\frac{y_{ki}+1}{num_{Y}})\right)+(1-\beta)$
Log Normal (Ribero, Vikalo, and De Veciana 2022) | Independent availability obeying lognormal | - | - | $c_{k}\sim\text{lognormal}(0,ln\frac{1}{1-\beta})$ | $\frac{c_{k}}{\max_{i}c_{i}}$
Sin Log Normal (Ribero, Vikalo, and De Veciana 2022) |  Sin-like intermittent availability of with LN | round $t$ | - | $c_{k}\sim\text{lognormal}(0,ln\frac{1}{1-\beta})$ | $\frac{c_{k}}{\max_{i}c_{i}}\left(0.4sin\left(\frac{1+(t\%T_{p})}{T_{p}}2\pi\right)+0.5\right)$

Table 1: An Overview of Different Client Availability Modes. Dataset | Synthetic(0.5, 0.5) | CIFAR10 | FashionMNIST
---|---|---|---
Availability | IDL | LN | SLN | LDF | MDF | IDL | LN | SLN | LDF | MDF | IDL | YMF | YC
UniformSample | 0.302 | 0.320 | 0.324 | 0.330 | 0.362 | 0.975 | 1.042 | 1.038 | 1.049 | 0.999 | 0.315 | 0.331 | 0.333
MDSample | 0.302 | 0.322 | 0.328 | 0.328 | 0.326 | 0.971 | 1.037 | 1.048 | 1.051 | 0.991 | 0.315 | 0.333 | 0.338
Power-of-Choice | 0.691 | 0.362 | 0.352 | 0.557 | 0.301 | 1.287 | 1.108 | 1.078 | 1.267 | 1.026 | 0.345 | 0.326 | 0.311
FedProx $\mu=0.01$ | 0.301 | 0.346 | 0.376 | 0.319 | 0.410 | 0.972 | 1.056 | 1.162 | 1.039 | 0.995 | 0.315 | 0.331 | 0.374
FedGS $\alpha=0.0$ | 0.307 | 0.305 | 0.320 | 0.309 | 0.310 | 1.006 | 0.976 | 1.002 | 0.974 | 0.967 | 0.302 | 0.310 | 0.324
FedGS $\alpha=0.5$ | 0.311 | 0.306 | 0.319 | 0.308 | 0.311 | 0.977 | 0.973 | 1.000 | 0.966 | 0.974 | 0.299 | 0.312 | 0.312
FedGS $\alpha=1.0$ | 0.328 | 0.306 | 0.318 | 0.308 | 0.311 | 0.968 | 0.972 | 0.996 | 0.971 | 0.963 | 0.300 | 0.308 | 0.310
FedGS $\alpha=2.0$ | 0.306 | 0.307 | 0.320 | 0.308 | 0.311 | 0.970 | 0.975 | 1.001 | 0.973 | 0.969 | 0.310 | 0.303 | 0.312
FedGS $\alpha=5.0$ | 0.317 | 0.307 | 0.321 | 0.309 | 0.311 | 0.976 | 0.974 | 0.996 | 0.972 | 0.972 | 0.307 | 0.303 | 0.307
Table 2: The optimal testing loss of methods running under different client
availability modes on three datasets. Each result in the table is averaged
over 3 different random seeds.

## Experiment

### Experimental Setup

#### Datasets and models to be trained

We validate FedGS on three commonly used federated datasets: Synthetic (0.5,
0.5) (Li et al. 2020), CIFAR10 (Krizhevsky, Hinton et al. 2009) and
FashionMNIST (Xiao, Rasul, and Vollgraf 2017). For Syntetic dataset, we follow
the settings use by (Li et al. 2020) to generate imbalance and non-i.i.d.
dataset with 30 clients. For CIFAR10, we unequally partition the dataset into
100 clients following the label distribution $Y_{k}\sim Dir(\alpha p)$ (Hsu,
Qi, and Brown 2019) ($p$ is the global label distribution). For FashionMNIST,
we balance the data sizes for 100 clients, each of whom owns data of only two
labels. We train a logistic regression model for Synthetic(0.5, 0,5) and CNN
models for CIFAR10 and FashionMNIST. More details on datasets are in Appendix
C.

#### Client Availability

We first review the client availability settings discussed in existing FL
literature (Ribero, Vikalo, and De Veciana 2022; Gu et al. 2021), a common way
is to allocate an active probability to each client at each round. We observe
that the client’s active probability may depend on data distribution or time
(Ribero, Vikalo, and De Veciana 2022; Gu et al. 2021). We mainly conclude the
existing client availability modes and propose a comprehensive set of seven
client availability modes in Table 1 to conduct experiments under arbitrary
availability. For each mode, we set a coefficient $\beta\in[0,1]$ to control
the degree of the global unavailability, where a large value of $\beta$
suggests a small chance for most devices to be active. A further explanation
about these availability modes is provided in Appendix C, where we also
visualize the active state of clients at each round.

#### Baselines

We compare our method FedGS with: (1) UniformSample (McMahan et al. 2017),
which samples available clients uniformly without replacement, (2)
FedProx/MDSample (Li et al. 2020), which samples available clients with a
probability proportion to their local data size and trains w/wo proximal term,
(3) Power-of-Choice (Cho, Wang, and Joshi 2020), which samples available
clients with top-$M$ highest loss on local data and is robust to the client
unavailability. Particularly, all the reported results of our FedGS are
directly based on the oracle 3DG. We put results obtained by running FedGS on
the constructed 3DG in the Appendix B.

#### Hyper-parameters

For each dataset, we tune the hyper-parameters by grid search with FedAvg, and
we adopt the optimal parameters on the validation dataset of FedAvg to all the
methods. The batch size is $B=10$ for Synthetic and $B=32$ for both CIFAR10
and FashionMNIST. The optimal parameters for Synthetic, Cifar10, FashionMNIST
are resepctively $\eta=0.1,E=10$, $E=10,\eta=0.03$ and $E=10,\eta=0.1$. We
round-wisely decay the learning srate by a factor of $0.998$ for all the
datasets. More details about the hyper-parameters are put in Appendix C.

#### Implementation

All our experiments are run on a 64 GB-RAM Ubuntu 18.04.6 server with Intel(R)
Xeon(R) CPU E5-2630 v4 @ 2.20GHz and 4 NVidia(R) 2080Ti GPUs. All code is
implemented in PyTorch 1.12.0.

### Results of Impact of Client Availability

We run experiments under different client availability modes to study the
impact of arbitrary client availability, where the main results are shown in
Table 2. Overall, the optimal model performance measured by the test loss is
impacted by the client availability modes for all methods and over all three
datasets. On Synthetic, UniformSample suffers the worst model performance
degradation, $19.8\%$ (i.e. IDL v.s. MDF), while that for MDSample is $8.6\%$
(i.e. IDL v.s. LDF). FedGS retrains a strong model performance, with a
degradation no more than $5\%$ for all the values of $\alpha$. Further, our
proposed FedGS achieves the best performance under all the availability modes
except for IDL and MDF. For IDL, our FedGS still yields competitive results
comparing with UniformSample and MDSample (0.306 v.s. 0.302). For MDF,
although Power-of-Choice achieves the optimal result, its model performance is
extremely unstable across different availability modes, e.g., its model
performance is almost $200\%$ worse than the others for IDL. Meanwhile, FedGS
still achieves $4.9\%$ improvement over MDSample and $14.3\%$ over
UniformSample in this case. For CIFAR10 and FashionMNIST, all the optimal
results fall into the region runned with FedGS. Using $\alpha>0$ brings a non-
trivial improvement over using $\alpha=0$ in most of the client availability
modes, which suggests that the variance reduction of FedGS can also benefit FL
training.

Figure 4: The results of final client sampling counts on FashionMNIST-YMF-0.9
and Cifar10-LN-0.5.

Figure 5: The testing loss curve respectively on FashionMNIST-YMF-0.9 and
CIFAR10-LN-0.5.

### Results of Client Selection Fairness

As shown in Fig. 4, $\textsc{FedGS}_{\alpha=1}$ can substantially enhance
fairness in client selection, which results in a uniform distribution of
client sample counts both on FashionMNIST with YMF-0.9 and CIFAR10 with
LN-0.5. We also show the corresponding curves of test loss in Fig. 5, which
show that FedGS can stabilize FL training and find a better solution.

### Effectiveness of 3DG Construction

To validate the effectiveness of our method to reconstruct the oracle 3DG
based on the functional similarity of model parameters, we use the F1-score of
predicting the edges in the oracle 3DG to measure the quality of the
construction, and we compare results with those obtained using the cosine
similarity. The oracle 3DG is generated with $\epsilon=0.1$ and
$\sigma^{2}=0.01$. Considering the difference in the feature space of the
oracle and those of the model-based methods, we vary the value of
$\epsilon\in\\{0,0.01,0.05,0.1,0.5\\}$ and report the results with the highest
F1-score for each method. Results in Table 3 confirm the effectiveness of the
proposed method to approximate the oracle 3DG, where the functional-similarity
method achieves a higher F1-score than the cos-similarity method on both
datasets. The results of FedGS running on the model-based 3DG are included in
Appendix B.

Dataset | Method | Precision | Recall | F1-Score
---|---|---|---|---
CIFAR10 | functional similarity | 0.8789 | 0.8700 | 0.8744
cosine similarity | 1.0000 | 0.1316 | 0.2327
FashionMNIST | functional similarity | 0.9761 | 0.7097 | 0.8218
cosine similarity | 0.3765 | 0.9853 | 0.5448
Table 3: The effectiveness of how to construct 3DG.

## Related Works

### Client Sampling in FL

Client sampling is proven to has a significant impact on the stability of the
learned model (Cho, Wang, and Joshi 2020). (McMahan et al. 2017) uniformly
samples clients without replacement to save communication efficiency. (Li et
al. 2020) samples clients proportion to their local data size and uniformly
aggregate the models with full client availability. (Fraboni et al. 2021)
reduces the variance of model to accelerate the training process.
Nevertheless, these works ignored the long-term bias introduced by arbitrary
client availability, which will result in the model overfitting on a
particular data subset. Recent works (Ribero, Vikalo, and De Veciana 2022; Gu
et al. 2021; Huang et al. 2020) are aware of such long-term bias from the
arbitrary availability of clients. However, these two competitive issues (e.g.
stable model updates and bias-free training) have not been considered
simultaneously.

### Graph Construction in FL

When it is probable to define the topology structure among clients in FL,
several works directly utilized underlying correlations among different
clients according to their social relations (He et al. 2021). Other works
proposed to connect the clients with their spatial-temporal relations as a
graph (Meng, Rambhatla, and Liu 2021; Zhang et al. 2021). However, those works
are used to conduct explicit correlations between clients (e.g. social
relation, spatial relation), which were not able to uncover the important and
implicit connections among clients. In short, we are the first to construct
Data-Distribution-Dependency Graph (3DG) to learn the potential data
dependency of sampled clients, which is proven to both guarantee a fair client
sampling scheme and improve the model performance under arbitrary client
availability.

## Conclusion

We addressed the long-term bias and the stability of model updates
simultaneously to enable faster and more stable FL under arbitrary client
availability. To this end, we proposed the FedGS framework that models
clients’ data correlations with a Data-Distribution-Dependency Graph (3DG) and
utilizes the graph to stabilize the model updates. To mitigate the long-term
bias, we minimize the variance of the numbers of times that clients are
sampled under the far-distance-on-3DG constraint. Our experimental results on
three real datasets under a comprehensive set of seven client availability
modes confirm the robustness of FedGS on arbitrary client availability modes.
In the future, we plan to study how to define and construct 3DG across various
ML tasks.

## Acknowledgements

The research was supported by Natural Science Foundation of China (62272403,
61872306), Fundamental Research Funds for the Central Universities
(20720200031), FuXiaQuan National Independent Innovation Demonstration Zone
Collaborative Innovation Platform (No.3502ZCQXT2021003), and Open Fund of PDL
(WDZC20215250113).

## References

  * Azam et al. (2021) Azam, S. S.; Hosseinalipour, S.; Qiu, Q.; and Brinton, C. 2021.  Recycling Model Updates in Federated Learning: Are Gradient Subspaces Low-Rank?  In _International Conference on Learning Representations_.
  * Baek et al. (2022) Baek, J.; Jeong, W.; Jin, J.; Yoon, J.; and Hwang, S. J. 2022.  Personalized Subgraph Federated Learning.  arXiv:2206.10206.
  * Balakrishnan et al. (2021) Balakrishnan, R.; Li, T.; Zhou, T.; Himayat, N.; Smith, V.; and Bilmes, J. 2021\.  Diverse client selection for federated learning via submodular maximization.  In _International Conference on Learning Representations_.
  * Cho, Wang, and Joshi (2020) Cho, Y. J.; Wang, J.; and Joshi, G. 2020.  Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies.  arXiv:2010.01243.
  * Du and Zhan (2002) Du, W.; and Zhan, Z. 2002.  Building decision tree classifier on private data.  _Electrical Engineering and Computer Science_.
  * Fraboni et al. (2021) Fraboni, Y.; Vidal, R.; Kameni, L.; and Lorenzi, M. 2021.  Clustered sampling: Low-variance and improved representativity for clients selection in federated learning.  In _International Conference on Machine Learning_ , 3407–3416. PMLR.
  * Gu et al. (2021) Gu, X.; Huang, K.; Zhang, J.; and Huang, L. 2021.  Fast federated learning in the presence of arbitrary device unavailability.  _Advances in Neural Information Processing Systems_ , 34: 12052–12064.
  * He et al. (2021) He, C.; Balasubramanian, K.; Ceyani, E.; Yang, C.; Xie, H.; Sun, L.; He, L.; Yang, L.; Yu, P. S.; Rong, Y.; Zhao, P.; Huang, J.; Annavaram, M.; and Avestimehr, S. 2021.  FedGraphNN: A Federated Learning System and Benchmark for Graph Neural Networks.  arXiv:2104.07145.
  * Hsu, Qi, and Brown (2019) Hsu, T.-M. H.; Qi, H.; and Brown, M. 2019.  Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification.  arXiv:1909.06335.
  * Huang et al. (2020) Huang, T.; Lin, W.; Wu, W.; He, L.; Li, K.; and Zomaya, A. Y. 2020.  An efficiency-boosting client selection scheme for federated learning with fairness guarantee.  _IEEE Transactions on Parallel and Distributed Systems_ , 32(7): 1552–1564.
  * Karimireddy et al. (2020) Karimireddy, S. P.; Kale, S.; Mohri, M.; Reddi, S.; Stich, S.; and Suresh, A. T. 2020.  Scaffold: Stochastic controlled averaging for federated learning.  In _International Conference on Machine Learning_ , 5132–5143. PMLR.
  * Krizhevsky, Hinton et al. (2009) Krizhevsky, A.; Hinton, G.; et al. 2009.  Learning multiple layers of features from tiny images.
  * Li et al. (2020) Li, T.; Sahu, A. K.; Zaheer, M.; Sanjabi, M.; Talwalkar, A.; and Smith, V. 2020\.  Federated optimization in heterogeneous networks.  _Proceedings of Machine Learning and Systems_ , 2: 429–450.
  * Li et al. (2019) Li, X.; Huang, K.; Yang, W.; Wang, S.; and Zhang, Z. 2019.  On the Convergence of FedAvg on Non-IID Data.  arXiv:1907.02189.
  * McMahan et al. (2017) McMahan, B.; Moore, E.; Ramage, D.; Hampson, S.; and y Arcas, B. A. 2017.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , 1273–1282. PMLR.
  * Meng, Rambhatla, and Liu (2021) Meng, C.; Rambhatla, S.; and Liu, Y. 2021.  Cross-node federated graph neural network for spatio-temporal data modeling.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, 1202–1211.
  * Peng (2007) Peng, B. 2007.  The determinant: A means to calculate volume.  _Recall_ , 21: a22.
  * Pisinger (1999) Pisinger, D. 1999.  _Exact solution of p-dispersion problems_.  DIKU.
  * Ribando (2006) Ribando, J. M. 2006.  Measuring solid angles beyond dimension three.  _Discrete & Computational Geometry_, 36(3): 479–487.
  * Ribero, Vikalo, and De Veciana (2022) Ribero, M.; Vikalo, H.; and De Veciana, G. 2022.  Federated Learning Under Intermittent Client Availability and Time-Varying Communication Constraints.  arXiv:2205.06730.
  * Shundong, Mengyu, and Wenting (2021) Shundong, L.; Mengyu, Z.; and Wenting, X. 2021.  Secure Scalar Product Protocols.  _Chinese Journal of Electronics_ , 30(6): 1059–1068.
  * Wang et al. (2009) Wang, I.-C.; Shen, C.-H.; Zhan, J.; Hsu, T.-s.; Liau, C.-J.; and Wang, D.-W. 2009\.  Toward empirical aspects of secure scalar product.  _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , 39(4): 440–447.
  * Wang et al. (2020) Wang, J.; Liu, Q.; Liang, H.; Joshi, G.; and Poor, H. V. 2020.  Tackling the objective inconsistency problem in heterogeneous federated optimization.  _Advances in neural information processing systems_ , 33: 7611–7623.
  * Xiao, Rasul, and Vollgraf (2017) Xiao, H.; Rasul, K.; and Vollgraf, R. 2017.  Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms.  arXiv:1708.07747.
  * Xu and Lyu (2020) Xu, X.; and Lyu, L. 2020.  A Reputation Mechanism Is All You Need: Collaborative Fairness and Adversarial Robustness in Federated Learning.  arXiv:2011.10464.
  * Xu et al. (2021) Xu, X.; Lyu, L.; Ma, X.; Miao, C.; Foo, C. S.; and Low, B. K. H. 2021.  Gradient driven rewards to guarantee fairness in collaborative machine learning.  _Advances in Neural Information Processing Systems_ , 34: 16104–16117.
  * Yan et al. (2020) Yan, Y.; Niu, C.; Ding, Y.; Zheng, Z.; Wu, F.; Chen, G.; Tang, S.; and Wu, Z. 2020\.  Distributed Non-Convex Optimization with Sublinear Speedup under Intermittent Client Availability.  arXiv:2002.07399.
  * Zhang et al. (2021) Zhang, C.; Zhang, S.; James, J.; and Yu, S. 2021.  FASTGNN: A topological information protected federated learning approach for traffic speed forecasting.  _IEEE Transactions on Industrial Informatics_ , 17(12): 8464–8474.
  * Zhao et al. (2018) Zhao, Y.; Li, M.; Lai, L.; Suda, N.; Civin, D.; and Chandra, V. 2018.  Federated Learning with Non-IID Data.  arXiv:1806.00582.

##  Appendix A A. Proof of Theorem 1

###### Proof.

Supposing there are $C$ types of data in the global dataset, the global
dataset can be represented by the data ratio vector
$\mathbb{p}^{*}=[p_{1}^{*},p_{2}^{*},...,p_{C}^{*}]^{\top}$, where each data
type’s ratio is $p_{i}^{*}>0$ and $\mathbb{1}^{\top}\mathbb{p}^{*}=1$. Then,
each client $c_{k}$’s local data distribution can also be represented by
$\mathbb{p}_{k}=[p_{k1},p_{k2},...,p_{kC}]^{\top},\mathbb{1}^{\top}\mathbb{p}_{k}=1$.
We slightly modify the way of constructing 3DG as

$\displaystyle\begin{split}R_{ij}=\left\\{\begin{array}[]{ll}0,&i=j\\\
\|e_{i}-e_{j}\|_{2}^{2}&i\neq j\end{array}\right.\end{split}$

where $e_{i}=\frac{p_{i}}{\|p_{i}\|},e_{j}=\frac{p_{j}}{\|p_{j}\|}$ and the
principle of the smaller similarity corresponding to the larger distance still
holds. Given that 3DG is a complete graph, we demonstrate that the shortest-
path distance matrix $\mathbb{H}$ is the same to $\mathbb{R}$, since
$distance(i,k)+distance(k,j)\geq distance(i,j)$ is always established for any
$k$.

In each communication round $t$, the server samples $M$ clients to
participate. By denoting the sampled clients’ normalized data distribution as
$\mathbb{P}_{t}=[\mathbb{e}_{i_{1}},...,\mathbb{e}_{i_{M}}]\in\mathbb{R}_{+}^{C\times
M}$, the average shortest-path distance of these selected clients is

$\displaystyle f(S_{t})$ $\displaystyle=\frac{1}{M(M-1)}\sum_{i,j\in
S_{t}}H_{ij}$ (24) $\displaystyle=\frac{1}{M(M-1)}\left(\sum_{i,j\in
S_{t}}(2-2e_{i}^{\top}e_{j})\right)$ (25)
$\displaystyle=\frac{2M}{M-1}-\frac{2}{M(M-1)}\|\mathbb{P}_{t}^{\top}\mathbb{P}_{t}\|_{m1}$
(26)

After receiving the local models, the server aggregates their uploaded models
to obtain

$\displaystyle\theta_{t+1}=\sum_{k\in
S_{t}}w_{k}\theta^{t+1}_{k}=\theta_{t}+\sum_{k\in
S_{t}}w_{k}\Delta\theta_{k}^{t}$ (27)

where $w_{k}$ is the aggregation weight of the selected client $c_{k}$ and
$\mathbb{1}^{\top}\mathbb{w}=1$. Now, the problem is how possible can the
aggregated model update recover the true model update $\Delta\theta_{t}$ that
is computed on all the clients?

To answer this problem, we first simply consider the model update computed on
all the $i$th type of data to be $\Delta\bar{\theta}_{ti}\in\mathbb{R}^{d}$
and
$\mathbb{\Delta}_{t}=[\Delta\bar{\theta}_{t1},...,\Delta\bar{\theta}_{tC}]\in\mathbb{R}^{d\times
C}$, then we can approximate the true model update by

$\displaystyle\Delta\theta_{t}^{*}$
$\displaystyle=\sum_{i=1}^{C}p_{i}^{*}\Delta\bar{\theta}_{ti}$ (28)
$\displaystyle=\mathbb{\Delta}_{t}\mathbb{p}*$ (29)

Similarly, each client $c_{k}$’s model update can also be represented by

$\displaystyle\Delta\theta_{k}^{t}=\sum_{i=1}^{C}p_{ki}\Delta\bar{\theta}_{ti}=\mathbb{\Delta}_{t}\mathbb{p}_{k}$
(30)

Then, the aggregated model update is

$\displaystyle\sum_{k\in S_{t}}w_{k}\Delta\theta_{k}^{t}$
$\displaystyle=\sum_{k\in
S_{t}}\mathbb{\Delta}_{t}\frac{\mathbb{p}_{k}}{\|\mathbb{p}_{k}\|}w_{k}\|\mathbb{p}_{k}\|$
(31)
$\displaystyle=\mathbb{\Delta}_{t}\mathbb{P}_{t}(\mathbb{w}\odot[\|\mathbb{p}_{1}\|,...,\|\mathbb{p}_{M}\|]^{\top})$
(32) $\displaystyle=\mathbb{\Delta}_{t}\mathbb{P}_{t}\mathbb{\tilde{w}}$ (33)

When there exists an optimal weight vector $\mathbb{w}^{*}$ such that
$\exists\mu>0,\mu\mathbb{P}_{t}\mathbb{w}^{*}=\mathbb{p}^{*}$, we demonstrate
that the sampled subset can well approximate the true model update, which
requires the true weight $\mathbb{p}^{*}$ to fall into the region of the
convex cone $\mu\mathbb{P}_{t}\mathbb{w}^{*}$. Given the assumption that
$p^{*}$ is uniformly distributed in the simplex of $\mathbb{R}^{C}$, the
problem becomes how to compare the probability
$\textit{Pr}\left(\mathbb{p}^{*}\in\\{\mu\mathbb{P}_{t}\mathbb{w}^{*}|\mathbb{1}^{\top}\mathbb{w}=1,\mathbb{w}\geq
0,\mu>0\\}\right)$ for different $\mathbb{P}_{t}$.

Figure 6: The example of the angle of $n$ vectors in $n$-dimension space,
where $n=2$ for the left and $n=3$ for the right.

Let’s first consider the 2-dimension case (i.e. the left one of Fig.6). Given
two vectors $p_{1}$ and $p_{2}$, the probability can be measured by the ratio
of the angle between $p_{1}$ and $p_{2}$ as $\frac{\phi}{\pi/2}$. For the
cases where the dimension is higher than $n=2$ (i.e. the right one in Fig.6.),
(Ribando 2006) defines the normalized measurement of solid angle

$\displaystyle\tilde{V}_{\Omega}=\frac{\text{vol}_{C}(\Omega\cap
B_{C})}{\text{vol}_{C}(B_{C})}=\frac{\text{vol}_{C-1}(\Omega\cap
S_{C-1})}{\text{vol}_{C-1}S_{C-1}}$ (34)

where $\text{vol}_{C}$ is the usual volume form in $\mathbb{R}^{C}$, $B_{C}$
is the unit ball in $\mathbb{R}^{C}$ and $S_{C}$ is the unit $C$-sphere.
Further, they provide a way to compute the solid angle for $C$ unit positive
vector

$\displaystyle\tilde{V}_{\Omega}=\frac{1}{\pi^{C/2}}\int_{\mathbb{R}^{C}_{\geq
0}}e^{-\mathbb{u}^{\top}\mathbb{P}_{t}^{\top}\mathbb{P}_{t}\mathbb{u}}|\det\mathbb{P}_{t}|d\mathbb{u}$
(35)

which represents the probability of the optimal weight in the convex cone by
projecting $p^{*}$ and each ray (i.e. column) in $\mathbb{P}_{t}$ onto the
surface of a unit sphere centered at $O$ in $\mathbb{R}^{C}$.

For the case where the number of sampled clients $M$ is smaller than $C$ or
$M=C$ but $|\det\mathbb{P}_{t}|=0$, we have $\tilde{V}_{\Omega}=0$ (i.e.
simply repeating one of the vectors in $P_{t}$ when $M<C$ until the number of
vectors reaches $C$), which means it’s nearly impossible to recover the
uniformly distributed optimal weight by directly modifying the aggregation
weights of the sampled clients. One way to approximate the global model update
in this case is to choose clients with higher data quality in priority (i.e.
local data distribution similar to the global one), which needs
$\mathbb{p}^{*}$ and $\mathbb{p}_{k}$ are already known and is out of the
scope of our discussion. Therefore, we limit our discussion to the case where
$|\det\mathbb{P}_{t}|\neq 0$ and $M=C$ (i.e. the solid angle for $M>C$ can be
computed by first dissecting $\mathbb{P}_{t}$ into simplicial cones (Ribando
2006)).

Based on the equation (35), we demonstrate that the large average shortest-
path distance will encourage a large $\tilde{V}_{\Omega}$. We rearrang the
equation (35) as

$\displaystyle\tilde{V}_{\Omega}=\left(\frac{|\det\mathbb{P}_{t}|}{\pi^{C/2}}\right)\left(\int_{\mathbb{R}^{C}_{\geq
0}}e^{-\sum_{i,j\in[C]}u_{i}u_{j}\mathbb{e}_{i}^{\top}\mathbb{e}_{j}}d\mathbb{u}\right)$
(36)

Now we respectively show how enlarging the average shortest-path distance
(i.e. the equation (24)) leads to the increasing of the two terms on the right
hand side of the equation (36).

#### The Impact on The First Term.

To study how the determinant is impacted by the average shortest-path distance
of the sampled clients, we compute the volume of the parallelepiped with the
columns in $\mathbb{P}_{t}$ (i.e. Definition 1 and Definition 2) to obtain
$|\det\mathbb{P}_{t}|$ according to Lemma 1 (Peng 2007).

######  Definition 1.

Let $\mathbb{e}_{1},...,\mathbb{e}_{C}\in\mathbb{R}^{C}$. A parallelepiped
$P=P(\mathbb{e}_{1},...,e_{C})$ is the set

$\displaystyle P=\\{\sum_{i=1}^{C}t_{i}\mathbb{e}_{i}|0\leq t_{i}\leq 1\text{
for }i\text{ from }1\text{ to }C\\}$ (37)

######  Definition 2.

The $n$-dimensional volume of a parallelepiped is

$\displaystyle\begin{split}\text{Vol}_{k}[P(\mathbb{e}_{1},...,\mathbb{e}_{k})]=\left\\{\begin{array}[]{ll}\|\mathbb{e}_{1}\|,&k=1\\\
\text{Vol}_{k-1}[P(\mathbb{e}_{1},...,\mathbb{e}_{k-1})]\|\mathbb{\tilde{e}}_{k}\|,&k>1\end{array}\right.\end{split}$

where
$\mathbb{\tilde{e}}_{k}=\mathbb{e}_{k}+(\mathbb{e}_{1},...,\mathbb{e}_{k-1})\mathbb{a}=\mathbb{e}_{k}+\mathbb{E}_{k-1}\mathbb{a}_{k}$
and the unique chosen of $\mathbb{a}_{k}$ satisfies
$\mathbb{\tilde{e}}_{k}^{\top}\mathbb{e}_{i}=0,\forall i\in[k-1]$.

######  Lemma 1.

Given a $C$-dimensional parallelepiped $P$ in $C$-dimensional space defined by
columns in $\mathbb{P}_{t}$, we have $\text{Vol}_{C}(P)=|\det\mathbb{P}_{t}|$

By denoting $P_{k}=P(\mathbb{e}_{1},...,\mathbb{e}_{k})$, the absolute value
of the determinant of $\mathbb{P}_{t}$ is

$\displaystyle|\det\mathbb{P}_{t}|=\text{Vol}_{C}(P_{C})=||\mathbb{\tilde{e}}_{C}||\text{Vol}_{C-1}(P_{C-1})$
(38)
$\displaystyle=\sqrt{(\mathbb{e}_{C}+\mathbb{E}_{C-1}\mathbb{a}_{C})^{\top}(\mathbb{e}_{C}+\mathbb{E}_{C-1}\mathbb{a}_{C})}\text{Vol}_{C-1}(P_{C-1})$
(39)

Since $\mathbb{\tilde{e}}_{C}^{\top}\mathbb{e}_{i}=0,\forall i\in[C-1]$, we
have

$\displaystyle\mathbb{E}_{C-1}^{\top}(\mathbb{e}_{C}+\mathbb{E}_{C-1}\mathbb{a}_{C})=0$
(40) $\displaystyle\Rightarrow\mathbb{a}_{C}$
$\displaystyle=-(\mathbb{E}_{C-1}^{\top}\mathbb{E}_{C-1})^{-1}\mathbb{E}_{C-1}^{\top}\mathbb{e}_{C}$
(41)

Thus, the inner product of $\mathbb{\tilde{e}}_{C}$ with itself is

$\displaystyle\mathbb{\tilde{e}}_{C}^{\top}\mathbb{\tilde{e}}_{C}=\|\mathbb{e}_{C}-\mathbb{E}_{C-1}(\mathbb{E}_{C-1}^{\top}\mathbb{E}_{C-1})^{-1}\mathbb{E}_{C-1}^{\top}\mathbb{e}_{C}\|_{2}^{2}$
(42) $\displaystyle=1-[\mathbb{e}_{C}^{\top}\mathbb{e}_{i}]_{i\neq
C}^{\top}(\mathbb{E}_{C-1}^{\top}\mathbb{E}_{C-1})^{-1}[\mathbb{e}_{C}^{\top}\mathbb{e}_{i}]_{i\neq
C}$ (43)

Given $|\det P|\neq 0\rightarrow rank(\mathbb{E}_{C-1})=C-1$, we have that
$\mathbb{E}_{C-1}^{\top}\mathbb{E}_{C-1}$ is a real symmetric matrix and full
rank, which indicates that it is orthogonally diagonalizable. Thus, we
orthogonally diagonalize $\mathbb{E}_{C-1}^{\top}\mathbb{E}_{C-1}$ into
$Q\Lambda Q^{\top}$ to obtain its inverse
$(\mathbb{E}_{C-1}^{\top}\mathbb{E}_{C-1})^{-1}=Q\Lambda^{-1}Q^{\top}$ where
$\lambda_{i}>0$. And we rewrite the equation (43) with
$\mathbb{h}_{C}=[\mathbb{e}_{C}^{\top}\mathbb{e}_{1},...,\mathbb{e}_{C}^{\top}\mathbb{e}_{C-1}]$
as:

$\displaystyle 1-\mathbb{h}_{C}^{\top}\tilde{Q}\tilde{Q}^{\top}\mathbb{h}_{C}$
$\displaystyle=1-\|\tilde{Q}\mathbb{h}_{C}\|_{2}^{2}$ (44)
$\displaystyle=1-\sum_{i=1}^{C-1}\frac{h_{i}^{2}}{\lambda_{i}^{2}}$ (45)
$\displaystyle=1-\sum_{i=1}^{C-1}\frac{1}{\lambda_{i}^{2}}(\mathbb{e}_{C}^{\top}\mathbb{e}_{i})^{2}$
(46)

From the equation (46), we can see that keeping $\mathbb{e}_{C}$ less similar
with all the other vectors (i.e. $\mathbb{e}_{C}^{\top}\mathbb{e}_{i},\forall
i\neq C$) will increase $|\det\mathbb{P}_{t}|$. In addition, the analysis
doesn’t specify the $C$th vector in $\mathbb{P}_{t}$ to be any particular
client. Therefore, enlarging $f(S_{t})$ will also enlarge the absolute value
of the determinant of $\mathbb{P}_{t}$.

#### The Impact on The Second Term.

According to Cauchy–Schwarz inequality,

$\displaystyle\int_{\mathbb{R}^{C}_{\geq
0}}e^{-\sum_{i,j\in[C]}u_{i}u_{j}\mathbb{e}_{i}^{\top}\mathbb{e}_{j}}d\mathbb{u}$
(47) $\displaystyle\geq\int_{\mathbb{R}^{C}_{\geq 0}}$ $\displaystyle
e^{-\sqrt{\sum_{i,j\in[C]}(u_{i}u_{j})^{2}}\sqrt{\sum_{i,j\in[C]}(\mathbb{e}_{i}^{\top}\mathbb{e}_{j})^{2}}}d\mathbb{u}$
(48) $\displaystyle\geq\int_{\mathbb{R}^{C}_{\geq 0}}$ $\displaystyle
e^{-\sqrt{\sum_{i,j\in[C]}(u_{i}u_{j})^{2}}\sqrt{\sum_{i,j\in[C]}\mathbb{e}_{i}^{\top}\mathbb{e}_{j}}}d\mathbb{u}$
(49) $\displaystyle=\int_{\mathbb{R}^{C}_{\geq 0}}$ $\displaystyle
e^{-\sqrt{\sum_{i,j\in[C]}(u_{i}u_{j})^{2}}\|\mathbb{P}_{t}^{\top}\mathbb{P}_{t}\|_{m1}^{\frac{1}{2}}}d\mathbb{u}$
(50)

which indicates that enlarging $f(S_{t})$ in the equation (24) can improve the
lower bound of the second term of the solid angle.

Therefore, we conclude that keeping the average shortest-path distance of the
sampled subset to be large will increase the chance to find a proper
aggregation weight to well approximate the true model update.

∎

##  Appendix B B. Results on Constructed 3DG

We also run FedGS on the 3DG constructed by using the proposed functional
similarity and cosine similarity of model parameters. We vary the same
$\alpha\in\\{0,0.5,1,2,5\\}$ for $\text{FedGS}_{func}$ and
$\text{FedGS}_{cos}$, and list the optimal results of them with the same
settings of Table 2, as is listed in Table 4. For Synthetic dataset,
$\text{FedGS}_{cos}$ outperforms $\textbf{FedGS}and\textbf{FedGS}_{func}$
under most of the client availability, which suggests that our definition of
the oracle graph on Synthetic dataset is not the true oracle one. For CIFAR10,
$\text{FedGS}_{func}$’s performance is competitive with the results obtained
by FedGS, and the two methods consistently outperform $\textbf{FedGS}_{cos}$
in most cases. For FashionMNIST, $\text{FedGS}_{func}$ and
$\text{FedGS}_{cos}$ suffer more performance reduction than CIFAR10. However,
they still outperform MDSample and UniformSample when client availability
changes (0.313 v.s. 0.333 in YC).

Setting | FedGS | $\textbf{FedGS}_{func}$ | $\textbf{FedGS}_{cos}$
---|---|---|---
Synthetic | IDL | 0.306 | 0.304 | 0.304
LN | 0.305 | 0.306 | 0.304
SLN | 0.318 | 0.319 | 0.318
LDF | 0.308 | 0.306 | 0.307
MDF | 0.310 | 0.310 | 0.309
CIFAR10 | IDL | 0.968 | 0.963 | 0.971
LN | 0.972 | 0.972 | 0.973
SLN | 0.996 | 0.991 | 0.994
LDF | 0.966 | 0.975 | 0.967
MDF | 0.963 | 0.962 | 0.965
Fashion | IDL | 0.299 | 0.305 | 0.304
YMF | 0.303 | 0.307 | 0.307
YC | 0.307 | 0.314 | 0.313
Table 4: The comparison of testing loss of FedGS running on the
Oracle/Constructed 3DG.

##  Appendix C C. Experimental Details

### Datasets

#### Synthetic.

We follow the setting in (Li et al. 2020) to generate this dataset by

$\displaystyle
y_{k,i}=\text{argmax}\\{softmax(\mathbb{W}_{k}\mathbb{x}_{k,i}+\mathbb{b}_{k})\\}$
(51)

where $(\mathbb{x}_{k,i},y_{k,i})$ is the $i$th example in the local data
$D_{k}$ of client $c_{k}$. For each client $c_{k}$, its local optimal model
parameter $(\mathbb{W}_{k},\mathbb{b}_{k})$ is generated by
$\mu_{k}\sim\mathcal{N}(0,\alpha)\in\mathbb{R},\mathbb{W}_{k}[i,j]\sim\mathcal{N}(\mu_{k},1),\mathbb{W}_{k}\in\mathbb{R}^{10\times
60},\mathbb{b}_{k}[i]\sim\mathcal{N}(\mu_{k},1),\mathbb{b}_{k}\in\mathbb{R}^{10}$,
and its local data distribution is generated by
$B_{k}\sim\mathcal{N}(0,\beta),\mathbb{v}_{k}[i]\sim\mathcal{N}(B_{k},1),\mathbb{v}_{k}\in\mathbb{R}^{60},\mathbb{x}_{k,i}\sim\mathcal{N}(\mathbb{v}_{k},\mathbb{\Sigma})\in\mathbb{R}^{60},\mathbb{\Sigma}=\text{diag}(\\{i^{-1.2}\\}_{i=1}^{60})$.
The local data size for each client is $n_{k}\sim lognormal(4,2)$. In our
experiments, we generate this dataset for 30 clients with $\alpha=\beta=0.5$.

#### CIFAR10.

The CIFAR10 dataset (Krizhevsky, Hinton et al. 2009) consists of totally 60000
32x32 colour images in 10 classes (i.e. 50000 training images and 10000 test
images). We partition this dataset into 100 clients with both data size
imbalance and data heterogeneity. To create the data imbalance, we set each
client’s local data size $n_{k}\sim lognormal(log(\frac{n}{N})-0.5,1)$ to keep
the mean data size is $\bar{n}=\frac{n}{N}$. Then, we generate the local label
distribution $\mathbb{p}_{k}\sim Dirichlet(\alpha\mathbb{p}*)$ for each
client, where $\mathbb{p}*$is the label distribution in the original dataset.
Particularly, we loop replacing the local label distribution of clients with
the new generated one from the same distribution until there exists no
conflict with the allocated local data sizes, which allows the coexisting of
controllable data imbalance and data heterogeneity. We use $\alpha=1.75$ in
our experiments and provide the visualized partition in Fig.7(a).

#### FashionMNIST.

The dataset (Xiao, Rasul, and Vollgraf 2017) consists of a training set of
60,000 examples and a test set of 10,000 examples, where each example is a
$28\times 28$ size image of fashion and associated with a label from 10
classes. In this work, we partition this dataset into 100 clients and equally
allocate the same number of examples to each one, where each client owns data
from two labels according to (McMahan et al. 2017). A direct visualization of
the partitioned result is provided in Fig.7(b).

(a) CIFAR10

(b) FashionMNIST

Figure 7: The visualization of data partition for CIFAR10 (a) and FashionMNIST
(b). Each bar in the figures represents a client’s local dataset and each
label is assign to one color. The length of each bar reflects the size of the
local data.

#### Models.

For CIFAR10 and FashionMNIST, we use CNNs that are respectively used for
CIFAR10 and MNIST in (McMahan et al. 2017). For Synthetic dataset, we use the
same logistical regression model as (Li et al. 2020).

### Hyperparameters

For each dataset, we partition each client’s local data into training and
validating parts. Then, we tune the hyperparameters with FedAvg(McMahan et al.
2017) by grid search on the validation datasets under the ideal client
availability. The batch size is $B=10$ for Synthetic and $B=32$ for both
CIFAR10 and FashionMNIST. Specifically, we fixed the local updating steps
instead of epochs to avoid unexpected bias caused by imbalanced data (Wang et
al. 2020). We search the number of local update steps in $E\in\\{10,50,100\\}$
for all the datasets and the learning rate
$\eta_{Synthetic}\in\\{0.01,0.05,0.1,0.3\\},\eta_{CIFAR10,Fashion}\in\\{0.003,0.01,0.03,0.1\\}$.
For CIFAR10, the optimal parameters are $E=10,\eta=0.03$ and we train the
model for 1000 rounds. For Synthetic, we train the model for 1000 round using
$\eta=0.1,E=10$. For FashionMNIST, we train the model for 500 rounds with the
optimal parameters $E=10,\eta=0.1$. We round-wisely decay the learning srate
by a factor of $0.998$ for all the datasets. To simulate the communication
constraint of the server, we fixed the proportion of selected clients to be
$0.1$ for CIFAR10 and FashionMNIST, $0.2$ for Synthetic dataset.

### Client Availability Modes

To obtain the results in Table 2, we conduct experiments under the client
availability modes of IDL, LN0.5, SLN0.5, LDF0.7, MDF0.7, YMF0.9 and YC0.9
across different datasets, where the float number at the end of the name of
these settings is the coefficient $\beta$ that controls the degree of the
global unavailability of clients. For each client availability mode, we
visualize the active states of clients in each communication round, which
provides an intuitive way to distinguish the difference between the client
availability modes. In Fig.8, we respectively visualize the IDL, LDF0.7,
MDF0.7 in Synthetic, LN0.5, SLN0.5 in CIFAR10 and YMF0.9, YC0.9 in
FashionMNIST. For a fair comparison of different methods, we use an
independent random seed (i.e. independent to the other random seeds used to
optimizing the model) to control the active states of clients in each
communication round, which promise the active states of clients will stay the
same when running different methods.

Figure 8: The active states of clients in each communication round under
different availability modes.

### Oracle 3DG For Datasets

For FashionMNIST and CIFAR10, we use the local data distribution vectors as
the features to calculate the similarities among clients. For Synthetic, since
the difference between clients’ local data mainly locates in the optimal
model, we directly use the local optimal model parameters
$(\mathbb{W}_{k},\mathbb{b}_{k})$ as the feature vectors. Then, we use the
inner dot as the similarity function to compute the similarity matrix
$\mathbb{V}$. We further normalize the similarity value $V_{ij}$ to $[0,1]$ by
computing
$V_{ij}^{\prime}=\frac{V_{ij}-\min_{i,j}V_{ij}}{\max_{i,j}V_{ij}-\min_{i,j}V_{ij}}$,
and finally use the normalized similarity matrices to construst the oracle
3DGs as mentioned in Sec.3.2.

##  Appendix D D. Scalar Product Protocal

In our first method to construct the 3DG, we use techniques based on SSPP to
compute the dot product of private vectors of parties. We argue that any
existing solutions of SSPP can be used in our settings. Here we introduce (Du
and Zhan 2002) to our FL scenario. The original protocol works as follows.
Alice and Bob have different features on the same individuals and want to
calculate the scalar product of their private vectors $\mathbb{A}$ and
$\mathbb{B}$, both of size $m$ where $m$ is the sample size of the datasets.
They will do this with the help of a commodity server we have named Merlin.
The protocol consists of the following steps. First, Merlin generates two
random vectors $\mathbb{R}_{a}$, $\mathbb{R}_{b}$ of size $m$ and two scalars
$r_{a}$ and $r_{b}$ such that $r_{a}+r_{b}=\mathbb{R}_{a}\cdot\mathbb{R}_{b}$,
where either $r_{a}$ or $r_{b}$ is randomly generated. Merlin than sends
$\\{\mathbb{R}_{a},r_{a}\\}$ to Alice and $\\{\mathbb{R}_{b},r_{b}\\}$ to Bob.
Second, Alice sends $\mathbb{\hat{A}}=\mathbb{A}+\mathbb{R}_{a}$ to Bob, and
Bob sends $\mathbb{\hat{B}}=\mathbb{B}+\mathbb{R}_{b}$ to Alice. Third, Bob
generates a random number $v_{2}$ and computes
$u=\mathbb{\hat{A}}\cdot\mathbb{B}+r_{b}-v_{2}$, then sends the result to
Alice. Fourth, Alice computes
$u-(\mathbb{R_{a}}\cdot\mathbb{\hat{B}})+r_{a}=\mathbb{A}\cdot\mathbb{B}-v_{2}=v_{1}$
and sends the result to Bob. Finally, Bob then calculates the final result
$v_{1}+v_{2}=\mathbb{A}\cdot\mathbb{B}$. In our FL settings, since there are
no communications between clients, we pass intermediate variables between
clients through the server. The pseudo codes in Algorithm 2 summarizes the
steps of scalar product in our FL settings.

Algorithm 2 Scalar Product

Input:The client $A$’s feature vector $\mathbb{A}\in\mathbb{R}^{d}$, and the
client $B$’s feature vector $\mathbb{B}\in\mathbb{R}^{d}$

1: Server generates two random vectors $\mathbb{R}_{a}\in\mathbb{R}^{d}$,
$\mathbb{R}_{b}\in\mathbb{R}^{d}$ and two scalars $r_{a}$ and $r_{b}$ such
that $r_{a}+r_{b}=\mathbb{R}_{a}\cdot\mathbb{R}_{b}$, where either $r_{a}$ or
$r_{b}$ is randomly generated.

2: Server sends $\\{\mathbb{R}_{a},r_{a}\\}$ to client $A$ and
$\\{\mathbb{R}_{b},r_{b}\\}$ to client $B$.

3: Client $A$ sends $\mathbb{\hat{A}}=\mathbb{A}+\mathbb{R}_{a}$ to server,
and client $B$ sends $\mathbb{\hat{B}}=\mathbb{B}+\mathbb{R}_{b}$ to server.

4: Server sends $\mathbb{\hat{A}}$ to client $B$, and $\mathbb{\hat{B}}$ to
client $A$.

5: Client $B$ generates a random number $v_{2}$ and computes
$u=\mathbb{\hat{A}}\cdot\mathbb{B}+r_{b}-v_{2}$, then sends $u$ and $v_{2}$ to
server.

6: Server sends $u$ to client $A$.

7: Client $A$ computes
$u-(\mathbb{R_{a}}\cdot\mathbb{\hat{B}})+r_{a}=\mathbb{A}\cdot\mathbb{B}-v_{2}=v_{1}$
and sends $v_{1}$ to the server.

8: Server calculates the scalar product
$v_{1}+v_{2}=\mathbb{A}\cdot\mathbb{B}$.


# Expanding RIB Capabilities at the Cyclotron Institute: 3He-LIG production
with an Isobar Separator LSTAR

D. Melconian<EMAIL_ADDRESS>G.P.A. Berg  P.D. Shidling  M. Couder  M.
Brodeur  G. Chubarian  V.E. Iacob  J. Klimo  G. Tabacaru

###### Abstract

A new 3He-driven IGISOL production station and mass separator have been
designed to produce neutron-deficient low-mass isotopes at the Cyclotron
Institute for the TAMUTRAP facility. The LSTAR design has a mass resolution
$M/\Delta M\geq 3,000$ to reject contaminants with $>95\%$ efficiency.

###### keywords:

High-resolution isobar separator , Light-ion guide , Charged-particle
spectrometers

††journal: Nuclear Instruments and Methods in Physics Research B

[CI]Cyclotron Institute, Texas A&M University, College Station, TX USA
77843-3366 [PHYS]Department of Physics & Astronomy, Texas A&M University,
College Station, TX USA 77843-4242 [ND]Department of Physics & Astronomy,
University of Notre Dame, Notre Dame, IN USA 46556

##  1 Introduction

The primary goal of a new facility, TAMUTRAP, at the Cyclotron Institute,
Texas A&M University, is to look for physics beyond the standard model by
searching for possible scalar or tensor currents contributing to the weak
interaction in nuclear $\beta$ decay [1, 2, 3]. In particular, it will enable
the measurement of the $\beta$-$\nu$ correlation parameter in several $T=2$
and $T=3/2$ superallowed $\beta$-delayed proton emitters initially confined in
a novel and unique cylindrical Penning trap [4]. This trap has been designed
to be very large (180-mm inner diameter) so that $\beta$-delayed protons of up
to 4.25 MeV energy are fully contained radially by the 7-T field of the
magnet. We have commissioned the TAMUTRAP facility by demonstrating the
ability to perform precise mass measurements using offline ion sources. Once
the radioactive ion beam (RIB) is successfully produced and transported to
TAMUTRAP, we will be uniquely suited to observe the $\beta$-delayed proton
decays of 20,21Mg, 24,25Si, 28,29S, 32,33Ar and 36,37Ca with $4\pi$ collection
of the $\beta$s and delayed protons. An overview of the TAMUTRAP facility and
scientific program is described in Ref. [5].

Here we describe our plans for producing the proton-rich beams for TAMUTRAP
(the “He-LIG” station) and the separator (“LSTAR”) designed to purify and
transport the beams to the TAMUTRAP facility.

##  2 RIB Production: 3He-LIG

The K150 cyclotron has been recommissioned at the Cyclotron Institute (CI) at
Texas A&M to produce these radioactive ion beams using the IGISOL (Ion Guide
Isotope Separator On-Line) technique [6]. In this technique the nuclei of
interest are produced by a primary beam of protons on a thin target. The low-
energy fusion-evaporation reaction products enter a small chamber ($\sim$1
cm3) filled with ultra-high purity helium gas. The products are slowed down in
the gas and transported by a gas flow out of the gas cell and injected through
a differentially-pumped electrode system to the high-vacuum section of an
isotope separator for further acceleration and separation. The IGISOL
technique extracts ions very quickly ($\approx$1 ms) allowing for the
extraction of short-lived nuclei with typically $\approx$1% efficiency [7].

The current $p$-LIG effort at the CI uses up to 40-MeV protons for $(p,n)$
reactions, charge-breeds the extracted reaction products in a ECRIS before
injecting into the CI’s K500 superconducting cyclotron for re-acceleration
[8]. In order to produce the neutron-deficient RIBs of interest for TAMUTRAP
via ($p,2n$) and ($p,3n$) reactions, adequate production requires using
$(10-22)$ MeV/u 3He as the driver for the LIG station rather than protons;
thus we are developing a new “He-LIG” system which will share a gas-cell
chamber with the current $p$-LIG, but use separate gas-cells and extract RIB
in the opposite direction to a new beamline.

Figure 1: The He-LIG gas cell and SPIG system (top) and observed decay
spectrum with our test cell (bottom). The K150 3He primary beam reacts with a
thin target mounted in front of the gas cell (not shown, out of the page). The
reaction products are stopped in the gas cell are quickly transported to the
two-stage SPIG transport system by the high flow of helium gas. The low energy
part of the decay product spectrum is dominated by $\beta$s, but the proton
peaks from 25Si are clearly seen.

We have tested a prototype gas cell, depicted in the top panel of Fig. 1,
using a natMg target and observed the three prominent proton branches
following the $\beta$ decay of 25Si (see the lower panel of Fig. 1). The
efficiency of the system was about $1-2$ orders of magnitude below other LIG
systems (e.g. at Jyväskylä), but our updated design addresses many expected
deficiencies of the prototype and we expect to reach efficiencies of $\geq$1%.
We have designed a new chamber which will allow for precise alignment of both
$p$\- and He-LIG stations as well as quick and simple changeover procedures
between the two systems. Once the new He-LIG system is assembled, we will
characterize its efficiency and emittance using the pepper-pot technique.

##  3 RIB Purification: LSTAR

The isotopes of interest for the TAMUTRAP program are relatively far from
stability, so the production rates of nearby contaminants are a concern
because too much beam can overload the RFQ cooler and buncher. We therefore
require an isobar separator capable of purifying the produced RIB well enough
to purify the most difficult case, separating 36Ca from 36K. The most
significant design requirements for the separator are:

  1. 1.

A mass resolving power of $M/\Delta M\geq 3,000$ for $6\leq A\leq 50$,

  2. 2.

High acceptance and transmission ($>95\%$),

  3. 3.

No energy compensation (meaning no electric dispersive elements),

  4. 4.

Purely electrostatic focusing elements (so that settings are independent of
mass), and

  5. 5.

The separator must be compact to fit in the existing space available in Cave 5
of the Cyclotron Institute (see Fig. 2) and have the focus be at the entrance
to TAMUTRAP’s RFQ cooler and buncher.

Figure 2: Top view of Cave 5 showing the planned layout of LSTAR. RIB produced
in the He-LIG will be transported out of the $p$/He-LIG chamber with SPIGs and
accelerated to 65 keV to the object of LSTAR. The RFQ placed at the focal
plane of LSTAR will collect the purified RIB, allowing easy transport of
cooled, bunched beams to the TAMUTRAP facility.

Our design, the Light-ion guide Separator for Texas A&M’s Radioactive ion
beams (LSTAR), was inspired by the concept of CARIBU’s separator at ANL [9]
since it shares many of the design specifications. The elements of our design
and how it will couple to the He-LIG are schematically shown in Fig. 2. The
primary $p$ or 3He beam from the K150 enters from the left and the RIBs are
produced in the dual $p$/He-LIG chamber; when running in He-LIG mode, the RIB
will be directed down and turned $30^{\circ}$ via a curved sextupole ion guide
(SPIG) and then accelerated to 65 keV to the object of LSTAR. After a 1.2 m
long drift, the beam is tuned by several electrostatic elements, bent
horizontally by two $62.5^{\circ}$ dipole magnets B1 and B2, with an
electrostatic multipole, M, between the dipoles, and focused by several
electrostatic quadrupoles onto the focal plane. Two electrostatic hexapoles,
S1 and S2, are included in the combined function multipoles (Q+oct)1,2. The
layout is symmetric about the central electrostatic multipole M to reduce
higher-order aberrations. This ion optics for this system, shown with sample
ray traces in Fig. 3, has been optimized to 3rd order and verified to 7th
order using the program COSY INFINITY [10]. The technical design of LSTAR will
be described in detail in a forthcoming publication [11].

Figure 3: Dispersive (horizontal) and non-dispersive (vertical) ion optics of
the LSTAR design.

We have performed detailed studies of the expected performance of LSTAR based
on the ion optics calculated in COSY. We start with the distribution of ion
positions and velocities from the end of the SPIG of the He-LIG system as
simulated by SIMION [12]. Using these rays as input, we accelerated the ions
to 65 keV and traced them through LSTAR using COSY. The same initial rays but
with a mass difference $\Delta M/M=3,000$ were also traced to determine how
well contaminants will be vetoed. The studies included the
$0.65\pi\,\mathrm{mm}\,\mathrm{mrad}$ emittance and 3.33 eV energy spread
predicted by SIMION. Position and angular misalignments of the elements of
LSTAR were randomly varied as Gaussians of widths 0.25 mm and 0.25 mrad,
respectively, and the results averaged to determine the tolerances required.
Figure 4 shows the distribution of ions at the focal plane of LSTAR (top) and
how broadened the distributions are if the initial emittance is twice what
SIMION predicts (bottom). Similar results are seen when other tolerances
($\Delta E$ and positions/angles of elements) are similarly broken.

In summary, LSTAR is expected to have a $\geq 95\%$ efficiency for the ions of
interest while completely removing all contaminants if position and angular
misalignments are $\leq$0.25 mm and $\leq$0.25 mrad, respectively, and SIMION
estimates of the emittance and energy spread are realistic.

Figure 4: Performance of LSTAR using the initial emittance and energy spread
as simulated by SIMION. Top: distribution of good (green) and $\Delta
M/M=3,000$ contaminant (red) ions at the focal plane of LSTAR. Bottom: same,
but with twice the emittance estimated using SIMION. Complete separation of
the contaminants is still achievable with 75% acceptance of the species of
interest..

##  4 Outlook

A new beamline for the production and purification of proton-rich beams, which
will enable TAMUTRAP’s studies of $\beta$ decay to test the standard model has
been described. Detailed studies of the design indicate the separator will
completely remove contaminants with masses $M/\Delta M\geq 3,000$ with $>95\%$
transmission. Longer term future prospects include using TAMUTRAP for
astrophysical studies with the Rogachev group, and injecting the cooled,
bunched RIB into the K500 after charge-breeding with an EBIT.

##  5 Acknowledgements

This work was supported by the U.S. Department of Energy, Ofﬁce of Science,
under Award No. DEFG02-93ER40773, and by the Department of Energy, National
Nuclear Security Administration under Award No. DE-NA0003841 (CENTAUR).
G.P.A.B., M.B., and M.C. acknowledge support of the National Science
Foundation under Grant PHY-2011890.

## References

  * [1] J.D. Jackson, S.B. Treiman and H.W. Wyld, Phys. Rev. 106, 517 (1957).
  * [2] A. Falkowski, M. Gonzáleez-Alonso and O. Naviliat-Cuncic, J. High Energy Phys. 2021, 126 (2021).
  * [3] P.D. Shidling, _et al._ , Hyperﬁne Interact. 240, 40 (2019).
  * [4] M. Mehlman, _et al._ , Nucl. Instr. and Meths. A712, 9 (2013).
  * [5] P.D. Shidling, _et al._ , Int J. Mass Spect 468, 116636 (2021).
  * [6] I. Moore, P. Dendooven and J. Arje, Hyperfine Interacts 223, 17 (2014).
  * [7] J. Äystö, Nucl. Phys. A 693, 477 (2001).
  * [8] D.P. May, F.P. Abegglen, J. Arje, and G. Tabacaru, “Charge-Breeding of Radioactive Ions at the Texas A&M Cyclotron Institute”, in _Proc. ECRIS’18_ , Catania, Italy, Sep 2018, pp. 20–23.
  * [9] C.N. Davids and D. Peterson, Nucl. Instrum. Meth. in Phys. Res. B266, 4449 (2008).
  * [10] K. Makino and M. Berz, “COSY INFINITY Version 9,” Nucl. Instrum. Meth. in Phys. Res. A558, 346715 (2006).
  * [11] G.P.A. Berg, _et al._ , in preparation.
  * [12] D.A. Dahl, Int. J. Mass. Spectr. 3, 200 (2000).