# Differentially Private Distributed Computation
via Public-Private Communication Networks

Lei Wang, Yang Liu, Ian Manchester, and Guodong Shi L. Wang, I. Manchester and
G. Shi are with Australian Centre for Field Robotics, The University of
Sydney, Australia. E-mail: (lei.wang2; ian.manchester;
guodong.shi@sydney.edu.au)Y. Liu is with Tencent Cloud Product Department,
P.R. China. E-mail<EMAIL_ADDRESS>
###### Abstract

This paper studies the problem of multi-agent computation under the
differential privacy requirement of the agents’ local datasets against
eavesdroppers having access to node-to-node communications. We first propose
for the network equipped with public-private networks. The private network is
sparse and not even necessarily connected, over which communications are
encrypted and secure along with the intermediate node states; the public
network is connected and may be dense, over which communications are allowed
to be public. In this setting, we propose a multi-gossip Privacy-
Preserving/Summation-Consistent (PPSC) mechanism over the private network,
where at each step, randomly selected node pairs update their states in such a
way that they are shuffled with random noise while maintaining summation
consistency. It is shown that this mechanism can achieve any desired
differential privacy level with any prescribed probability. Next, we embed
this mechanism in distributed computing processes, and propose privacy-
guarantee protocols for three basic computation tasks, where an adaptive
mechanism adjusts the amount of noise injected in PPSC steps for privacy
protection, and the number of regular computation steps for accuracy
guarantee. For average consensus, we develop a PPSC-Gossip averaging consensus
algorithm by utilizing the multi-gossip PPSC mechanism for privacy encryption
before an averaging consensus algorithm over the public network for local
computations. For network linear equations and distributed convex
optimization, we develop two respective distributed computing protocols by
following the PPSC-Gossip averaging consensus algorithm with an additional
projection or gradient descent step within each step of computation. Given any
privacy and accuracy requirements, it is shown that all three proposed
protocols can compute their corresponding problems with the desired
computation accuracy, while achieving the desired differential privacy.
Numerical examples are used to illustrate the validity of the established
theoretical results. In particular, our framework demonstrates clear
improvements in terms of learning accuracy for classification problems
compared to existing approaches under the same privacy budget.

##  1 Introduction

The study of distributed algorithms for network-wide computation problems over
a multi-agent system is an emerging research topic of significance in the
fields of smart grids [1], mobile robotic networks [2], intelligent
transportation [3] and machine learning [4, 5]. In such problems, each agent
(or node, representing a subsystem or a computing unit) over a network is
assigned with a local dataset over which a local cost function is defined.
Under a distributed computing scheme, the local datasets are encoded in either
individual initial node states or update rules; agents share their node states
over a communication network; these node states are updated based on the local
datasets and the received neighboring states. During such a computing process,
when an attacker, a malicious user, or an eavesdropper has access to part or
the entirety of node-to-node communications, the local datasets/costs may be
inferred. Since the local dataset or cost function of an agent may contain
sensitive private information for the agent, new risks of privacy breach
arise.

In the literature, several insightful privacy-preserving distributed computing
frameworks have been proposed. First of all, datasets themselves may be
encrypted, e.g., via homomorphic encryption, and then used for optimization or
computation, e.g., [6, 7, 8]. For encryption-based approaches, the resulting
cyphertext is generally of high dimensionality, resulting in high
communication and computation complexities. Besides, a quantitative privacy
protection metric is usually absent. Another notable approach is to perturb
the node communications or iterations with random noise [9, 10], providing a
quantitative privacy guarantee and the robustness to post-processing and side
information under the notion of differential privacy [11]. The added random
noises in the computation process, however, may significantly jeopardize the
computation accuracy [9, 12, 13, 14]. There is a gap in the literature, where
one cannot achieve computational accuracy, convergence efficiency, and
provable privacy guarantees all together, but needs to search for convenient
tradeoffs among the three aspects, for distributed computing.

We consider a multi-agent system where each agent holds a local private
dataset, e.g., a local number, equation, or function. The system seeks to
compute a value that depends on the datasets at all agents. In distributed
computing schemes, agents hold individual dynamical states; share these states
with neighbors over a communication network; and compute the update of the
states based on their local datasets and received neighboring states.
Specifically, we investigate the following three distributed computation tasks
that are extensively studied in the literature: average consensus [15, 16],
network linear equations [17, 18, 19], and distributed convex optimization
[12, 20, 21]. We propose a public-private setup for the node-to-node
communication network. In this public-private network, the public network is
connected and may be dense, over which communications are allowed to be
public, while the private network is sparse and not even necessarily
connected, over which communications are secure. We aim to develop distributed
computing protocols such that the three considered computation tasks are
solved with any prescribed accuracy level, while the differential privacy is
preserved with arbitrary privacy budgets, i.e., removing the trade-off between
computing accuracy and privacy.

###  1.1 Contributions

Over the private network, a Multi-Gossiping PPSC mechanism is proposed for
injecting noises to node states to establish privacy protection, in a way that
the summation of the node stats is maintained. Given any privacy budgets, we
prove that the Multi-Gossiping PPSC mechanism can achieve the desired
differential privacy under an arbitrary probability. The key idea for this
strong privacy guarantee is enough amount of noise injected in the mechanism,
and a sufficient number of recursions. In the meantime, the mechanism itself
maintains that the summation of the input and the output across the network
stay consistent, a property that may be explored for accuracy satisfaction in
distributed computation.

Next, we embed the Multi-Gossiping PPSC in the distributed computing
processes, and establish several privacy-guarantee protocols for the three
considered computation tasks. The following results are established.

  * •

For average consensus, we develop a PPSC-Gossip averaging consensus algorithm.
The PPSC multi-gossiping mechanism is employed over the private network for
privacy encryption, followed by an averaging consensus algorithm over the
public network for local computations. We prove an explicit lower bound for
the local computation depth, under which the proposed algorithm can achieve
the differential privacy at any privacy level and with any prescribed
probability, while computing the exact network average at any accuracy level.

  * •

For network linear equations and distributed convex optimization, we develop
two respective distributed computing protocols, where within each step of
computation, the PPSC-Gossip averaging consensus algorithm is implemented with
an additional projection or gradient descent step. Given any prescribed levels
for privacy and accuracy requirements, we prove that the two protocols offer
both privacy and accuracy guarantees.

To the best of our knowledge, these results are the first kind in the
literature with both proven differential privacy and computation accuracy
guarantees. Of course, compared to existing privacy-preserving algorithms for
these distributed computation problems, our privacy-preserving protocols rely
critically on secure communications over the private network and a generally
more lengthy computation process. Also, we note that the private network is
not necessarily connected, and thus it is not a straightforward conclusion
that such a sparse private communication structure can deliver a global
differential privacy assurance. In fact, a key idea in the protocols lies in
an adaptive selection of the computation depth for accuracy guarantee,
according to the given privacy level.

###  1.2 Related Work

Our work builds upon the existing literature of the differential privacy and
three basic computation problems: average consensus, network linear algebraic
equation and distributed convex optimization. In the area of distributed
computation, extensive research results have been reported to design and
analyze algorithms for these three computation tasks both in continuous and
discrete time as well as in deterministic and stochastic settings, see, e.g.,
[22, 17, 18, 23, 24] and references therein. Regarding the differential
privacy, since the introduction in [11], it has gained a significant
developments in many fields, including estimation [25], control [26], learning
[27], etc. Of most relevance to this paper are recent works [9, 12, 13, 28] on
differentially private distributed computing algorithms. In [13],
exponentially decaying noises are added to the communication messages for an
average consensus algorithm with a differential privacy guarantee on initial
values. This idea is further developed in [28, 29] for better noise adding
mechanisms. In [9, 12], distributed optimization problems with privacy-
sensitive objective functions are addressed and differentially private
computing protocols are developed by introducing random perturbations to
objective functions [12] or node states [9]. Similar ideas have been explored
in [30] to preserve privacy of optimization constraints. In all these results,
the introduction of larger random noise can provide a better differential
privacy guarantee on the one hand, but on the other hand leads to a larger
computation error in the mean square sense. That is, there is a trade-off
between the differential privacy and computation accuracy. It is worth
pointing out that there are some computing algorithms, which can solve
computing problems with any prescribed accuracy, but under other privacy
notions. For example, in [15], by adding and subtracting decaying random
noises to the averaging consensus process, it is shown that the average can be
computed asymptotically in the mean square sense, while preserving the privacy
in the sense that the maximum likelihood estimate of initial states has
nonzero variance.

The idea of PPSC protocol and its potential application to distributed
optimization were reported in [31]. This paper supersedes the work in [31] by
extending the PPSC framework to multi-gossiping setup, and propose and prove
concrete privacy-preserving algorithms. The proposed computing protocols are
established on the multi-gossiping PPSC algorithm, which is an extension of
the classic gossip process [32, 33]. Instead of averaging the two selected
nodes by exchanging states [32, 33], multiple node pairs are selected at each
time in our gossip algorithm and a directional communication of the perturbed
state is conducted between each selected node pair, such that their states are
shuffled with random noise while maintaining the summation. Recent advances on
gossiping protocols include new privacy-preserving gossip algorithms [34]. On
the other hand, the idea of shuffling data for differential privacy is also
studied in [35, 36], where each agent randomizes its own local data, and then
submits the resulting randomized data to a secure shuffler for random
permutation before being public for computation purpose. In such a protocol, a
central shuffler is needed, and as in the previous differentially private
computing protocols, it leads to a trade-off between the privacy and accuracy.
As a comparison, our computing protocols are distributed and there is no such
a trade-off.

Our results are also related to the frameworks of federated learning [21], a
recent advance in privacy protection for machine learning. In federated
learning schemes, training datasets are distributed over a network of nodes,
and a trusted center randomly selects a fraction of local nodes for model
training, aggregates their local computations, and sends back the averaged
updates as the network level decision. When the communications between the
computing center and decentralized nodes are accessed by an eavesdropper, the
local training datasets may face privacy risks since information about such
datasets is exposed in the communications [37]. To handle such privacy
concern, our PPSC framework may be embedded into the federated learning and
provide enhanced privacy preservation as well, in the way that local nodes
shuffle their decentralized computation results over a PPSC framework before
sending them to the trusted center.

Notation. Denote $\mathbf{e}_{i}$ as a basis vector whose entries are all zero
except for the $i$-th being one. We denote $\textnormal{pdf}(\cdot)$ as the
probability density function of a random variable. For any matrix
$\mathbf{A}\in\mathbb{R}^{m\times n}$, denote by $\sigma(\mathbf{A})$ the set
of all singular values of $\mathbf{A}$, and
$\sigma_{M}(\mathbf{A}),\sigma_{m}(\mathbf{A})$ the maximum and minimum
singular values, respectively. For any set $X\subset\mathbb{R}^{n}$, we let
$1_{X}(x)$ be a characteristic function, satisfying $1_{X}(x)=1$ for $x\in X$
and $1_{X}(x)=0$ for $x\notin X$. Given any matrix, we denote its column and
row spaces by $\textnormal{range}(\cdot)$ and $\mbox{span}\;(\cdot)$,
respectively. With a slight abuse of notation, the range of a function is
denoted by $\textnormal{range}(\cdot)$. For any subspace
$\mathscr{E}\in\mathbb{R}^{n}$, we denote
$\mathpzc{P}_{\mathscr{E}}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ as the
orthogonal projection onto the subspace $\mathscr{E}$.

##  2 Problem Definition

###  2.1 Distributed Computing for Multi-agent Systems

We consider a multi-agent network with $n$ agents indexed in the set
$\mathrm{V}=\\{1,\dots,n\\}$. The agents are equipped with node-to-node
communications and local private datasets. The goal of the system is to
compute a network-level solution aggregated from all local datasets at each of
the agents via distributed protocols.

  * (i)

(Average consensus e.g., [15, 16]) Each agent $i$ holds a local private number
$d_{i}\in\mathbb{R}$. The computation goal of agents is to compute the average
$d^{\ast}=\frac{1}{n}\sum_{i=1}^{n}d_{i}$.

  * (ii)

(Network linear equations e.g., [17, 18, 19]) Each agent $i$ holds a private
linear equation $\mathfrak{E}_{i}:\,\mathbf{H}_{i}^{\top}\mathbf{y}=z_{i}$
with an unknown $\mathbf{y}\in\mathbb{R}^{m}$,
$\mathbf{H}_{i}\in\mathbb{R}^{m}$ and $z_{i}\in\mathbb{R}$. The agents aim to
solve the overall linear equation

$\mathfrak{E}:\quad\mathbf{H}\mathbf{y}=\mathbf{z}\,,$ (1)

with $\mathbf{H}\in\mathbb{R}^{n\times m}$ and $\mathbf{z}\in\mathbb{R}^{n}$,
the $i$-th row of which are $\mathbf{H}_{i}^{\top}$ and $z_{i}$, respectively.

  * (iii)

(Distributed convex optimization e.g., [12, 20, 21]) Each agent $i$ holds a
private convex function $f_{i}(\cdot):\mathbb{R}^{m}\rightarrow\mathbb{R}$.
The computation goal of agents is to solve the optimization problem

${\begin{array}[]{rcl}\textnormal{minimize}&&f(\mathbf{y}):=\sum_{i=1}^{n}f_{i}(\mathbf{y})\\\
\textnormal{subject to}&&\mathbf{y}\in\mathtt{C}\end{array}}$ (2)

with a compact convex set $\mathtt{C}\subset\mathbb{R}^{m}$.

###  2.2 Public-Private Communication Networks

We propose for the multi-agent system to have a public-private network model:
the public network $\mathrm{G}=(\mathrm{V},\mathrm{E})$ and the private
network $\mathrm{G}_{\rm p}=(\mathrm{V},\mathrm{E}_{\rm p})$, where the latter
may or may not be a subgraph of the former (see Figure 1). We impose the
following standing assumption throughout the paper.

Figure 1: The public network ${\rm G}$ (left) and the private network ${\rm
G}_{\rm p}$ (right).

Standing Assumption. (i) The public network (graph) ${\rm G}$ is undirected
and connected; Each node $i\in\mathrm{V}$ over private network (graph)
$\mathrm{G}_{\rm p}$ has a positive degree $r_{i}>0$. (ii) All node-to-node
communications over $\mathrm{G}_{\rm p}$ are secure and private; all node-to-
node communicating messages over $\mathrm{G}$ are public.

Note that the private network $\mathrm{G}_{\rm p}$ may be very sparse, and it
is _not even necessarily connected_. The secure communications over the
private network $\mathrm{G}_{\rm p}$ can be realized via data encryption of
communicating messages [38, 39].

###  2.3 Differentially Private Distributed Computation

Denote $\mathscr{M}$ as the mapping that maps the collection of the local
datasets to all the node-to-node communications over the public graph
$\mathrm{G}$.

######  Definition 1.

(i) A distributed protocol is differentially private if differential privacy
for the mapping $\mathscr{M}$ can be achieved under any prescribed privacy
budget.

(ii) A distributed protocol is computationally accurate if the protocol can
output a solution that is within any prescribed error bound at each agent of
the system.

We are interested in distributed computing algorithms for the above three
basic distributed computation tasks that offer both such differential privacy
and computation accuracy.

Secure public network vs Public-private networks. The proposed public-private
network assumes a trusted private network $\mathrm{G}_{\rm p}$. If all node-
to-node communications over the connected public graph $\mathrm{G}$ are made
secure, then standard distributed protocols will not face any privacy risk
against communication eavesdroppers. The introduction of this public-private
network setting has the following advantages:

  * (i)

Data encryption and decryption for establishing secure point-to-point
communications are often computationally costly. Therefore, compared to having
the entire network $\mathrm{G}$ equipped with secure node-to-node
communications, a sparse secure network $\mathrm{G}_{\rm p}$ provides improved
scalability.

  * (ii)

Even if all the links over the public network $\mathrm{G}$ are made secure, it
does not preclude the possibility that certain node $k\in\mathrm{V}$ is a
planted malicious node [15]. Then all communications sent to this node $k$ and
often the states of $k$’s neighbors become exposed for privacy risks despite
the communications to $k$ being secure. While over the sparse private network
$\mathrm{G}_{\rm p}$, each node only needs one secure neighbor. Therefore, the
public-private network setting helps counter privacy risks caused by in-
network malicious nodes.

The usage of a public-private network architecture has been proposed in the
context of social computing, where the public social network is visible to
everyone and a private social network is only visible to each node locally
[40, 41].

##  3 PPSC Mechanism and PPSC-Gossip Averaging Consensus

In this section, we propose a multi-gossiping PPSC mechanism over the private
network as a distributed random node states shuffling scheme with summation
preservation. We prove that such a PPSC mechanism can be made differentially
private in terms of its input and output at an arbitrary privacy budget level
in a probabilistic sense. Next, we show that the PPSC-Gossip mechanism over
the private network can be combined with a standard consensus algorithm over
the public network, and then an adaptive depth allocation will guarantee both
differential privacy and computational accuracy.

###  3.1 Multi-Gossiping PPSC Mechanism

Let $\mathrm{G}_{\rm p}$ admit $q$ connected components with the $k$-th
component denoted by $\mathrm{G}_{\rm p}^{k}=(\mathrm{V}^{k},\mathrm{E}_{\rm
p}^{k})$. We propose the following Multi-Gossiping Privacy-
Preserving/Summation-Consistent (PPSC) mechanism, which consists of $S$
iterations over the private network $\mathrm{G}_{\rm p}$.

Input: Initial states $\beta_{i}(0)$, $i\in\mathrm{V}$.

For $t=1,\ldots,S$, run the following iterations over $\mathrm{G}_{\rm p}$.

  * 1.

At each $\mathrm{G}_{\rm p}^{k}$, an agent $k_{i}$ is randomly selected with
probability $1\over{n_{k}}$; an agent $k_{j}$ is then randomly selected from
$k_{i}$’s neighbors with probability $1\over r_{k_{i}}$. Let
$\mathrm{e}^{k}_{{\rm p}}(t)=(k_{i},k_{j})$ be the selected edge.

  * 2.

Each agent $k_{i}$, $k=1,\ldots,q$ randomly and independently generates noise
$\gamma_{k}(t)\sim\mathcal{N}(0,\sigma_{\gamma}^{2})$, and sends
$\omega_{k}(t)=\beta_{k_{i}}(t)-\gamma_{k}(t)$ to the agent $k_{j}$ over the
edge $\mathrm{e}^{k}_{{\rm p}}(t)$.

  * 3.

Each agent updates its state following

$\begin{array}[]{l}\beta_{k_{i}}(t)=\beta_{k_{i}}(t-1)-\omega_{k}(t)\,,\quad
k=1,\ldots,q;\\\ \beta_{k_{j}}(t)=\beta_{k_{j}}(t-1)+\omega_{k}(t)\,,\quad
k=1,\ldots,q;\\\ \beta_{h}(t)=\beta_{h}(t-1)\,,\quad\qquad\qquad
h\in\mathrm{V}\backslash\bigcup_{k=1}^{q}\\{k_{i},k_{j}\\}\,.\end{array}$

Output: $\beta_{i}(S)$, $i\in\mathrm{V}$.

Algorithm 1 Multi-Gossiping PPSC mechanism

(a)

(b)

(c)

(d)

Figure 2: The gossip process between a pair of nodes. The selected agents and
edge are highlighted in dark gray.

Note that in each iteration of the multi-gossiping PPSC mechanism, a pair of
gossiping nodes essentially “shuffle” their states in a specific way: one node
holds a noisy summation of the two node states, and another node holds a noise
correlated to the first node’s new state. This is related, but different from
the idea of shuffling data [35, 36], where randomized local data is sent to a
central secure shuffler, and then the shuffler applies random permutations
before being public for the computation purpose. The multi-gossiping PPSC
mechanism does not rely on central secure shufflers; and the outcomes of the
nodes states after the multi-gossiping PPSC mechanism and permutation
shuffling are not the same.

