# Dynamics-Based Algorithm-Level Privacy Preservation for Push-Sum Average
Consensus

Huqiang Cheng, Xiaofeng Liao, and Huaqing Li H. Cheng and X. Liao are with Key
Laboratory of Dependable Services Computing in Cyber Physical Society-Ministry
of Education, College of Computer Science, Chongqing University, Chongqing,
China, 400044. E-mail<EMAIL_ADDRESS>xfliao@cqu.edu.cn._(Corresponding
author: Xiaofeng Liao.)_ H. Li is with Chongqing Key Laboratory of Nonlinear
Circuits and Intelligent Information Processing, College of Electronic and
Information Engineering, Southwest University, Chongqing, China, 400715.
E-mail<EMAIL_ADDRESS>
###### Abstract

Average consensus is essential for multi-agent systems to achieve specific
functions and is widely used in network control, information fusion, etc. In
conventional average consensus algorithms, all agents reach an agreement by
individual calculations and sharing information with their respective
neighbors. Nevertheless, the information interactions that occur in the
communication network may make privacy information be revealed. In this paper,
we develop a new privacy-preserving average consensus method for unbalanced
digraphs. Specifically, we ensure privacy preservation by carefully embedding
randomness in mixing weights to confuse communications and introducing an
extra auxiliary parameter to mask the state-updated rule in initial several
iterations. In parallel, we exploit the intrinsic robustness of consensus
dynamics to guarantee that the average consensus is precisely achieved.
Theoretical results demonstrate that the designed algorithms can converge
linearly to the exact average consensus value and can guarantee privacy
preservation of agents against both honest-but-curious and eavesdropping
attacks. The designed algorithms are fundamentally different compared to
differential privacy based algorithms that enable privacy preservation via
sacrificing consensus performance. Finally, numerical experiments validate the
correctness of the theoretical findings.

###### Index Terms:

Average consensus, privacy preservation, push-sum, unbalanced digraph.

##  I Introduction

As is known to all, multi-agent systems are growing rapidly in many fields
such as smart grid, smart transportation, and blockchain, etc. An important
feature of such systems is that the agents collaborate with each other to
reach a consensus. To achieve this, the average consensus algorithm has
emerged. Considering a network with $N$ agents, the objective of such
algorithms is to make the states of all agents converge asymptotically to the
average of their initial values.

Averaging consensus is an essential ingredient in decentralized networks.
Typical applications include network control [1], data fusion [2, 3], UAV
formation [4], etc. In order to make all agents’ states reach the average of
initial values, most of average consensus methods always demand that agents
share their correct states with each other. This may result in privacy
information being revealed, and it is highly inadvisable from the perspective
of privacy protection. Indeed, privacy protection is critical in numerous
distributed collaboration applications, such as smart grids, sensor networks,
banking and medical systems. This is necessary to encourage participation in
collaboration, as agents are often unwilling to sacrifice their privacy for
favorable performance. A simple example is a group of individuals engaging in
a discussion regarding a specific topic and reaching a common view while
maintaining the confidentiality of each individual view [5]. A further common
example is in power systems where several generators need to agree on costs as
well as ensuring the confidentiality of their respective generation
information [6]. As the frequency of privacy breaches continues to rise, it
has become increasingly urgent to safeguard the privacy of every individual in
distributed systems.

###  I-A Related Works

Several algorithms have been available to tackle the growing privacy concerns
in average consensus. One of the mostly widespread non-encryption privacy-
preserving techniques is differential privacy.[7], which essentially injects
uncorrelated noise to the transmitted state information. This technique has
already been applied in some algorithms [8, 9, 10, 11, 12]. However, such
algorithms cannot achieve exact average consensus owing to its inherent
compromise between the privacy level and the consensus performance. This makes
differential privacy algorithms unpalatable for sensor networks and cyber-
physical systems with high requirements for consensus accuracy. To address the
loss in consensus accuracy, some enhancement works [13, 14, 15] based on
differential privacy algorithms were proposed by judiciously adding the
correlated noise.

Yet, the above mentioned algorithm is only valid for undirected and balanced
networks. In real-world scenarios, communication among agents is usually
directed and unbalanced. For example, broadcasting at different power levels,
the communication activity corresponds to a directed and unbalanced graph. For
privacy issues in unbalanced digraph, Altafini [16] used appropriate hiding
maps to preserve the real values. Several observability-based methods [17, 18,
19] have also been developed, and their basic idea is to minimize the
observability information of the compromised nodes by designing an appropriate
network topology. Using homomorphic encryption techniques, the authors in [20,
21, 22, 23] proposed a series of encryption-based algorithms. However, this
type of method requires substantial computational and communication overhead,
which is unfriendly to resource-limited systems. Recently, state-decomposition
based methods [24, 25] have been favored by researchers. The idea of such
algorithms is to divide the states of agents into two sub-states with one
containing insignificant information for communication with other agents and
the other containing sensitive information only for internal information
exchange. Another extension of privacy-preserving consensus is dynamics-based
methods [26, 27, 28], which is also the focus of this paper. An important
benefit of such algorithms is that no trade-off exists between privacy and
consensus performances, and they are easy to implement in conjunction with
techniques like homomorphic encryption, differential privacy, etc. Note that,
in contrast to state-decomposition based methods, dynamics-based methods have
a simpler structure and seem easier to much understand and implement.

###  I-B Main Contributions

In this paper, our work contributes to enrich the dynamic-based privacy-
preserving methods over unbalanced directed networks. Specifically, the
contributions contain the points listed next.

  1. I)

Based on the conventional push-sum algorithm, we design a novel push-sum
algorithm enabling privacy preservation. Specifically, during the initial
several iterations, we ensure privacy preservation by carefully embedding
randomness in mixing weights to confuse communications and introducing an
extra auxiliary parameter to mask the state-updated rule. As well, to ensure
consensus accuracy, exploiting the intrinsic robustness of consensus dynamics
to cope with uncertain changes in information exchanges, we carefully redesign
the push-sum protocol so that the “total mass” of the system is invariant in
the presence of embedded randomness.

  2. II)

We provide a formal and rigorous analysis of convergence rate. Specifically,
our analysis consists two parts. One is to analyze the consensus performance
of the initial several iterations with randomness embedded, and the other is
to analyze that of remaining randomness-free dynamics, which has the same
structure as the conventional push-sum method [29, 30]. Our analysis exploits
the properties of the mixing matrix product and norm relations to build
consensus contractions of each dynamic. The result shows that the designed
algorithm attains a linear convergence rate and explicitly captures the effect
of mixing matrix and network connectivity structure on convergence rate.

  3. III)

Relaxing the privacy notion of considering only exact initial values in [15,
32, 33, 34], we present two new privacy notions for honest-but-curious attacks
and eavesdropping attacks (see Definition 3), respectively, where the basic
idea is that the attacker has an infinite number of uncertainties in the
estimation of the initial value through the available information. The privacy
notions are more generalized in the context that the attacker is not only
unable to determine the exact initial value but also the valid range of the
initial value.

  4. IV)

Last but not least, this paper presents a version of the privacy-preserving
algorithm in the vector-state case, which has rarely been discussed in
existing works. Of course, we also briefly discuss its convergence and privacy
properties.

_Notations:_ $\mathbb{R}$ and $\mathbb{N}$ are the natural and real number
sets, respectively. $\mathbf{0}$, $\mathbf{1}$, and $\mathbf{I}$ represent
all-zero vector, all-one vector, and identity matrix, respectively, whose
dimensions are clear from context. For any matrix $\mathbf{A}$, its $ij$-th
element is denoted by $A_{ij}$. Let $\left|\mathcal{S}\right|$ be the
cardinality of set $\mathcal{S}$. $\otimes$ denotes the Kronecker product. The
$\ell_{2}$-norm (resp. $\ell_{1}$-norm) is signified by $\lVert\cdot\rVert$
(resp. $\lVert\cdot\rVert_{1}$).

##  II Preliminaries

We recall several important properties and concepts associated with the graph
theory, conventional push-sum protocol, and privacy preservation.

###  II-A Graph Theory

Consider a network consisting of $N$ agents and it is modeled as a digraph
$\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right)$, where
$\mathcal{V}=\left\\{1,\cdots,N\right\\}$ is the agent set, and $\mathcal{E}$
is the edge set which comprises of pairs of agents and characterizes the
interactions between agents, i.e., agent $i$ affects the dynamics of agent $j$
if a directed line from $i$ to $j$ exists, expressed as
$\left(j,i\right)\in\mathcal{E}$. Moreover, let
$\left(i,i\right)\notin\mathcal{E}$ for any $i\in\mathcal{V}$, i.e., no self-
loop exists in digraph. We let
$\mathcal{N}_{i}^{\text{in}}=\left\\{j\left|\left(i,j\right)\in\mathcal{E}\right.\right\\}$
and
$\mathcal{N}_{i}^{\text{out}}=\left\\{j\left|\left(j,i\right)\in\mathcal{E}\right.\right\\}$
be the in-neighbor and out-neighbor sets of agent $i$, respectively. Notice
that the senses of $j\in\mathcal{N}_{i}^{\text{out}}$ and
$i\in\mathcal{N}_{j}^{\text{in}}$ are equivalent. For $i,j\in\mathcal{V}$, a
trail from $i$ to $j$ is a chain of consecutively directed lines. The digraph
$\mathcal{G}$ is _strongly connected_ if at least one trail lies between any
pair of agents. The associated incidence matrix
$\mathbf{R}=\left[R_{i\varepsilon_{j}}\right]_{N\times\left|\mathcal{E}\right|}$
for graph $\mathcal{G}$ is given by

$\displaystyle R_{ie}=\begin{cases}1,&\text{if the starting point of
the}\,\,e\text{-th}\,\,\text{edge}\,\,(i,j)\,\,\text{is}\,\,j;\\\ -1,&\text{if
the starting point of
the}\,\,e\text{-th}\,\,\text{edge}\,\,(i,j)\,\,\text{is}\,\,i;\\\
0,&\text{otherwise}.\\\ \end{cases}$

One could readily check that the sum of each column of $\mathbf{R}$ is zero,
i.e., $\sum\nolimits_{i=1}^{N}{R_{il}}=0$.

######  Assumption 1.

The directed network $\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right)$ is
strongly connected, and the set $\mathcal{V}$ contains $N$ agents with $N>2$.

###  II-B Conventional Push-Sum Method

Regarding the investigation of average consensus, the push-sum algorithm [29,
30] is a well-established protocol, which is summarized in Algorithm 1. All
agents simultaneously update two variable states: $x_{i}\left(k\right)$ and
$y_{i}\left(k\right)$, and the sensitive information of agent $i$ is the
initial value $x_{i}\left(0\right)$.

Algorithm 1 Push-Sum Algorithm

1: Initial setting: Set $x_{i}\left(0\right)=z_{i}\left(0\right)=x_{i}^{0}$
and $y_{i}\left(0\right)=1$ for $i\in\mathcal{V}$. The mixing weight
associated with any edge $\left(j,i\right)\in\mathcal{E}$ is indicated as
$C_{ji}$. Let $C_{ji}\in\left(0,1\right)$ if
$j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}$ and $C_{ji}=0$
otherwise. Besides, $\sum\nolimits_{j=1}^{N}{C_{ji}}=1$ for $i\in\mathcal{V}$.

2: for $k=0,1,\cdots$ do

3: Agent $i$ sends the computed $C_{li}x_{i}\left(k\right)$ and
$C_{li}y_{i}\left(k\right)$ to $l\in\mathcal{N}_{i}^{\text{out}}$.

4: Agent $i$ uses $C_{ij}x_{j}\left(k\right)$ and $C_{ij}y_{j}\left(k\right)$
received from $j\in\mathcal{N}_{i}^{\text{in}}$ to update $x_{i}$ and $y_{i}$
as follows:  $\displaystyle
x_{i}\left(k+1\right)=\sum_{j\in\mathcal{N}_{i}^{\text{in}}\cup\left\\{i\right\\}}{C_{ij}x_{j}\left(k\right)},$
(1) $\displaystyle
y_{i}\left(k+1\right)=\sum_{j\in\mathcal{N}_{i}^{\text{in}}\cup\left\\{i\right\\}}{C_{ij}y_{j}\left(k\right)},$
(2)

5: Agent $i$ computes
$z_{i}\left(k+1\right)=x_{i}\left(k+1\right)/y_{i}\left(k+1\right)$.

6: Until a stopping criteria is satisfied, e.g., agent $i$ stops if
$\left|z_{i}\left(k+1\right)-\bar{x}^{0}\right|<\epsilon$ for some predefined
$\epsilon>0$, where
$\bar{x}^{0}\triangleq\sum\nolimits_{j=1}^{N}{x_{j}\left(0\right)}/N$.

7: end for

Define
$\mathbf{x}\left(k\right)=\left[x_{1}\left(k\right),\cdots,x_{N}\left(k\right)\right]^{\top}$,
$\mathbf{y}\left(k\right)=\left[y_{1}\left(k\right),\cdots,y_{N}\left(k\right)\right]^{\top}$,
and $\mathbf{C}=\left[C_{ij}\right]_{N\times N}$. We can rewrite (1) and (2)
as

$\displaystyle\mathbf{x}\left(k+1\right)=\mathbf{Cx}\left(k\right),$ (3)
$\displaystyle\mathbf{y}\left(k+1\right)=\mathbf{Cy}\left(k\right),$ (4)

initialized with
$\mathbf{x}\left(0\right)=\left[x_{1}^{0},\cdots,x_{N}^{0}\right]^{\top}$ and
$\mathbf{y}\left(0\right)=\mathbf{1}$. For the setting of mixing weights
$\left\\{C_{ij}\left|i,j\in\mathcal{V}\right.\right\\}$ in Algorithm 1, we can
easily know that $\mathbf{C}$ is column-stochastic.

Under Assumption 1, $\mathbf{C}^{k}$ converges to rank-$1$ matrix at an
exponential rate [37, 38]. Let $\mathbf{C}^{\infty}$ be the infinite power of
matrix $\mathbf{C}$, i.e.,
$\mathbf{C}^{\infty}=\lim_{k\rightarrow\infty}\,\,\mathbf{C}^{k}$. Applying
the Perron-Frobenius theorem [39] gives
$\mathbf{C}^{\infty}=\bm{\pi}\mathbf{1}^{\top}$, where
$\bm{\pi}=\left[\pi_{1},\cdots,\pi_{N}\right]^{\top}$. Using facts that
$\mathbf{x}\left(k\right)=\mathbf{C}^{k}\mathbf{x}\left(0\right)$ and
$\mathbf{y}\left(k\right)=\mathbf{C}^{k}\mathbf{y}\left(0\right)$, we have