Taking a pair of nodes for instance, an overview of this gossip process is
illustrated in Figure 2. The map from the input $\bm{\beta}\in\mathbb{R}^{n}$
to the output $\mathbf{y}_{\rm ppsc}\in\mathbb{R}^{n}$ along the $S$-step
Multi-Gossiping PPSC mechanism can be represented as $\mathscr{M}_{\rm S}$,
i.e., $\mathbf{y}_{\rm ppsc}=\mathscr{M}_{\rm
S}\big{(}\bm{\beta}\big{)}:=\mathsf{C}_{\mathsf{E}_{\rm
p}}\bm{\beta}+\mathsf{D}_{\mathsf{E}_{\rm p}}{\bm{\gamma}}$, where
${\bm{\gamma}}=[{\bm{\gamma}}_{1};\ldots;{\bm{\gamma}}_{q}]$ with
${\bm{\gamma}}_{k}=[\gamma_{k}(1);\ldots;\gamma_{k}(S)]$, and
$\mathsf{C}_{\mathsf{E}_{\rm p}}\in\mathbb{R}^{n\times n}$ and
$\mathsf{D}_{\mathsf{E}_{\rm p}}\in\mathbb{R}^{n\times S}$ are some random
matrices associated with the selected edge sequence $\mathsf{E}_{\rm
p}=\big{\\{}\mathsf{E}_{\rm p}^{1},\ldots,\mathsf{E}_{\rm p}^{q}\big{\\}}$
with $\mathsf{E}_{\rm p}^{k}=\big{\\{}\mathsf{e}_{\rm
p}^{k}(1),\ldots,\mathsf{e}_{\rm p}^{k}(S)\big{\\}}$, $k=1,\ldots,q$. Let an
eavesdropper with full observations of $(\mathsf{E}_{\rm p},\mathbf{y}_{\rm
ppsc})$ attempt to infer the input $\bm{\beta}$. Under any observed
$\mathsf{E}_{\rm p}$, we define two inputs
$\bm{\beta}^{\prime},\bm{\beta}\in\mathbb{R}^{n}$ as $\mu$-adjacent if they
satisfy $\|\bm{\beta}-\bm{\beta}^{\prime}\|\leq\mu$ and
$\mathsf{C}_{\mathsf{E}_{\rm
p}}(\bm{\beta}-\bm{\beta}^{\prime})\in\textnormal{range}\big{(}\mathsf{D}_{\mathsf{E}_{\rm
p}}\big{)}$, and denote $\mathscr{M}_{\rm
S}\big{(}\bm{\beta}\,|\,\mathsf{E}_{\rm p}\big{)}$ as the $\mathscr{M}_{\rm
S}$ conditioned on the observed $\mathsf{E}_{\rm p}$. We introduce the
following differential privacy notion for the Multi-Gossiping PPSC mechanism
[11].

######  Definition 2.

Let $\mu>0$, $\epsilon>0$ and $0<\delta<1/2$. The $\mathscr{M}_{\rm S}$ is
termed to be $(\epsilon,\delta)$-differentially private under $\mu$-adjacency
if for all $R\subseteq\textnormal{range}(\mathscr{M}_{\rm S})$, there holds

${\begin{array}[]{l}\mathbb{P}\left(\mathscr{M}_{\rm
S}\big{(}\bm{\beta}\,|\,\mathsf{E}_{\rm p}\big{)}\in R\right)\leq
e^{\epsilon}\mathbb{P}\left(\mathscr{M}_{\rm
S}\big{(}\bm{\beta}^{\prime}\,|\,\mathsf{E}_{\rm p}\big{)}\in
R\right)+\delta\end{array}}$ (3)

for any two $\mu$-adjacent $\bm{\beta},\bm{\beta}^{\prime}\in\mathbb{R}^{n}$.

Denote $n_{k}=|\mathrm{V}^{k}|$, $n_{\max}=\max\\{n_{1},\ldots,n_{q}\\}$, and
$r^{\dagger}=\min\\{{r_{1}^{\rm min}}/{r_{1}^{\rm max}},\ldots,{r_{q}^{\rm
min}}/{r_{q}^{\rm max}}\\}$ with $r_{k}^{\rm
min}=\min\\{r_{k_{1}},\ldots,r_{k_{q}}\\}$ and $r_{k}^{\rm
max}=\max\\{r_{k_{1}},\ldots,r_{k_{q}}\\}$, $k=1,\ldots,q$. Let
$\kappa(\epsilon,\delta)=\frac{\mathcal{Q}^{-1}(\delta)+\sqrt{(\mathcal{Q}^{-1}(\delta))^{2}+2\epsilon}}{2\epsilon}$
with
$\mathcal{Q}(w)=\frac{1}{\sqrt{2\pi}}\int_{w}^{\infty}e^{-\frac{v^{2}}{2}}dv$.
Denote by $\Theta_{\mathsf{E}_{\rm p}}$ the set of all possible edge sequences
$\mathsf{E}_{\rm p}$ in the $S$-step Multi-Gossiping PPSC mechanism, and let
$\lambda_{\rm ppsc}=\displaystyle\min_{\mathsf{E}_{\rm
p}\in\Theta_{\mathsf{E}_{\rm
p}}}\sigma_{m}^{+}\big{(}\mathsf{D}_{\mathsf{E}_{\rm p}}\big{)}$ with
$\sigma_{m}^{+}(\cdot)$ denoting the minimal nonzero singular value. Finally,
introduce

$S_{\rho}^{\ast}=\Big{(}{\log(1-\rho^{1\over q})-\log
n_{\max}}\Big{)}/\Big{(}{\log\big{(}1-\frac{1+r^{\dagger}}{n_{\max}}\big{)}}\Big{)}.$

Then we have the following result.

######  Theorem 1.

Let $\mu>0$, $\epsilon>0$, $0<\delta<1/2$ and $0<\rho<1$. Suppose $S\geq
S_{\rho}^{\ast}$ and
$\sigma_{\bm{\gamma}}\geq{\mu\kappa(\epsilon,\delta)}/\lambda_{\rm ppsc}$.
Then with a probability that is at least $\rho$, the $S$-Step Multi-Gossiping
PPSC mechanism is $(\epsilon,\delta)$-differentially private under
$\mu$-adjacency.

###  3.2 Discussion: Privacy within the Private Graph

Theorem 1 establishes the fact that the input-output mapping for an $S$-step
PPSC multi-gossiping can be made differentially private with any privacy
budget with an arbitrarily high probability. We have assumed that the node-to-
node communications for the $S$-step PPSC multi-gossiping are secure in the
standing assumption. Now, what if a malicious node, saying $m_{\ast}$, is
within the multi-agent system, so that all communications associated with node
$m_{\ast}$ become known to an eavesdropper (or equivalently, node $m_{\ast}$
is the eavesdropper)?

First of all, nodes never send their true states to other nodes in the multi-
gossiping PPSC procedure. Consequently, the presence of such a malicious node
does not impose immediate privacy concerns. Moreover, since $\mathrm{G}_{\rm
p}$ is not connected, only the nodes within the same connected component as
$m_{\ast}$ are subjected to this additional privacy risk. Therefore, the
sparsity of $\mathrm{G}_{\rm p}$ becomes quite useful.

Next, consider the case where a node $j$ is the sole neighbor of this
malicious node $m_{\ast}$ over $\mathrm{G}_{\rm p}$. Combing the communication
from node $j$, $\beta_{j}(0)-\gamma$, and the outcome of the PPSC mechanism
$\gamma$ at node $j$, node $m_{\ast}$ will be able to infer the exact input
$\beta_{j}(0)$ of the node $j$. As a result, the privacy of node $j$ in terms
of $\beta_{j}(0)$ will be fully lost to this malicious node $m_{\ast}$. To
overcome this, it suffices for the node $j$ to have at least one trustful
neighbor $k$, so that the state of node $j$ may have been shuffled between $j$
and $k$, which is not known to $m_{\ast}$. In general, if each node over
$\mathrm{G}_{\rm p}$ has at least one trustful neighbor, the privacy of the
nodes will have further guarantee in terms of identifiability of
$\beta_{i}(0),i\in\mathrm{V}$ from $\beta_{i}(S),i\in V$ in the presence of
malicious nodes. Therefore, the structure of $\mathrm{G}_{\rm p}$ would enable
stronger internal privacy preservation that goes beyond Theorem 1, due to the
shuffling effect [35, 36] that comes along the PPSC procedure. We leave a
quantitive analysis for this PPSC enabled internal privacy protection in
future works since it is not fully aligning with the scope of the current
paper.

###  3.3 The PPSC-Gossip Averaging Consensus Algorithm

Denote each iteration of the $S$-step Multi-Gossiping PPSC mechanism as
$\mathsf{MultiGossipPPSC}$. Let each edge in $\rm G$ have the same weight
$a\in(0,{1}/{n}]$, and denote ${\rm N}_{i}$ as the neighbor set of node
$i\in{\rm V}$. In the following, the PPSC-Gossip averaging consensus (PPSC-
Gossip-AC) algorithm is presented.

Input: The local private datasets $d_{i}$, $i\in\mathrm{V}$, and parameters
$S\in\mathbb{N}_{+}$ and $T\in\mathbb{N}_{+}$.

Initialize: Set $s\leftarrow 0$ and $x_{i}(s)\leftarrow d_{i}$ for
$i\in\mathrm{V}$.

For $s=1,\ldots,S$, over $\mathrm{G}_{\rm p}$ run

$\mathbf{x}_{s}=\mathsf{MultiGossipPPSC}\big{(}\mathbf{x}_{s-1}\big{)}$ with
$\mathbf{x}_{s}=[x_{1}(s);\ldots;x_{n}(s)]$

For $s=S+1,\ldots,S+T$, over $\mathrm{G}$ run

$x_{i}(s)=x_{i}(s-1)+a\sum\limits_{j\in{\rm N}_{i}}(x_{j}(s-1)-x_{i}(s-1))$
for $i\in\mathrm{V}$

Output: $x_{i}(S+T)$, $i\in\mathrm{V}$.

Algorithm 2 PPSC-Gossip Averaging Consensus (PPSC-Gossip-AC) Algorithm

The PPSC-Gossip-AC algorithm is comprised of two stages: PPSC-Gossip stage and
Average-Consensus stage. The former is to run the multi-gossiping PPSC
mechanism with input $\mathbf{x}_{0}$ and output $\mathbf{x}_{S}$ over the
private network $\mathrm{G}_{\rm p}$ for privacy encryption. At the Average-
Consensus stage, for $s=S+1,S+2,\ldots,S+T$, the standard averaging consensus
algorithm is carried out over the public network $\mathrm{G}$ for local
computations, where the node-to-node communications are
$\mathbf{x}_{S},\mathbf{x}_{S+1},\ldots,\mathbf{x}_{S+T-1}$.

Denote ${\bf d}=[d_{1};d_{2};\ldots;d_{n}]$ and $\chi_{\rm
ea}=[\mathbf{x}_{S};\mathbf{x}_{S+1};\ldots;\mathbf{x}_{S+T-1}]$, and define
the map from ${\bf d}$ to $\chi_{\rm ea}$ as $\chi_{\rm ea}=\mathscr{M}_{\rm
av}\big{(}{\bf d}\big{)}\,.$ Let an eavesdropper with full observations of the
selected edges (i.e., $\mathsf{E}_{\rm p}$) during the PPSC-Gossip stage and
the node-to-node communications (i.e., $\chi_{\rm ea}$) over the public graph
$\rm G$. In the following, similar to in Definition 2, we specify the
differential privacy of the PPSC-Gossip-AC algorithm.

######  Definition 3.

Let $\mu>0$, $\epsilon>0$ and $0<\delta<1/2$. The $\mathscr{M}_{\rm av}$ is
termed to be $(\epsilon,\delta)$-differentially private under $\mu$-adjacency
if for all $R\subseteq\textnormal{range}(\mathscr{M}_{\rm av})$, there holds

${\begin{array}[]{l}\mathbb{P}\left(\mathscr{M}_{\rm av}\big{(}{\bf
d}\,|\,\mathsf{E}_{\rm p}\big{)}\in R\right)\leq
e^{\epsilon}\mathbb{P}\left(\mathscr{M}_{\rm av}\big{(}{\bf
d}^{\prime}\,|\,\mathsf{E}_{\rm p}\big{)}\in R\right)+\delta\end{array}}$ (4)

for any two $\mu$-adjacent $\mathbf{d},\mathbf{d}^{\prime}\in\mathbb{R}^{n}$.

Denote by $\mathbf{A}\in\mathbb{R}^{n\times n}$ the Laplacian matrix of graph
$\rm G$, and $\lambda_{{\rm G}}$ the algebraic connectivity of ${\rm G}$,
i.e., the second smallest eigenvalue of the Laplacian matrix $\mathbf{A}$.
Clearly, $0\leq\lambda_{{\rm G}}<1$ by the standing assumption. One of our
main results is summarized below.

######  Theorem 2.

For any $\mu>0$, $\epsilon>0$, $0<\delta<1/2$, $0<\rho<1$ and $\nu>0$, let
$S\geq S_{\rho}^{\ast}$,
$\sigma_{\bm{\gamma}}\geq{\mu\kappa(\epsilon,\delta)}/\lambda_{\rm ppsc}$, and

$T\geq\Big{(}{\log\nu-\log(n\|\mathbf{d}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})}\Big{)}/\Big{(}{2\log(1-\lambda_{\rm
G})}\Big{)}\,.$ (5)

Then, the PPSC-Gossip-AC algorithm

  * (i)

preserves $(\epsilon,\delta)$-differential privacy under $\mu$-adjacency with
a probability that is at least $\rho$, and

  * (ii)

computes the average with a $\nu$-accuracy, i.e.,
$\mathbb{E}\,\|\mathbf{x}_{S+T}-\frac{1}{n}{\bf 1}_{n}{\bf 1}_{n}^{\top}{\bf
d}\|^{2}\leq\nu\,.$

By Markov’s inequality, the condition
$\mathbb{E}\,\|\mathbf{x}_{S+T}-\frac{1}{n}{\bf 1}_{n}{\bf 1}_{n}^{\top}{\bf
d}\|^{2}\leq\nu$ guarantees that

$\mathbb{P}\Big{(}\|\mathbf{x}_{S+T}-\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}{\bf d}\|\geq\varsigma\Big{)}\leq\frac{\nu}{\varsigma^{2}}$

for any $\varsigma>0$. In other words, Theorem 2 establishes that
$\mathbf{x}_{S+T}$ may get arbitrarily close to $\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}{\bf d}$ for arbitrarily high probability when $\nu$ is chosen to
be small enough.

##  4 PPSC-Gossip Linear-Equation Solver

In this section, the PPSC-Gossip-AC algorithm is explored to solve the network
linear equation (1). Recall that in such a network linear equation, each agent
$i$ holds a linear algebraic equation
$\mathfrak{E}_{i}:\,\mathbf{H}_{i}^{\top}\mathbf{y}=z_{i}$ with an unknown
$\mathbf{y}\in\mathbb{R}^{m}$, $\mathbf{H}_{i}\in\mathbb{R}^{m}$ and
$z_{i}\in\mathbb{R}$, and all agents aim to solve the overall linear equation
$\mathbf{H}\mathbf{y}=\mathbf{z}$, where the $i$-th row of
$\mathbf{H}\in\mathbb{R}^{n\times m}$ and $\mathbf{z}\in\mathbb{R}^{n}$ are
$\mathbf{H}_{i}^{\top}$ and $z_{i}$, respectively.

Regarding solutions of the equation (1), there are three cases: (i) a unique
exact solution; (ii) a unique least-squares solution; (iii) infinite number of
solutions. In the following, we focus on the case (i), and suppose
$\mbox{rank}\;(\mathbf{H})=m$ and $\mathbf{z}\in\mbox{span}\;(\mathbf{H})$,
which guarantees the unique exact solution
$\mathbf{y}^{\ast}:=(\mathbf{H}^{\top}\mathbf{H})^{-1}\mathbf{H}^{\top}\mathbf{z}$.
We note that the case (ii) can be handled by adapting the algorithm in the
next section.

###  4.1 Adjacency of Linear Equations

Note that solutions of each linear equation $\mathfrak{E}_{i}$ specify a
unique affine solution subspace
$\mathscr{E}_{i}:=\big{\\{}\mathbf{y}\in\mathbb{R}^{m}:\mathbf{H}_{i}^{\top}\mathbf{y}=z_{i}\big{\\}}$.
In the following, the adjacency of two linear equations is characterized by
the distance of their corresponding affine solution subspaces.

For any two affine subspaces
$\mathscr{E}_{i}:=\big{\\{}\mathbf{y}\in\mathbb{R}^{m}:\mathbf{H}_{i}^{\top}\mathbf{y}=z_{i}\big{\\}}$
and
$\mathscr{E}_{i}^{\prime}:=\big{\\{}\mathbf{y}\in\mathbb{R}^{m}:{\mathbf{H}_{i}^{\prime}}^{\top}\mathbf{y}=z_{i}^{\prime}\big{\\}}$,
we define two distances between them by

$\mbox{d}_{\textnormal{rotational}}(\mathscr{E}_{i},\mathscr{E}_{i}^{\prime}):=\bigg{\|}\frac{\mathbf{H}_{i}\mathbf{H}_{i}^{\top}}{\mathbf{H}_{i}^{\top}\mathbf{H}_{i}}-\frac{\mathbf{H}_{i}^{\prime}\mathbf{H}_{i}^{\prime\top}}{\mathbf{H}_{i}^{\prime\top}\mathbf{H}_{i}^{\prime}}\bigg{\|}\,$
(6)
$\mbox{d}_{\textnormal{translational}}(\mathscr{E}_{i},\mathscr{E}_{i}^{\prime}):=\bigg{\|}\frac{z_{i}\mathbf{H}_{i}}{\mathbf{H}_{i}^{\top}\mathbf{H}_{i}}-\frac{z_{i}^{\prime}\mathbf{H}_{i}^{\prime}}{\mathbf{H}_{i}^{\prime\top}\mathbf{H}_{i}^{\prime}}\bigg{\|}\,.$
(7)

For the affine subspace $\mathscr{E}_{i}$, we say that
$\mathscr{L}_{i}:=\big{\\{}\mathbf{y}\in\mathbb{R}^{m}:{\mathbf{H}_{i}}^{\top}\mathbf{y}=0\big{\\}}$
is the subspace associated to $\mathscr{E}_{i}$, and
$\frac{z_{i}\mathbf{H}_{i}}{\mathbf{H}_{i}^{\top}\mathbf{H}_{i}}$ is the
translational vector from $\mathscr{L}_{i}$ to $\mathscr{E}_{i}$. Similarly,
$\mathscr{L}_{i}^{\prime}$ can be identified for $\mathscr{E}_{i}^{\prime}$.
The intuition and rational in introducing these two distances (6) and (7) are
the following:

  * (i)

The $\mbox{d}_{\textnormal{rotational}}$ is the gap of the two respective
orthogonal projection operators onto $\mathscr{L}_{i}$ and
$\mathscr{L}_{i}^{\prime}$, i.e.,

$\begin{array}[]{rcl}\mbox{d}_{\textnormal{rotational}}=\sup\limits_{\|\mathbf{y}\|=1}\|\mathpzc{P}_{\mathscr{L}_{i}}(\mathbf{y})-\mathpzc{P}_{\mathscr{L}_{i}^{\prime}}(\mathbf{y})\|\,;\end{array}$

  * (ii)

The $\mbox{d}_{\textnormal{translational}}$ is the distance between the two
translational vectors of $\mathscr{E}_{i},\mathscr{E}_{i}^{\prime}$.

A geometric illustration of both distances is shown in Figures 3(a) and 3(b),
respectively.

(a) The distance $\mbox{d}_{\textnormal{rotational}}$

(b) The distance $\mbox{d}_{\textnormal{translational}}$

Figure 3: An illustration of the “distance” between two affine subspaces
$\mathscr{E}_{i}$ and $\mathscr{E}_{i}^{\prime}$. The affine subspaces are
green lines, and their associated subspaces and translational vectors are
denoted by blue lines and red dashed lines with arrows, respectively.

In view of the previous analysis, we quantify the “distance” between two
affine subspaces $\mathscr{E}_{i},\mathscr{E}_{i}^{\prime}$ by the sum of two
quantities:
$\mbox{d}_{\textnormal{rotational}}(\mathscr{E}_{i},\mathscr{E}_{i}^{\prime})$
defined in (6) and
$\mbox{d}_{\textnormal{translational}}(\mathscr{E}_{i},\mathscr{E}_{i}^{\prime})$
defined in (7). This further inspires the following definition.

######  Definition 4.

For two linear equations $\mathfrak{E}:\mathbf{H}\mathbf{y}=\mathbf{z},\
\mathfrak{E}^{\prime}:\mathbf{H}^{\prime}\mathbf{y}=\mathbf{z}^{\prime}$, we
call them to be $\mu$-adjacent if

$\textnormal{d}_{\textnormal{rotational}}(\mathscr{E}_{i},\mathscr{E}_{i}^{\prime})+\textnormal{d}_{\textnormal{translational}}(\mathscr{E}_{i},\mathscr{E}_{i}^{\prime})\leq\mu\,,\quad\quad
i\in\mathrm{V}.$

###  4.2 Distributed Computing Protocol

In the following, the PPSC-Gossip network linear-equation (PPSC-Gossip-NLE)
solver is presented.

Input: Local data $(\mathbf{H}_{k},\mathbf{z}_{k})$, $k\in\mathrm{V}$, initial
value $\zeta_{0}\in\mathbb{R}^{m}$, and parameters $S,T,L\in\mathbb{N}_{+}$.

Initialize: $s\leftarrow 0$, $l\leftarrow 0$ and
$x_{k}(s)\leftarrow\mathpzc{P}_{\mathscr{E}_{k}}(\zeta_{0})$ for
$k\in\mathrm{V}$.

For $l=0,1,\ldots,L-1$, run

For $s=l(S+T+1)+1,\ldots,l(S+T+1)+S$, over $\mathrm{G}_{\rm p}$ run

$\mathbf{x}_{s}=\mathsf{MultiGossipPPSC}\big{(}\mathbf{x}_{s-1}\big{)}$

For $s=l(S+T+1)+S+1,\ldots,l(S+T+1)+S+T$, over $\mathrm{G}$ run

$x_{k}(s)=x_{i}(s-1)+a\sum\limits_{j\in{\rm N}_{i}}(x_{j}(s-1)-x_{i}(s-1))$
for $k\in\mathrm{V}$.

For $s=l(S+T+1)+S+T+1$, run

$x_{k}(s)=\mathpzc{P}_{\mathscr{E}_{k}}(x_{k}(s-1))$ for $k\in\mathrm{V}$.

Output: $x_{k}(L(S+T+1))$, for $k\in\mathrm{V}$.

Algorithm 3 PPSC-Gossip Network Linear-Equation (PPSC-Gossip-NLE) Solver

The PPSC-Gossip-NLE solver is comprised of $L$ recursions, each of which needs
$S+T+1$ steps and consists of three different procedures in order: (i) PPSC-
Gossip procedure with $S$ steps; (ii) Average-Consensus procedure with $T$
steps; (iii) one-step orthogonal projection. The procedures (i) and (ii)
together are exactly the PPSC-Gossip-AC algorithm. At the procedure (iii), the
computation is self performed by each agent to orthogonally project its state
to its own affine subspace, where the local private datasets are encoded.

###  4.3 Computation Accuracy and Differential Privacy

Let
$\chi_{l}=[\mathbf{x}_{l(S+T+1)+S};\mathbf{x}_{l(S+T+1)+S+1};\ldots;\mathbf{x}_{l(S+T+1)+S+T}]$
and $\chi_{\rm ea}=[\chi_{0};\ldots;\chi_{L-1}]$. Define the sequence of all
selected communication edges at the PPSC-Gossip procedures as
$\mathcal{E}_{\rm p}=\\{\mathcal{E}_{{\rm p},0},\ldots,\mathcal{E}_{{\rm
p},L-1}\\}$ with $\mathcal{E}_{{\rm p},l}=\big{(}\mathsf{E}_{{\rm
p},l}^{1},\ldots,\mathsf{E}_{{\rm p},l}^{q}\big{)}$ and $\mathsf{E}_{{\rm
p},l}^{k}=\left(\mathsf{e}_{{\rm p}}^{k}(l(S+T+1)+1),\ldots,\mathsf{e}_{{\rm
p}}^{k}(l(S+T+1)+S)\right).$ Define the map from the network linear equations
$\mathfrak{E}$ to $\chi_{\rm ea}$ as $\chi_{\rm ea}=\mathscr{M}_{\rm
eq}\big{(}\mathfrak{E}\big{)}$. As in the previous sections, let an
eavesdropper with full observations of the selected edges (i.e.,
$\mathcal{E}_{\rm p}$) at the PPSC-Gossip procedure and the node-to-node
communications (i.e.,$\chi_{\rm ea}$) over the public network $\mathrm{G}$. In
the following, we specify the differential privacy of the PPSC-Gossip-NLE
solver.

######  Definition 5.

Let $\mu>0$, $\epsilon>0$ and $0<\delta<1/2$. The $\mathscr{M}_{\rm eq}$ is
termed to be _$(\epsilon,\delta)$ -differentially private under
$\mu$-adjacency_ if for all $R\subseteq\textnormal{range}(\mathscr{M}_{\rm
eq})$, there holds

${\begin{array}[]{l}\mathbb{P}\left(\mathscr{M}_{\rm
eq}\big{(}\mathfrak{E}\,|\,\mathcal{E}_{\rm p}\,\big{)}\in R\right)\leq
e^{\epsilon}\mathbb{P}\left(\mathscr{M}_{\rm
eq}\big{(}\mathfrak{E}^{\prime}\,|\,\mathcal{E}_{\rm p}\big{)}\in
R\right)+\delta\end{array}}$ (8)

for any two $\mu$-adjacent equations $\mathfrak{E}^{\prime},\mathfrak{E}$.

Let
$\lambda_{H}=\sigma_{M}\big{(}\mathbf{I}_{m}-\frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{H}_{i}\mathbf{H}_{i}^{\top}}{\mathbf{H}_{i}^{\top}\mathbf{H}_{i}}\big{)}$.
As $\mbox{rank}\;(\mathbf{H})=m$ by assumption, it can be seen that matrix
$\frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{H}_{i}\mathbf{H}_{i}^{\top}}{\mathbf{H}_{i}^{\top}\mathbf{H}_{i}}$
is strictly positive definite with all eigenvalues within the unit circle.
Thus, $1>\lambda_{H}\geq 0$. Let

$\begin{array}[]{l}L^{\ast}(\nu)={\left(\log\nu-\log(2n\|\zeta_{0}-\mathbf{y}^{\ast}\|^{2})\right)}/{\big{(}\log(\varepsilon_{0}+\lambda_{H}^{2})-\log(1+\varepsilon_{0})\big{)}}\\\
S^{\ast}(\rho,L)=\Big{(}{\log(1-\rho^{\frac{1}{2qL}})-\log
n_{\max}}\Big{)}/\left({\log(1-\frac{1+r^{\dagger}}{n_{\max}})}\right)\\\
\sigma_{\bm{\gamma}}^{\ast}(\epsilon,\nu,L,S)={\mu\kappa(\frac{\epsilon}{L},\delta_{\sharp})(\sqrt{\nu}+\phi_{\nu}+\sqrt{n})}/{\lambda_{\rm
ppsc}}\end{array}$

with $1>\varepsilon_{0}>0$,
$\phi^{\ast}(\nu)=2\sqrt{n}\|\mathbf{y}^{\ast}\|+\sqrt{n}\|\zeta_{0}\|+\frac{2-\lambda_{H}}{1-\lambda_{H}}\sqrt{\nu}$
and $\delta_{\sharp}(\epsilon,\delta,L)=(\delta+e^{\epsilon})^{1\over
L}-\exp(\frac{\epsilon}{L})$, and

$\begin{array}[]{rcl}T^{\ast}(\rho,\nu,L,S,\sigma_{{\bm{\gamma}}})=\frac{1}{\log(1-\lambda_{\rm
G})}\min\left\\{\frac{1}{2}\log\frac{(1-\rho^{1\over
2L})\nu}{{\phi^{\ast}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}},\log\frac{1-\lambda_{H}^{2}}{5n(1+{1\over\varepsilon_{0}})},\log\frac{\nu(1-\lambda_{H}^{2})}{16(n\|\mathbf{y}^{\ast}\|^{2}+S^{2}q^{2}\sigma_{{\bm{\gamma}}}^{2})}\right\\}\,.\end{array}$

Next, we show that the PPSC-Gossip-NLE solver can solve the linear equations
with any accuracy level, while achieving an arbitrary
$(\epsilon,\delta)$-differential privacy with any prescribed probability.

######  Theorem 3.

For any $\mu>0$, $\epsilon>0$, $0<\delta<1/2$, $\rho>0$ and $\nu>0$, let
$L\geq L^{\ast}$, $S\geq S^{\ast}$,
$\sigma_{\bm{\gamma}}\geq\sigma_{\bm{\gamma}}^{\ast}$, and $T\geq T^{\ast}$.
Then, the PPSC-Gossip-NLE solver

  * (i)

preserves $(\epsilon,\delta)$-differential privacy under $\mu$-adjacency with
a probability that is at least $\rho$, and

  * (ii)

computes the solution with a $\nu$-accuracy, i.e.,
$\mathbb{E}\left(\|\mathbf{x}_{L(S+T+1)}-({\bf
1}_{n}\otimes\mathbf{y}^{\ast})\|^{2}\right)\leq\nu$.

##  5 PPSC-Gossip Distributed Convex Optimization

In this section, the PPSC-Gossip-AC algorithm is explored to solve the
distributed convex optimization problem (2), i.e., each agent $i$ holds a
private convex function $f_{i}(\cdot):\mathbb{R}^{m}\rightarrow\mathbb{R}$,
and all agents aim to solve the optimization problem
$\min_{\mathbf{y}\in\mathtt{C}}f(\mathbf{y}):=\sum_{i=1}^{n}f_{i}(\mathbf{y})$,
where $\mathtt{C}\subset\mathbb{R}^{m}$ is a compact convex set.

In order to facilitate a convenient discussion, we assume all functions
$f_{i}$, $i=1,\ldots,n$ are parameterized in the form of
$f_{i}(\mathbf{y})=g_{i}(\tau_{i},\mathbf{y})$, where parameter vectors
$\tau_{i}\in\mathcal{T}$ are privacy-sensitive with a public bounded set
$\mathcal{T}\subset\mathbb{R}^{d}$, and functions
$g_{i}:\mathbb{R}^{d}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$ are
continuously differentiable. Without loss of generality we assume that the
structure (form) of $g_{i}$ is public and the privacy sensitivity takes place
at the parameters $\tau_{i}$. The adjacency of two functions is characterized
as below.

######  Definition 6.

Let $f_{i}(\mathbf{y})=g_{i}(\tau_{i},\mathbf{y})$ and
$f_{i}^{\prime}(\mathbf{y})=g_{i}(\tau_{i}^{\prime},\mathbf{y})$ with
$\tau_{i},\tau_{i}^{\prime}\in\mathcal{T}$ for $i\in\mathrm{V}$. We say
$\mathbf{F}=[f_{1}(\mathbf{y});\ldots;f_{n}(\mathbf{y})]$ and
$\mathbf{F}^{\prime}=[f_{1}^{\prime}(\mathbf{y});\ldots;f_{n}^{\prime}(\mathbf{y})]$
to be $\mu$-adjacent if $\|\tau_{i}-\tau_{i}^{\prime}\|\leq\mu$ holds for
$i\in\mathrm{V}$.

###  5.1 Distributed Computing Protocol

Let $\mathpzc{P}_{\mathtt{C}}(\mathbf{y})$ be the projection of
$\mathbf{y}\in\mathbb{R}^{m}$ on the set $\mathtt{C}$, i.e.,
$\mathpzc{P}_{\mathtt{C}}(\mathbf{y})=\arg\min_{\mathbf{y}^{\prime}\in\mathtt{C}}\|\mathbf{y}-\mathbf{y}^{\prime}\|\,.$
In the following, the PPSC-Gossip distributed convex optimization (PPSC-
Gossip-DCO) algorithm is presented.

Input: The subgradient $\nabla f_{k}(\cdot)$, stepsize $\alpha_{l}>0$, initial
value $\zeta_{0}\in\mathtt{C}$ and parameters $S,T,L\in\mathbb{N}_{+}$.

Initialize: $s\leftarrow 0$, $l\leftarrow 0$ and
$x_{k}(s)\leftarrow\mathpzc{P}_{\mathtt{C}}\big{(}\zeta_{0}-\alpha_{0}\nabla
f_{k}(\zeta_{0})\big{)}$.

For $l=0,1,\ldots,L-1$, over $\mathrm{G}_{\rm p}$ run

For $s=l(S+T+1)+1,\ldots,l(S+T+1)+S$, run

$\mathbf{x}_{s}=\mathsf{MultiGossipPPSC}\big{(}\mathbf{x}_{s-1}\big{)}$

For $s=l(S+T+1)+S+1,\ldots,l(S+T+1)+S+T$, over $\mathrm{G}$ run

$x_{k}(s)=x_{i}(s-1)+a\sum\limits_{j\in{\rm N}_{i}}(x_{j}(s-1)-x_{i}(s-1))$
for $k\in\mathrm{V}$.

For $s=l(S+T+1)+S+T+1$, at each node $k\in\mathrm{V}$ run

$x_{k}(s)=\mathpzc{P}_{\mathtt{C}}\big{(}x_{k}(s-1)-\alpha_{l+1}\nabla
f_{k}(x_{k}(s-1))\big{)}$ for $k\in\mathrm{V}$.

Output: $x_{k}(L(S+T+1))$, for $k\in\mathrm{V}$.

Algorithm 4 PPSC-Gossip Distributed Convex Optimization (PPSC-Gossip-DCO)
Algorithm

As in the PPSC-Gossip-NLE algorithm, the above PPSC-Gossip-DCO algorithm is
also comprised of $L$ recursions, each of which needs $S+T+1$ steps and
consists of three different procedures in order: (i) PPSC-Gossip procedures
with $S$ steps; (ii) Average-Consensus procedures with $T$ steps; (iii) one-
step projected subgradient descent. The procedures of (i) and (ii) together
are exactly the PPSC-Gossip-AC algorithm, while the third procedure is self
performed by each agent to take the subgradient descent and then projection on
the convex set $\mathtt{C}$. In this way, the local private functions $f_{k}$
are encoded in the update rules in the form of the subgradients.

###  5.2 Computation Accuracy and Differential Privacy

We follow the definitions of $\mathcal{E}_{\rm p}$ and $\chi_{\rm ea}$ in
Section 4, and define the map from the functions
$\mathbf{F}:=[f_{1};f_{2};\ldots;f_{n}]$ to $\chi_{\rm ea}$ as $\chi_{\rm
ea}=\mathscr{M}_{\rm op}\big{(}\mathbf{F}\big{)}$. As in the previous
sections, let an eavesdropper with full observations of the selected edges
(i.e., $\mathcal{E}_{\rm p}$) at the PPSC-Gossip procedure and the node-to-
node communications (i.e.,$\chi_{\rm ea}$) over the public network
$\mathrm{G}$. We then specify the notion of differential privacy for the PPSC-
Gossip-DCO algorithm.

######  Definition 7.

Let $\mu>0$, $\epsilon>0$ and $0<\delta<1/2$. The $\mathscr{M}_{\rm op}$ is
termed to be $(\epsilon,\delta)$-differentially private under $\mu$-adjacency
if for all $R\subseteq\textnormal{range}(\mathscr{M}_{\rm op})$, there holds

${\begin{array}[]{l}\mathbb{P}\left(\mathscr{M}_{\rm
op}\big{(}\mathbf{F}\,|\,\mathcal{E}_{\rm p}\big{)}\in R\right)\leq
e^{\epsilon}\mathbb{P}\left(\mathscr{M}_{\rm
op}\big{(}\mathbf{F}^{\prime}\,|\,\mathcal{E}_{\rm p}\big{)}\in
R\right)+\delta\end{array}}$ (9)

for any two $\mu$-adjacent $\mathbf{F}^{\prime},\mathbf{F}$.

We denote the optimal solution set of (2) as
$\mathtt{C}^{\dagger}\subseteq\mathtt{C}$. Let
$\phi^{\dagger}=\max\limits_{\mathbf{y}\in\mathtt{C}}\|\mathbf{y}\|$ and

$g^{\dagger}=\max\limits_{(i,\tau_{i},\mathbf{y})\in\mathrm{V}\times\mathcal{T}\times\Omega_{\nu}}\left\|\frac{\partial
g_{i}}{\partial\mathbf{y}}(\tau_{i},\mathbf{y})\right\|$

with
$\Omega_{\nu}:=\\{\mathbf{y}\in\mathbb{R}^{m}:\|\mathbf{y}\|^{2}\leq\max\limits_{\mathbf{y}^{\prime}\in\mathtt{C}}\|\mathbf{y}^{\prime}\|^{2}+\nu\\}$.
Let

$\begin{array}[]{l}S^{\dagger}(\rho,L)=\Big{(}{\log(1-\rho^{\frac{1}{qL}})-\log
n_{\max}}\Big{)}/{\log(1-\frac{1+r^{\dagger}}{n_{\max}})}\\\
\sigma_{\bm{\gamma}}^{\dagger}(\mu,\epsilon,\delta,L)={n\mu
g^{\dagger}\mathcal{R}(\frac{\epsilon}{L},\delta_{\sharp})}/{\lambda_{\rm
ppsc}}\\\
T^{\dagger}(p,\nu,L,S,\sigma_{{\bm{\gamma}}})=\Big{(}{\log((1-p^{1\over
L})\nu\alpha_{L}^{4})-\log(n{\phi^{\dagger}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})}\Big{)}/{\log(1-\lambda_{\rm
G})^{2}}\,.\end{array}$

Regarding the differential privacy and computation accuracy of the PPSC-
Gossip-DCO algorithm, the following result is formulated.

######  Theorem 4.

Let the stepsize $\alpha_{l}=\frac{1}{l+1}$. For any $\mu>0$, $\epsilon>0$,
$0<\delta<1/2$, $0<\rho<1$, $0<p<1$ and $\nu>0$, there exists an
$L^{\dagger}>0$ such that for all $L\geq L^{\dagger}$, $S\geq S^{\dagger}$,
$\sigma_{\bm{\gamma}}\geq\sigma_{\bm{\gamma}}^{\dagger}$ and $T\geq
T^{\dagger}$, the PPSC-Gossip-DCO algorithm

  * (i)

computes a $\nu$-accuracy with a probability that is at least $p$, i.e.,

${\mathbb{P}\left(\|\mathbf{x}_{L(S+T+1)}-\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger}\|^{2}\leq\nu\right)\geq
p\,,\quad\mbox{for some $\mathbf{y}^{\dagger}\in\mathtt{C}^{\dagger}$}}$ (10)

  * (ii)