$\displaystyle\underset{k\rightarrow\infty}{\lim}\,\,z_{i}\left(k\right)$
$\displaystyle=\underset{k\rightarrow\infty}{\lim}\,\,\frac{x_{i}\left(k\right)}{y_{i}\left(k\right)}=\frac{\left[\mathbf{C}^{\infty}\mathbf{x}\left(0\right)\right]_{i}}{\left[\mathbf{C}^{\infty}\mathbf{y}\left(0\right)\right]_{i}}$
$\displaystyle=\frac{\pi_{i}\sum\nolimits_{j=1}^{N}{x_{j}\left(0\right)}}{\pi_{i}\sum\nolimits_{j=1}^{N}{y_{j}\left(0\right)}}=\frac{\sum\nolimits_{j=1}^{N}{x_{j}\left(0\right)}}{N},$
(5)

where $\left[\cdot\right]_{i}$ means the $i$-th element of
$\left[\cdot\right]$. Therefore, the ratio $z_{i}\left(k\right)$ gradually
reaches to $\bar{x}^{0}$. See [29, 30, 31] for more details.

###  II-C Privacy Concern

We first introduce two prevalent attack types, namely, honest-but-curious
attacks and eavesdropping attacks, and then explain that Algorithm 1 fails to
preserve privacy due to the explicit sharing of state variables.

######  Definition 1.

An honest-but-curious attack is an attack in which some agents, who follow the
state-update protocols properly, try to infer the initial values of other
agents by using the received information.

######  Definition 2.

An eavesdropping attack is an attack in which an external eavesdropper is able
to capture all sharing information by wiretapping communication channels so as
to infer the private information about sending agents.

In general, in terms of information leakage, an eavesdropping attack is more
devastating than an honest-but-curious attack as it can capture all
transmitted information, while the latter can only access the received
information. Yet, the latter has the advantage that the initial values
$\left\\{x_{j}^{0}\right\\}$ of all honest-but-curious agents $j$ are
accessible, which are unavailable to the external eavesdroppers.

For the average consensus, the sensitive information to be protected is the
initial value $x_{i}\left(0\right)$, $i\in\mathcal{V}$. Recall that at the
first iteration, agent $i$ will send the computed values
$C_{ji}x_{i}\left(0\right)$ and $C_{ji}y_{i}\left(0\right)$ to all of its out-
neighbors $j\in\mathcal{N}_{i}^{\text{out}}$. Then, the initial value
$x_{i}\left(0\right)$ is uniquely inferable by the honest-but-curious agent
$j$ using
$x_{i}\left(0\right)=\frac{C_{ij}x_{i}\left(0\right)}{C_{ij}y_{i}\left(0\right)}$
and $y_{i}\left(0\right)=1$. Therefore, the honest-but-curious agents are
always able to infer the sensitive information of its in-neighbors. Likewise,
one can readily check that external eavesdroppers are also able to easily
infer sensitive information about all agents. Therefore, the privacy concern
is not addressed in the conventional push-sum method. In this work, we try to
study the privacy concern and develop a privacy-preserving version of
Algorithm 1 to achieve exact average consensus.

###  II-D Performance Metric

Our task is to propose an average consensus algorithm that can achieve exact
convergence while guaranteeing privacy security. According to the above
discussion, we thus conclude that the following two requirements for privacy-
preserving push-sum algorithms must be satisfied.

  1. i)

Exact output: After the last iteration of the algorithm, each agent should
converge to the average consensus point $\bar{x}^{0}$.

  2. ii)

Privacy preservation: During the entire algorithm implementation, the private
information, i.e., the initial value $x_{i}^{0}$, of each legitimate agent $i$
should be preserved against both honest-but-curious and eavesdropping attacks.

In order to respond to the above two requirements, two metrics are required to
quantify them.

Output metric: To measure the accuracy of the output, we adopt the consensus
error $\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert$. The
algorithm achieves exact consensus if
$\lim_{k\rightarrow\infty}\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert=0$.
Furthermore, the algorithm is said to be _elegant_ if
$\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert=\mathcal{O}(\rho^{k})$,
$\rho\in\left(0,1\right)$.

Privacy metric: For the honest-but-curious attacks, we consider the presence
of some honest-but-curious agents $\mathcal{H}$. The accessible information
set of $\mathcal{H}$ is represented as
$\mathcal{I}_{h}\left(k\right)=\left\\{\mathcal{I}_{j}\left(k\right)\left|j\in\mathcal{H}\right.\right\\}$,
where $\mathcal{I}_{j}\left(k\right)$ represents the information available to
agent $j\in\mathcal{H}$ at iteration $k$. Given a moment
$k^{\prime}\in\mathbb{N}$, the access information of agents $\mathcal{H}$ in
time period $0-k$ is $\mathcal{I}_{h}\left(0:k^{\prime}\right)=\cup_{0\leq
k\leq k^{\prime}}\mathcal{I}_{h}\left(k\right)$. For any information sequence
$\mathcal{I}_{h}\left(0:k^{\prime}\right)$, define $\mathcal{S}_{0}^{i}$ as
the set of all possible initial values at the legitimate agent $i$, where all
initial values leave the information accessed by agents $\mathcal{H}$
unchanged. That is to say, there exist any two initial values
$x_{i}^{0},\tilde{x}_{i}^{0}\in\mathcal{S}_{0}^{i}$ with
$x_{i}^{0}\neq\tilde{x}_{i}^{0}$ such that
$\tilde{\mathcal{I}}_{h}\left(0:k^{\prime}\right)=\mathcal{I}_{h}\left(0:k^{\prime}\right)$.
The diameter of $\mathcal{S}_{0}^{i}$ is defined as

$\displaystyle\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)=\underset{x_{i}\left(0\right),\tilde{x}_{i}\left(0\right)\in\mathcal{S}_{0}^{i}}{\text{sup}}\left|x_{i}\left(0\right)-\tilde{x}_{i}\left(0\right)\right|.$

For the eavesdropping attacks, we consider the presence of an external
eavesdropper whose available information is denoted as
$\mathcal{I}_{e}\left(k\right)$, $k\in\mathbb{N}$. Let
$\mathcal{I}_{e}\left(0:k^{\prime}\right)=\cup_{0\leq k\leq
k^{\prime}}\mathcal{I}_{e}\left(k\right)$. Similar to the honest-but-curious
attacks, we define $\mathcal{S}_{0}$ as the set of all possible initial values
for all agents, where all initial values leave the information accessed by an
external eavesdropper unchanged. That is, there exist
$\mathbf{x}\left(0\right),\mathbf{\tilde{x}}\left(0\right)\in\mathcal{S}_{0}$
with $\mathbf{x}\left(0\right)\neq\mathbf{\tilde{x}}\left(0\right)$ such that
$\mathcal{I}_{e}\left(k\right)=\tilde{\mathcal{I}}_{e}\left(k\right)$. In
addition, the diameter of $\mathcal{S}_{0}$ is given as

$\displaystyle\mathbf{D}\left(\mathcal{S}_{0}\right)=\underset{\mathbf{x}\left(0\right),\mathbf{\tilde{x}}\left(0\right)\in\mathcal{S}_{0}}{\text{sup}}\lVert\mathbf{x}\left(0\right)-\mathbf{\tilde{x}}\left(0\right)\rVert.$

For the honest-but-curious and eavesdropping attacks, we use
$\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)$ for all legitimate agents
$i\in\mathcal{V}\setminus\mathcal{H}$ and
$\mathbf{D}\left(\mathcal{S}_{0}\right)$ for all agents to measure the
individual privacy and algorithm-level confidentiality, respectively. For more
details, see the definition below.

######  Definition 3.

The algorithm is said to be elegant in terms of privacy preservation, if
$\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)=\infty$ or
$\mathbf{D}\left(\mathcal{S}_{0}\right)=\infty$ for any information sequence
$\mathcal{I}_{h}\left(0:k^{\prime}\right)$ or
$\mathcal{I}_{e}\left(0:k^{\prime}\right)$, $k^{\prime}\in\mathbb{N}$,
respectively.

The privacy notion in Definition 3 is similar to the one in $l$-diversity
[36], in which the diversity of any privacy information is measured by the
amount of different estimates for the information. Greater diversity means
greater uncertainty about privacy information. In our setting, the privacy
information is the initial value $x_{i}^{0}$ (resp.
$\mathbf{x}\left(0\right)$), whose diversity is measured by the diameter
$\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)$ (resp.
$\mathbf{D}\left(\mathcal{S}_{0}\right)$). Larger diameters imply greater
uncertainty in the estimation of the initial values.

######  Remark 1.

Note that Definition 3 indicates that attackers cannot uniquely determine an
exact value or even a valuable range of $x_{i}^{0}$, and hence is more
stringent than the notion defined in [32, 33, 34], which only considers the
privacy information not to be exactly inferred.

##  III Privacy-Preserving Push-Sum Algorithm

According to the above analysis, one can know that adopting the same weight
$C_{ij}$ for both $C_{ij}x_{i}\left(0\right)$ and $C_{ij}y_{i}\left(0\right)$
cause privacy (i.e., initial values) leakage. To solve the issue, the work
[26] introduces the following weight generation mechanism in the framework of
Algorithm 1 and thus develops a privacy-preserving push-sum algorithm.

Protocol 1 Weight generation mechanism

1: Required parameters: Parameters $K\in\mathbb{N}$ and
$\eta\in\left(0,1\right)$ are known to each agent.

2: Two sets of tailored mixing weights associated with any edge
$\left(j,i\right)\\!\in\\!\mathcal{E}$ are generated. Specifically, if
$k\\!\leq\\!K$, two groups of mixing weights
$\left\\{\\!C_{ji}^{1}\\!\left(k\right)\\!\in\\!\mathbb{R}\left|\\!\,\,j\\!\in\\!\mathcal{N}_{i}^{\text{out}}\\!\cup\\!\left\\{i\right\\}\right.\\!\right\\}$
and
$\left\\{\\!C_{ji}^{2}\left(k\right)\\!\in\\!\mathbb{R}\left|\\!\,\,j\\!\in\\!\mathcal{N}_{i}^{\text{out}}\\!\cup\\!\left\\{i\right\\}\right.\\!\right\\}$
associated with agent $i$ are generated, which satisfy
$\sum\nolimits_{j=1}^{N}{C_{ji}^{1}\left(k\right)}=1$ and
$\sum\nolimits_{j=1}^{N}{C_{ji}^{2}\left(k\right)}=1$; otherwise, only one
group of mixing weights
$\left\\{C_{ji}^{1}\left(k\right)=C_{ji}^{2}\left(k\right)\in\left(\eta,1\right)\left|\,\,j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}\right.\right\\}$,
also subject to the sum $1$ condition, is generated. Note that
$\left\\{C_{ji}^{1}\left(k\right)\right\\}$ and
$\left\\{C_{ji}^{2}\left(k\right)\right\\}$ are mixed in $x_{i}$ and $y_{i}$,
respectively. Moreover, agent $i$ always sets $C_{ji}^{1}\left(k\right)=0$ and
$C_{ji}^{2}\left(k\right)=0$ for
$j\notin\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}$.

Fig. 1 briefly depicts the basic process of the algorithm [26]. Obviously, the
difference between the method [26] and the conventional push-sum algorithm
lies only in the computation of the first $K$ steps. For the network in Fig.
1(b), assume that $x_{1}^{0}=a$, $x_{2}^{0}=b$, and $x_{3}^{0}=c$. The weight
generation mechanism is to make
$\mathbf{C}_{1}\left(k\right)\neq\mathbf{C}_{2}\left(k\right)$ for $k\leq K$,
and thus make it impossible for honest-but-curious agents to infer
$x_{i}\left(0\right)$ when running the push-sum algorithm (i.e., Algorithm 1).
In the first $K$-step dynamic calculations, one has
$x_{1}^{0}=a^{{}^{\prime}}$, $x_{2}^{0}=b^{{}^{\prime}}$, and
$x_{3}^{0}=c^{{}^{\prime}}$. Since the normal push-sum algorithm is executed
after the $K$-step calculations, it is necessary to have
$a+b+c=a^{{}^{\prime}}+b^{{}^{\prime}}+c^{{}^{\prime}}$ to ensure convergence
to the exact consensus point. To put it simply, the $K$-step dynamics can be
regarded as a re-initialization operation on the initial value.

(a) A simple graph of $3$ agents

(b) A brief computation process

Figure 1: The idea of the method [26].

The method in [26] has been proved to reach an exact consensus point, and the
sensitive information of legitimate agents is not inferred by honest-but-
curious agents. However, there are three significant challenges that have not
been addressed in the work [26].

  1. 1)

In the initial $K$ iterations, although each weight is arbitrary, the sum $1$
condition still imposes a constraint on the weight setting.

  2. 2)

The method in [26] requires the use of other techniques, such as homomorphic
encryption, to safeguard sensitive information from being captured by external
eavesdroppers.

  3. 3)

The work [26] only proves that the algorithm can converge exactly to the
consensus point, but does not provide a specific convergence rate.

To solve the above problems, we carefully redesign the push-sum rule to
address challenges 1) and 2), whereas Challenge 3) is addressed in Section IV.
From [26], we can know that the dynamics-based privacy-preserving algorithm
mainly operates on the first $K$ iterations to preserve the privacy
information. Hence, the following exposition is for the case $k\leq K$. Recall
the update rule of the $x$-variable in [26],

$\displaystyle
x_{i}\left(k+1\right)=\sum_{j\in\mathcal{N}_{i}^{\text{in}}\cup\left\\{i\right\\}}{C_{ij}^{1}\left(k\right)x_{j}\left(k\right)},$

where $C_{ij}^{1}\left(k\right)$ is generated from Protocol 1. Note that the
sum $1$ condition is used to ensure that the sum of all variables at each
$k\leq K$ is invariant, that is,

$\displaystyle\sum_{i=1}^{N}{x_{i}\left(k+1\right)}=\sum_{i=1}^{N}{x_{i}\left(k\right)}.$
(6)

Thus, if we wish to circumvent this restriction, the new update rule must make
(6) hold. Specifically, we take advantage of the fact that the amount of
messages sent and received is equal for the entire system (i.e., the total
mass of the system is fixed) and modify the update of the $x$-variable as

$\displaystyle
x_{i}\left(k+1\right)=x_{i}\left(k\right)+\varXi_{i}\left(k\right)$ (7)

with