preserves $(\epsilon,\delta)$-differential privacy under $\mu$-adjacency with
a probability that is at least $\rho$.

Regarding the design of the stepsize $\alpha_{l}$, we note that any
$\alpha_{l}$ satisfying (i) $\lim\limits_{l\rightarrow\infty}\alpha_{l}=0$;
(ii)
$\lim\limits_{l\rightarrow\infty}\sum\limits_{i=0}^{l}\alpha_{i}^{2}<\infty$;
(iii) $\lim\limits_{l\rightarrow\infty}\sum\limits_{i=0}^{l}\alpha_{i}=\infty$
is feasible [20]. We also remark that the distributed computing protocol in
Algorithm 5 can be adapted to compute the unique least-squares solution of the
network linear equations (1). The idea, motivated by [17], lies in modifying
the procedure of projected subgradient descent at $s=(l+1)(S+T+1)-1$ to the
following

$x_{k}(s)=x_{k}(s-1)+\alpha_{l+1}\big{(}\mathpzc{P}_{\mathscr{E}_{k}}(x_{k}(s-1))-x_{k}(s-1)\big{)}\,,\quad\mbox{
$\forall\,\,k\in{\rm V}$}\,.$

Under the resulting distributed computing protocol, all results in Theorem 4
can still be preserved, i.e., the unique least-squares solution can be
computed with an arbitrarily given accuracy, while achieving an arbitrary
$(\epsilon,\delta)$-differential privacy with any prescribed probability.

##  6 Case Studies

In this section, we provide a series of numerical examples that illustrate the
effectiveness of our results.

###  6.1 Averaging Consensus

In this subsection, numerical simulations are conducted to demonstrate the
feasibility of the proposed PPSC-Gossip-AC algorithm. We consider a system of
10 agents over an public cycle network ${\rm G}$ as in Figure 4(a), where each
edge is assigned with weight $1\over 10$ and each agent $i$ holds a sensitive
number $d_{i}$ (see Table 1).

Table 1: Private datasets for average consensus $d_{1}=10$ | $d_{2}=100$ | $d_{3}=20$ | $d_{4}=-30$ | $d_{5}=-20$
---|---|---|---|---
$d_{6}=60$ | $d_{7}=70$ | $d_{8}=0$ | $d_{9}=80$ | $d_{10}=-20$

(a)

(b)

(c)

Figure 4: The public network ${\rm G}$ and the private network ${\rm G}_{\rm
p}$ with $n=10$.

In order to assess the effect of ${\rm G}_{\rm p}$, we run the multi-gossiping
PPSC mechanism over three kinds of ${\rm G}_{\rm p}$: Figures 4(a), 4(b) and
4(c), having one, two and three components, respectively, and show the
relationship between the iteration step $S$ and the differential privacy
probability $\rho$, the latter of which is indeed the probability of the event
$\mathcal{Q}_{S}$ that all node states have altered after the $S$-step multi-
gossiping PPSC mechanism. Figure 5 shows that a larger $\rho$ requires a
larger $S$ for all three graphs ${\rm G}_{\rm p}$, and given any $\rho$, the
smallest $S$ is needed by the ${\rm G}_{\rm p}$ in Figure 4(c). Thus, in the
following simulations ${\rm G}_{\rm p}$ is fixed as in Figure 4(c). Under this
${\rm G}_{\rm p}$, we then compare the minimal $S$ required practically (i.e.,
in Figure 5) and theoretically (i.e., in Theorem 2) to fulfill the requirement
of probability $\rho$. Table 2 indicates that the theoretic $S$ in Theorem 2
is indeed more conservative under each $\rho$. In the following simulations,
we let the desired differential privacy probability $\rho=0.9998$, which can
be guaranteed by $S=25$ as in Table 2.

Throughout all simulations, following the standard differential privacy
guideline [42], we fix $\mu=1$ and let $\delta=10^{-6}$. With these
$\mu,\delta$, we consider various privacy levels
$\epsilon=10^{-3},10^{-2},10^{-1}$ and run the PPSC-Gossip-AC algorithm with
the noise variance $\sigma_{\bm{\gamma}}$ chosen as the minimal value
$\sigma_{\bm{\gamma}}^{\ast}$ in Theorem 2. Figure 6(a) shows the performance
of the algorithm under different privacy requirements. The computation
accuracy strictly decreases as $T$ increases for all privacy levels
$\epsilon$, while a larger averaging step $T$ is required under a smaller
privacy level $\epsilon$ to reach the same computation accuracy. To show
whether the theoretic $T$ in Theorem 2 can fulfill the desired computation
accuracy, we compare it with the practical one in Figure 6(a) to reach various
accuracy $\nu$. Table 3(c) indicates that under each pair of $(\epsilon,\nu)$,
the $T$ in Theorem 2 is larger and thus guarantees the desired computation
accuracy. We also compare our PPSC-Gossip-AC algorithm with the He2020
algorithm in [29], whose computation accuracy under different privacy
requirements $\epsilon$ is presented in Figure 6(b). As seen from Figure 6(b),
a higher privacy requirement results in a larger computation error. This
indicates a trade-off between the computation accuracy and privacy in [29],
while such a trade-off does not exist in PPSC-Gossip-AC algorithm.

Figure 5: Relation between $S$ and $\rho$ under different ${\rm G}_{\rm p}$
($10^{6}$ samples). Table 2: A comparison of minimal $T$ to reach various
accuracy $\nu$ in Theorem 2 and Figure 6(a)

$\rho$ | Theo. 2 | Fig. 5
---|---|---
$0.7126$ | 8 | 5
$0.9393$ | 12 | 8
$0.9867$ | 15 | 11

$\rho$ | Theo. 2 | Fig. 5
---|---|---
$0.9970$ | 18 | 14
$0.9993$ | 21 | 17
$0.9998$ | 25 | 20

(a) The PPSC-Gossip-AC algorithm

(b) The algorithm of He2020 [29]

Figure 6: The computation accuracy in the mean square sense Table 3: A
comparison of minimal $T$ to reach various accuracy $\nu$ in Theorem 2 and
Figure 6(a)

$\nu$ | Theo. 2 | Fig. 6(a)
---|---|---
$10^{0}$ | 341 | 226
$10^{-1}$ | 371 | 255
$10^{-2}$ | 400 | 285
(a) $\epsilon=10^{-3}$

$\nu$ | Theo. 2 | Fig. 6(a)
---|---|---
$10^{0}$ | 282 | 167
$10^{-1}$ | 312 | 197
$10^{-2}$ | 341 | 227
(b) $\epsilon=10^{-2}$

$\nu$ | Theo. 2 | Fig. 6(a)
---|---|---
$10^{0}$ | 223 | 123
$10^{-1}$ | 253 | 153
$10^{-2}$ | 282 | 183
(c) $\epsilon=10^{-1}$

###  6.2 Network Linear Equations

In this subsection, we apply the PPSC-Gossip-NLE solver to solve the network
linear algebraic equation over the public network ${\rm G}$ in Figure 4, where
each edge is assigned with weight $1\over 4$ and each agent $i$ holds a
sensitive equation $\mathfrak{E}_{i}$ (see Table 4).

We consider three computation accuracy requirements
$\nu=10^{0},10^{-1},10^{-2}$, and thus select $L=207$, $L=260$ and $L=313$,
respectively according to Theorem 3. For these cases, we fix the differential
privacy probability as $\rho=0.95$ and thus let $S=26$ for all simulations.
For each accuracy requirement $\nu=10^{0},10^{-1},10^{-2}$ and privacy
requirement $\epsilon=10^{-3},10^{-2},10^{-1}$, we run the PPSC-Gossip-NLE
solver with the private network ${\rm G}_{\rm p}$ in Figure 4(c) and the noise
variance $\sigma_{\bm{\gamma}}$ as the minimal value
$\sigma_{\bm{\gamma}}^{\ast}$ in Theorem 3. The simulation results are
presented in Figure 7 and Tables 5(c)-6(c). Figures 7(a), 7(b) and 7(c)
demonstrate the relationship between the resulting computation accuracy and
the averaging step $T$ at various pairs of accuracy and privacy requirements,
i.e., $(\nu,\epsilon)$. In all these figures, it can be seen that as $T$
increases, the resulting computation accuracy decreases until a lower bound
that is smaller than the expected accuracy $\nu$. Under each pair of
$(\nu,\epsilon)$, from Table 5(c) the theoretic $T$ in Theorem 3 is larger
than that in Figures 7(a), 7(b) and 7(c), and from Table 6(c) the resulting
differential privacy probability is larger than the expected $\rho=0.95$.
Therefore, the proposed solver following Theorem 3 achieves the desired
computation accuracy and differential privacy, simultaneously.

Table 4: Private datasets for solving network linear equations with solution $\mathbf{y}^{\ast}=[5;-10;10;-5;1;5]$ $\mathbf{H}_{1}=[1;2;0;0;0;0]$; $z_{1}=-15$ |  $\mathbf{H}_{6}=[2;0;1;0;2;1]$; $z_{6}=27$
---|---
$\mathbf{H}_{2}=[1;1;1;0;0;0]$; $z_{2}=5$ |  $\mathbf{H}_{7}=[1;1;1;2;0;1]$; $z_{7}=0$
$\mathbf{H}_{3}=[0;1;1;0;0;3]$; $z_{3}=15$ |  $\mathbf{H}_{8}=[3;1;5;6;8;-2]$; $z_{8}=23$
$\mathbf{H}_{4}=[0;-1;1;2;5;-2]$; $z_{4}=5$ |  $\mathbf{H}_{9}=[0;-2;0;1;5;0]$; $z_{9}=20$
$\mathbf{H}_{5}=[5;-2;0;2;0;1]$; $z_{5}=40$ |  $\mathbf{H}_{10}=[0;0;0;0;2;-1]$; $z_{10}=-3$

(a) Expected accuracy $\nu=10^{0}$

(b) Expected accuracy $\nu=10^{-1}$

(c) Expected accuracy $\nu=10^{-2}$

Figure 7: The actual accuracy
$\mathbb{E}\|\mathbf{x}_{L(S+T+1)}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}$
under various expected privacy $\nu$ and accuracy $\epsilon$. Table 5: A
comparison of minimal $T$ to reach various accuracy $\nu$ in Theorem 3 and
Figure 7

$\nu$ | Theo. 3 | Fig. 7
---|---|---
$10^{0}$ | 552 | 204
$10^{-1}$ | 579 | 217
$10^{-2}$ | 605 | 229
(a) $\epsilon=10^{-3}$

$\nu$ | Theo. 3 | Fig. 7
---|---|---
$10^{0}$ | 507 | 180
$10^{-1}$ | 533 | 192
$10^{-2}$ | 559 | 207
(b) $\epsilon=10^{-2}$

$\nu$ | Theo. 3 | Fig. 7
---|---|---
$10^{0}$ | 461 | 155
$10^{-1}$ | 487 | 170
$10^{-2}$ | 513 | 182
(c) $\epsilon=10^{-1}$

Table 6: Resulting differential privacy probability under various accuracy and
privacy levels

$\nu$ | probability
---|---
$10^{0}$ | 0.9975
$10^{-1}$ | 0.9975
$10^{-2}$ | 0.9970
(a) $\epsilon=10^{-3}$

$\nu$ | probability
---|---
$10^{0}$ | 0.9983
$10^{-1}$ | 0.9970
$10^{-2}$ | 0.9971
(b) $\epsilon=10^{-2}$

$\nu$ | probability
---|---
$10^{0}$ | 0.9977
$10^{-1}$ | 0.9970
$10^{-2}$ | 0.9967
(c) $\epsilon=10^{-1}$

###  6.3 Classification with Logistic Loss Function

Finally, we investigate the practical performance of the PPSC-Gossip-DCO
algorithm in contrast to existing privacy-preserving distributed optimization
protocols [9, 12] for a linear classification problem. We assume each node $i$
of the public network $\mathrm{G}$ holds a database that consists of samples
$(a_{i,j},b_{i,j})\in\mathbb{R}^{m}\times\\{0,1\\}$ with $j=1,\dots,N_{i}$ and
$i=1,\ldots,n$. Note that $a_{i,j},b_{i,j}$ represent a sample’s features and
label, respectively. Then we specify the objective in (2) as the training goal
of the well-known logistic regression classifier, i.e.,

$f_{i}(\mathbf{y})=\sum\limits_{j=1}^{N_{i}}b_{ij}a_{ij}^{\top}\mathbf{y}-\log(1+\exp(a_{ij}^{\top}\mathbf{y}))+\frac{\lambda}{2n}\|\mathbf{y}\|^{2}\,,\quad
i=1,\ldots,n.$

To conduct numerical experiments, we specify the feasible space $\mathtt{C}$
in (2) as a unit ball and adopt the MNIST111See
http://yann.lecun.com/exdb/mnist/ dataset as the overall database. MNIST is a
database of handwritten digits consisting of $60000$ samples and $784$
features in the training set, and $10000$ samples in the test set. We
artificially and evenly allocate all training samples to all nodes of
$\mathrm{G}$ in Figure 4(a), so that all three protocols, including the PPSC-
Gossip-DCO algorithm with the private network $\mathrm{G}_{\mathrm{p}}$ in
Figure 4(c), Huang2015 [9], Nozari2018 [12], can be executed over $\mathrm{G}$
with uniform privacy budgets $\epsilon=0.001,0.01,0.1$ for $L=3000$ steps. At
each $l$, we let
$\bar{\mathbf{y}}(l)=\sum\limits_{i=1}^{n}\mathbf{y}_{i}(l)/n$ denote the
network’s estimate towards the global logistic model, based on which
prediction is performed over both the training set and the test set. The Area
under the Curve (AUC), calculated based on the true and the predicted labels,
is a metric ranging from zero to one for model evaluation. It represents the
probability that a random positive sample whose $b_{ij}=1$ has a larger
predicted label than that of a random negative sample whose $b_{ij}=0$. Note
that the larger the AUC is, the better prediction can be made under the model.
A model with AUC 0.5 is no better than a random guess. In this example, we
will evaluate the instantaneous models at each $l$ trained under the mentioned
three algorithms by calculating their AUC, and plot the AUC trajectory for
various $\epsilon$ in Figure 8.

We observe in Figure 8(a) \- 8(c), although the AUC of Nozari2018 [12]
promptly converges to $0.78,0.80,0.82$ for $\epsilon=0.001,0.01,0.1$, it soon
gets overtaken by that of the PPSC-Gossip-DCO algorithm between the $1200$\-
and $1400$-th iteration. From the $1500$-th iteration, the AUC of the PPSC-
Gossip-DCO algorithm stays at a high and steady level of $0.85$, implying that
the model trained under the PPSC-Gossip-DCO algorithm has a much better
predictive ability than that of Nozari2018 [12], especially for the smallest
$\epsilon=0.001$. In fact, thank to the “shuffle and average” mechanism of the
PPSC-Gossip-DCO algorithm, it manages to train almost the same and accurate
model as the privacy-preserving requirement goes stronger. In addition,
Huang2015 [9], which preserves the data privacy at a high cost of perturbing
the shared states, only drives the AUC to a low level below $0.6$.

Based on the observations above, on the one hand, we find that the PPSC-
Gossip-DCO algorithm outperforms the objective-perturbing method Nozari2018
[12] in the long run because of the exact objective function adopted in the
PPSC-Gossip-DCO algorithm. This superiority is even more significant under
high differential privacy requirements. On the other hand, the state-
perturbing strategy Huang2015 [9] gains the model nearly no knowledge, because
exponentially decaying step size is implemented for the compliance of
differential privacy, which provides no feasibility guarantee. In conclusion,
for this experiment the PPSC-Gossip-DCO algorithm has an overwhelming
advantage over Huang2015 [9] and Nozari2018 [12] in terms of accuracy, at the
price of, of course, a higher computation overhead.

(a) Expected accuracy $\nu=10^{0}$

(b) Expected accuracy $\nu=10^{-1}$

(c) Expected accuracy $\nu=10^{-2}$

Figure 8: The AUC under various expected privacy $\nu$ and accuracy
$\epsilon$.

##  7 Conclusions

In this paper, differentially private distributed computing protocols were
developed for computation tasks of average consensus, network linear algebraic
equation and distributed convex optimization via public-private networks. Such
protocols were established on the Multi-Gossiping PPSC mechanism over a
private communication graph, where randomly selected node pairs update their
states in such a way that they are shuffled with random noise while
maintaining summation consistency. By embedding the multi-gossip PPSC
mechanism for privacy encryption before an averaging consensus algorithm over
the public network for local computations, we developed a PPSC-Gossip
averaging consensus algorithm, which can compute the average with any desired
accuracy, while achieving any desired differential privacy with any prescribed
probability. This PPSC-Gossip averaging consensus algorithm was then employed
to develop two respective distributed computing protocols for network linear
equations and distributed convex optimization. It was shown that both
protocols can offer both differential privacy and computation accuracy
guarantees. In future works, it is of interest to investigate the possibility
of integrating the PPSC framework or its extensions to distributed
optimization problems without gradient information or problems with online
settings where data arrives at the nodes sequentially.

##  Appendix A Proof of Theorem 1

###  A.1 Preliminaries

Without loss of generality, we let all nodes be indexed such that $i<j$ for
any nodes $i\in\mathrm{V}^{k}$ and $j\in\mathrm{V}^{k+1}$.

Let $\mathrm{V}^{k}=\\{k_{1},\ldots,k_{n_{k}}\\}$, and denote by
$\mathsf{e}_{\rm p}^{k}(s)=\big{(}k_{s_{\rm out}},k_{s_{\rm in}}\big{)}$ the
randomly selected edge during gossiping procedure in component
$\mathrm{G}_{\rm p}^{k}$ at $s\in[1,S]$. Let $\mathsf{C}_{\mathsf{E}_{\rm
p}^{k}}=\displaystyle\prod_{s=1}^{S}\mathsf{C}_{S-s+1}^{k}$ with
$\mathsf{C}_{s}^{k}\in\mathbb{R}^{n_{k}\times n_{k}}$ be a matrix each column
$h$ of which is $\mathbf{e}_{h}$ except the $s_{\rm out}$-th column that is
$\mathbf{e}_{s_{\rm in}}$, and $\mathsf{D}_{\mathsf{E}_{\rm
p}^{k}}\in\mathbb{R}^{n_{k}\times S}$ be a matrix the $h$-th column of which
is $\prod_{s=1}^{S-h}\mathsf{C}_{S-s+1}^{k}(\mathbf{e}_{h_{\rm
out}}-\mathbf{e}_{h_{\rm in}})$ for $h=1,2,\ldots,S-1$ and $\mathbf{e}_{S_{\rm
out}}-\mathbf{e}_{S_{\rm in}}$ for $h=S$. We note that both random matrices
$\mathsf{C}_{\mathsf{E}_{\rm p}^{k}}$ and $\mathsf{D}_{\mathsf{E}_{\rm
p}^{k}}$ are determined by the randomly selected edge sequence
$\mathsf{E}_{\rm p}^{k}$, and given any positive integer $S$, there is a
finite-number set $\Theta_{a}^{k}$ of $\mathsf{E}_{\rm p}^{k}$. Thus, the map
$\mathcal{M}_{\rm S}$ can be explicitly expressed by

${\mathbf{y}_{\rm ppsc}=\mathcal{M}_{\rm
S}(\bm{\beta}):=\mathsf{C}_{\mathsf{E}_{\rm
p}}\bm{\beta}+\mathsf{D}_{\mathsf{E}_{\rm p}}{\bm{\gamma}}\,}$ (11)

with $\mathsf{C}_{\mathsf{E}_{\rm
p}}=\mbox{blkdiag}\;\big{(}\mathsf{C}_{\mathsf{E}_{\rm
p}^{1}},\ldots,\mathsf{C}_{\mathsf{E}_{\rm p}^{q}}\big{)}$ and
$\mathsf{D}_{\mathsf{E}_{\rm
p}}=\mbox{blkdiag}\;\big{(}\mathsf{D}_{\mathsf{E}_{\rm
p}^{1}},\ldots,\mathsf{D}_{\mathsf{E}_{\rm p}^{q}}\big{)}$. Moreover, the
expression of $\lambda_{\rm ppsc}$ can be simplified as

$\lambda_{\rm ppsc}=\min\\{\lambda_{\rm ppsc}^{1},\ldots,\lambda_{\rm
ppsc}^{q}\\}\,,\qquad\mbox{with $\lambda_{\rm
ppsc}^{k}=\displaystyle\min_{\mathsf{E}_{\rm
p}^{k}\in\Theta_{a}^{k}}\sigma_{m}^{+}\big{(}\mathsf{D}_{\mathsf{E}_{\rm
p}^{k}}\big{)}$, $k=1,\ldots,q$.}$

###  A.2 A technical lemma

Next, we present a lemma on $p_{0}$-privacy covering time for the multi-
gossiping PPSC mechanism.

######  Definition 8.

Introduce $\mathcal{Q}_{s}$ as the event that all nodes have altered their
states at least once during the time $s\in[1,t]$. For any $p_{0}\in(0,1)$, the
$p_{0}$-privacy covering time for the multi-gossiping PPSC mechanism is
defined by

$S_{p_{0}}(\mathrm{G}_{\rm
p})=\inf\\{t:1-\mathbb{P}(\mathcal{Q}_{t})\leq{p_{0}}\\}.$

In this definition, the $S_{p_{0}}(\mathrm{G}_{\rm p})$ denotes the time
needed to guarantee the event $\mathcal{Q}_{s}$ with probability $1-p_{0}$.
Regarding this time $S_{p_{0}}(\mathrm{G}_{\rm p})$, we present the following
result.

######  Lemma 1.

For any ${p_{0}}\in(0,1)$, the ${p_{0}}$-privacy covering time associated with
graph $\mathrm{G}_{\rm p}$ for the multi-gossiping PPSC mechanism satisfies

$S_{p_{0}}(\mathrm{G}_{\rm p})\geq\frac{\log(1-(1-p_{0})^{1\over q})-\log
n_{\max}}{\log(1-\frac{1+r^{\dagger}}{n_{\max}})}.$

###### Proof.

For any $k=1,\ldots,q$, we denote $\mathcal{F}_{k_{i}}^{t}$ the event that
node $k_{i}\in{\rm G}_{\rm p}^{k}$ has its state changed at least once during
the time interval $[1,t]$, i.e., $\mathcal{F}_{k_{i}}^{t}=\\{x_{k_{i}}(t)\neq
x_{k_{i}}(0)\\}$. Then, it is seen that node $k_{i}$ has its state changed at
any $s\in\\{1,\dots,t\\}$ with
$\frac{1}{n_{k}}+\frac{1}{n_{k}}\sum_{j=1}^{r_{k_{i}}}\frac{1}{r_{k_{j}}}$
probability. Then it follows

$\mathbb{P}(\mathcal{F}_{k_{i}}^{t})=1-\big{(}1-\frac{1}{n_{k}}-\frac{1}{n_{k}}\sum_{j=1}^{r_{k_{i}}}\frac{1}{r_{k_{j}}}\big{)}^{t}\geq
1-\big{(}1-\frac{1+r_{k}^{\dagger}}{n_{k}}\big{)}^{t}$ (12)

with $r_{k}^{\dagger}=\frac{r_{k}^{\rm min}}{r_{k}^{\rm max}}$. Clearly,
$\mathcal{Q}_{s}=\bigcap\limits_{i\in\mathrm{V}}\mathcal{F}_{i}^{t}$. By (12)
and the Fréchet inequalities [43], we have

$\begin{array}[]{rcl}\mathbb{P}(\mathcal{Q}_{t})&=&\prod\limits_{k=1}^{q}\mathbb{P}\left(\bigcap\limits_{i\in\mathrm{V}^{k}}\mathcal{F}_{i}^{t}\right)\geq\prod\limits_{k=1}^{q}\left(\sum\limits_{i=1}^{n_{k}}\mathbb{P}(\mathcal{F}_{k_{i}}^{t})-(n_{k}-1)\right)\\\
&\geq&\prod\limits_{k=1}^{q}\left(1-{n_{k}}(1-\frac{1+r_{k}^{\dagger}}{n_{k}})^{t}\right)\geq\left(1-{n_{\max}}\big{(}1-\frac{1+r^{\dagger}}{n_{\max}}\big{)}^{t}\right)^{q}.\end{array}$
(13)

The proof is thus completed with (13). ∎

###  A.3 Proof of Theorem 1

From the structure of the multi-gossip algorithm, it follows that for all
possible edge sequences $\mathsf{E}_{\rm p}=\big{\\{}\mathsf{E}_{\rm
p}^{1},\ldots,\mathsf{E}_{\rm p}^{q}\big{\\}}$, we have
$\|\mathsf{C}_{\mathsf{E}_{\rm p}}\|_{1}=1$ and
$\mbox{rank}\;(\mathsf{D}_{\mathsf{E}_{\rm p}})\leq n-q$. Let $\mathsf{E}_{\rm
p}^{\ast}$ be the sequence of communication edges observed by eavesdroppers,
and $\mathbf{C}\in\mathbb{R}^{n\times n}$ and
$\mathbf{D}\in\mathbb{R}^{n\times qS}$ be the resulting values of
$\mathsf{C}_{\mathsf{E}_{\rm p}^{\ast}}$ and $\mathsf{D}_{\mathsf{E}_{\rm
p}^{\ast}}$, respectively. Thus, the $\mathscr{M}_{\rm S}$ conditioned on
$\mathsf{E}_{\rm p}^{\ast}$ takes the form

${\mathbf{y}_{\rm ppsc}=\mathscr{M}_{\rm
S}\big{(}{\bm{\beta}}\,|\,\mathsf{E}_{\rm
p}^{\ast}\big{)}=\mathbf{C}\bm{\beta}+\mathbf{D}{\bm{\gamma}}\,}$ (14)

with $\|\mathbf{C}\|_{1}=1$ and $\mbox{rank}\;(\mathbf{D})\leq n-q$. Then, we
denote $\mbox{rank}\;(\mathbf{D}):=r\leq n-q$, and
$\mathbf{D}^{\perp}\in\mathbb{R}^{(n-r)\times n}$ be such that
$\mathbf{D}^{\perp}\mathbf{D}=0$ and $\mbox{rank}\;(\mathbf{D}^{\perp})=n-r$.
Let $U_{a}\in\mathbb{R}^{r\times n}$ be such that
$U_{a}U_{a}^{\top}=\mathbf{I}_{r}$ and $\mathbf{T}_{\rm
M}:=\begin{bmatrix}\mathbf{D}^{\perp}\cr
U_{a}\end{bmatrix}\in\mathbb{R}^{n\times n}$ is nonsingular. Thus, the matrix
$\Sigma_{a}:=U_{a}\mathbf{D}$ satisfies $\mbox{rank}\;(\Sigma_{a})=r$ and
$\sigma_{m}(\Sigma)=\lambda_{\rm ppsc}^{2}$ with
$\Sigma:=\Sigma_{a}\Sigma_{a}^{\top}$.

With $p_{0}=1-\rho$ and $S\geq S_{\rho}^{\ast}$, it can be seen from Lemma 1
that the event $\mathcal{Q}_{S}$ occurs with the probability larger than
$\rho$. Conditioned on $\mathcal{Q}_{S}$, we proceed to analyze the
differential privacy of the mechanism (14). According to [25], for any two
$\mu$-adjacent $\bm{\beta},{\bm{\beta}}^{\prime}\in\mathbb{R}^{n}$, we have

$\begin{array}[]{rcl}&&\mathbb{P}\big{(}\mathscr{M}_{\rm
S}(\bm{\beta}\,|\,\mathsf{E}_{\rm p}^{\ast})\in
R\big{)}=\mathbb{P}\big{(}\mathbf{T}_{\rm
M}\mathbf{C}\bm{\beta}+\mathbf{T}_{\rm
M}\mathbf{D}{\bm{\gamma}}\in\mathbf{T}_{\rm M}R\big{)}\\\
&=&\mathbb{P}(U_{a}\mathbf{C}\bm{\beta}+\Sigma_{a}{\bm{\gamma}}\in
R^{\prime})\\\
&=&(2\pi)^{-\frac{r}{2}}\frac{1}{\sigma_{{\bm{\gamma}}}\mbox{det}\;(\Sigma)^{\frac{1}{2}}}\displaystyle\int_{R^{\prime}}\exp\bigg{(}-\frac{1}{2\sigma_{{\bm{\gamma}}}^{2}}(u-U_{a}\mathbf{C}\bm{\beta})^{\top}\Sigma^{-1}(u-U_{a}\mathbf{C}\bm{\beta})\bigg{)}{\rm
d}u\\\
&\leq&\exp(\epsilon)\cdot\mathbb{P}(U_{a}\mathbf{C}\bm{\beta}^{\prime}+\Sigma_{a}{\bm{\gamma}}\in
R^{\prime})+\mathbb{P}\bigg{(}\frac{1}{\sigma_{{\bm{\gamma}}}}{\tilde{\bm{\beta}}}^{\top}\mathbf{C}^{\top}U_{a}^{\top}\Sigma^{-\frac{1}{2}}v\geq\epsilon-\frac{1}{2\sigma_{{\bm{\gamma}}}^{2}}\|\Sigma^{-\frac{1}{2}}U_{a}\mathbf{C}\tilde{\bm{\beta}}\|^{2}\bigg{)}\\\
&\leq&\exp(\epsilon)\cdot\mathbb{P}\big{(}\mathbf{T}_{\rm
M}\mathbf{C}\bm{\beta}^{\prime}+\mathbf{T}_{\rm
M}\mathbf{D}{\bm{\gamma}}\in\mathbf{T}_{\rm
M}R\big{)}+\mathbb{P}\bigg{(}Z\geq\frac{\epsilon\sigma_{{\bm{\gamma}}}\sqrt{\sigma_{m}(\Sigma)}}{\|\mathbf{C}\|_{1}\mu}-\frac{\|\mathbf{C}\|_{1}\mu}{2\sigma_{{\bm{\gamma}}}\sqrt{\sigma_{m}(\Sigma)}}\bigg{)}\\\
&=&\exp(\epsilon)\cdot\mathbb{P}\big{(}\mathscr{M}_{\rm
S}(\bm{\beta}^{\prime}\,|\,\mathsf{E}_{\rm p}^{\ast})\in
R\big{)}+\mathbb{P}\bigg{(}Z\geq\frac{\epsilon\sigma_{{\bm{\gamma}}}\sqrt{\sigma_{m}(\Sigma)}}{\|\mathbf{C}\|_{1}\mu}-\frac{\|\mathbf{C}\|_{1}\mu}{2\sigma_{{\bm{\gamma}}}\sqrt{\sigma_{m}(\Sigma)}}\bigg{)}\end{array}$

with $R^{\prime}=U_{a}R$,
$\tilde{\bm{\beta}}={\bm{\beta}}-{\bm{\beta}}^{\prime}$,
$v\sim\mathcal{N}(0,\mathbf{I}_{r})$ and $Z\sim\mathcal{N}(0,1)$.

Thus, the $(\epsilon,\delta)$-differential privacy is preserved with
probability larger than $\rho$, if

${\delta\geq\mathcal{Q}\bigg{(}\frac{\epsilon\sigma_{{\bm{\gamma}}}\sqrt{\sigma_{m}(\Sigma)}}{\|\mathbf{C}\|_{1}\mu}-\frac{\|\mathbf{C}\|_{1}\mu}{2\sigma_{{\bm{\gamma}}}\sqrt{\sigma_{m}(\Sigma)}}\bigg{)}\,\,.}$
(15)

With $\mathcal{Q}(w)$ being a strictly decreasing smooth function,
$\sigma_{m}(\Sigma)=\lambda_{\rm ppsc}^{2}$ and $\|\mathbf{C}\|_{1}=1$, it is
clear that (15) is equivalent to

$\frac{\epsilon\lambda_{\rm
ppsc}}{\mu}\sigma_{{\bm{\gamma}}}^{2}-\mathcal{Q}^{-1}(\delta)\sigma_{{\bm{\gamma}}}-\frac{\mu}{2\lambda_{\rm
ppsc}}\geq 0\,,$

which is clearly true by recalling that
$\sigma_{\bm{\gamma}}\geq\frac{{\mu\kappa(\epsilon,\delta)}}{\lambda_{\rm
ppsc}}$.

##  Appendix B Proof of Theorem 2

Since no extra randomness is introduced during the averaging consensus stage,
it can be seen that the desired $(\epsilon,\delta)$-differential privacy is
guaranteed with probability higher than $\rho$ by the proof of Theorem 1 in
Appendix A. In the following, we will focus on the computation accuracy.

######  Lemma 2.

Along the PPSC-Gossip-AC algorithm, there holds

${\mathbb{E}\|\mathbf{x}_{S+T}-\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}\mathbf{x}_{0}\|^{2}\leq[n\|\mathbf{x}_{0}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}]\cdot(1-\lambda_{\rm
G})^{2T}.}$ (16)

###### Proof.

We first observe that

${\mathbb{E}\,\|\mathbf{x}_{S}-\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}\mathbf{x}_{0}\|^{2}=\mathbb{E}\,\|\mathbf{x}_{S}\|^{2}+\frac{1}{n}\left|\mathbf{1}_{n}^{\top}\mathbf{x}_{0}\right|^{2}-\frac{2}{n}\mathbf{1}_{n}^{\top}\mathbf{x}_{0}\mathbf{1}_{n}^{\top}\mathbb{E}\mathbf{x}_{S}.}$
(17)

Next, we will seek the upper bound of each term on the right hand side of (17)
so as to get the upper bound of $\mathbb{E}\,\|\mathbf{x}_{S}-\frac{1}{n}{\bf
1}_{n}{\bf 1}_{n}^{\top}\mathbf{x}_{0}\|^{2}$. By (11) and
$\mathbb{E}\,{\bm{\gamma}}=0$, the first term satisfies

${\mathbb{E}\,\|\mathbf{x}_{S}\|^{2}\leq\mathbb{E}\,\|\mathsf{C}_{\mathsf{E}_{\rm
p}}\|_{\rm
F}^{2}\|\mathbf{x}_{0}\|^{2}+\mathbb{E}\,\|\mathsf{D}_{\mathsf{E}_{\rm
p}}\|_{\rm F}^{2}\|{\bm{\gamma}}\|^{2}.}$ (18)

By the structure of the PPSC multi-gossiping mechanism, it can be verified
that there are deterministically $n$ ones in the entries of
$\mathsf{C}_{\mathsf{E}_{\rm p}}$, and at most $qS$ ones and $qS$ minus ones
in $\mathsf{D}_{\mathsf{E}_{\rm p}}$, i.e., $\|\mathsf{C}_{\mathsf{E}_{\rm
p}}\|_{\rm F}=\sqrt{n},\|\mathsf{D}_{\mathsf{E}_{\rm p}}\|_{\rm
F}\leq\sqrt{2qS}$. In addition,
$\mathbb{E}\,\|{\bm{\gamma}}\|^{2}=qS\sigma_{{\bm{\gamma}}}^{2}$. Then it
follows from (18) that

${\mathbb{E}\,\|\mathbf{x}_{S}\|^{2}\leq
n\|\mathbf{x}_{0}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}.}$ (19)

To analyze the third term of (17), we observe that
$\mathbf{x}_{S}=\mathsf{C}_{\mathsf{E}_{\rm
p}}\mathbf{x}_{0}+\mathsf{D}_{\mathsf{E}_{\rm p}}{\bm{\gamma}}$. By the
structure of the PPSC multi-gossiping mechanism again, we note that there hold
$\mathbf{1}_{n}^{\top}\mathsf{C}_{\mathsf{E}_{\rm p}}=\mathbf{1}_{n}^{\top}$
and $\mathbf{1}_{n}^{\top}\mathsf{D}_{\mathsf{E}_{\rm p}}=0$,
deterministically. Thus, we have

${\begin{array}[]{rcl}\frac{2}{n}\mathbf{1}_{n}^{\top}\mathbf{x}_{0}\mathbf{1}_{n}^{\top}\mathbb{E}\mathbf{x}_{S}&=&\frac{2}{n}\mathbf{1}_{n}^{\top}\mathbf{x}_{0}\big{(}\mathbb{E}(\mathbf{1}_{n}^{\top}\mathsf{C}_{\mathsf{E}_{\rm
p}})\mathbf{x}_{0}+\mathbb{E}\mathbf{1}_{n}^{\top}\mathsf{D}_{\mathsf{E}_{\rm
p}}{\bm{\gamma}}\big{)}\\\
&=&\frac{2}{n}|\mathbf{1}_{n}^{\top}\mathbf{x}_{0}|^{2}\end{array}}$ (20)

Thus, substituting (19) and (20) into (17) yields

${\begin{array}[]{rcl}\mathbb{E}\,\|\mathbf{x}_{S}-\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}{\mathbf{x}_{0}}\|^{2}&\leq&n\|\mathbf{x}_{0}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}-\frac{1}{n}\left|\mathbf{1}_{n}^{\top}\mathbf{x}_{0}\right|^{2}\,\leq
n\|\mathbf{x}_{0}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}\,.\end{array}}$
(21)

With the upper bound in (21), we now proceed to show the bound of
$\mathbb{E}\left(\|\mathbf{x}_{S+T}-\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}\mathbf{x}_{0}\|^{2}\right)$. Notice that
$\mathbf{x}_{s+1}=(\mathbf{I}_{n}-\mathbf{A})\mathbf{x}_{s}$ for $s\geq S$,
which yields

$\begin{array}[]{rcl}\|\mathbf{x}_{S+T}-\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}\mathbf{x}_{0}\|^{2}&=&\|(\mathbf{I}_{n}-\mathbf{A}-\frac{1}{n}{\bf
1}_{n}{\bf 1}_{n}^{\top})(\mathbf{x}_{S}-\frac{1}{n}{\bf 1}_{n}{\bf
1}_{n}^{\top}\mathbf{x}_{0})\|^{2}\leq\|\mathbf{x}_{S}-\frac{1}{n}{\bf
1}_{n}{\bf 1}_{n}^{\top}\mathbf{x}_{0}\|^{2}(1-\lambda_{\rm
G})^{2T}\,.\end{array}$

This, together with (21), completes the proof. ∎

This lemma in turn proves the desired computation accuracy in combination with
$\mathbf{x}_{0}=\mathbf{d}$ and (5).

##  Appendix C Proof of Theorem 3

###  C.1 Preliminaries

Let $\bm{\zeta}_{0}=\mathbf{1}_{n}\otimes\zeta_{0}$ and
$\bm{\zeta}_{l}=\mathbf{x}_{(l-1)(S+T+1)+S}$, $l=1,\ldots,L$. Denote by
$\gamma_{k}(s)\in\mathbb{R}^{m}$ the randomly and independently generated
noise vector in the $k$-th component of ${\rm G}_{\rm p}$ at time
$s\in[l(S+T+1)+1,l(S+T+1)+S]$, $l=0,1,\ldots,L-1$. Let
${\bm{\gamma}}_{l}=[{\bm{\gamma}}_{1,l};{\bm{\gamma}}_{2,l};\ldots;{\bm{\gamma}}_{q,l}]$
with