$\varXi_{i}\left(k\right)\\!\triangleq\\!\sum_{j\in\mathcal{N}_{i}^{\text{in}}}{C_{ij}^{1}\left(k\right)x_{j}\left(k\right)}\\!-\\!\sum_{j\in\mathcal{N}_{i}^{\text{out}}}{C_{ji}^{1}\left(k\right)x_{i}\left(k\right)},$

where $C_{ij}^{1}\left(k\right)$ is generated via Protocol 1, but it does not
have to satisfy the sum $1$ condition. It holds
$\sum\nolimits_{i=1}^{N}{\varXi_{i}\left(k\right)}=0$. Obviously, summing
$x_{i}\left(k+1\right)$ in (7) over $i=1,\cdots,N$ yields (6). However, the
update rule (7) is valid for honest-but-curious attacks and really ineffective
for eavesdropping attacks, see Corollary 2 below. Thus, we further introduce
an auxiliary parameter $\sigma\left(k\right)\in\mathbb{R}$ for $k\leq K$,
which is public information known for all agents, but not to the external
eavesdropper. Details of our method are summarized in Algorithm 2.

Algorithm 2 Secure average consensus algorithm

1: Initial setting: Set $x_{i}\left(0\right)=z_{i}\left(0\right)=x_{i}^{0}$
and $y_{i}\left(0\right)=1$ for $i\in\mathcal{V}$. Parameters
$K\in\mathbb{N}$, $\sigma\left(k\right)\in\mathbb{R}$ for $k\in\mathbb{N}$,
and $\eta\in\left(0,1\right)$ are known to each agent.

2: Weight generation: Two sets of random mixing weights associated with any
edge $\left(j,i\right)\in\mathcal{E}$ are generated. One is for $y_{i}$, and
the other is for $x_{i}$. Specifically, for $y_{i}\left(k\right)$ at any
$k\in\mathbb{N}$, a group of mixing weights
$\left\\{C_{ji}^{2}\left(k\right)\in\left(\eta,1\right)\left|j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}\right.\right\\}$
associated with agent $i$ are generated, which satisfy
$\sum\nolimits_{j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}}^{\,\,}{C_{ji}^{2}\left(k\right)}=1$.
For $x_{i}\left(k\right)$ at any $k\in\mathbb{N}$, if $k\leq K$, a group of
mixing weights
$\left\\{C_{ji}^{1}\left(k\right)\in\mathbb{R}\left|\,\,j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}\right.\right\\}$
associated with agent $i$ are generated; Otherwise, a group of mixing weights
$\left\\{C_{ji}^{1}\left(k\right)=C_{ji}^{2}\left(k\right)\in\left(\eta,1\right)\left|j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}\right.\right\\}$
associated with agent $i$ are generated. Moreover, agent $i$ always sets
$C_{ji}^{1}\left(k\right)=0$ and $C_{ji}^{2}\left(k\right)=0$ for
$j\notin\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}$.

3: for $k=0,1,\cdots$ do

4: Agent $i$ sends the computed $C_{li}^{1}\left(k\right)x_{i}\left(k\right)$
and $C_{li}^{2}\left(k\right)y_{i}\left(k\right)$ to
$l\in\mathcal{N}_{i}^{\text{out}}$.

5: Agent $i$ uses $C_{ij}^{1}\left(k\right)x_{j}\left(k\right)$ and
$C_{ij}^{2}\left(k\right)y_{j}\left(k\right)$ received from
$j\in\mathcal{N}_{i}^{\text{in}}$ to update $x_{i}$ and $y_{i}$ as follows:
$\displaystyle
x_{i}\left(k+1\right)\\!=\\!\begin{cases}x_{i}\left(k\right)\\!+\\!\sigma\left(k\right)\varXi_{i}\left(k\right),&\text{if}\,\,k\leq
K;\\\
\underset{j\in\mathcal{N}_{i}^{\text{in}}\cup\\{i\\}}{\sum}C_{ij}^{1}\left(k\right)x_{j}\left(k\right),&\text{if}\,\,k\geq
K+1.\\\ \end{cases}$ (8) $\displaystyle
y_{i}\left(k+1\right)=\underset{j\in\mathcal{N}_{i}^{\text{in}}\cup\\{i\\}}{\sum}C_{ij}^{2}\left(k\right)y_{j}\left(k\right),k\geq
0.$ (9)

6: Agent $i$ computes
$z_{i}\left(k+1\right)=x_{i}\left(k+1\right)/y_{i}\left(k+1\right)$.

7: Until a stopping criteria is satisfied, e.g., agent $i$ stops if
$\left|z_{i}\left(k+1\right)-\bar{x}^{0}\right|<\epsilon$ for some predefined
$\epsilon>0$.

8: end for

######  Remark 2.

Note that we mainly embed randomness for $\mathbf{C}_{1}\left(k\right)$ in the
first $K$ iterations and do not consider $\mathbf{C}_{2}\left(k\right)$. This
is another difference from the method [26], which embeds independent
randomness for both $\mathbf{C}_{1}\left(k\right)$ and
$\mathbf{C}_{2}\left(k\right)$ in the first $K$ iterations. In fact, embedding
randomness for $\mathbf{C}_{1}\left(k\right)$ alone can guarantee that
$\mathbf{C}_{1}\left(k\right)\neq\mathbf{C}_{2}\left(k\right)$ for $k\leq K$,
and the auxiliary variable $y$ does not contain privacy information, so there
is no need to embed randomness for $\mathbf{C}_{2}\left(k\right)$ either. Of
course, if embedding randomness for $\mathbf{C}_{2}\left(k\right)$ is
necessary, the update of the $y$-variable in (9) is formulated as:

$\displaystyle y_{i}\left(k+1\right)$ $\displaystyle=$ $\displaystyle
y_{i}\left(k\right)\\!+\\!\sigma^{{}^{\prime}}\left(k\right)\left(\sum_{j\in\mathcal{N}_{i}^{\text{in}}}{C_{ij}^{2}\left(k\right)y_{j}\left(k\right)}\\!-\\!\sum_{j\in\mathcal{N}_{i}^{\text{in}}}{C_{ij}^{2}\left(k\right)y_{j}\left(k\right)}\right),$

where $\sigma^{{}^{\prime}}\left(k\right)$ and $C_{ij}^{2}\left(k\right)$ are
generated in a similar way as $\sigma\left(k\right)$ and
$C_{ij}^{1}\left(k\right)$ of Algorithm 2.

##  IV Convergence analysis

Following Algorithm 2, it holds from the dynamics (8)-(9)

$\displaystyle\mathbf{x}\left(k+1\right)=\mathbf{C}_{1}\left(k\right)\mathbf{x}\left(k\right),k\geq
K,$ (10)
$\displaystyle\mathbf{y}\left(k+1\right)=\mathbf{C}_{2}\left(k\right)\mathbf{y}\left(k\right),k\geq
0,$ (11)

where
$\mathbf{C}_{1}\left(k\right)=\left[C_{ij}^{1}\left(k\right)\right]_{N\times
N}$ and
$\mathbf{C}_{2}\left(k\right)=\left[C_{ij}^{2}\left(k\right)\right]_{N\times
N}$. It is known from the setting of Algorithm 2 that: i)
$\mathbf{C}_{1}\left(k\right)$ and $\mathbf{C}_{2}\left(k\right)$ are time-
varying and column-stochastic; and ii)
$\mathbf{C}_{1}\left(k\right)=\mathbf{C}_{2}\left(k\right)$ for $k\geq K$.

Define
$\mathbf{\Phi}_{1}\left(k:s\right)=\mathbf{C}_{1}\left(k\right)\cdots\mathbf{C}_{1}\left(s\right)$
and
$\mathbf{\Phi}_{2}\left(k:s\right)=\mathbf{C}_{2}\left(k\right)\cdots\mathbf{C}_{2}\left(s\right)$
for $k\geq s\geq 0$. Particularly,
$\mathbf{\Phi}_{1}\left(k:k\right)=\mathbf{C}_{1}\left(k\right)$ and
$\mathbf{\Phi}_{2}\left(k:k\right)=\mathbf{C}_{2}\left(k\right)$. Recursively
computing (10) and (11), we can obtain

$\displaystyle\mathbf{x}\left(k+1\right)=\mathbf{\Phi}_{1}\left(k:K+1\right)\mathbf{x}\left(K+1\right),k\geq
K+1,$ (12)
$\displaystyle\mathbf{y}\left(k+1\right)=\mathbf{\Phi}_{2}\left(k:0\right)\mathbf{y}\left(0\right),k\geq
0,$ (13)

where it holds
$\mathbf{\Phi}_{1}\left(k:K+1\right)=\mathbf{\Phi}_{2}\left(k:K+1\right)$ for
$k\geq K+1$. Left-multiplying both sides of (12) and (13) by
$\mathbf{1}^{\top}$ gives

$\displaystyle\mathbf{1}^{\top}\mathbf{x}\left(k+1\right)=\mathbf{1}^{\top}\mathbf{x}\left(K+1\right),k\geq
K+1,$ (14)
$\displaystyle\mathbf{1}^{\top}\mathbf{y}\left(k+1\right)=\mathbf{1}^{\top}\mathbf{y}\left(0\right)=N,k\geq
0,$ (15)

where we use the column stochasticities of
$\mathbf{\Phi}_{1}\left(k:K+1\right)$ and $\mathbf{\Phi}_{2}\left(k:0\right)$.
For the first $K$ dynamics of $x_{i}$ in (8), we have from
$\sum\nolimits_{i=1}^{N}{\varXi_{i}\left(k\right)}=0$ that

$\displaystyle\mathbf{1}^{\top}\mathbf{x}\left(k+1\right)=$
$\displaystyle\sum_{i=1}^{N}{x_{i}\left(k+1\right)}=\sum_{i=1}^{N}{\left(x_{i}\left(k\right)+\sigma\left(k\right)\varXi_{i}\left(k\right)\right)}$
$\displaystyle\,\,=$
$\displaystyle\sum_{i=1}^{N}{x_{i}\left(k\right)}=\mathbf{1}^{\top}\mathbf{x}\left(k\right)=\mathbf{1}^{\top}\mathbf{x}\left(0\right),$
(16)

which matches the relation (6). Combining (14) and (16) gives

$\displaystyle\mathbf{1}^{\top}\mathbf{x}\left(k+1\right)=\mathbf{1}^{\top}\mathbf{x}\left(0\right),k\geq
0.$ (17)

Note that the dynamics of Algorithm 2 for iterations $k\geq K$ are analogous
to the conventional push-sum method. Considering (17) in depth, it can be seen
that the injected randomness of the first $K$ dynamics has no impact on the
consensus performance, i.e.,
$\lim_{k\rightarrow\infty}z_{i}\left(k\right)=\bar{x}^{0}$.

Next we show that Algorithm 2 can guarantee linear convergence rate to
$\bar{x}^{0}$, i.e., for $k\in\mathbb{N}$, it holds
$\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert\leq c\rho^{k}$,
where $c>0$, $\rho\in\left(0,1\right)$, and
$\mathbf{z}\left(k\right)=\left[z_{1}\left(k\right),\cdots,z_{N}\left(k\right)\right]^{\top}$.

######  Theorem 1.

Let $\\{\left(z_{i}\left(k\right)\right)_{i=1}^{N}\\}_{k\in\mathbb{N}}$ be the
sequence generated by Algorithm 2, and the network $\mathcal{G}$ satisfies
Assumption 1. Then, it holds, for all $k\in\mathbb{N}$,

$\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert\leq c\rho^{k},$

where $\rho=\left(1-\eta^{N-1}\right)^{\frac{1}{N-1}}$ and $c$ is a constant
whose expression is provided in (45).

###### Proof.

The detailed proof is available in Appendix A. ∎

######  Remark 3.

Theorem 1 indicates that Algorithm 1 can achieve an $\mathcal{O}(\rho^{k})$
convergence rate with $\rho=(1-\eta^{N-1})^{\frac{1}{N-1}}$. Evidently, a
smaller $\rho$ yields a better convergence rate. A straightforward way to
obtain a smaller $\rho$ is to increase $\eta$. However, it is essential to be
aware that $\eta$ cannot be close to $1$ arbitrarily due to the nonnegativity
and column stochasticity of the mixing matrix for $k\geq K+1$. To satisfy the
weight generation mechanism in Algorithm 2, it holds $0\leq\eta\leq
1/\left(\max_{i}\left|\mathcal{N}_{i}^{\text{out}}\right|+1\right)$.

##  V Privacy analysis

Now, we analyze that Algorithm 2 is resistant to both honest-but-curious and
eavesdropping attacks.

###  V-A Performance Against Honest-but-curious Attacks

We show Algorithm 2 can enable privacy preservation against honest-but-curious
attacks in the following theorem.

######  Theorem 2.

Consider an $N$-agent distributed network that satisfies Assumption 1. In the
context of the presence of some honest-but-curious agents that collude with
each other, the initial value $x_{i}^{0}$ of legitimate agent $i$ can be
preserved if
$\mathcal{N}_{i}^{\text{out}}\cup\mathcal{N}_{i}^{\text{in}}\nsubseteq\mathcal{H}$
holds.

###### Proof.

Recalling the definition of privacy metric in Section II-D, it can be shown
that the privacy of agent $i$ can be preserved as long as
$\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)=\infty$. The available information
to $\mathcal{H}$ is
$\mathcal{I}_{h}=\left\\{\mathcal{I}_{j}\left|j\in\mathcal{H}\right.\right\\}$,
where $\mathcal{I}_{j}$ denotes the information available to each individual
$j\in\mathcal{H}$ given as

$\displaystyle\mathcal{I}_{j}=$
$\displaystyle\left\\{\mathcal{I}_{j}^{\text{state}}\left(k\right)\cup\mathcal{I}_{j}^{\text{send}}\left(k\right)\cup\mathcal{I}_{j}^{\text{receive}}\left(k\right)\left|k\geq
0\right.\right\\}$ $\displaystyle\cup\left\\{\sigma\left(k\right)\left|0\leq
k\leq
K\right.\right\\}\cup\left\\{y_{m}\left(0\right)=1\left|m\in\mathcal{V}\right.\right\\}$
$\displaystyle\cup\left\\{C_{nj}^{1}\left(k\right),C_{nj}^{2}\left(k\right)\left|m\in\mathcal{V},k\geq
0\right.\right\\}$

with

$\displaystyle\mathcal{I}_{j}^{\text{state}}\left(k\right)=\left\\{x_{j}\left(k\right),y_{j}\left(k\right)\right\\}$
$\displaystyle\mathcal{I}_{j}^{\text{send}}\left(k\right)\\!=\\!\left\\{C_{nj}^{1}\left(k\right)x_{j}\left(k\right),C_{nj}^{2}\left(k\right)y_{j}\left(k\right)\left|n\in\mathcal{N}_{j}^{\text{out}}\cup\left\\{j\right\\}\right.\right\\}$
$\displaystyle\mathcal{I}_{j}^{\text{receive}}\left(k\right)=\left\\{C_{jm}^{1}\left(k\right)x_{m}\left(k\right),C_{jm}^{2}\left(k\right)y_{m}\left(k\right)\left|m\in\mathcal{N}_{j}^{\text{in}}\right.\right\\}.$

To prove $\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)=\infty$, it suffices to
show that agents in $\mathcal{H}$ fail to judge whether the initial value of
agent $i$ is $x_{i}^{0}$ or $\tilde{x}_{i}^{0}=x_{i}^{0}+\delta$ where
$\delta$ is an arbitrary value in $\mathbb{R}$ and
$x_{i}^{0},\tilde{x}_{i}^{0}\in\mathcal{S}_{0}^{i}$. Note that agents in
$\mathcal{H}$ are only able to infer $x_{i}^{0}$ using $\mathcal{I}_{h}$. In
other words, if the initial value $\tilde{x}_{i}^{0}=x_{i}^{0}+\delta$ makes
the information $\tilde{\mathcal{I}}_{h}$ accessed by agents of $\mathcal{H}$
unchanged, i.e., $\tilde{\mathcal{I}}_{h}=\mathcal{I}_{h}$, then
$\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)=\infty$. Hence, we only need to
prove that there is $\tilde{\mathcal{I}}_{h}=\mathcal{I}_{h}$ in the case
$\tilde{x}_{i}^{0}\neq x_{i}^{0}$.

Since
$\mathcal{N}_{i}^{\text{out}}\cup\mathcal{N}_{i}^{\text{in}}\nsubseteq\mathcal{H}$,
there exists at least one agent
$l\in\mathcal{N}_{i}^{\text{out}}\cup\mathcal{N}_{i}^{\text{in}}\setminus\mathcal{H}$.
Thus, some settings on initial values of agent $l$ and mixing weights
associated with agent $l$ satisfying the requirements in Algorithm 2 make it
necessary that $\tilde{\mathcal{I}}_{h}=\mathcal{I}_{h}$ for any
$\tilde{x}_{i}^{0}$. More specifically, the initial settings are given as

$\displaystyle\tilde{x}_{m}^{0}=x_{m}^{0},m\in\mathcal{V}\setminus\left\\{i,l\right\\},$
(18a) $\displaystyle\tilde{x}_{i}^{0}=x_{i}^{0}+\delta,$ (18b)
$\displaystyle\tilde{x}_{l}^{0}=x_{l}^{0}-\delta,$ (18c)

where $\delta$ is nonzero and does not equal either $-x_{i}\left(0\right)$ or
$x_{l}\left(0\right)$. Apparently, such an initial value setting has no impact
on the sum of the original initial values. Then, we properly choose the mixing
weights such that $\tilde{\mathcal{I}}_{h}=\mathcal{I}_{h}$. Here, “properly”
means the choosing mixing weights should obey the weight generation mechanism
in Algorithm 2. Our analysis will be continued in two cases,
$l\in\mathcal{N}_{i}^{\text{out}}$ and $l\in\mathcal{N}_{i}^{\text{in}}$,
respectively.

Case I: We consider $l\in\mathcal{N}_{i}^{\text{out}}$. One can derive
$\tilde{\mathcal{I}}_{h}=\mathcal{I}_{h}$ if the weights are set as

$\displaystyle\tilde{C}_{mn}^{1}\left(0\right)=C_{mn}^{1}\left(0\right),m\in\mathcal{V},n\in\mathcal{V}\setminus\left\\{i,l\right\\},$
(19a)
$\displaystyle\tilde{C}_{mi}^{1}\left(0\right)=C_{mi}^{1}\left(0\right)x_{i}^{0}/\tilde{x}_{i}^{0},m\in\mathcal{V}\setminus\left\\{i,l\right\\},$
(19b)
$\displaystyle\tilde{C}_{li}^{1}\left(0\right)=\left(\sigma\left(0\right)C_{li}^{1}\left(0\right)x_{i}^{0}+\delta\right)/\sigma\left(0\right)\tilde{x}_{i}^{0},$
(19c)
$\displaystyle\tilde{C}_{ml}^{1}\left(0\right)=C_{ml}^{1}\left(0\right)x_{l}^{0}/\tilde{x}_{l}^{0},m\in\mathcal{V}\setminus\left\\{l\right\\},$
(19d)
$\displaystyle\tilde{C}_{ii}^{1}\left(0\right),\tilde{C}_{ll}^{1}\left(0\right)\in\mathbb{R},$
(19e)
$\displaystyle\tilde{C}_{mn}^{1}\left(k\right)=C_{mn}^{1}\left(k\right),m,n\in\mathcal{V},k\geq
1,$ (19f)
$\displaystyle\tilde{C}_{mn}^{2}\left(k\right)=C_{mn}^{2}\left(k\right),m,n\in\mathcal{V},k\geq
0.$ (19g)

Case II: We consider $l\in\mathcal{N}_{i}^{\text{in}}$. One can derive
$\tilde{\mathcal{I}}_{h}=\mathcal{I}_{h}$ if the weights are set as

$\displaystyle\tilde{C}_{mn}^{1}\left(0\right)=C_{mn}^{1}\left(0\right),m\in\mathcal{V},n\in\mathcal{V}\setminus\left\\{i,l\right\\},$
(20a)
$\displaystyle\tilde{C}_{mi}^{1}\left(0\right)=C_{mi}^{1}\left(0\right)x_{i}^{0}/\tilde{x}_{i}^{0},m\in\mathcal{V}\setminus\left\\{i\right\\},$
(20b)
$\displaystyle\tilde{C}_{ml}^{1}\left(0\right)=C_{ml}^{1}\left(0\right)x_{l}^{0}/\tilde{x}_{l}^{0},m\in\mathcal{V}\setminus\left\\{i,l\right\\},$
(20c)
$\displaystyle\tilde{C}_{il}^{1}\left(0\right)=\left(\sigma\left(0\right)C_{il}^{1}\left(0\right)x_{l}^{0}-\delta\right)/\sigma\left(0\right)\tilde{x}_{l}^{0},$
(20d)
$\displaystyle\tilde{C}_{ii}^{1}\left(0\right),\tilde{C}_{ll}^{1}\left(0\right)\in\mathbb{R},$
(20e)
$\displaystyle\tilde{C}_{mn}^{1}\left(k\right)=C_{mn}^{1}\left(k\right),m,n\in\mathcal{V},k\geq
1,$ (20f)
$\displaystyle\tilde{C}_{mn}^{2}\left(k\right)=C_{mn}^{2}\left(k\right),m,n\in\mathcal{V},k\geq
0.$ (20g)

Combining Cases I and II, it can be derived that
$\tilde{\mathcal{I}}_{h}=\mathcal{I}_{h}$ under the initial value
$\tilde{x}_{i}^{0}=x_{i}^{0}+\delta\in\mathcal{S}_{0}^{i}$. Then

$\displaystyle\mathbf{D}\left(\mathcal{S}_{0}^{i}\right)\geq\underset{\delta\in\mathbb{R}}{\text{sup}}\left|x_{i}^{0}-\tilde{x}_{i}^{0}\right|=\underset{\delta\in\mathbb{R}}{\text{sup}}\left|\delta\right|=\infty$

Therefore, the initial value $x_{i}^{0}$ of agent $i$ is preserved against
agents $\mathcal{H}$ if agent $i$ has at least one legitimate neighbor
$l\in\mathcal{V}\setminus\mathcal{H}$. ∎

######  Remark 4.

According to (19e) and (20e), one knows that that the privacy of the proposed
algorithm does not have any requirement for the weights
$\tilde{C}_{ii}^{1}\left(0\right)$ and $\tilde{C}_{ll}^{1}\left(0\right)$,
while the existing dynamic-based privacy-preserving algorithms [26], [41]
cannot achieve privacy protection in such a loose setting due to the
constraint of the sum $1$ condition. Therefore, the proposed algorithm has
stronger generalization capability.

Note that if
$\mathcal{N}_{i}^{\text{out}}\cup\mathcal{N}_{i}^{\text{in}}\subset\mathcal{H}$
for $i\in\mathcal{V}\setminus\mathcal{H}$, the initial value $x_{i}^{0}$ will
be inferred by $\mathcal{H}$, see Corollary 1 below.

######  Corollary 1.

Under the settings of Theorem 2, the initial value $x_{i}^{0}$ of agent
$i\notin\mathcal{H}$ can be inferred if
$\mathcal{N}_{i}^{\text{out}}\cup\mathcal{N}_{i}^{\text{in}}\subset\mathcal{H}$
holds.

###### Proof.

Recalling and recursively computing the update of $x$-variable for $k\leq K$
yields

$\displaystyle x_{i}\left(K+1\right)-x_{i}\left(0\right)$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{K}\\!{\sigma\left(t\right)\\!\left(\\!\sum_{n\in\mathcal{N}_{i}^{\text{in}}}\\!{C_{in}^{1}\left(t\right)x_{n}\left(t\right)}\\!-\\!\sum_{m\in\mathcal{N}_{i}^{\text{out}}}\\!{C_{mi}^{1}\left(t\right)x_{i}\left(t\right)}\\!\right)}.$
(21)

Then, using the column stochasticities of $\mathbf{C}_{1}\left(k\right)$ for
$k\geq K+1$ and $\mathbf{C}_{2}\left(k\right)$ for $k\geq 0$, we can arrive

$\displaystyle
x_{i}\left(k\right)=C_{ii}^{1}\left(k\right)x_{i}\left(k\right)+\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{1}\left(k\right)x_{i}\left(k\right)},k\geq
K,$ $\displaystyle
y_{i}\left(k\right)=C_{ii}^{2}\left(k\right)y_{i}\left(k\right)+\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{2}\left(k\right)y_{i}\left(k\right)},k\geq
0.$

Combining the above relations with (8) and (9), it follows that

$\displaystyle x_{i}\left(k\right)-x_{i}\left(K+1\right)$ $\displaystyle=$
$\displaystyle\sum_{t=K+1}^{k-1}\\!{\left(\\!\sum_{n\in\mathcal{N}_{i}^{\text{in}}}{C_{in}^{1}\left(t\right)x_{n}\left(t\right)}\\!-\\!\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{1}\left(t\right)x_{i}\left(t\right)}\\!\right)},$
(22) $\displaystyle y_{i}\left(k\right)-y_{i}\left(0\right)$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{k-1}{\left(\sum_{n\in\mathcal{N}_{i}^{\text{in}}}{C_{in}^{2}\left(t\right)y_{n}\left(t\right)}\\!-\\!\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{2}\left(t\right)y_{i}\left(t\right)}\right)}.$
(23)

Further, combining the results in (21) and (22) gives

$\displaystyle x_{i}\left(k\right)-x_{i}\left(0\right)$ $\displaystyle=$
$\displaystyle\sum_{t=K+1}^{k-1}{\left(\sum_{n\in\mathcal{N}_{i}^{\text{in}}}{C_{in}^{1}\left(t\right)x_{n}\left(t\right)}-\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{1}\left(t\right)x_{i}\left(t\right)}\right)}$
$\displaystyle+\sum_{t=0}^{K}{\sigma\left(t\right)\left(\sum_{n\in\mathcal{N}_{i}^{\text{in}}}{C_{in}^{1}\left(t\right)x_{n}\left(t\right)}-\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{1}\left(t\right)x_{i}\left(t\right)}\right)}.$
(24)

Note that each agent $j\in\mathcal{H}$ has access to $\mathcal{I}_{h}$. If
$\mathcal{N}_{i}^{\text{out}}\cup\mathcal{N}_{i}^{\text{in}}\subset\mathcal{H}$
holds for legitimate agent $i$, all the information involved on the right
sides of (23) and (24) is accessible to the honest-but-curious agents. Then,
using $y_{i}\left(0\right)=1$ and (23), agent $j$ can capture
$y_{i}\left(k\right)$ for all $k$. Further, as
$C_{ij}^{1}\left(k\right)=C_{ij}^{2}\left(k\right)$ for $k\geq K+1$,
$x_{i}\left(k\right)$ can be inferred correctly by agent $j$ using

$\displaystyle
x_{i}\left(k\right)=\frac{C_{ji}^{1}\left(k\right)x_{i}\left(k\right)}{C_{ji}^{2}\left(k\right)y_{i}\left(k\right)}y_{i}\left(k\right).$

Making use of (24), the desired initial value $x_{i}\left(0\right)=x_{i}^{0}$
is revealed. ∎

###  V-B Performance Against Eavesdropping Attacks

We show Algorithm 2 can enable privacy preservation against eavesdropping
attacks in the following theorem.

######  Theorem 3.

Consider an $N$-agent distributed network that satisfies Assumption 1. In the
context of the presence of an external eavesdropper who is able to capture all
transmitted information, the initial values
$\left\\{x_{i}^{0}\right\\}_{i\in\mathcal{V}}$ of all agents can be preserved.

###### Proof.

Recalling the definition of privacy metric in Section II-D, it can be shown
that the privacy of agent $i$ can be preserved as long as
$\mathbf{D}\left(\mathcal{S}_{0}\right)=\infty$. The available information to
the external eavesdropper is summarized as follows:

$\displaystyle\mathcal{I}_{e}=\left\\{C_{ij}^{1}\left(k\right)x_{j}\left(k\right),C_{ij}^{2}\left(k\right)y_{j}\left(k\right)\left|\forall
i,j\in\mathcal{V},i\neq j,k\geq 0\right.\right\\}$

The dynamic (8) can be reformulated as

$\displaystyle\mathbf{x}\left(k+1\right)=\mathbf{x}\left(k\right)+\sigma\left(k\right)\mathbf{R}\Delta\mathbf{x}\left(k\right),k\leq
K,$ (25)