${\bm{\gamma}}_{k,l}=[{\bm{\gamma}}_{k}(l(S+T+1)+1);{\bm{\gamma}}_{k}({l(S+T+1)+2});\ldots;{\bm{\gamma}}_{k}(l(S+T+1)+S)]\,,$

for $l=0,1,\ldots,L-1$. For any $\mathbf{x}=[x_{1};\ldots;x_{n}]$ with
$x_{k}\in\mathbb{R}^{m}$, $k=1,\ldots,n$, we denote

$\mathpzc{P}_{\mathscr{E}}(x_{1},\ldots,x_{n})=\begin{pmatrix}\mathpzc{P}_{\mathscr{E}_{1}}(x_{1})\\\
\vdots\\\
\mathpzc{P}_{\mathscr{E}_{n}}(x_{n})\end{pmatrix}:=(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})\mathbf{x}+\mathcal{Z}_{\rm H}$

with

$\mathcal{H}_{\rm
H}=\mbox{diag}\left(\frac{\mathbf{H}_{1}\mathbf{H}_{1}^{\top}}{\mathbf{H}_{1}^{\top}\mathbf{H}_{1}}\,\ldots\,\frac{\mathbf{H}_{n}\mathbf{H}_{n}^{\top}}{\mathbf{H}_{n}^{\top}\mathbf{H}_{n}}\right)\,,\quad\mathcal{Z}_{H}=\begin{pmatrix}\frac{z_{1}\mathbf{H}_{1}^{\top}}{\mathbf{H}_{1}^{\top}\mathbf{H}_{1}}&\ldots&\frac{z_{n}\mathbf{H}_{n}^{\top}}{\mathbf{H}_{n}^{\top}\mathbf{H}_{n}}\end{pmatrix}^{\top}\,.$

According to Algorithm 4, we observe that

$\begin{array}[]{rl}\bm{\zeta}_{l+1}&=\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}\mathpzc{P}_{\mathscr{E}}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}\big{)}+\mathsf{D}_{\mathcal{E}_{{\rm
p},l}}{\bm{\gamma}}_{l}\\\ &=\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}+\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}\mathcal{Z}_{\rm H}+\mathsf{D}_{\mathcal{E}_{{\rm
p},l}}{\bm{\gamma}}_{l}\end{array}$

for $l=0,1,\ldots,L-1$, where $\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}=\mbox{blkdiag}\;\big{(}\mathsf{C}_{\mathsf{E}_{{\rm
p},l}^{1}},\ldots,\mathsf{C}_{\mathsf{E}_{{\rm
p},l}^{q}}\big{)}\otimes\mathbf{I}_{m}$ and $\mathsf{D}_{\mathcal{E}_{{\rm
p},l}}=\mbox{blkdiag}\;\big{(}\mathsf{D}_{\mathsf{E}_{{\rm
p},l}^{1}},\ldots,\mathsf{D}_{\mathsf{E}_{{\rm
p},l}^{q}}\big{)}\otimes\mathbf{I}_{m}$, with $\mathsf{C}_{\mathsf{E}_{{\rm
p},l}^{k}}=\displaystyle\prod_{s=1}^{S}\mathsf{C}_{l(L+S+1)+S-s+1}^{k}$ and
$\mathsf{D}_{\mathsf{E}_{{\rm p},l}^{k}}\in\mathbb{R}^{n_{k}\times S}$ being a
matrix the $h$-th column of which is
$\prod_{s=1}^{S-h}\mathsf{C}_{l(L+S+1)+S-s+1}^{k}(\mathbf{e}_{h_{\rm
out}}-\mathbf{e}_{h_{\rm in}})$ for $h=1,2,\ldots,S-1$ and $\mathbf{e}_{S_{\rm
out}}-\mathbf{e}_{S_{\rm in}}$ for $h=S$, in which $\mathsf{C}_{s}^{k}$
follows the definition in Appendix A.

Denote $\bm{\phi}_{l}=\mathbf{x}_{l(S+T+1)}$, $l=0,1,\ldots,L$. Thus, we have

$\begin{array}[]{rcl}\bm{\phi}_{l+1}&=&\mathpzc{P}_{\mathscr{E}}\left(((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l+1}\right)\\\
&=&(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l+1}+\mathcal{Z}_{\rm
H}\\\ &=&(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})[\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}\bm{\phi}_{l}+\mathsf{D}_{\mathcal{E}_{{\rm
p},l}}{\bm{\gamma}}_{l}]+\mathcal{Z}_{\rm H}\\\
&=&\frac{1}{n}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I})\bm{\phi}_{l}+\mathcal{Z}_{\rm
H}+(\mathbf{I}_{mn}-\mathcal{H}_{\rm H})\Delta_{l}(\bm{\phi}_{l})\end{array}$

for $l=0,1,\ldots,L-1$, where $\bm{\phi}_{0}=(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{0}+\mathcal{Z}_{\rm
H}$ and

${\Delta_{l}(\bm{\phi}_{l})=((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})[\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}\bm{\phi}_{l}+\mathsf{D}_{\mathcal{E}_{{\rm
p},l}}{\bm{\gamma}}_{l}]-\frac{1}{n}\big{(}(\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\otimes\mathbf{I}_{m}\big{)}\bm{\phi}_{l}\,.}$
(22)

Before we proceed to the proof of the theorem, the following lemmas are
formulated.

######  Lemma 3.

There holds

$\big{\|}\frac{1}{n}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\big{\|}\leq\lambda_{H}\,.$
(23)

###### Proof.

We consider an auxiliary system

$X_{l+1}=\frac{1}{n}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})X_{l}\,,\quad
X\in\mathbb{R}^{mn}\,.$

Letting
$\vartheta_{l}=\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I})X_{l}$
yields
$\vartheta_{l+1}=\big{(}\mathbf{I}_{mn}-\frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{H}_{i}\mathbf{H}_{i}^{\top}}{\mathbf{H}_{i}^{\top}\mathbf{H}_{i}}\big{)}\vartheta_{l}\,.$
Thus we have $\|\vartheta_{l}\|\leq\|\vartheta_{0}\|\lambda_{H}^{l}$, which
yields

$\|X_{l+1}\|=\big{\|}\frac{1}{n}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{mn})X_{l}\big{\|}=\big{\|}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})(\mathbf{1}_{n}\otimes\mathbf{I}_{m})\vartheta_{l}\big{\|}\leq\sqrt{n}\|\vartheta_{0}\|\lambda_{H}^{l}\,.$

Therefore, it can be inferred that $X_{l}$ exponentially converges to zero and
(23) must hold. ∎

######  Lemma 4.

Given any $l=0,1,\ldots,L-1$, if $\|\Delta_{i}(\bm{\phi}_{i})\|^{2}\leq\nu$
holds for all $i=0,1,\ldots,l$, then there must hold
$\|\bm{\phi}_{l+1}\|\leq\phi^{\ast}$, with
$\phi^{\ast}=2\sqrt{n}\|\mathbf{y}^{\ast}\|+\sqrt{n}\|\zeta_{0}\|+\frac{2-\lambda_{H}}{1-\lambda_{H}}\sqrt{\nu}$.

###### Proof.

Note that

${\bm{\phi}_{l+1}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}=\frac{1}{n}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})(\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast})+(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})\Delta_{l}(\bm{\phi}_{l})\,.}$ (24)

with
$\bm{\phi}_{0}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}=(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})(\mathbf{1}_{n}\otimes(\zeta_{0}-\mathbf{y}^{\ast}))$.
By Lemma 3, if $\|\Delta_{i}(\bm{\phi}_{i})\|^{2}\leq\nu$ holds for all
$i=0,1,\ldots,l$, we then have
$\|\bm{\phi}_{l+1}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|\leq\lambda_{H}\|\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|+\sqrt{\nu}$,
leading to

$\|\bm{\phi}_{l+1}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|\leq\sqrt{n}\|\zeta_{0}-\mathbf{y}^{\ast}\|\lambda_{H}^{(l+1)}+\frac{2-\lambda_{H}}{1-\lambda_{H}}\sqrt{\nu}\,.$

Thus, we have $\|\bm{\phi}_{l+1}\|\leq\phi^{\ast}$, which completes the proof.
∎

###  C.2 Proof of statement (i).

Let $\mathcal{E}_{{\rm p},l}^{\ast}$ be the sequence of communication edges
that is observed by the eavesdroppers during the time
$s\in[l(S+L+1),l(S+L+1)+S]$, and ${\mathbf{C}}_{l}\in\mathbb{R}^{mn\times mn}$
and $\mathbf{D}_{l}\in\mathbb{R}^{mn\times mS}$ be the resulting values of
$\mathsf{C}_{\mathcal{E}_{{\rm p},l}^{\ast}}$ and
$\mathsf{C}_{\mathcal{E}_{{\rm p},l}^{\ast}}$. For any $0<p_{0}<1$, by the
arguments of Lemma 1, it follows that if $S\geq\frac{\log{(1-p_{0}^{1\over
q})}-\log n_{\max}}{\log(1-\frac{1+r^{\dagger}}{n_{\max}})}$, the event
$\mathcal{Q}_{S}^{l}$ that all node states have altered during the time
$s\in[l(S+T+1)+1,l(S+T+1)+S]$ occurs with probability larger than $p_{0}$ for
$l=0,1,\ldots,L-1$, i.e., $\mathbb{P}(\mathcal{Q}_{s}^{l})\geq p_{0}$. Then we
let $p_{0}=\rho^{1\over 2L}$, and the following lemmas are formulated with
$S,T$ being in Theorem 3.

######  Lemma 5.

There holds

$\begin{array}[]{l}\mathbb{P}\left(\|\Delta_{0}(\bm{\phi}_{0})\|^{2}\leq{\nu}\,|\,\mathcal{Q}_{S}^{0}\right)\geq
p_{0}\\\
\mathbb{P}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\leq{\nu}\,|\,\big{(}\bigcap_{i=0}^{l}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)\geq
p_{0}\,,\qquad\quad\mbox{for all }l=1,2,\ldots,L-1\end{array}$

###### Proof.

Following the arguments of Lemma 2, it can be easily seen that

$\begin{array}[]{l}\mathbb{E}\left(\|\Delta_{0}(\bm{\phi}_{0})\|^{2}\,|\,\mathcal{Q}_{S}^{0}\right)\leq(n\|\bm{\phi}_{0}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})(1-\lambda_{\rm
G})^{2T}\leq(n{\phi^{\ast}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})(1-\lambda_{\rm
G})^{2T}.\end{array}$

Using Markov’s inequality, we have
$\mathbb{P}\left(\|\Delta_{0}(\bm{\phi}_{0})\|^{2}\geq{\nu}\right)\leq\frac{\mathbb{E}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\right)}{\nu}$.
Thus, we have

${\mathbb{P}\left(\|\Delta_{0}(\bm{\phi}_{0})\|^{2}\leq{\nu}\right)\geq
1-\frac{[n{\phi^{\ast}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}](1-\lambda_{\rm
G})^{2T}}{\nu}\,.}$ (25)

Similarly, we now prove the second inequality. With Lemma 4 and by the
arguments of Lemma 2, we have

$\begin{array}[]{l}\mathbb{E}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\,|\,\big{(}\bigcap_{i=0}^{l-1}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)\leq(n{\phi^{\ast}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})(1-\lambda_{\rm
G})^{2T}\end{array}$

for all $l=1,2,\ldots,L-1$. Thus, we have

$\begin{array}[]{rcl}&&\mathbb{P}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\leq{\nu}\,|\,\big{(}\bigcap_{i=0}^{l-1}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)\\\
&=&1-\mathbb{P}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\geq{\nu}\,|\,\big{(}\bigcap_{i=0}^{l-1}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)\\\
&\geq&1-\displaystyle\frac{\mathbb{E}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\,|\,\big{(}\bigcap_{i=0}^{l-1}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)}{\nu}\,.\\\
&\geq&1-\displaystyle\frac{[n{\phi^{\ast}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}](1-\lambda_{\rm
G})^{2T}}{\nu}\end{array}$

This together with (25) completes the proof by combining with the fact that

$T\geq\frac{\log\big{(}(1-p_{0})\nu\big{)}-\log({\phi^{\ast}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})}{2\log(1-\lambda_{\rm
G})}\,.$

∎

With this lemma, we then can obtain that

$\mathbb{P}\left(\mathcal{Q}_{S}^{0}\bigcap\|\Delta_{0}(\bm{\phi}_{0}))\|^{2}\leq{\nu}\right)=\mathbb{P}\left(\|\Delta_{0}(\bm{\phi}_{0})\|^{2}\leq{\nu}\,|\,\mathcal{Q}_{S}^{0}\right)\mathbb{P}\left(\mathcal{Q}_{S}^{0}\right)\geq(p_{0})^{2}\,,$

and recursively for $l=1,\ldots,L-1$, we have

$\begin{array}[]{rcl}&&\mathbb{P}\left(\bigcap_{i=0}^{l}\bigg{(}\mathcal{Q}_{S}^{i}\bigcap\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\bigg{)}\right)\\\
&=&\mathbb{P}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\leq{\nu}\,|\,\big{(}\bigcap_{i=0}^{l}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)\mathbb{P}\left(\big{(}\bigcap_{i=0}^{l}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)\\\
&\geq&p_{0}\mathbb{P}\left(\big{(}\bigcap_{i=0}^{l}\mathcal{Q}_{S}^{i}\big{)}\bigcap\big{(}\bigcap_{i=0}^{l-1}\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\big{)}\right)\\\
&=&p_{0}\mathbb{P}\left(\mathcal{Q}_{S}^{l}\right)\mathbb{P}\left(\bigcap_{i=0}^{l-1}\bigg{(}\mathcal{Q}_{S}^{i}\bigcap\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\bigg{)}\right)\\\
&\geq&(p_{0})^{2}\cdot\mathbb{P}\left(\bigcap_{i=0}^{l-1}\bigg{(}\mathcal{Q}_{S}^{i}\bigcap\|\Delta_{i}(\bm{\phi}_{i}))\|^{2}\leq{\nu}\bigg{)}\right)\,.\end{array}$

In view of the above analysis, we thus have

$\mathbb{P}\left(\bigcap_{l=0}^{L-1}\bigg{(}\mathcal{Q}_{S}^{l}\bigcap\|\Delta_{l}(\bm{\phi}_{l}))\|^{2}\leq{\nu}\bigg{)}\right)\geq(p_{0})^{2L}=\rho\,.$

Conditioned on the event
$\bigcap_{l=0}^{L-1}\big{(}\mathcal{Q}_{S}^{l}\bigcap\|\Delta_{l}(\bm{\phi}_{l}))\|^{2}\leq{\nu}\big{)}$,
we are now proceeding to analyze the differential privacy of PPSC-Gossip
network linear-equation solver. Let $\mathcal{E}_{\rm
p}^{\ast}=\big{\\{}\mathcal{E}_{{\rm p},0}^{\ast},\mathcal{E}_{{\rm
p},1}^{\ast},\ldots,\mathcal{E}_{{\rm p},L-1}^{\ast}\big{\\}}$. For any two
$\mu$-adjacent equations $\mathfrak{E}:\mathbf{H}\mathbf{y}=\mathbf{z},\
\mathfrak{E}^{\prime}:\mathbf{H}^{\prime}\mathbf{y}=\mathbf{z}^{\prime}$, we
let $R_{l}\subseteq\mathbb{R}^{mn}$ and denote the events

$\begin{array}[]{rcl}{\mathcal{F}_{l}^{\rm
ea}}=\\{\mathbf{C}_{l}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}+\mathbf{C}_{l}\mathcal{Z}_{\rm
H}+\mathbf{D}_{l}{\bm{\gamma}}_{l}\in R_{l}\\}\\\ {\mathcal{F}_{l}^{\rm
ea}}^{\prime}=\\{\mathbf{C}_{l}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H}^{\prime})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}+\mathbf{C}_{l}\mathcal{Z}_{\rm
H}^{\prime}+\mathbf{D}_{l}{\bm{\gamma}}_{l}\in R_{l}\\}\end{array}$

for $l=0,1,\ldots,L-1$, with

$\mathcal{H}_{\rm
H}^{\prime}=\mbox{diag}\begin{pmatrix}\frac{\mathbf{H}_{1}^{\prime}{\mathbf{H}_{1}^{\prime}}^{\top}}{{\mathbf{H}_{1}^{\prime}}^{\top}\mathbf{H}_{1}^{\prime}}&\ldots&\frac{{\mathbf{H}_{n}^{\prime}}{\mathbf{H}_{n}^{\prime}}^{\top}}{{\mathbf{H}_{n}^{\prime}}^{\top}{\mathbf{H}_{n}^{\prime}}}\end{pmatrix}\,,\quad\mathcal{Z}_{H}^{\prime}=\begin{pmatrix}\frac{z_{1}^{\prime}{\mathbf{H}_{1}^{\prime}}^{\top}}{{\mathbf{H}_{1}^{\prime}}^{\top}{\mathbf{H}_{1}^{\prime}}}&\ldots&\frac{z_{n}^{\prime}{\mathbf{H}_{n}^{\prime}}^{\top}}{{\mathbf{H}_{n}^{\prime}}^{\top}{\mathbf{H}_{n}^{\prime}}}\end{pmatrix}^{\top}\,.$

Thus, recalling the fact that the Average-Consensus procedure in Algorithm 4
is deterministic, we can see that for all
$R\subseteq\mbox{range}(\mathscr{M}_{\rm eq})$, there always exist
$R_{l}\subseteq\mathbb{R}^{mn}$, $l=0,1,\ldots,L-1$ such that there holds

$\begin{array}[]{l}\mathbb{P}\big{(}\mathscr{M}_{\rm
eq}\big{(}\mathfrak{E}\,|\,\mathcal{E}_{\rm p}^{\ast}\big{)}\in
R\big{)}=\mathbb{P}\big{(}\bigcap_{l=0}^{L-1}{\mathcal{F}_{l}^{\rm
ea}}\big{)}=\mathbb{P}\big{(}{\mathcal{F}_{0}^{\rm
ea}}\big{)}\cdot\prod_{l=1}^{L-1}\mathbb{P}\big{(}{\mathcal{F}_{l}^{\rm
ea}}|\,\bigcap_{k=0}^{l-1}{\mathcal{F}_{k}^{\rm ea}}\big{)}\\\ \end{array}$

With this in mind, we observe that

$\begin{array}[]{rcl}&&\|\big{(}\mathbf{C}_{l}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}+\mathbf{C}_{l}\mathcal{Z}_{\rm
H}\big{)}-\big{(}\mathbf{C}_{l}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H}^{\prime})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}+\mathbf{C}_{l}\mathcal{Z}_{\rm
H}^{\prime}\big{)}\|\\\ &\leq&\|\mathbf{C}_{l}(\mathcal{H}_{\rm
H}^{\prime}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}\|+\|\mathbf{C}_{l}(\mathcal{Z}_{\rm
H}-\mathcal{Z}_{\rm H}^{\prime})\big{)}\|\\\
&\leq&\mu\|((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}\|+\mu\sqrt{n}\\\
\end{array}$

where the second inequality is obtained by using the facts that
$\|\mathbf{C}_{l}\|_{1}=1$ and $\mathfrak{E}$ and $\mathfrak{E}^{\prime}$ are
$\mu$-adjacent. Thus, for $l=0$, we have

$\begin{array}[]{rcl}&&\|\big{(}\mathbf{C}_{0}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{0}+\mathbf{C}_{0}\mathcal{Z}_{\rm
H}\big{)}-\big{(}\mathbf{C}_{0}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H}^{\prime})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{0}+\mathbf{C}_{0}\mathcal{Z}_{\rm
H}^{\prime}\big{)}\|\\\ &\leq&\mu\sqrt{n}(\|\zeta_{0}\|+1)\\\
&\leq&\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})\,,\end{array}$