where $\mathbf{R}$ denotes the incidence matrix associated network
$\mathcal{G}$, and $\Delta\mathbf{x}\left(k\right)$ is a stack vector whose
$i$-th element is $C_{mn}^{1}\left(k\right)x_{n}\left(k\right)$ with $(m,n)$
being the $i$-th edge in $\mathcal{E}$. Note that the external eavesdropper is
only able to infer all
$\left\\{x_{i}\left(0\right)\right\\}_{i\in\mathcal{V}}$ using
$\mathcal{I}_{e}$. To prove $\mathbf{D}\left(\mathcal{S}_{0}\right)=\infty$,
it is required to indicate that any initial value
$\mathbf{\tilde{x}}\left(0\right)\triangleq\mathbf{x}\left(0\right)+\Delta\sigma\left(0\right)\mathbf{R}\Delta\mathbf{x}\left(0\right)\in\mathcal{S}_{0}$
makes the information $\tilde{\mathcal{I}}_{e}$ accessed by the external
eavesdropper unchanged, i.e., $\tilde{\mathcal{I}}_{e}=\mathcal{I}_{e}$, where
$\Delta\sigma\left(0\right)$ is any value in $\mathbb{R}$. Hence, we only need
to prove that there is $\tilde{\mathcal{I}}_{e}=\mathcal{I}_{e}$ in the case
$\mathbf{\tilde{x}}\left(0\right)\neq\mathbf{x}\left(0\right)$. Specifically,
one can derive $\tilde{\mathcal{I}}_{e}=\mathcal{I}_{e}$ if some settings are
as follows:

$\displaystyle\tilde{C}_{mn}^{1}\left(0\right)=C_{mn}^{1}\left(0\right)x_{n}^{0}/\tilde{x}_{n}^{0},m,n\in\mathcal{V},m\neq
n,$ (26a)
$\displaystyle\tilde{C}_{nn}^{1}\left(0\right)\in\mathbb{R},n\in\mathcal{V},$
(26b)
$\displaystyle\tilde{\sigma}\left(0\right)=\sigma\left(0\right)+\Delta\sigma\left(0\right),$
(26c)
$\displaystyle\tilde{C}_{mn}^{1}\left(k\right)=C_{mn}^{1}\left(k\right),m,n\in\mathcal{V},k\geq
1,$ (26d)
$\displaystyle\tilde{C}_{mn}^{2}\left(k\right)=C_{mn}^{2}\left(k\right),k\geq
0,$ (26e)
$\displaystyle\tilde{\sigma}\left(k\right)=\sigma\left(k\right),k\geq 1.$
(26f)

Further, owing to the fact that the rank of $\mathbf{R}$ is $N-1$ and the
nullity of $\mathbf{R}$ is $\left|\mathcal{E}\right|-N-1$, one can conclude
that $\Delta\mathbf{x}\left(0\right)$ is any vector in
$\mathbb{R}^{\left|\mathcal{E}\right|}$. In other words, the probability of
$\Delta\mathbf{x}\left(0\right)$ landing in the null space of $\mathbf{R}$ is
zero. Thus, for any $n\in\mathcal{V}$, it holds

$\displaystyle\left[\mathbf{R}\Delta\mathbf{x}\left(0\right)\right]_{n}$
$\displaystyle=$
$\displaystyle\sum_{m\in\mathcal{N}_{n}^{\text{in}}}{C_{nm}^{1}\left(0\right)x_{m}\left(0\right)}-\sum_{m\in\mathcal{N}_{n}^{\text{out}}}{C_{mn}^{1}\left(0\right)x_{n}\left(0\right)}\neq
0.$

Naturally,
$\tilde{x}_{n}\left(0\right)-x_{n}\left(0\right)=\left[\Delta\sigma\left(0\right)\mathbf{R}\Delta\mathbf{x}\left(0\right)\right]_{n}$
can be any value in $\mathbf{R}$. Therefore,

$\displaystyle\mathbf{D}\left(\mathcal{S}_{0}\right)=$
$\displaystyle\underset{\mathbf{x}\left(0\right),\mathbf{\tilde{x}}\left(0\right)\in\mathcal{S}_{0}}{\text{sup}}\lVert\mathbf{x}\left(0\right)-\mathbf{\tilde{x}}\left(0\right)\rVert$
$\displaystyle=$
$\displaystyle\underset{\Delta\sigma\left(0\right)\in\mathbb{R}}{\text{sup}}\lVert\Delta\sigma\left(0\right)\mathbf{R}\Delta\mathbf{x}\left(0\right)\rVert=\infty.$

That is to say, all initial values
$\left\\{x_{i}\left(0\right)\right\\}_{i\in\mathcal{V}}$ are preserved against
the external eavesdropper. ∎

######  Remark 5.

Under the eavesdropping attack, we still have a loose setting for
$\tilde{C}_{nn}^{1}\left(0\right)$, $n\in\mathcal{V}$, which is another
reflection of the generalization ability of the proposed algorithm.

######  Corollary 2.

Under the settings of Theorem 3, if the update rule (8) is substituted with
(7), i.e., $\sigma\left(k\right)=1$ for $k\leq K$, Algorithm 2 cannot preserve
the privacy of each agent $i$ against eavesdropping attacks.

###### Proof.

Recursively computing the update of $x$-variable in (7) for $k\leq K$ yields

$\displaystyle x_{i}\left(K+1\right)-x_{i}\left(0\right)$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{K}{\left(\sum_{n\in\mathcal{N}_{i}^{\text{in}}}{C_{in}^{1}\left(t\right)x_{n}\left(t\right)}-\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{1}\left(t\right)x_{i}\left(t\right)}\right)}.$
(27)

Note that (22) and (23) still hold in this setting. Combining (27) with (22)
yields

$\displaystyle x_{i}\left(k\right)-x_{i}\left(0\right)$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{k-1}{\left(\sum_{n\in\mathcal{N}_{i}^{\text{in}}}{C_{in}^{1}\left(t\right)x_{n}\left(t\right)}-\sum_{m\in\mathcal{N}_{i}^{\text{out}}}{C_{mi}^{1}\left(t\right)x_{i}\left(t\right)}\right)}.$
(28)

Since the external eavesdropper can capture all transmitted information, all
terms in the right sides of (23) and (28) can be accessed by the external
eavesdropper. Then, using $y_{i}\left(0\right)=1$ and (23), agent $j$ can
capture $y_{i}\left(k\right)$ for all $k$. Further, since
$C_{ij}^{1}\left(k\right)=C_{ij}^{2}\left(k\right)$ for $k\geq K+1$,
$x_{i}\left(k\right)$ can be inferred correctly by agent $j$ using

$\displaystyle
x_{i}\left(k\right)=\frac{C_{ji}^{1}\left(k\right)x_{i}\left(k\right)}{C_{ji}^{2}\left(k\right)y_{i}\left(k\right)}y_{i}\left(k\right).$

Making use of (28), the desired initial value $x_{i}\left(0\right)=x_{i}^{0}$
is inferred. ∎

######  Remark 6.

According to the discussions above, it is evident that the first $K$-step
perturbations are crucial for preserving privacy against honest-but-curious
attacks, while the time-varying parameter $\sigma\left(t\right)$ is pivotal in
protecting privacy from eavesdropping attacks.

######  Remark 7.

Theorem 1 states that the randomness of embeddings in the first $K$ iterations
has no impact on the consensus performance. Besides, from the privacy
analysis, we can see that only changing the mixing weights and auxiliary
parameter at the iteration $k=0$ is enough to mask the initial values. That
is, we can make the proposed algorithm protect the initial value
$x_{i}\left(0\right)$ by simply embedding randomness to
$\mathbf{C}_{1}\left(0\right)$ (i.e., setting $K=1$). Here, our consideration
of $K\geq 1$ is to preserve more intermediate states $x_{i}\left(k\right)$,
but this also delays the consensus process, see Figs. 6 and 7. Therefore, if
the intermediate states are not information of privacy concern, we directly
set $K=1$ to obtain the best convergence performance.

##  VI Extensions

The privacy protocol in this paper can also be applied to the case of vector
states. Actually, privacy (i.e., the agent’s initial vector state) is
naturally protected provided that each scalar element of the vector state is
assigned an independent mixing weights. The details of the privacy protocol
for the vector-state case are summarized in Algorithm 3.

TABLE I: Parameter design Parameter |  Iteration $k\leq K$ |  Iteration $k\geq K+1$
---|---|---
$\mathbf{\Lambda}\left(k\right)$ |  $\mathbf{\Lambda}\left(k\right)=\text{diag}\left\\{\sigma_{1}\left(k\right),\cdots,\sigma_{d}\left(k\right)\right\\}$, where each $\sigma_{l}\left(k\right)$, $l=1,\cdots d$, is chosen from $\mathbb{R}$ independently |  $\setminus$
$C_{ij}^{2}\left(k\right)$ | Each $C_{ij}^{2}\left(k\right)$ is chosen from $\left[\eta,1\right]$ for $j\in\mathcal{N}_{i}^{\text{in}}\cup\left\\{i\right\\}$ with satisfying $\sum\nolimits_{i=1}^{N}{C_{ij}^{1}\left(k\right)}=1$
$\mathbf{C}_{ij}^{1}\left(k\right)$ |  $\mathbf{C}_{ij}^{1}\left(k\right)=\text{diag}\\{C_{ij,1}^{1}\left(k\right),\cdots,C_{ij,d}^{1}\left(k\right)\\}$, where each $C_{ij,l}^{1}\left(k\right)$, $l=1,\cdots d$, is chosen from $\mathbb{R}$ for $i\in\mathcal{N}_{j}^{\text{out}}\cup\left\\{j\right\\}$ independently |  $\mathbf{C}_{ij}^{1}\left(k\right)=C_{ij}^{1}\left(k\right)I$, where $C_{ij}^{1}\left(k\right)=C_{ij}^{2}\left(k\right)$
Algorithm 3 Secure average consensus algorithm in the vector-state case

1: Initial setting: Set
$\mathbf{x}_{i}\left(0\right)=\mathbf{x}_{i}^{0}\in\mathbb{R}^{d}$ and
$y_{i}\left(0\right)=1$ for $i\in\mathcal{V}$. Parameters $K\in\mathbb{N}$,
$\mathbf{\Lambda}\left(k\right)\in\mathbb{R}^{d\times d}$ for
$k\in\mathbb{N}$, and $\eta\in\left(0,1\right)$ are known to each agent.

2: Weight generation: See TABLE I.

3: for $k=0,1,\cdots$ do

4: Agent $i$ sends the computed
$\mathbf{C}_{li}^{1}\left(k\right)\mathbf{x}_{i}\left(k\right)$ and
$C_{li}^{2}\left(k\right)y_{i}\left(k\right)$ to
$l\in\mathcal{N}_{i}^{\text{out}}$.

5: Agent $i$ uses
$\mathbf{C}_{ij}^{1}\left(k\right)\mathbf{x}_{j}\left(k\right)$ and
$C_{ij}^{2}\left(k\right)y_{j}\left(k\right)$ from
$j\in\mathcal{N}_{i}^{\text{in}}$ to update $\mathbf{x}_{i}$ and $y_{i}$ as
follows:
$\displaystyle\mathbf{x}_{i}\left(k+1\right)=\begin{cases}\mathbf{x}_{i}\left(k\right)+\mathbf{\Lambda}\left(k\right)\bm{\varXi}_{i}\left(k\right),&\text{if}\,\,k\leq
K;\\\
\underset{j\in\mathcal{N}_{i}^{\text{in}}\cup\left\\{i\right\\}}{\sum}{\mathbf{C}_{ij}^{1}\left(k\right)\mathbf{x}_{j}\left(k\right)}&\text{if}\,\,k\geq
K+1.\\\ \end{cases}$ (29) $\displaystyle
y_{i}\left(k+1\right)=\underset{j\in\mathcal{N}_{i}^{\text{in}}\cup\left\\{i\right\\}}{\sum}{C_{ij}^{2}\left(k\right)y_{j}\left(k\right)},k\geq
0,$ (30) where
$\bm{\varXi}_{i}\left(k\right)\\!\triangleq\\!\underset{j\in\mathcal{N}_{i}^{\text{in}}}{\sum}\\!{\mathbf{C}_{ij}^{1}\left(k\right)\\!\mathbf{x}_{j}\left(k\right)}\\!-\\!\underset{j\in\mathcal{N}_{i}^{\text{out}}}{\sum}\\!{\mathbf{C}_{ji}^{1}\left(k\right)\\!\mathbf{x}_{i}\left(k\right)}$.

6: Agent $i$ computes
$\mathbf{z}_{i}\left(k+1\right)=\mathbf{x}_{i}\left(k+1\right)/y_{i}\left(k+1\right)$.

7: Until a stopping criteria is satisfied, e.g., agent $i$ stops if
$\lVert\mathbf{z}\left(k\right)-\mathbf{1}\otimes\mathbf{\bar{x}}^{0}\rVert<\epsilon$
for some predefined $\epsilon>0$, where
$\mathbf{\bar{x}}^{0}=\sum\nolimits_{j=1}^{N}{\mathbf{x}_{j}\left(0\right)}/N$.

8: end for

###  VI-A Performance analysis

Apparently, there is no change in the update of $y_{i}$, so we mainly focus on
the update of $\mathbf{x}_{i}$. Note that setting
$\mathbf{C}_{ij}^{1}\left(k\right)=\mathbf{0}$ and
$C_{ij}^{2}\left(k\right)=0$ for
$j\notin\mathcal{N}_{i}^{\text{in}}\cup\left\\{i\right\\}$, the update rule
(29) is transformed into

$\displaystyle\mathbf{x}_{i}\left(k+1\right)=\sum_{j=1}^{N}{\mathbf{C}_{ij}^{1}\left(k\right)\mathbf{x}_{j}\left(k\right)},k\geq
K+1.$

Define
$\mathbf{x}\left(k\right)=[\left(\mathbf{x}_{1}\left(k\right)\right)^{\top},\cdots,\left(\mathbf{x}_{N}\left(k\right)\right)^{\top}]^{\top}$,
$\mathbf{y}\left(k\right)=\left[y_{1}\left(k\right),\cdots,y_{2}\left(k\right)\right]^{\top}$,
$\mathbf{C}_{2}\left(k\right)=\left[C_{ij}^{2}\right]_{N\times N}$, and
$\mathbf{\tilde{C}}_{1}\left(k\right)$ is a block matrix with the
$\left(ij\right)$-th block entry being $\mathbf{C}_{ij}^{1}\left(k\right)$.
Then, the dynamic above can be further reformulated as

$\displaystyle\mathbf{x}\left(k+1\right)=\mathbf{\tilde{C}}_{1}\left(k\right)\mathbf{x}\left(k\right),k\geq
K+1,$ (31)