and for $l=1,\ldots,L-1$, we have

$\begin{array}[]{rcl}&&\|\big{(}\mathbf{C}_{l}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}+\mathbf{C}_{l}\mathcal{Z}_{\rm
H}\big{)}-\big{(}\mathbf{C}_{l}(\mathbf{I}_{mn}-\mathcal{H}_{\rm
H}^{\prime})((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}+\mathbf{C}_{l}\mathcal{Z}_{\rm
H}^{\prime}\big{)}\|\\\
&\leq&\mu\|\Delta_{l-1}(\bm{\phi}_{l-1})+\frac{1}{n}\big{(}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m}\big{)}\bm{\phi}_{l-1}\|+\mu\sqrt{n}\\\
&\leq&\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})\end{array}$

where the first inequality is obtained by using
$\Delta_{l-1}(\bm{\phi}_{l-1})+\frac{1}{n}\big{(}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m}\big{)}\bm{\phi}_{l-1}=((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}$,
and the second is obtained by using the conditioned event
$\bigcap_{l=0}^{L-1}\big{(}\mathcal{Q}_{S}^{l}\bigcap\|\Delta_{l}(\bm{\phi}_{l}))\|^{2}\leq{\nu}\big{)}$
and Lemma 4.

As in the arguments in Appendix A, we can obtain

$\begin{array}[]{rcl}&&\mathbb{P}(\mathscr{M}_{\rm
eq}\big{(}\mathfrak{E}\,|\,\mathcal{E}_{\rm p}^{\ast}\big{)}\in
R\big{)}=\mathbb{P}\big{(}{\mathcal{F}_{0}^{\rm
ea}}\big{)}\cdot\prod_{l=1}^{L-1}\mathbb{P}\big{(}{\mathcal{F}_{l}^{\rm
ea}}|\,\bigcap_{k=0}^{l-1}{\mathcal{F}_{k}^{\rm ea}}\big{)}\\\
&\leq&\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{0}^{\rm
ea}}^{\prime}\big{)}+\mathbb{P}\big{(}Z_{0}\geq\frac{\epsilon\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}{L\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}-\frac{\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}{2\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}\big{)}\bigg{)}\cdot\\\
&&\cdot\prod_{l=1}^{L-1}\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{l}^{\rm
ea}}^{\prime}|\,\bigcap_{k=1}^{l-1}{\mathcal{F}_{k}^{\rm
ea}}^{\prime}\big{)}+\mathbb{P}\big{(}Z_{l}\geq\frac{\epsilon\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}{L\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}-\frac{\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}{2\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}\big{)}\bigg{)}\\\ &\leq&\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{0}^{\rm
ea}}^{\prime}\big{)}+\delta_{\ast}\bigg{)}\cdot\prod_{l=1}^{L-1}\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{l}^{\rm
ea}}^{\prime}|\,\bigcap_{k=1}^{l-1}{\mathcal{F}_{k}^{\rm
ea}}^{\prime}\big{)}+\delta_{\ast}\bigg{)}\\\
&\leq&\exp(\epsilon)\mathbb{P}\big{(}\mathscr{M}_{\rm
eq}\big{(}\mathfrak{E}^{\prime}\,|\,\mathcal{E}_{\rm p}^{\ast}\big{)}\in
R\big{)}+\big{(}\exp\big{(}\frac{\epsilon}{L}\big{)}+\delta_{\ast})^{L}-e^{\epsilon}\end{array}$

with $Z_{l}\sim\mathcal{N}(0,1)$, and

$\delta_{\ast}=\mathcal{Q}\bigg{(}\frac{\epsilon\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}{L\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}-\frac{\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}{2\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}\bigg{)}\,.$

With $\delta_{\sharp}=(\delta+e^{\epsilon})^{1\over
L}-\exp(\frac{\epsilon}{L})$ and
$\sigma_{\bm{\gamma}}\geq\sigma_{\bm{\gamma}}^{\ast}:={\mu\kappa(\frac{\epsilon}{L},\delta_{\sharp})(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}/{\lambda_{\rm
ppsc}}$, we have

$\kappa(\frac{\epsilon}{L},\delta_{\sharp})\leq\frac{\lambda_{\rm
ppsc}\sigma_{{\bm{\gamma}}}}{\mu(\sqrt{\nu}+\phi^{\ast}+\sqrt{n})}$

yielding $\delta_{\sharp}\geq\delta_{\ast}$. This indicates
$(\delta+e^{\epsilon})^{1\over L}\geq\delta_{\ast}+\exp(\frac{\epsilon}{L})$,
leading to

$\delta\geq\big{(}\exp\big{(}\frac{\epsilon}{L}\big{)}+\delta_{\ast}\big{)}^{L}-e^{\epsilon}\,.$

Therefore, there holds

$\mathbb{P}\big{(}\mathscr{M}_{\rm eq}\big{(}\mathfrak{E}\,|\,\mathcal{E}_{\rm
p}^{\ast}\big{)}\in
R\big{)}\leq\exp(\epsilon)\mathbb{P}\big{(}\mathscr{M}_{\rm
eq}\big{(}\mathfrak{E}^{\prime}\,|\,\mathcal{E}_{\rm p}^{\ast}\big{)}\in
R\big{)}+\delta\,,$

which completes this part of proof.

###  C.3 Proof of statement (ii)

We observe that each $\Delta_{l}(\bm{\phi}_{l})$ defined in (22),
$l=0,1,\ldots,L-1$ can be regarded as the computation error of the PPSC-
Gossip-AC algorithm with initial state $\bm{\phi}_{l}$. Thus, by Lemma 2, we
have

$\begin{array}[]{rcl}\mathbb{E}\|\Delta_{l}(\bm{\phi}_{l})\|^{2}&\leq&(n\mathbb{E}\|\bm{\phi}_{l}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})(1-\lambda_{\rm
G})^{2T}\\\
&\leq&\big{(}2n\mathbb{E}\|\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}+2n\|\mathbf{y}^{\ast}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}\big{)}(1-\lambda_{\rm
G})^{2T}\,.\end{array}$

where the last inequality is obtained by using the
H$\ddot{\textnormal{o}}$lder inequality.

In view of this, with (24) and using the H$\ddot{\textnormal{o}}$lder
inequality again, we thus have

$\begin{array}[]{l}\mathbb{E}\|\bm{\phi}_{l+1}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}\leq\lambda_{H}^{2}\mathbb{E}\|\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}+\mathbb{E}\|\Delta_{l}(\bm{\phi}_{l})\|^{2}+2\sqrt{\lambda_{H}^{2}\mathbb{E}\|\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}\mathbb{E}\|\Delta_{l}(\bm{\phi}_{l})\|^{2}}\\\
\qquad\leq(\lambda_{H}^{2}+2n(1-\lambda_{\rm
G})^{2T})\mathbb{E}\|\bm{\phi}_{l-1}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}+\big{[}2n\|\mathbf{y}^{\ast}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}\big{]}(1-\lambda_{\rm
G})^{2T}\\\
\qquad+\bigg{[}3n\mathbb{E}\|\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}+2n\|\mathbf{y}^{\ast}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}\bigg{]}\cdot(1-\lambda_{\rm
G})^{T}\\\ \leq\big{(}\lambda_{H}^{2}+5n(1-\lambda_{\rm
G})^{T}\big{)}\mathbb{E}\|\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}+4\big{(}n\|\mathbf{y}^{\ast}\|^{2}+q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}\big{)}(1-\lambda_{\rm
G})^{T}\,.\\\ \end{array}$

This yields

$\begin{array}[]{l}\mathbb{E}\|\bm{\phi}_{L}-\mathbf{1}\otimes\mathbf{y}^{\ast}\|^{2}\leq\|\bm{\phi}_{0}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}(\lambda_{H}^{2}+5n(1-\lambda_{\rm
G})^{T})^{L}+\frac{4(n\|\mathbf{y}^{\ast}\|^{2}+S^{2}\sigma_{{\bm{\gamma}}}^{2})(1-\lambda_{\rm
G})^{T}}{1-\lambda_{H}^{2}-5n(1-\lambda_{\rm G})^{T}}\end{array}$

with $\|\bm{\phi}_{0}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}\leq
n\|\zeta_{0}-\mathbf{y}^{\ast}\|^{2}$. With the selections of $L$ and $T$ in
Theorem 3, we have

$\begin{array}[]{l}\lambda_{H}^{2}+5n(1-\lambda_{\rm
G})^{T}\leq\frac{\varepsilon_{0}+\lambda_{H}^{2}}{1+\varepsilon_{0}}\\\
\|\bm{\phi}_{0}-\mathbf{1}_{n}\otimes\mathbf{y}^{\ast}\|^{2}(\lambda_{H}^{2}+5n(1-\lambda_{\rm
G})^{T})^{L}\leq\frac{\nu}{2}\\\
\frac{4(n\|\mathbf{y}^{\ast}\|^{2}+S^{2}\sigma_{{\bm{\gamma}}}^{2})(1-\lambda_{\rm
G})^{T}}{1-\lambda_{H}^{2}-5n(1-\lambda_{\rm
G})^{T}}\leq\frac{\nu}{2}\,.\end{array}$

This in turn completes the proof.

##  Appendix D Proof of Theorem 4

###  D.1 Preliminaries

Following the terminologies in Appendix C, we let
$\bm{\zeta}_{0}=\mathbf{1}_{n}\otimes\zeta_{0}$ and
$\bm{\zeta}_{l}\in\mathbb{R}^{nm}$ denote the netowrk state vector after the
$l$ PPSC-Gossip procedure, and $\bm{\phi}_{0}=\mathbf{x}_{0}$ and
$\bm{\phi}_{l}$ denote the network state vector after the $l$-th procedure of
projected subgradient descent. Denote

$\mathpzc{P}_{\mathtt{C}^{n}}(x_{1},\ldots,x_{n})=\begin{pmatrix}\mathpzc{P}_{\mathtt{C}}(x_{1})\\\
\vdots\\\ \mathpzc{P}_{\mathtt{C}}(x_{n})\end{pmatrix}\,,\quad\mbox{for
$x_{k}\in\mathbb{R}^{m}$}\,$

and

$\nabla\mathbf{F}(x_{1},\ldots,x_{n})=\begin{pmatrix}\nabla f_{1}(x_{1})\\\
\vdots\\\ \nabla f_{n}(x_{n})\end{pmatrix}=\begin{pmatrix}\frac{\partial
f_{1}}{\partial x_{1}}(x_{1})\\\ \vdots\\\ \frac{\partial f_{n}}{\partial
x_{n}}f_{n}(x_{n})\end{pmatrix}\,,\quad\mbox{for $x_{k}\in\mathbb{R}^{m}$}\,.$

According to Algorithm 5, we have

${\begin{array}[]{rl}\bm{\zeta}_{l+1}&=\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}\bm{\phi}_{l}+\mathsf{D}_{\mathcal{E}_{{\rm
p},l}}{\bm{\gamma}}_{l}\,,\quad\mbox{for $l=0,1,\ldots,L-1$}\end{array}}$ (26)

and

${\begin{array}[]{rcl}\bm{\phi}_{l+1}&=&\mathpzc{P}_{\mathtt{C}^{n}}\left(\big{(}(\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m}\big{)}\bm{\zeta}_{l+1}-\alpha_{l+1}\nabla\mathbf{F}\big{(}\big{(}(\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m}\big{)}\bm{\zeta}_{l+1}\big{)}\right)\,\,,\quad\mbox{for
$l=0,1,\ldots,L-1$}\\\ \end{array}}$ (27)

###  D.2 Proof of statement (i)

We define

$\begin{array}[]{rcl}\bm{\psi}_{l}(\bm{\phi}_{l})&=&\mathpzc{P}_{\mathtt{C}^{n}}\left(\big{(}(\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m}\big{)}\bm{\zeta}_{l+1}-\alpha_{l+1}\nabla\mathbf{F}\big{(}\big{(}(\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m}\big{)}\bm{\zeta}_{l+1}\big{)}\right)\\\
&&-\big{(}(\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m}\big{)}\bm{\zeta}_{l+1}+\alpha_{l+1}\nabla\mathbf{F}\big{(}\big{(}(\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m}\big{)}\bm{\zeta}_{l+1}\big{)}\\\
\Delta_{l}(\bm{\phi}_{l})&=&((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})[\mathsf{C}_{\mathcal{E}_{{\rm
p},l}}\bm{\phi}_{l}+\mathsf{D}_{\mathcal{E}_{{\rm
p},l}}\Gamma_{l}]-\frac{1}{n}[(\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\otimes\mathbf{I}_{m}]\bm{\phi}_{l}\,.\end{array}$

This then rewrites (27) as

$\begin{array}[]{l}\bm{\phi}_{l+1}=\frac{1}{n}(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{l}+\Delta_{l}(\bm{\phi}_{l})-\alpha_{l+1}\nabla\mathbf{F}\big{(}\frac{1}{n}(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{l}+\Delta_{l}(\bm{\phi}_{l})\big{)}+\bm{\psi}_{l}(\bm{\phi}_{l})\,.\end{array}$

To complete this part of proof, we present the following lemma.

######  Lemma 6.

Suppose $\|\Delta_{l}(\bm{\phi}_{l})\|\leq\sqrt{\nu}\alpha_{l+1}^{2}$ for all
$l\geq 0$. Then there exists an $L^{\dagger}$, independent of $S$, $T$ and
$\sigma_{\bm{\gamma}}$, and a $\mathbf{y}^{\dagger}\in\mathtt{C}^{\dagger}$
such that
$\|\bm{\phi}_{L}-\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger}\|^{2}\leq\nu$ holds
for all $L\geq L^{\dagger}$.

###### Proof.

We denote
$\theta_{l}=\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{l}-\mathbf{y}^{\ddagger}$
for any $\mathbf{y}^{\ddagger}\in\mathtt{C}^{\dagger}$, which yields

$\theta_{l+1}=\theta_{l}+\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\Delta_{l}-\frac{\alpha_{l+1}}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})+\Delta_{l}\big{)}+\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\psi}_{l}(\bm{\phi}_{l})\,.$

According to Lemma 1.(b) in [20], this further implies

$\begin{array}[]{rcl}\|\theta_{l+1}\|^{2}&\leq&\left\|\theta_{l}+\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\Delta_{l}-\frac{\alpha_{l+1}}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})+\Delta_{l}\big{)}\right\|^{2}-\frac{1}{n}\|\bm{\psi}_{l}(\bm{\phi}_{l})\|^{2}\\\
&\leq&\|\theta_{l}\|^{2}+\frac{1}{n}\|\Delta_{l}\|^{2}+\frac{2}{n}\|\Delta_{l}\|\|\theta_{l}\|+\frac{\alpha_{l+1}^{2}}{n}\left\|\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})+\Delta_{l}\big{)}\right\|^{2}\\\
&&-\frac{2\alpha_{l+1}}{n}\mathbf{1}_{n}^{\top}\left[\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\dagger})+\Delta_{l}\big{)}-\mathbf{F}(\mathbf{1}_{n}\otimes\mathbf{y}^{\ddagger})\right]-\frac{1}{n}\|\bm{\psi}_{l}(\bm{\phi}_{l})\|^{2}\,.\end{array}$

If $\|\Delta_{l}(\bm{\phi}_{l})\|\leq\sqrt{\nu}\alpha_{l+1}^{2}$ for all
$l=1,2,\ldots,L$, we then have

${\begin{array}[]{rcl}\|\theta_{l+1}\|^{2}&\leq&\|\theta_{l}\|^{2}+\frac{\nu}{n}\alpha_{l+1}^{4}+\frac{2\sqrt{\nu}}{n}\alpha_{l+1}^{2}\|\theta_{l}\|+\frac{\alpha_{l+1}^{2}}{n}\left\|\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})+\Delta_{l}\big{)}\right\|^{2}\\\
&&+\sqrt{\nu}\alpha_{l+1}^{3}\left\|\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})+\Delta_{l}\big{)}\right\|\\\
&&-\frac{2\alpha_{l+1}}{n}\mathbf{1}_{n}^{\top}\left[\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})\big{)}-\mathbf{F}(\mathbf{1}_{n}\otimes\mathbf{y}^{\ddagger})\right]-\frac{1}{n}\|\bm{\psi}_{l}(\bm{\phi}_{l})\|^{2}\end{array}}$
(28)

for each $\mathbf{y}^{\ddagger}\in\mathtt{C}^{\dagger}$. Note that each
$\nabla f_{k}$ is bounded over the set $\Omega_{\nu}$, i.e., there exists a
$L_{\nu}>0$ such that $\|\nabla f_{k}(\mathbf{y})\|\leq L_{\nu}$, for all
$\mathbf{y}\in\Omega_{\nu}$ and $k\in{\rm V}$. Since
$\theta_{l}+\mathbf{y}^{\ddagger}=\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{l}\in\mathtt{C}\subset\Omega_{\nu}$,
we have

${\begin{array}[]{l}\left\|\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})\big{)}\right\|^{2}\leq
nL_{\nu}^{2}\\\
\mathbf{e}_{i}^{\top}\left[\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\ddagger})+\Delta_{l}\big{)}-\mathbf{F}(\mathbf{1}_{n}\otimes\mathbf{y}^{\ddagger})\right]\geq
0\,,\quad\mbox{for all $i=1,\ldots,n$}\end{array}}$ (29)

which yields

$\begin{array}[]{rcl}\|\theta_{l+1}\|^{2}&\leq&\|\theta_{l}\|^{2}+\frac{\nu}{n}\alpha_{l+1}^{4}+\frac{2\sqrt{\nu}}{n}\alpha_{l+1}^{2}\|\theta_{l}\|+\alpha_{l+1}^{2}L_{\nu}^{2}+\sqrt{n\nu}\alpha_{l+1}^{3}L_{\nu}-\frac{1}{n}\|\bm{\psi}_{l}(\bm{\phi}_{l})\|^{2}\end{array}$
(30)

for each $\mathbf{y}^{\ddagger}\in\mathtt{C}^{\dagger}$. By dropping the last
negative term and using the facts that $\|\theta_{l-1}\|$ is bounded by
$\theta_{l}+\mathbf{y}^{\ddagger}=\frac{1}{n}\sum_{k=1}^{n}\bm{\phi}_{l,k}\in\mathtt{C}$
and $\lim_{l\rightarrow\infty}\sum_{i=1}^{l}\alpha_{i}^{2}<\infty$, we can
conclude that the sequence $\\{\|\theta_{l}\|\\}$, i.e.,
$\\{\|\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{l}-\mathbf{y}^{\ddagger}\|\\}$
is convergent for each $\mathbf{y}^{\ddagger}\in\mathtt{C}^{\dagger}$. Since
$\frac{1}{n}(\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{l}$ is
bounded, it must have a limit point $\mathbf{y}^{\dagger}$. On the other hand,
by (28), we can obtain

$\begin{array}[]{l}\|\theta_{l+1}\|^{2}+\sum\limits_{i=0}^{l}\frac{2\alpha_{i+1}}{n}\mathbf{1}_{n}^{\top}\left[\mathbf{F}\big{(}\frac{1}{n}(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{i}\big{)}-\mathbf{F}(\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger})\right]\\\
\qquad\leq\|\theta_{0}\|^{2}+\sum\limits_{i=0}^{l}\big{(}\frac{\nu}{n}\alpha_{i+1}^{4}+\frac{2\sqrt{\nu}}{n}\alpha_{i+1}^{2}\|\theta_{i}\|+\alpha_{i+1}^{2}L_{\nu}^{2}+\sqrt{n\nu}\alpha_{i+1}^{3}L_{\nu}\big{)}\,,\end{array}$

the right side of which is bounded by
$\lim_{l\rightarrow\infty}\sum_{i=1}^{l}\alpha_{i}^{2}<\infty$ and the fact
that $\|\theta_{i}\|$ is bounded. This in turn implies

$\lim_{l\rightarrow\infty}\sum\limits_{i=0}^{l}\frac{2\alpha_{i+1}}{n}\mathbf{1}_{n}^{\top}\left[\mathbf{F}\big{(}\frac{1}{n}(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{i}\big{)}-\mathbf{F}(\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger})\right]<\infty\,.$

By $\lim_{l\rightarrow\infty}\sum_{i=1}^{l}\alpha_{l}=\infty$ and the latter
of (29), we have

$\lim_{l\rightarrow\infty}\mathbf{F}\big{(}\frac{1}{n}(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\otimes\mathbf{I}_{m})\bm{\phi}_{l}\big{)}-\mathbf{F}(\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger})=\mathbf{F}\big{(}\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger}\big{)}-\mathbf{F}(\mathbf{1}_{n}\otimes\mathbf{y}^{\ddagger})=0\,,$