Note that
$\mathbf{\tilde{C}}_{1}\left(k\right)=\mathbf{C}_{2}\left(k\right)\otimes\mathbf{I}$
holds for $k\geq K+1$. Define
$\mathbf{\tilde{\Phi}}_{1}\left(k:s\right)=\mathbf{\tilde{C}}_{1}\left(k\right)\cdots\mathbf{\tilde{C}}_{1}\left(s\right)$
for $k\geq s\geq 0$. Particularly,
$\mathbf{\tilde{\Phi}}_{1}\left(k:k\right)=\mathbf{\tilde{C}}_{1}\left(k\right)$.
Recursively computing (31), we obtain

$\displaystyle\mathbf{x}\left(k+1\right)=\mathbf{\tilde{\Phi}}_{1}\left(k:K+1\right)\mathbf{x}\left(K+1\right),k\geq
K+1,$ (32)

where
$\mathbf{\tilde{\Phi}}_{1}\left(k:K+1\right)=\mathbf{\Phi}_{2}\left(k:K+1\right)\otimes\mathbf{I}$
for $k\geq K+1$. Then, it holds

$\displaystyle\left(\mathbf{1}^{\top}\\!\otimes\\!\mathbf{I}\right)\\!\mathbf{x}\left(k\\!+\\!1\right)\\!=\\!\left(\mathbf{1}^{\top}\\!\otimes\\!\mathbf{I}\right)\\!\mathbf{x}\left(K+1\right),k\\!\geq\\!K+1,$
(33)

For $k\leq K$, using
$\sum\nolimits_{i=1}^{N}{\bm{\varXi}_{i}\left(k\right)}=\mathbf{0}$, we have

$\displaystyle\left(\mathbf{1}^{\top}\otimes\mathbf{I}\right)\mathbf{x}\left(k+1\right)=\sum_{i=1}^{N}{\mathbf{x}_{i}\left(k+1\right)}$
$\displaystyle\,\,=$
$\displaystyle\sum_{i=1}^{N}{\left(\mathbf{x}_{i}\left(k\right)+\mathbf{\Lambda}\left(k\right)\bm{\varXi}_{i}\left(k\right)\right)}$
$\displaystyle\,\,=$
$\displaystyle\sum_{i=1}^{N}{\mathbf{x}_{i}\left(k\right)}=\left(\mathbf{1}^{\top}\otimes\mathbf{I}\right)\mathbf{x}\left(k\right),$
(34)

Combining (33) and (34) yields

$\displaystyle\left(\mathbf{1}^{\top}\otimes\mathbf{I}\right)\mathbf{x}\left(k+1\right)=\left(\mathbf{1}^{\top}\otimes\mathbf{I}\right)\mathbf{x}\left(0\right)$

From the analysis above, it is clear that Algorithm 3 retains the same
properties in the vector state case as it does in the scalar state case. So,
we have the following theorems.

######  Theorem 4.

Let
$\\{\left(\mathbf{z}_{i}\left(k\right)\right)_{i=1}^{N}\\}_{k\in\mathbb{N}}$
be the sequence generated by Algorithm 3,
$\mathbf{\bar{x}}^{0}=\sum\nolimits_{j=1}^{N}{\mathbf{x}_{j}^{0}}/N$ be the
average point, and the network $\mathcal{G}$ satisfies Assumption 1. Then, it
holds, for all $k\in\mathbb{N}$,
$\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert\leq c\rho^{k}$,
where $c^{{}^{\prime}}=\sqrt{d}c$.

###### Proof.

The proof follows the similar path to Theorem 1, the difference lies only in
the use of the Kronecker product and thus omitted. ∎

######  Theorem 5.

Consider an $N$-agent distributed network that satisfies Assumption 1. Let
$\mathcal{H}$ denote the set of all honest-but-curious agents. The following
statements hold:

  1. 1)

Under the settings of Theorem 2, the initial value $x_{i}\left(0\right)$ of
agent $i\notin\mathcal{H}$ running Algorithm 3 can be preserved against
$\mathcal{H}$ if
$\mathcal{N}_{i}^{\text{out}}\cup\mathcal{N}_{i}^{\text{in}}\nsubseteq\mathcal{H}$
holds;

  2. 2)

Under the settings of Theorem 3, the initial values $x_{i}\left(0\right)$ of
all agents $i\notin\mathcal{H}$ can be preserved against external
eavesdroppers who have access to all transmitted information.

###### Proof.

According to the analysis of Theorems 2 and 3, we can know that each scalar-
state element in the vector state can be preserved against both honest-but-
curious and eavesdropping attacks. Therefore, each vector state can also be
preserved. ∎

##  VII Experiments Validation

We construct simulations to confirm the consensus and the privacy performances
of our methods.

We simulate two networks $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ in Figs. 2
and 3, respectively. One is a simple directed network with $5$ agents and the
other is a large-scale directed network with $1000$ agents.

Figure 2: $\mathcal{G}_{1}$.

Figure 3: $\mathcal{G}_{2}$.

###  VII-A Consensus Performance

We pick the network $\mathcal{G}_{1}$ and set $\eta=0.01$. In Algorithm 2, at
iteration $k\leq K$, as required in Algorithm 2, the mixing weights
$C_{ji}^{1}\left(k\right)$ for
$j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}$ are selected from
$\left(-100,100\right)$. $x_{1}^{0},\cdots,x_{5}^{0}$ take values of
$10,15,20,25,30$, respectively, and thus $\bar{x}^{0}=20$. The parameter
$\sigma\left(k\right)$ is generated from $\mathcal{N}\left(0,10\right)$ for
all $k\leq K$. In Algorithm 3, at iteration $k\leq K$, the parameters
$\sigma_{l}\left(k\right)$ are generated from $\mathcal{N}\left(0,10\right)$
for $l=1,\cdots,d$ with $d=3$, and the mixing weights
$C_{ij,l}^{1}\left(k\right)$ are chosen from $\left(-100,100\right)$ for
$l=1,\cdots,d$ and $j\in\mathcal{N}_{i}^{\text{out}}\cup\left\\{i\right\\}$.
Each component of the initial values $\mathbf{x}_{i}^{0}\in\mathbb{R}^{d}$,
$i=1,\cdots,5$, is generated from the Gaussian distributions with different
mean values $0,20,40$.

Figure 4: The trajectories of states $\\{z_{i}\left(k\right)\\}$ in Algorithm
2.

Figure 5: The trajectories of states $\\{\mathbf{z}_{i}\left(k\right)\\}$ in
Algorithm 3.

Figure 6: The evolutions of $e\left(k\right)$ under Algorithm 2.

Figure 7: The evolutions of $e\left(k\right)$ under Algorithm 3.

The evolutionary trajectories of the state variables
$\mathbf{z}\left(k\right)$ of Algorithms 2 and 3 are plotted in Figs. 4 and 5,
respectively, where we set $K=2$. Furthermore, we also use
$e\left(k\right)=\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert$
to measure the consensus performance. Note that
$e\left(k\right)=\lVert\mathbf{z}\left(k\right)-\mathbf{1}\otimes\mathbf{\bar{x}}^{0}\rVert$
in the vector-state case. The evolutions of $e\left(k\right)$ are shown in
Figs. 6 and 7. One can observe that: i) Each estimate $z_{i}\left(k\right)$
converges to the average value $\bar{x}^{0}$, and the consensus rate
$\mathcal{O}\left(\rho^{k}\right)$ is achieved; and ii) a larger $K$ means a
slower consensus rate.

Furthermore, we compare our algorithms with three data-obfuscation based
methods, i.e., the differential privacy algorithm [10], the decaying noise
algorithm [14], and the finite-noise-sequence algorithm [15]. Here, we set
$K=2$, and the adopted mixing matrix $W$ is from [10]. Specifically, the
element $W_{ij}$ is set to
$1/\left(\left|\mathcal{N}_{j}^{\text{out}}\right|+1\right)$ if
$i\in\mathcal{N}_{j}^{\text{out}}\cup\left\\{j\right\\}$; otherwise,
$W_{ij}=0$. Since the directed and unbalanced networks are more generalizable
than the undirected and balanced ones adopted in [10, 14, 15], these
algorithms cannot achieve average consensus, as reported in Figs. 8, 9, and
10.

Figure 8: The trajectories of all states $\\{x_{i}\left(k\right)\\}$ in [10].

Figure 9: The trajectories of all states $\\{x_{i}\left(k\right)\\}$ in [14].

Figure 10: The trajectories of all states $\\{x_{i}\left(k\right)\\}$ in [15].

Figure 11: The consensus performance over network $\mathcal{G}_{2}$.

###  VII-B Scalability Performance

We then show the scalability of our algorithms using the network
$\mathcal{G}_{2}$ (see Fig. 3), which has $1000$ agents. In $\mathcal{G}_{2}$,
each agent $i$ has $6$ out-neighbors, where one belongs to a directed cycle
graph connecting all agents and the other is linked uniformly at random. Each
initial value $x_{i}^{0}$/$\mathbf{x}_{i}^{0}$ is generated from i.i.d
$\mathcal{N}\left(0,1\right)$. The parameters $\eta$ and $K$ take values of
$0.05$ and $3$, respectively. In addition, the vector dimension $d$ is set to
$10$. The mixing weights and
$\sigma\left(k\right)$/$\mathbf{\Lambda}\left(k\right)$ are generated in the
same way as the above experiments. We plot the consensus error
$e\left(k\right)$ in Fig. 11. It is stated that the proposed algorithms still
ensure that all agents linearly converge to the correct average value even if
a large-scale network is used.

###  VII-C Privacy Performance

Finally, we evaluate the privacy-preserving performances of Algorithms 2 and
3. Under the network $\mathcal{G}_{1}$, we consider the initial value of the
legitimate agent $1$ will suffer from the joint inference of honest-but-
curious agents $4,5$, and agent $2$ is legitimate. In the scalar-state case
(i.e., Algorithm 2), we set $x_{1}^{0}=40$ and $x_{2}^{0},\cdots,x_{N}^{0}$
are generated from the Gaussian distributions with $50$ variance and zero mean
while the initial value $\mathbf{x}_{1}^{0}$ denotes the digit $0$ from the
MNIST dataset [42] and $\mathbf{x}_{2}^{0},\cdots,\mathbf{x}_{N}^{0}$ are
randomly generated from i.i.d. $\mathcal{N}\left(0,50\right)$ in the vector-
state case (i.e, Algorithm 3). Moreover, we set $k=2$ and the maximal
iteration $M=200$.

To infer $x_{1}^{0}$, agents $\mathcal{H}=\left\\{4,5\right\\}$ construct some
linear equations below based on their available information
$\mathcal{I}_{h}=\left\\{\mathcal{I}_{4},\mathcal{I}_{5}\right\\}$:

$\displaystyle x_{1}\left(k+1\right)-x_{1}\left(k\right)$
$\displaystyle+\sigma\left(k\right)C_{21}^{1}\left(k\right)x_{1}\left(k\right)=\sigma\left(k\right)\Delta
x\left(k\right),0\leq k\leq K,$ (35a) $\displaystyle
x_{1}\left(k\\!+\\!1\right)\\!-\\!x_{1}\left(k\right)\\!+\\!C_{21}^{1}\left(k\right)x_{1}\left(k\right)\\!=\\!\Delta
x\left(k\right),K\\!+\\!1\\!\leq\\!k\\!\leq\\!M,$ (35b) $\displaystyle
y_{1}\\!\left(k\\!+\\!1\right)\\!-\\!y_{1}\\!\left(k\right)\\!+\\!C_{21}^{2}\left(k\right)y_{1}\left(k\right)\\!=\\!\Delta
y\left(k\right)\\!,0\\!\leq\\!k\\!\leq\\!M,$ (35c)

where

$\displaystyle\Delta
x\left(k\right)=\sum_{m\in\left\\{4,5\right\\}}{C_{1m}^{1}\left(k\right)x_{m}\left(k\right)}-\sum_{n\in\left\\{4,5\right\\}}{C_{n1}^{1}\left(k\right)x_{1}\left(k\right)},$
$\displaystyle\Delta
y\left(k\right)=\sum_{m\in\left\\{4,5\right\\}}{C_{1m}^{2}\left(k\right)y_{m}\left(k\right)}-\sum_{n\in\left\\{4,5\right\\}}{C_{n1}^{2}\left(k\right)y_{1}\left(k\right)}.$

Furthermore, agents $\mathcal{H}$ can also construct, for
$k=K+1,K+2,\cdots,M$,

$\displaystyle x_{1}\left(k\right)-z_{1}\left(k\right)y_{1}\left(k\right)=0,$
(35d)

where $z_{1}\left(k\right)$ can be derived from

$\displaystyle
z_{1}\left(k\right)=\frac{C_{41}^{1}\left(k\right)x_{1}\left(k\right)}{C_{41}^{2}\left(k\right)y_{1}\left(k\right)},$

since $C_{41}^{1}\left(k\right)=C_{41}^{2}\left(k\right)$ for $k\geq K+1$.

The number of linear equations is $\\!3M\\!-\\!K\\!+\\!2\\!$ while that of
unknown variables to $\mathcal{H}$ is $\\!4M\\!+\\!5\\!$, including
specifically
$x_{1}\left(0\right),\cdots,x_{1}\left(M\\!+\\!1\right),C_{21}^{1}\left(0\right)\\!x_{1}\left(0\right),\cdots,C_{21}^{1}\left(M\right)\\!x_{1}\left(M\right),$
$y_{1}\left(1\right),\cdots,y_{1}\left(M\\!+\\!1\right),C_{21}^{2}\left(0\right)y_{1}\left(0\right),\cdots,C_{21}^{2}\left(M\right)y_{1}\left(M\right)$.
Consequently, there are infinitely many solutions due to the fact that the
number of equations is less than that of unknown variables. The analysis of
the vector-state case is similar to that of the scalar-state case, so it will
not be elaborated here. To uniquely determine $x_{1}^{0}$, we use the least-
squares solution to infer $x_{1}^{0}$. In this experiment, agents in
$\mathcal{H}$ estimate $x_{1}^{0}$ for $1000$ times in the scalar-state case,
and for $24$ times in the vector-state case. The results are shown in Figs. 12
and 13. One can observe that agents in $\mathcal{H}$ fail to obtain a nice
estimate of $x_{1}^{0}$.

Next, we consider the case of eavesdropping attacks. The parameter settings
follow the above experiment. Let us choose agent $1$ to illustrate that the
proposed algorithms are privacy-preserving against external eavesdropping
attacks. To infer the value $x_{1}^{0}$, the external eavesdropper constructs
some linear equations below based on its available information
$\mathcal{I}_{e}$:

$\displaystyle
x_{1}\left(k+1\right)-x_{1}\left(k\right)=\sigma\left(k\right)\Delta\hat{x}\left(k\right),0\leq
k\leq K+1,$ (36a) $\displaystyle
x_{1}\left(k+1\right)-x_{1}\left(k\right)=\Delta\hat{x}\left(k\right),K+1\leq
k\leq M,$ (36b) $\displaystyle
y_{1}\left(k+1\right)-y_{1}\left(k\right)=\Delta\hat{y}\left(k\right),0\leq
k\leq M,$ (36c)

where

$\displaystyle\Delta\hat{x}\left(k\right)\\!=\\!\sum_{m\in\left\\{4,5\right\\}}{C_{1m}^{1}\left(k\right)x_{m}\left(k\right)}\\!-\\!\sum_{n\in\left\\{2,4,5\right\\}}{C_{n1}^{1}\left(k\right)x_{1}\left(k\right)},$
$\displaystyle\Delta\hat{y}\left(k\right)\\!=\\!\sum_{m\in\left\\{4,5\right\\}}{C_{1m}^{2}\left(k\right)y_{m}\left(k\right)}\\!-\\!\sum_{n\in\left\\{2,4,5\right\\}}{C_{n1}^{2}\left(k\right)y_{1}\left(k\right)}.$

Further, the external eavesdropper can deduce from (36) that

$\displaystyle
x_{1}\left(K+1\right)-x_{1}\left(0\right)=\sum_{t=0}^{K}{\sigma\left(t\right)\Delta\hat{x}\left(t\right)},$
(37a) $\displaystyle
x_{1}\\!\left(k\\!+\\!1\right)\\!-\\!x_{1}\left(K\\!+\\!1\right)\\!=\\!\sum_{t=K\\!+\\!1}^{k}{\Delta\hat{x}\left(t\right)},K\\!+\\!1\\!\leq\\!k\\!\leq\\!M,$
(37b) $\displaystyle
y_{1}\left(k+1\right)-y_{1}\left(0\right)=\sum_{t=0}^{k}{\Delta\hat{y}\left(t\right)},0\leq
k\leq M.$ (37c)

Obviously, all terms in the right side of (37) can be accessed by the external
eavesdropper. Consequently, using $y_{1}\left(0\right)=1$, the eavesdropper
can be aware of all $y_{1}\left(k\right)$, $k\in\mathbb{N}$. Moreover, the
external eavesdropper can capture
$C_{21}^{1}\left(k\right)x_{1}\left(k\right)$ and
$C_{21}^{2}\left(k\right)y_{1}\left(k\right)$ for $k=K+1,\cdots,M$. Then,
$x_{1}\left(k\right)$ for $k=K+1,\cdots,M$ can be derived using

$\displaystyle
x_{1}\left(k\right)=\frac{C_{21}^{1}\left(k\right)x_{1}\left(k\right)}{C_{21}^{2}\left(k\right)y_{1}\left(k\right)}y_{1}\left(k\right)$

This implies that all information in (36b) and (36c) is captured by the
external eavesdropper, which is considerably different from the case of
honest-but-curious attacks. So, only (36a) has some unknown variables
$\sigma\left(k\right)$, $k=0,\cdots,K$ and $x_{1}\left(0\right)$ for the
external eavesdropper. The vector-state case leads to the same results as the
scalar-state case by following the same analysis path, so it is not stated
again. In this experiment, we still use the least-squares solution to estimate
$x_{1}^{0}$. The external eavesdropper estimates $x_{1}^{0}$ for $1000$ times
in the scalar-state case, and for $24$ times in the vector-state case. Figs.
14 and 15 show the estimated results. One can observe that the external
eavesdropper cannot obtain nice estimate of $x_{1}^{0}$.

Figure 12: Scalar-state case: Estimation results of $x_{1}^{0}$ by
$\mathcal{H}$.

Figure 13: Vector-state case: Estimation results of $\mathbf{x}_{1}^{0}$ by
$\mathcal{H}$.

Figure 14: Scalar-state case: Estimation results of $x_{1}^{0}$ by the
external eavesdropper.

Figure 15: Vector-state case: Estimation results of $\mathbf{x}_{1}^{0}$ by
the external eavesdropper.

##  VIII Conclusion

We proposed two privacy-preserving push-sum algorithms over unbalanced
digraphs, and theoretically analyzed the linear convergence rate of them and
proved that they can guarantee the privacy of agents against both honest-but-
curious and eavesdropping attacks. Finally, numerical experiments further
confirmed the soundness of our work. Future work will consider a method that
can eliminate $K$ and still protect privacy.

##  IX Acknowledgment

The authors would like to thank Huan Gao, an Associate Professor with the
School of Automation, Northwestern Polytechnical University, for his precious
guidance and help in experimental validation. This work was supported in part
by the National Key R&D Program of China under Grant 2018AAA0100101, in part
by the National Natural Science Foundation of China under Grant 61932006 and
61772434, in part by the Chongqing technology innovation and application
development project under Grant cstc2020jscx-msxmX0156, and in part by the
Natural Science Foundation of Chongqing under Grant CSTB2022NSCQ-MSX1217.

## References

  * [1] F. Acciani, P. Frasca, G. Heijenk, and A. A. Stoorvogel, “Achieving robust average consensus over lossy wireless networks”, IEEE Transactions on Control of Network Systems, vol. 6, no. 1, pp. 127–137, 2019.
  * [2] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor fusion based on average consensus,” in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, 2005, pp. 63–70.
  * [3] B. Du, R. Mao, N. Kong, D. Sun, “Distributed data fusion for on-scene signal sensing with a multi-UAV system,” in IEEE Transactions on Control of Network Systems, vol. 7, no. 3, pp. 1330–1341, 2020.
  * [4] F. C. Souza, S. R. B. Dos Santos, A. M. de Oliveira, and S. N. Givigi, “Influence of network topology on UAVs formation control based on distributed consensus,” in IEEE International Systems Conference, 2022, pp. 1–8.
  * [5] J. N. Tsitsiklis, “Problems in decentralized decision making and computation,” Ph.D. dissertation, 1984.
  * [6] Z. Zhang and M. Y. Chow, “Incremental cost consensus algorithm in a smart grid environment,” in IEEE Power and Energy Society General Meeting, 2011, pp. 1–6.
  * [7] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Proceedings of the 3rd Theory Cryptography Conference, 2006, pp. 265–284.
  * [8] Z. Huang, S. Mitra, and N. Vaidya, “Differentially private distributed optimization,” in International Conference on Distributed Computing and Networking, 2015, pp. 1–10.
  * [9] 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.
  * [10] Z. Huang, S. Mitra, and G. Dullerud, “Differentially private iterative synchronous consensus,” in Proceedings of the 2012 ACM Workshop on Privacy in the Electronic Society, 2012, pp. 81–90.
  * [11] L. Gao, S. Deng, W. Ren, and C. Hu, “Differentially private consensus with quantized communication,” IEEE Transactions on Cybernetics, vol. 51, no. 8, pp. 4075–4088, Aug. 2021.
  * [12] D. Ye, T. Zhu, W. Zhou, and S. Y. Philip, “Differentially private malicious agent avoidance in multiagent advising learning,” IEEE Transactions on Cybernetics, vol. 50, no. 10, pp. 4214–4227, Oct. 2020.
  * [13] M. Kefayati, M. S. Talebi, B. H. Khalaj, and H. R. Rabiee, “Secure consensus averaging in sensor networks using random offsets,” in IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, 2007, pp. 556–560.
  * [14] Y. Mo and R. M. Murray, “Privacy preserving average consensus,” IEEE Transactions on Automatic Control, vol. 62, no. 2, pp. 753–765, 2017.
  * [15] N. E. Manitara and C. N. Hadjicostis, “Privacy-preserving asymptotic average consensus,” in European Control Conference (ECC), 2013, pp. 760–765.
  * [16] C. Altafini, “A dynamical approach to privacy preserving average consensus,” in Proceedings of IEEE 58th Conference on Decision and Control, 2019, pp. 4501–4506.
  * [17] S. Pequito, S. Kar, S. Sundaram, and A. P. Aguiar, “Design of communication networks for distributed computation with privacy guarantees,” in Proceedings of the 53rd IEEE Conference on Decision and Control, 2014, pp. 1370–1376.
  * [18] I. D. Ridgley, R. A. Freeman, and K. M. Lynch, “Simple, private, and accurate distributed averaging,” in Proceedings of IEEE 57th Annual Allerton Conference on Communication, Control, and Computing, 2019, pp. 446–452.
  * [19] A. Alaeddini, K. Morgansen, and M. Mesbahi, “Adaptive communication networks with privacy guarantees,” in Proceedings of American Control Conference, 2017, pp. 4460–4465.
  * [20] M. Kishida, “Encrypted average consensus with quantized control law,” in Proceedings of IEEE Conference on Decision and Control, 2018, pp. 5850–5856.
  * [21] C. N. Hadjicostis and A. D. Dominguez-Garcia, “Privacy-preserving distributed averaging via homomorphically encrypted ratio consensus,” IEEE Transactions on Automatic Control, vol. 65, no. 9, pp. 3887–3894, Sep. 2020.
  * [22] W. Fang, M. Zamani, and Z. Chen, “Secure and privacy preserving consensus for second-order systems based on paillier encryption,” Systems & Control Letters, vol. 148, pp. 104869, 2021.
  * [23] M. Ruan, H. Gao, and Y. Wang, “Secure and privacy-preserving consensus,” IEEE Transactions on Automatic Control, vol. 64, no. 10, pp. 4035–4049, Oct. 2019.
  * [24] Y. Wang, “Privacy-preserving average consensus via state decomposition,” IEEE Transactions on Automatic Control, vol. 64, no. 11, pp. 4711–4716, 2019.
  * [25] X. Chen, L. Huang, K. Ding, S. Dey, and L. Shi, “Privacy-preserving push-sum average consensus via state decomposition,” IEEE Transactions on Automatic Control, doi:10.1109/TAC.2023.3256479, 2023.
  * [26] H. Gao, C. Zhang, M. Ahmad, and Y. Q. Wang, “Privacy-preserving average consensus on directed graphs using push-sum,” in IEEE Conference on Communications and Network Security (CNS), 2018, pp. 1–9.
  * [27] H. Gao, and Y. Wang, “Algorithm-level confidentiality for average consensus on time-varying directed graphs,” IEEE Transactions on Network Science and Engineering, vol. 9, no. 2, pp. 918–931, 2022.
  * [28] Y. Liu, H. Gao, J. Du, and Y. Zhi, “Dynamics Based Privacy Preservation for Average Consensus on Directed Graphs,” in Proceedings of the 41st Chinese Control Conference, 2022, pp. 4955–4961.
  * [29] D. Kempe, A. Dobra, and J. Gehrke, “Gossip-based computation of aggregate information,” in Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 482–491.
  * [30] F. Bénézit, V. Blondel, P. Thiran, J. Tsitsiklis, and M. Vetterli, “Weighted gossip: Distributed averaging using non-doubly stochastic matrices,” in Proceedings of 2010 IEEE International Symposium on Information Theory, 2010, pp. 1753–1757.
  * [31] C. N. Hadjicostis, A. D. Domínguez-García, and T. Charalambous, “Distributed averaging and balancing in network systems: With applications to coordination and control,” Foundations and Trends in Systems and Control, vol. 5, no. 2–3, pp. 99–292, 2018.
  * [32] K. Liu, H. Kargupta, and J. Ryan, “Random projection-based multiplicative data perturbation for privacy preserving distributed data mining,” IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 1, pp. 92–106, 2005.
  * [33] S. Han,W. K. Ng, L.Wan, and V. C. Lee, “Privacy-preserving gradient-descent methods,” IEEE Transactions on Knowledge and Data Engineering, vol. 22, no. 6, pp. 884–899, 2009.
  * [34] N. Cao, C. Wang, M. Li, K. Ren, and W. Lou, “Privacy-preserving multi-keyword ranked search over encrypted cloud data,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 1, pp. 222–233, 2013.
  * [35] Y. Lu and M. Zhu, “On privacy preserving data release of linear dynamic networks,” Automatica, vol. 115, pp. 108839, 2020.
  * [36] A. Machanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam, “$L$-diversity: Privacy beyond $k$-anonymity,” ACM Transactions on Knowledge Discovery from Data, vol. 1, no. 1, pp. 3–es, 2007.
  * [37] E. Seneta, “Non-negative matrices and markov chains,” Springer, 1973.
  * [38] J. A. Fill, “Eigenvalue bounds on convergence to stationarity for nonreversible markov chains, with an application to the exclusion process,” The annals of applied probability, 1991, pp. 62–87.
  * [39] R. A. Horn and C. R. Johnson, “Matrix Analysis,” Cambridge university press Press, 2012.
  * [40] A. Nedić, 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.
  * [41] H. Gao, Y. Wang, and A. Nedić, “Dynamics based privacy preservation in decentralized optimization,” Automatica, vol. 151, pp. 110878, 2023.
  * [42] Y. LeCun, C. Cortes, and C. Burges, “MNIST handwritten digit database. [Online]. Available: http://yann. lecun.com/exdb/m,” in AT&T Labs, Florham Park, NJ, USA., 2020.

|  Huqiang Cheng received the B.E. degree in internet of things engineering
from Chongqing Three Gorges University, Chongqing, China, in 2018, and the
M.S. degree in signal and information processing from Southwest University,
Chongqing, China, in 2021. He is currently pursuing his Ph.D degree at the
College of Computer Science, Chongqing University, Chongqing, China.His
research interests include differential privacy, multi-agent system, and
distributed optimization.
---|---
|  Xiaofeng Liao (Fellow, IEEE) received the B.S. and M.S. degrees in
mathematics from Sichuan University, Chengdu, China, in 1986 and 1992,
respectively, and the Ph.D. degree in circuits and systems from the University
of Electronic Science and Technology of China, Chengdu, in 1997. From 1999 to
2012, he was a Professor with Chongqing University, Chongqing, China. From
July 2012 to July 2018, he was a Professor and the Dean of the College of
Electronic and Information Engineering, Southwest University, Chongqing. He is
currently a Professor and the Dean of the College of Computer Science,
Chongqing University. He is also a Yangtze River Scholar of the Ministry of
Education of China, Beijing, China. From March 2006 to April 2007, he was a
Research Fellow at the City University of Hong Kong. His current research
interests include optimization and control, machine learning, neural networks,
bifurcation and chaos, and cryptography. Prof. Liao currently serves as an
Associate Editor of the IEEE Transactions on Cybernetics and IEEE Transactions
on Neural Networks and Learning Systems.
---|---
|  Huaqing Li (Senior Member, IEEE) received the B.S. degree in Information
and Computing Science from Chongqing University of Posts and
Telecommunications, in 2009, and the Ph.D. degree in Computer Science and
Technology from Chongqing University in 2013. He was a Postdoctoral Researcher
at School of Electrical and Information Engineering, The University of Sydney
from Sept. 2014 to Sept. 2015, and at School of Electrical and Electronic
Engineering, Nanyang Technological University from Nov. 2015 to Nov. 2016.
From Jul. 2018, he was a professor at College of Electronic and Information
Engineering, Southwest University. His main research interests include
nonlinear dynamics and control, multi-agent systems, and distributed
optimization. He serves as a Regional Editor for Neural Computing &
Applications and an Editorial Board Member for IEEE ACCESS.
---|---