which yields $\mathbf{y}^{\dagger}\in\mathtt{C}^{\dagger}$. Therefore, by
fixing $\mathbf{y}^{\ddagger}$ as $\mathbf{y}^{\dagger}$ in the definition of
$\theta_{l}$, we have $\lim\limits_{l\rightarrow\infty}\theta_{l}=0$.

Bearing in mind the previous analysis, we then observe that

$\begin{array}[]{l}\bm{\phi}_{l+1}-\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger}=\mathbf{1}_{n}\otimes\theta_{l}+\Delta_{l}(\bm{\phi}_{l})-\alpha_{l+1}\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\dagger})+\Delta_{l}(\bm{\phi}_{l})\big{)}+\bm{\psi}_{l}(\bm{\phi}_{l})\end{array}$

which, if $\|\Delta_{l}(\bm{\phi}_{l})\|\leq\sqrt{\nu}\alpha_{l+1}^{2}$ for
all $l=0,1,\ldots,L-1$, leads to

$\|\bm{\phi}_{l+1}-\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger}\|\leq\sqrt{n}\|\theta_{l}\|+\sqrt{\nu}\alpha_{l+1}^{2}+\alpha_{l+1}nL_{\nu}+\|\bm{\psi}_{l}(\bm{\phi}_{l})\|\,.$

Regarding the bound of the last term in the above inequality, we observe that

$\begin{array}[]{rcl}\bm{\psi}_{l}(\bm{\phi}_{l})&=&\mathpzc{P}_{\mathtt{C}^{n}}\left(\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\dagger})+\Delta_{l}(\bm{\phi}_{l})-\alpha_{l+1}\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\dagger})+\Delta_{l}(\bm{\phi}_{l})\big{)}\right)\\\
&&-\left(\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\dagger})+\Delta_{l}(\bm{\phi}_{l})-\alpha_{l+1}\nabla\mathbf{F}\big{(}\mathbf{1}_{n}\otimes(\theta_{l}+\mathbf{y}^{\dagger})+\Delta_{l}(\bm{\phi}_{l})\big{)}\right)\end{array}$

which immediately follows that there exist $c_{1},c_{2}>0$ such that
$\|\bm{\psi}_{l}(\bm{\phi}_{l})\|\leq c_{1}\|\theta_{l}\|+c_{2}\alpha_{l+1}$.
Thus, as $\lim_{l\rightarrow\infty}\|\theta_{l}\|=0$ and
$\lim_{l\rightarrow\infty}\alpha_{l}=0$, we have
$\lim_{l\rightarrow\infty}\|\bm{\phi}_{l}-\mathbf{1}_{n}\otimes\mathbf{y}^{\dagger}\|=0$,
which completes the proof. ∎

By Lemma 2, we have
$\mathbb{E}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\right)\geq(n\|\bm{\phi}_{l}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})(1-\lambda_{\rm
G})^{2T}$ for all $l\geq 0$. Using Markov’s inequality, this implies that for
any $\nu>0$,

$\mathbb{P}\big{(}\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\geq\nu\alpha_{l+1}^{4}\big{)}\leq\frac{\mathbb{E}\left(\|\Delta_{l}(\bm{\phi}_{l})\|^{2}\right)}{\nu\alpha_{l+1}^{4}}\,$

yielding

$\mathbb{P}\left(\bigcap_{l=0}^{L-1}\|\Delta_{l}(\bm{\phi}_{l}))\|\leq\sqrt{\nu}\alpha_{l+1}^{2}\right)\geq\prod_{l=0}^{L-1}\bigg{(}1-\frac{[n\|\bm{\phi}_{l}\|^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2}](1-\lambda_{\rm
G})^{2T}}{\nu\alpha_{l+1}^{4}}\bigg{)}\,.$

Thus, with $\bm{\phi}_{l}\in\mathtt{C}$ for $l\geq 0$ and
$T\geq\frac{\log((1-p^{1\over
L})\nu\alpha_{L}^{4})-\log(n{\phi^{\dagger}}^{2}+2q^{2}S^{2}\sigma_{{\bm{\gamma}}}^{2})}{2\log(1-\lambda_{\rm
G})}$, we have

${\mathbb{P}\left(\bigcap_{l=0}^{L-1}\|\Delta_{l}(\bm{\phi}_{l}))\|\leq\sqrt{\nu}\alpha_{l+1}^{2}\right)\geq
p\,.}$ (31)

Therefore, the proof is completed by combining Lemma 6 and (31).

###  D.3 Proof of statement (ii)

By the arguments of Lemma 1, it immediately follows that the event
$\mathcal{Q}_{S}^{l}$ that all node states have altered during the time
$s\in[l(S+T+1)+1,l(S+T+1)+S]$ occurs with probability larger than
$\rho^{1\over L}$, i.e., $\mathbb{P}(\mathcal{Q}_{S}^{l})\geq\rho^{1\over L}$
and $\mathbb{P}\left(\bigcap_{l=0}^{L-1}\mathcal{Q}_{S}^{l}\right)\geq\rho$.
With this in mind, we now proceed to analyze the differential privacy of PPSC-
Gossip-DCO algorithm, conditioned on the event
$\bigcap_{l=0}^{L-1}\mathcal{Q}_{S}^{l}$.

As in Appendix C, we denote $\mathcal{E}_{\rm
p}^{\ast}:=\big{\\{}\mathcal{E}_{{\rm p},0}^{\ast},\mathcal{E}_{{\rm
p},1}^{\ast},\ldots,\mathcal{E}_{{\rm p},L-1}^{\ast}\big{\\}}$ as the sequence
of communication edges that is observed by the eavesdroppers during $L$
recursions of the Multi-Gossiping PPSC mechanism, and
${\mathbf{C}}_{l}\in\mathbb{R}^{mn\times mn}$ and
$\mathbf{D}_{l}\in\mathbb{R}^{mn\times mS}$ be the resulting values of
$\mathsf{C}_{\mathcal{E}_{{\rm p},l}^{\ast}}$ and
$\mathsf{C}_{\mathcal{E}_{{\rm p},l}^{\ast}}$.

Let $R_{l}\subseteq\mathbb{R}^{mn}$ and define the events

$\begin{array}[]{l}{\mathcal{F}_{l}^{op}}:=\left\\{\mathbf{C}_{l}\mathpzc{P}_{\mathtt{C}^{n}}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}-\alpha_{l}\nabla\mathbf{F}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}\big{)}\big{)}+\mathbf{D}_{l}{\bm{\gamma}}_{l}\in
R_{i}\right\\}\\\
{\mathcal{F}_{l}^{op}}^{\prime}:=\left\\{\mathbf{C}_{l}\mathpzc{P}_{\mathtt{C}^{n}}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}-\alpha_{l}\nabla\mathbf{F}^{\prime}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}\big{)}\big{)}+\mathbf{D}_{l}{\bm{\gamma}}_{l}\in
R_{i}\right\\}\end{array}$

for $l=0,1,\ldots,L-1$. Further, we define

$\begin{array}[]{l}\widetilde{\mathpzc{P}}_{l}:=\mathpzc{P}_{\mathtt{C}^{n}}\bigg{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}-\alpha_{l}\nabla\mathbf{F}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}\big{)}\bigg{)}\\\
\qquad\quad-\mathpzc{P}_{\mathtt{C}^{n}}\bigg{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}-\alpha_{l}\nabla\mathbf{F}^{\prime}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I}_{m})\bm{\zeta}_{l}\big{)}\bigg{)}\,,\end{array}$

which for any $\mu$-adjacent $\mathbf{F}^{\prime},\mathbf{F}$, satisfies

$\begin{array}[]{rcl}\|\widetilde{\mathpzc{P}}_{l}\|&\leq&\alpha_{l}\|\nabla\mathbf{F}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I})\bm{\zeta}_{l}\big{)}-\nabla\mathbf{F}^{\prime}\big{(}((\mathbf{I}_{n}-\mathbf{A})^{T}\otimes\mathbf{I})\bm{\zeta}_{l}\big{)}\|\\\
&\leq&\alpha_{l}\sum_{i=1}^{n}\|(\tau_{i}-\tau_{i}^{\prime})\|g^{\dagger}\\\
&\leq&ng^{\dagger}\mu\,.\end{array}$

Bearing in mind the previous analysis, as in the arguments in Appendices A and
C, we can obtain

$\begin{array}[]{rcl}&&\mathbb{P}(\mathscr{M}_{\rm
op}\big{(}\mathbf{F}\,|\,\mathcal{E}_{\rm p}^{\ast}\big{)}\in R\big{)}\\\
&\leq&\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{0}^{op}}^{\prime}\big{)}+\mathbb{P}\bigg{(}Z_{l}\geq\frac{\epsilon\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}{Lng^{\dagger}\mu}-\frac{ng^{\dagger}\mu}{2\sigma_{{\bm{\gamma}}}}\lambda_{\rm
ppsc}\bigg{)}\bigg{)}\\\
&&\cdot\prod\limits_{l=1}^{L-1}\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{l}^{op}}^{\prime}|\,\bigcap\limits_{k=1}^{l-1}{\mathcal{F}_{k}^{op}}^{\prime}\big{)}+\mathbb{P}\bigg{(}Z_{l}\geq\frac{\epsilon\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}{Lng^{\dagger}\mu}-\frac{ng^{\dagger}\mu}{2\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}\bigg{)}\bigg{)}\\\ &\leq&\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{0}^{op}}^{\prime}\big{)}+\delta_{\dagger}\bigg{)}\cdot\prod_{l=1}^{L-1}\bigg{(}\exp({\epsilon\over
L})\cdot\mathbb{P}\big{(}{\mathcal{F}_{l}^{op}}^{\prime}|\,\bigcap_{k=1}^{l-1}{\mathcal{F}_{k}^{op}}^{\prime}\big{)}+\delta_{\dagger}\bigg{)}\\\
&\leq&\exp(\epsilon)\mathbb{P}\big{(}\mathscr{M}_{\rm
op}(\mathbf{F}^{\prime}\,|\,\mathcal{E}_{\rm p}^{\ast})\in
R\big{)}+\big{(}\exp({\epsilon\over
L})+\delta_{\dagger}\big{)}^{L}-e^{\epsilon}\end{array}$

with $Z_{l}\sim\mathcal{N}(0,1)$, and
$\delta_{\dagger}=\mathcal{Q}\bigg{(}\frac{\epsilon\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}{Lng^{\dagger}\mu}-\frac{ng^{\dagger}\mu}{2\sigma_{{\bm{\gamma}}}\lambda_{\rm
ppsc}}\bigg{)}$. With $\sigma_{{\bm{\gamma}}}\geq\frac{n\mu
g^{\dagger}\mathcal{R}(\frac{\epsilon}{L},\delta_{\sharp})}{\lambda_{\rm
ppsc}}$ and $\delta_{\sharp}=(\delta+e^{\epsilon})^{1\over
L}-\exp({\epsilon\over L})$, it can be seen that $\big{(}\exp({\epsilon\over
L})+\delta_{\dagger}\big{)}^{L}-e^{\epsilon}\leq\delta$. The proof is thus
completed.

## References

  * [1] L. T. Berger and K. Iniewski, _Smart grid applications, communications, and security_. John Wiley & Sons, 2012\.
  * [2] L. Sabattini, N. Chopra, and C. Secchi, “Decentralized connectivity maintenance for cooperative control of mobile robotic systems,” _The International Journal of Robotics Research_ , vol. 32, no. 12, pp. 1411–1423, 2013\.
  * [3] J. Zhang, F. Wang, K. Wang, W. Lin, X. Xu, and C. Chen, “Data-driven intelligent transportation systems: A survey,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 12, no. 4, pp. 1624–1639, 2011.
  * [4] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein _et al._ , “Distributed optimization and statistical learning via the alternating direction method of multipliers,” _Foundations and Trends in Machine learning_ , vol. 3, no. 1, pp. 1–122, 2011.
  * [5] K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié, “Optimal algorithms for smooth and strongly convex distributed optimization in networks,” in _Proceedings of International Conference on Machine Learning_ , pp. 3027–3036, 2017.
  * [6] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in _Proceedings of the 41st annual ACM symposium on Theory of computing_ , pp. 169–178, 2009.
  * [7] Y. Shoukry, K. Gatsis, A. Alanwar, G. Pappas, S. Seshia, M. Srivastava, and P. Tabuada, “Privacy-aware quadratic optimization using partially homomorphic encryption,” in _Proceedings of the 55th IEEE Conference on Decision and Control_ , pp. 5053–5058, 2016.
  * [8] A. Gascón, P. Schoppmann, B. Balle, M. Raykova, J. Doerner, S. Zahur, and D. Evans, “Privacy-preserving distributed linear regression on high-dimensional data,” _Proceedings on Privacy Enhancing Technologies_ , no. 4, pp. 345–364, 2017.
  * [9] Z. Huang, S. Mitra, and N. Vaidya, “Differentially private distributed optimization,” in _Proceedings of the International Conference on Distributed Computing and Networking_ , pp. 1–10, 2015.
  * [10] R. Hall, A. Rinaldo, and L. Wasserman, “Differential privacy for functions and functional data,” _Journal of Machine Learning Research_ , vol. 14, no. Feb, pp. 703–727, 2013.
  * [11] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of Cryptography Conference_ , pp. 265–284, 2006.
  * [12] E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private distributed convex optimization via functional perturbation,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 1, pp. 395–408, 2018\.
  * [13] Z. Huang, S. Mitra, and G. Dullerud, “Differentially private iterative synchronous consensu,” in _Proceedings of the ACM workshop on Privacy in the electronic society_ , pp. 81–90, 2012.
  * [14] J. He, L. Cai, and X. Guan, “Preserving data-privacy with added noises: Optimal estimation and privacy analysis,” _IEEE Transactions on Information Theory_ , vol. 64, no. 8, pp. 5677–5690, 2018.
  * [15] Y. Mo and R. M. Murray, “Privacy preserving average consensus,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 2, pp. 753–765, 2016.
  * [16] A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, “On distributed averaging algorithms and quantization effects,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 11, pp. 2506–2517, 2009.
  * [17] G. Shi, B. D. Anderson, and U. Helmke, “Network flows that solve linear equations,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 2, pp. 2659–2674, 2017.
  * [18] S. Mou, J. Liu and A. S. Morse, “A Distributed Algorithm for Solving a Linear Algebraic Equation,” _IEEE Transactions on Automatic Control_ , vol.60, no.11, pp. 2863-2878, 2015.
  * [19] S. S. Vempala, R. Wang, and D. P. Woodruff, “The communication complexity of optimization,” in _Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics_ , pp. 1733-1752, 2020.
  * [20] A. Nedic, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus and optimization in multi-agent networks,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 4, pp. 922–938, 2010.
  * [21] J. Konečnỳ, B. McMahan, and D. Ramage, “Federated optimization: Distributed optimization beyond the datacenter,” _arXiv preprint arXiv:1511.03575_ , 2015.
  * [22] G. Shi, B. D. O. Anderson, and K. H. Johansson, “Consensus over random graph processes: Network Borel–Cantelli lemmas for almost sure convergence,” _IEEE Transactions on Information Theory_ , vol. 61, no. 10, pp. 5690–5707, 2015.
  * [23] O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao, “Optimal distributed online prediction using mini-batches,” _The Journal of Machine Learning Research_ , vol. 13, no. 1, pp. 165–202, 2012.
  * [24] K. Scaman, F. Bach, S. Bubeck, Y. Lee, and L. Massoulié, “Optimal convergence rates for convex distributed optimization in networks,” _The Journal of Machine Learning Research_ , vol. 20, pp. 1–31, 2019.
  * [25] L. N. Jerome and J. P. George, “Differentially private filtering,” _IEEE Transactions on Automatic Control_ , vol. 59, no. 2, pp. 341–354, 2014.
  * [26] Y. Kawano and M. Cao, “Design of privacy-preserving dynamic controllers,” _IEEE Transactions on Automatic Control_ , 2020.
  * [27] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , pp. 308–318, 2016\.
  * [28] E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design”, _Automatica_ , vol. 81, pp. 221–231, 2017.
  * [29] J. He, L. Cai, and X. Guan “Differential private noise adding mechanism and its application on consensus algorithm”, _IEEE Transactions on Signal Processing_ , vol. 68, pp. 4069–4082, 2020.
  * [30] S. Han, U. Topcu, and G. J. Pappas, “Differentially private distributed constrained optimization,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 1, pp. 50–64, 2016.
  * [31] Y. Liu, J. Wu, I. Manchester, and G. Shi, “Gossip algorithms that preserve privacy for distributed computation part i: The algorithms and convergence conditions,” in _Proceedings of IEEE Conference on Decision and Control_ , pp. 4499–4504, 2018.
  * [32] D. Kempe, A. Dobra, and G. Johannes, “Gossip-based computation of aggregate information,” in _Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science_ , pp. 1–10, 2003.
  * [33] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” _IEEE Transactions on Information Theory_ , vol. 52, no. 6, pp. 2508–2530, 2006.
  * [34] F. Hanzely, J. Konečnỳ, N. Loizou, P. Richtárik, and D. Grishchenko, “Privacy preserving randomized gossip algorithms,” _arXiv preprint arXiv:1706.07636_ , 2017.
  * [35] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev, “Distributed differential privacy via shuffling,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pp. 375–403, 2019.
  * [36] V. Balcer, A. Cheu, M. Joseph, and J. Mao, “Connecting robust shuffle privacy and pan-privacy,” _arXiv preprint arXiv:2004.09481_ , 2020.
  * [37] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _arXiv preprint arXiv:1912.04977_ , 2019.
  * [38] J. Menezes Alfred, C. van Oorschot Paul, and A. Vanstone Scott, _Handbook of Applied Cryptography_ , CRC Press, 1996.
  * [39] M. Bellare, A. Boldyreva, K. Kurosawa, and J. Staddon, “Multirecipient encryption schemes: How to save on bandwidth and computation without sacrificing security,” _IEEE Transactions on Information Theory_ , vol. 53, no. 11, pp. 3927–3943, 2007.
  * [40] B. Mirzasoleiman, M. Zadimoghaddam, and A. Karbasi, “Fast distributed submodular cover: Public-private data summarization,” _Advances in Neural Information Processing Systems_ , vol. 29, pp. 3594–3602, 2016.
  * [41] F. Chierichetti, A. Epasto, R. Kumar, S. Lattanzi, and V. Mirrokni, “Efficient algorithms for public-private social networks,” in _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 139–148, 2015.
  * [42] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [43] M. Fréchet, “Généralisation du théoreme des probabilités totales,” _Fundamenta Mathematicae_ , vol. 1, no. 25, pp. 379–387, 1935\.