##  Appendix A Proof of Theorem 1

###### Proof.

We divide the convergence analysis into two cases.

Case I: We consider the case of $k\geq K+2$. It holds
$\mathbf{C}_{1}\left(k\right)=\mathbf{C}_{2}\left(k\right)$. Recalling (12)
and (13), we can obtain that, for $l\geq 1$,

$\displaystyle\mathbf{x}\left(K+l+1\right)=\mathbf{\Phi}_{1}\left(K+l:K+1\right)\mathbf{x}\left(K+1\right),$
(38)
$\displaystyle\mathbf{y}\left(K+l+1\right)=\mathbf{\Phi}_{2}\left(K+l:K+1\right)\mathbf{y}\left(K+1\right).$
(39)

Referring the Corollary 2 in [40], there exists a sequence of stochastic
vectors $\left\\{\bm{\varphi}\left(k\right)\right\\}_{k\in\mathbb{N}}$ such
that, for any $i,j\in\mathcal{V}$,

$\displaystyle\left|\left[\mathbf{\Phi}_{1}\left(k:K+1\right)\right]_{ij}-\varphi_{i}\left(k\right)\right|\leq
c_{0}\rho^{k-K-1},$

where $c_{0}=2(1+\rho^{-N+1})/(1-\rho^{N-1})$ and
$\rho=(1-\eta^{N-1})^{\frac{1}{N-1}}$. Moreover,
$\varphi_{i}\left(k\right)\geq\eta^{N}/N$. Thus, we obtain, for $l\geq 1$,

$\displaystyle\left|\left[\mathbf{M}\left(K+l:K+1\right)\right]_{ij}\right|\leq
c_{0}\rho^{l-1}.$ (40)

where
$\mathbf{M}\left(K+l:K+1\right)\triangleq\mathbf{\Phi}_{1}\left(K+l:K+1\right)-\bm{\varphi}\left(K+l\right)\mathbf{1}^{\top}$.
Since $\mathbf{C}_{1}\left(k\right)=\mathbf{C}_{2}\left(k\right)$, it holds
that
$\mathbf{\Phi}_{1}\left(K+l:K+1\right)=\mathbf{\Phi}_{2}\left(K+l:K+1\right)$
for $l\geq 1$. So (38) and (39) can be evolved as

$\displaystyle\mathbf{x}\left(K+l+1\right)=$
$\displaystyle\mathbf{M}\left(K+l:K+1\right)\mathbf{x}\left(K+1\right)$
$\displaystyle+\bm{\varphi}\left(K+l\right)\mathbf{1}^{\top}\mathbf{x}\left(K+1\right),$
(41) $\displaystyle\mathbf{y}\left(K+l+1\right)=$
$\displaystyle\mathbf{M}\left(K+l:K+1\right)\mathbf{y}\left(K+1\right)$
$\displaystyle+N\bm{\varphi}\left(K+l\right),$ (42)

It follows from the Corollary 2(b) in [40] that
$y_{i}\left(k+1\right)=\left[\mathbf{M}\left(k:0\right)\mathbf{1}\right]_{i}+N\varphi_{i}\left(k\right)\geq\eta^{N}$
for any $k\in\mathbb{N}$. Using (16), we have

$\displaystyle\bar{x}^{0}=\frac{\sum\nolimits_{j=1}^{N}{x_{j}\left(0\right)}}{N}=\frac{\mathbf{1}^{\top}\mathbf{x}\left(0\right)}{N}=\frac{\mathbf{1}^{\top}\mathbf{x}\left(K+1\right)}{N}.$
(43)

Combining (41) and (42) with (43) yields

$\displaystyle\frac{x_{i}\left(K+l+1\right)}{y_{i}\left(K+l+1\right)}-\bar{x}^{0}$
$\displaystyle\,\,=$
$\displaystyle\frac{x_{i}\left(K+l+1\right)}{y_{i}\left(K+l+1\right)}-\frac{\mathbf{1}^{\top}\mathbf{x}\left(K+1\right)}{N}$
$\displaystyle=$
$\displaystyle\frac{\left[\mathbf{M}\left(K\\!+\\!l:K\\!+\\!1\right)\mathbf{x}\left(K\\!+\\!1\right)\right]_{i}\\!+\\!\varphi_{i}\left(k\\!+\\!l\right)\mathbf{1}^{\top}\mathbf{x}\left(K\\!+\\!1\right)}{y_{i}\left(K+l+1\right)}$
$\displaystyle-\frac{Q\left(K;i\right)}{Ny_{i}\left(K+l+1\right)}$
$\displaystyle=$
$\displaystyle\frac{\left[\mathbf{M}\left(K+l:K+1\right)\mathbf{x}\left(K+1\right)\right]_{i}}{y_{i}\left(K+l+1\right)}$
$\displaystyle-\frac{\mathbf{1}^{\top}\mathbf{x}\left(K+1\right)\left[\mathbf{M}\left(K+l:K+1\right)\mathbf{y}\left(K+1\right)\right]_{i}}{Ny_{i}\left(K+l+1\right)},$

where

$\displaystyle Q\left(K;i\right)\triangleq$
$\displaystyle\mathbf{1}^{\top}\mathbf{x}\left(K+1\right)\left[\mathbf{M}\left(K+l:K+1\right)\mathbf{y}\left(K+1\right)\right]_{i}$
$\displaystyle+N\varphi_{i}\left(k+l\right)\mathbf{1}^{\top}\mathbf{x}\left(K+1\right).$

Then, we can bound $\left|z_{i}\left(K+l+1\right)-\bar{x}^{0}\right|$ as

$\displaystyle\left|z_{i}\left(K+l+1\right)-\bar{x}^{0}\right|$
$\displaystyle\leq$
$\displaystyle\frac{\left|\left[\mathbf{M}\left(K+l:K+1\right)\mathbf{x}\left(K+1\right)\right]_{i}\right|}{y_{i}\left(K+l+1\right)}$
$\displaystyle+\frac{\left|\mathbf{1}^{\top}\mathbf{x}\left(K+1\right)\left[\mathbf{M}\left(K+l:K+1\right)\mathbf{y}\left(K+1\right)\right]_{i}\right|}{Ny_{i}\left(K+l+1\right)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\eta^{N}}\\!\left(\underset{j}{\max}\left|\left[\mathbf{M}\left(K\\!+\\!l:K\\!+\\!1\right)\right]_{ij}\right|\right)\\!\lVert\mathbf{x}\left(K\\!+\\!1\right)\rVert_{1}\\!+\\!\frac{1}{N\eta^{N}}\times$
$\displaystyle\left|\mathbf{1}^{\top}\mathbf{x}\left(K\\!+\\!1\right)\right|\left(\underset{j}{\max}\left|\left[\mathbf{M}\left(K\\!+\\!l:K\\!+\\!1\right)\right]_{ij}\right|\right)\lVert\mathbf{y}\left(K\\!+\\!1\right)\rVert_{1}$
$\displaystyle\leq$
$\displaystyle\frac{2}{\eta^{N}}\left(\underset{j}{\max}\left|\left[\mathbf{M}\left(K+l:K+1\right)\right]_{ij}\right|\right)\lVert\mathbf{x}\left(K+1\right)\rVert_{1}$

where the second inequality uses the relation
$y_{i}\left(K+l+1\right)\geq\eta^{N}$, and the last inequality is based on
$\lVert\mathbf{y}\left(K+1\right)\rVert_{1}=\sum\nolimits_{i=1}^{N}{\left|y_{i}\left(K+1\right)\right|}=\mathbf{1}^{\top}\mathbf{y}\left(K+1\right)=N$
and
$\left|\mathbf{1}^{\top}\mathbf{x}\left(K+1\right)\right|\leq\lVert\mathbf{x}\left(K+1\right)\rVert_{1}$.
Further taking into account (40), we have

$\displaystyle\left|z_{i}\left(K+l+1\right)-\bar{x}^{0}\right|\leq
2\eta^{-N}c_{0}\lVert\mathbf{x}\left(K+1\right)\rVert_{1}\rho^{l-1}.$

Thus, one can derive

$\displaystyle\lVert\mathbf{z}\left(K+l+1\right)-\bar{x}^{0}\mathbf{1}\rVert\leq
c_{1}\rho^{K+l+1},$ (44)

where
$c_{1}=2\sqrt{N}c_{0}\lVert\mathbf{x}\left(K+1\right)\rVert_{1}\eta^{-N}\rho^{-K-2}$.
Consequently, for $k\geq K+2$, we have
$\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert\leq
c_{1}\rho^{k}$.

Case II: We consider the case of $k\geq K+1$. Using
$y_{i}\left(k+1\right)=\left[\mathbf{M}\left(k:0\right)\mathbf{1}\right]_{i}+N\varphi_{i}\left(k\right)\geq\eta^{N}$,
we can arrive

$\displaystyle\frac{x_{i}\left(k\right)}{y_{i}\left(k\right)}-\bar{x}^{k}=\frac{x_{i}\left(k\right)}{y_{i}\left(k\right)}-\frac{\mathbf{1}^{\top}\mathbf{x}\left(k\right)}{N}$
$\displaystyle=$
$\displaystyle\frac{x_{i}\left(k\right)}{y_{i}\left(k\right)}-\frac{\mathbf{1}^{\top}\mathbf{x}\left(k\right)\left(\left[\mathbf{M}\left(k-1:0\right)\mathbf{1}\right]_{i}+N\varphi_{i}\left(k-1\right)\right)}{Ny_{i}\left(k\right)}.$

Then, we compute $\left|z_{i}\left(k\right)-\bar{x}^{k}\right|$ as

$\displaystyle\left|z_{i}\left(k\right)-\bar{x}^{k}\right|$
$\displaystyle\leq$
$\displaystyle\frac{\left|x_{i}\left(k\right)\right|}{y_{i}\left(k\right)}+\frac{\left|\mathbf{1}^{\top}\mathbf{x}\left(k\right)\left[\mathbf{M}\left(k-1:0\right)\mathbf{1}\right]_{i}\right|}{Ny_{i}\left(k\right)}$
$\displaystyle+\frac{\left|\mathbf{1}^{\top}\mathbf{x}\left(k\right)\varphi_{i}\left(k-1\right)\right|}{y_{i}\left(k\right)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\eta^{N}}\left|x_{i}\left(k\right)\right|+\frac{1}{N\eta^{N}}\left|\mathbf{1}^{\top}\mathbf{x}\left(k\right)\right|\left(\underset{j}{\max}\left|\left[\mathbf{M}\left(k-1:0\right)\right]\right|_{ij}\right)$
$\displaystyle+\frac{1}{\eta^{N}}\left|\mathbf{1}^{\top}\mathbf{x}\left(k\right)\right|\left(\underset{i}{\max}\,\,\varphi_{i}\left(k-1\right)\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{\eta^{N}}\lVert\mathbf{x}\left(k\right)\rVert_{1}+\frac{1}{N\eta^{N}}\lVert\mathbf{x}\left(k\right)\rVert_{1}c_{0}\rho^{k-1}$
$\displaystyle+\left(\frac{1}{\eta^{N}}-\frac{\left(N-1\right)}{N}\right)\lVert\mathbf{x}\left(k\right)\rVert_{1},$

where the last inequality uses the relation
$\varphi_{i}\left(k-1\right)\geq\frac{\eta^{N}}{N}$ for all $i\in\mathcal{V}$
and $k\geq 1$. Specifically, as $\bm{\varphi}\left(k\right)$ is a stochastic
vector, $\sum\nolimits_{i=1}^{N}{\varphi_{i}\left(k\right)}=1$ holds, which in
turn gives $\max_{i\in\mathcal{V}}\,\,\varphi_{i}\left(k-1\right)\leq
1-\left(N-1\right)\eta^{N}/N$. Thus, it yields that

$\displaystyle\lVert\mathbf{z}\left(k\right)-\bar{x}^{k}\mathbf{1}\rVert$
$\displaystyle\leq$
$\displaystyle\sqrt{N}\eta^{-N}\lVert\mathbf{x}\left(k\right)\rVert_{1}+N^{-1/2}\eta^{-N}\lVert\mathbf{x}\left(k\right)\rVert_{1}c_{0}\rho^{k-1}$
$\displaystyle+\sqrt{N}\eta^{-N}\lVert\mathbf{x}\left(k\right)\rVert_{1}$
$\displaystyle\leq$ $\displaystyle
c_{2}\lVert\mathbf{x}\left(k\right)\rVert_{1}+c_{3}\lVert\mathbf{x}\left(k\right)\rVert_{1}\rho^{k},$

where $c_{2}=2\sqrt{N}\eta^{-N}-\left(N-1\right)/\sqrt{N}$ and
$c_{3}=N^{-1/2}\eta^{-N}c_{0}\rho^{-1}$.

Combining Cases I and II and defining

$\displaystyle\\!\\!\\!\\!c\\!\triangleq\\!\max\\!\left\\{\\!\\!\\!\\!\begin{array}[]{c}c_{1},\left(c_{2}\\!+\\!c_{3}\right)\\!\lVert\mathbf{x}\left(0\right)\rVert_{1},\left(c_{2}\rho^{-1}\\!+\\!c_{3}\right)\\!\lVert\mathbf{x}\left(1\right)\rVert_{1},\\\
\cdots,\left(c_{2}\rho^{-K-1}\\!+\\!c_{3}\right)\lVert\mathbf{x}\left(K\\!+\\!1\right)\rVert_{1}\\\
\end{array}\\!\\!\\!\\!\right\\},$ (45)

one derives, for all $k\in\mathbb{N}$,

$\displaystyle\lVert\mathbf{z}\left(k\right)-\bar{x}^{0}\mathbf{1}\rVert\leq
c\rho^{k},$

which is the desired result. ∎