1

Privacy-preserving Average Consensus: Privacy
Analysis and Optimal Algorithm Design

arXiv:1609.06368v2 [cs.SY] 9 Feb 2017

Jianping He1,2 , Lin Cai2 , Chengcheng Zhao3 , Peng Cheng3 , and Xinping Guan1

Abstract—Privacy-preserving average consensus aims to guarantee the privacy of initial states and asymptotic consensus on
the exact average of the initial value. In existing work, it is
achieved by adding and subtracting variance decaying and zerosum random noises to the consensus process. However, there
is lack of theoretical analysis to quantify the degree of the
privacy protection. In this paper, we introduce the maximum
disclosure probability that the other nodes can infer one node’s
initial state within a given small interval to quantify the privacy. We develop a novel privacy definition, named (, δ)-dataprivacy, to depict the relationship between maximum disclosure
probability and estimation accuracy. Then, we prove that the
general privacy-preserving average consensus (GPAC) provides
(, δ)-data-privacy, and provide the closed-form expression of
the relationship between  and δ. Meanwhile, it is shown that
the added noise with uniform distribution is optimal in terms
of achieving the highest (, δ)-data-privacy. We also prove that
when all information used in the consensus process is available,
the privacy will be compromised. Finally, an optimal privacypreserving average consensus (OPAC) algorithm is proposed to
achieve the highest (, δ)-data-privacy and avoid the privacy
compromission. Simulations are conducted to verify the results.
Index Terms—Average consensus, Data privacy, Optimal algorithm, Disclosure probability.

I. I NTRODUCTION
Consensus has attracted extensive attention over the past
decades, since it is an efficient algorithm for distributed computing and control. A consensus algorithm refers to the action
that nodes in the network reach a global agreement regarding a
certain opinion using their local neighbors’ information only
[1]. Due to the strong robustness and scalability, consensus
has been applied in a variety of areas, e.g., coordination and
cooperation [2], [3], distributed estimation and optimization
[4], [5], sensor fusion [6], distributed energy management [7]
and sensing scheduling [8], and time synchronization [9]–[11].
Average consensus is the most commonly adopted consensus algorithm, where the agreement reached by the algorithm
equals the average of all nodes’ initial states. For traditional
average consensus algorithms, each node will broadcast its
real state to neighbor nodes during consensus process. Hence,
under traditional average consensus algorithms, the state information of each node is disclosed to its neighbor nodes.
1: Department of Automation, Shanghai Jiao Tong University, and Key Laboratory of System Control and Information Processing, Ministry of Education
of China, Shanghai, China jianpinghe.zju@gmail.com
2: The Dept. of Electrical & Computer Engineering at
the University of Victoria, BC, Canada jphe@uvic.ca;

jianpinghe.zju@gmail.com; cai@ece.uvic.ca
3: The State Key Lab. of Industrial Control Technology and Innovation Joint
Research Center for Industrial Cyber Physical Systems, Zhejiang University,
China zccsq90@gmail.com; pcheng@iipc.zju.edu.cn

However, in some applications, the initial states of nodes are
private information, which means that nodes do not want to
release their real initial states to other nodes [16]. For example,
consensus algorithm is adopted in social networks for a group
of members to compute the common opinion on a subject
[17]. In this application, each member may want to keep his
personal opinion on the subject secret to other members. Also,
in the multi-agent rendezvous problem [18], a group of nodes
want to eventually rendezvous at a certain location, while the
participators may not want to release their initial locations to
others. This means that when the privacy is concerned, each
node’s real state may not be available to the other nodes, and
thus the traditional consensus algorithm becomes invalid.
Recently, researchers have investigated the privacypreserving average consensus problem, which aims to guarantee that the privacy of initial state is preserved while average
consensus can still be achieved [12]–[16]. The basic idea is to
add random noise to the real state value during the communication to protect the privacy, and then carefully design the
noise adding process such that average consensus is achieved.
For example, Huang et al. [13] designed a differentially private
iterative synchronous consensus algorithm by adding independent and exponentially decaying Laplacian noises to the
consensus process. Their algorithm can guarantee differential
privacy. As the algorithm may converge to a random value,
the exact average consensus may not be guaranteed. Nozari et
al. [14] pointed out and proved that it is impossible to achieve
average consensus and differential privacy simultaneously.
Hence, they design a novel linear Laplacian-based consensus
algorithm, which guarantees that an unbiased estimate of
the average consensus can be achieved almost surely with
differential privacy. Manitara and Hadjicostis [15] proposed
a privacy preserving average consensus algorithm by adding
correlated noises to the consensus process. The proposed
algorithm guarantees the initial state of each node cannot be
perfectly inferred by the other “malicious” nodes. A sufficient
condition is provided under which the privacy of benign
agents’ initial states are preserved. More recently, Mo and
Murray in [16] well addressed the privacy-preserving average
consensus problem by designing a novel PPAC algorithm,
where exponentially decaying and zero-sum normal noises
are added to traditional consensus process. They proved that
PPAC algorithm achieves the exact average consensus in
the mean-square sense, and also proved that the algorithm
achieves minimum privacy breach in the sense of disclosed
space. Braca et al. in [22] examined the interplay between
learning and privacy over multi-agent consensus networks.
They provided an analytical characterization of the interplay

2

between learning and privacy for the consensus perturbing and
preserving strategy, respectively.
However, there is lack of theoretical results to quantify the
degree of the privacy protection and what is the relationship
between the estimation accuracy and privacy. To fill this gap,
in this paper, we provide theoretical privacy analysis for the
GPAC algorithm (consider the general noise adding process)
in the sense of the maximum disclosure probability that other
nodes can infer one node’s initial state within a given small
interval (a given estimation accuracy). A privacy definition,
named (, δ)-data-privacy, which is first introduced in our
previous work [21], is exploited to depict the maximum disclosure probability. This privacy definition reveals the relationship
between privacy and estimation accuracy. We provide theoretical results to quantify the degree of the privacy preservation
and demonstrate the quantitative relationship of the estimation
accuracy and the privacy under the GPAC algorithm. Based on
the analysis, it is found that the noise with uniform distribution
is the optimal one in terms of achieving the highest (, δ)data-privacy, and the exact initial state of a node can be
perfectly inferred, i.e., privacy is compromised, when a node
has all information used in the consensus process. Hence, to
solve this problem, we design a novel OPAC algorithm to
achieve average consensus as well as data-privacy. The main
contributions of this paper are summarized as follows.
• We prove that the GPAC algorithm provides (, δ)-dataprivacy, and obtain a closed-form expression of the
relationship between the estimation accuracy and the
privacy (the relationship between  and δ).
• We prove that for the added random noises, the uniform
distribution is optimal in the sense that a PPAC algorithm
can achieve the highest privacy when the mean and
variance of noises are fixed.
• We prove that when all the information used in the
consensus process are available for the estimation, the
maximum disclosure probability will converge to one,
i.e., the initial state of a node is perfectly inferred. This
result reveals how the exact initial state can be inferred.
• We design a novel OPAC algorithm to achieve average consensus while guarantees the highest (, δ)-dataprivacy. It is proved that OPAC algorithm converges to
the exact average consensus, and avoids the privacy to
be lost even if all the information used in the consensus
process is available for the estimation.
The remainder of this paper is organized as follows. Section
II introduces preliminary results and problem formulation. In
Section III, we provide theoretical results on the degree of
privacy pretection. The OPAC algorithm is proposed in Section
IV. Section V verifies the main results and conclusions are
given in Section VI.
II. P RELIMINARIES AND P ROBLEM F ORMULATION
The network is abstracted as an undirected and connected
graph, G = (V, E), where V is the set of nodes and E is
the set of the communication links (edges) between nodes.
(i, j) ∈ E if and only if (iff) nodes i and j can communicate
with each other. Let Ni be the neighbor set of node i, where
j ∈ Ni iff (i, j) ∈ E, i.e., Ni = {j|j ∈ V, (i, j) ∈ E, j 6= i}.

A. Average Consensus
Suppose that there are n (n ≥ 3) nodes in the network
(i.e., |V | = n), and each node i has an initial scalar state
xi (0), where xi (0) ∈ R. For an average consensus algorithm,
each node will communicate with its neighbor nodes and
update its state based on the received information to obtain
the average of all initial state’s values. Hence, the traditional
average consensus algorithm is given as follows,
X
xi (k + 1) = wii xi (k) +
wij xj (k),
(1)
j∈Ni

for ∀i ∈ V , which can be written in the matrix form as
x(k + 1) = W x(k),

(2)

where wii and wij are weights, and W is the weight matrix.
It is well known from [19] that if, 1) wii > 0, and wij > 0 for
(i, j) ∈ E and wij = 0 for otherwise; and 2) W is a doubly
stochastic matrix, then average consensus can be achieved by
(1), i.e.,
Pn
x` (0)
= x̄.
(3)
lim xi (k) = `=1
k→∞
n
When the privacy of nodes’ initial states are concerned, all
nodes are unwilling to release its real state to the neighbor
nodes at each iteration. It means that each xj (k) is unavailable
in (1). To preserve the privacy of nodes’ initial states, a widely
used approach is to add a random noise to the real state value
when a node needs to communicate with its neighbor nodes
at each iteration. We define a new state as
x+
i (k) = xi (k) + θi (k), i ∈ V,

(4)

where θi (k) is the added random noise for privacy preservation
at iteration k. With the noise adding process, the update
equation (1) is changed to,
X
xi (k + 1) = wii x+
wij x+
(5)
i (k) +
j (k)
j∈Ni

= wii [xi (k) + θi (k)] +

X

wij [xj (k) + θj (k)],

(6)

j∈Ni

for ∀i ∈ V . Therefore, a privacy-preserving average consensus algorithm is to design the added noises (including the
distribution and the correlations among them), such that the
goal of (1) is achieved under (5). Note that in (4), the noise
θi (k) is a general random noise (where its distribution is not
fixed), the algorithm (4)–(6) is thus named as the general
privacy-preserving average consensus (GPAC) algorithm in the
remainder part of this paper.
B. Privacy Definitions
Under (4), the broadcast information sequence of node i is
+
+
x+
i (0), xi (1), ..., xi (k), which will be received by its neighbor nodes. Hence, each neighbor node j can infer/estimate
the initial state xi (0) with the received information sequence
from node i. Note that each of the information output, x+
i (k),
equals the weighted sum of the received information in the
previous round plus a noise. Based on the information output,
node j will take the probability over the space of all noises

3

{θi (k)}∞
k=0 (where the space is denoted by Θ) to estimate
the values of the added noises. It then will infer xi (0) by
using the difference between each information output and the
estimated noises, i.e., x̂i (0) = x+
i (k) − θ̂i (k), where θ̂i (k)
is the estimation of random noise θik (θik = x+
i (k) − xi (0)).
Under this estimation, we have
n
o
Pr {|x̂i (0) − xi (0)| ≤ } = Pr |θ̂i (k) − θik | ≤  , (7)
where  ≥ 0 is a small constant.
To investigate the relationship between the estimation accuracy and privacy, by referring to [21], we then introduce an
privacy definition, named (, δ)-data-privacy, where 0 ≤  and
0 ≤ δ ≤ 1, as follows.
Definition 2.1: A GPAC algorithm provides (, δ)-dataprivacy, if and only if (iff),
δ=

max
θ̂i (k)∈Θ,k≥0

θik

Pr{|θ̂i (k) −

θik |

≤ },

x+
i (k)

simplicity, we assume that θi (k) and θj (k) are independently
and identically distributed (i.i.d) ∀k ≥ 0 and i 6= j. Let X be
the output of a random variable whose distribution is unknown
and with domain R. Without the knowledge of the distribution,
according to the principle of maximum entropy, we should
take the same probability over all the possible values of the
random variable to estimate the values of X. Therefore, given
an estimation X̂, it is reasonable to assume that
Z ν+
Pr{|X̂ − X| ≤ }  max
fθi (0) (y)dy.
(9)
ν∈Θ

ν−

Then, we define two information sets of node i up to
iteration k as follows,
+
Ii0 (k) = {x+
i (0), ..., xi (k)},

(10)

(8)
and
θik .

=
where
− xi (0) and θ̂i (k) is the estimation of
In the above definition, the estimation accuracy is denoted
by parameter  and the privacy is expressed by parameter δ.
From (8), it follows that δ is the maximum probability that
each neighbor node j can successfully estimate the initial
state xi (0) in a given interval [xi (0) − , xi (0) + ] with the
information output of node i only. δ is thus named as the
maximum disclosure probability.
Definition 2.2: Given an , if algorithms A1 and A2 provide (, δ1 )-data-privacy and (, δ2 )-data-privacy, respectively,
where δ1 < δ2 , then we say that A1 achieves a higher (, δ)data-privacy than A2 .

+
Ii1 (k) ={Ni , wii , wij , x+
i (0), xj (0),
+
..., x+
i (k), xj (k)|j ∈ Ni }.

(11)

The information set Ii0 (k) only includes the states x+
i (`), ` =
0, 1, ..., k, which are used for communication at iteration `.
Thus, its neighbor nodes can easily obtain Ii0 (k) by storing
the information received from node i at each iteration. The
information set Ii1 (k) includes all information used in consensus process (6) for node i. Other nodes may obtain these
information by an eavesdropping attack.

C. Problem Formulation

A. Privacy of the Algorithm

In this paper, we will investigate the privacy of the GPAC
algorithm (4)–(6) based on the definition of (, δ)-data-privacy,
and then design an optimal privacy-preserving average consensus (OPAC) algorithm in terms of (, δ)-data-privacy protection. In summary, we will consider the following four critical
problems: i) how to quantify and analyze the privacy of the
GPAC algorithm; ii) how will the distribution and correlation
of the added random noises affect the privacy; iii) when and
how will a node’s exact initial state be inferred by the other
nodes; iv) how to achieve the optimal (, δ)-data-privacy and
the exact average consensus, and avoid the privacy of nodes’
initial states to be lost.

In this subsection, based on the definition of (, δ)-dataprivacy, we first analyze the privacy of the GPAC algorithm
and reveal the relationship between the privacy and estimation
accuracy, when Ii0 (k) is available only.
Theorem 3.1: If Ii0 (k) is the only information available to
node j to estimate the value of xi (0) at iteration k, then
δ(k) =

max
θ̂i (k)∈Θ,k∈N+

= max Pr{|θ̂i (0) − θi0 | ≤ |Ii0 (0) }

Before presenting the main results, we first give the basic
assumptions and the information set used for state estimation.
Assume that the distribution and the correlation of the random
variable θi (k), k = 0, 1, ..., and the update rule of the GPAC
algorithm are available to all nodes. The full topology information and n are assumed to be unknown to any node, which
means that each node cannot know the neighbor set of its
neighbor nodes and the number of nodes in the whole network.
The initial states of nodes are assumed to be independent
from each other. For estimation, if there is no information
of a variable, then the variable is viewed with domain R. For

(12)

θ̂i (0)∈Θ

Z

θ̂i (0)+

= max
θ̂i (0)∈Θ

III. P RIVACY A NALYSIS OF GPAC

Pr{|θ̂i (k) − θik | ≤ |Ii0 (k) }

fθi (0) (y)dy,

(13)

θ̂i (0)−

i.e., the relationship between the privacy and the estimation
accuracy always satisfies (13), and the maximum disclosure
probability is not increased with iteration.
Proof: We first prove that, under Ii0 (0), (13) holds. With
0
Ii (0), node j can estimate xi (0) based on the fact that
0
x+
i (0) = xi (0) + θi (0) = xi (0) + θi ,

(14)

and the corresponding estimation x̂i (0) satisfies
x̂i (0) = x+
i (0) − θ̂i (0).

(15)

4

Then, for any estimation θ̂i (0), we have
n
o
Pr |θ̂i (0) − θi0 | ≤ |Ii0 (0)
o
n
= Pr θi (0) ∈ [θ̂i (0) − , θ̂i (0) + ]|Ii0 (0)
Z θ̂i (0)+
=
fθi (0)|I0 (0) (y)dy

n
o
Pr |θ̂i (1) − θi1 | ≤ |Ii0 (1)
o
n
≤ Pr |θi1 (1) − θ̂i1 (1)| ≤ |Ii0 (1),wii
Z z+
≤ max
fθi (0) (y)dy,
z∈Θ

(21)

z−

i

θ̂i (0)−

Z

θ̂i (0)+

≤ max
θ̂i (0)∈Θ

that

fθi (0) (y)dy,

(16)

θ̂i (0)−

which means that (13) holds under information Ii0 (0) at
iteration k = 0.
Then, we prove that (13) holds under Ii0 (1). With Ii0 (1),
node j can estimate xi (0) by using the fact of both (14) and
the following equation for estimation,
xi (1) + θi (1)
x+
i (1)
=
wii
wii
X wil
1
=x+
x+ (0) +
θi (1)
i (0) +
wii l
wii
l∈Ni
X wil
1
=xi (0) + θi (0) +
θi (1) +
x+ (0). (17)
wii
wii l
l∈Ni

Using (14) only, we have
n
o
Pr |θ̂i (0) − θi0 | ≤ |Ii0 (1)
Z θ̂i (0)+
=
fθi (0)|I0 (1) (y)dy
i

θ̂i (0)−

Z

θ̂i (0)+

≤ max
θ̂i (0)∈Θ

fθi (0) (y)dy.

(18)

θ̂i (0)−

Then, we consider the estimation using (17) only. Let
θi1 = θi (0) +

X wil
1
θi (1) +
x+ (0)
wii
wii l
l∈Ni

1
θi (1) + θi1 (1)
= θi (0) +
wii
= θi1 (0) + θi1 (1).

(19)

For any estimation θ̂i (1) (the estimation of θi1 ), we have
n
o
Pr |θ̂i (1) − θi1 | ≤ |Ii0 (1)
n
o
≤ Pr |θi1 − θ̂i (1)| ≤ |Ii0 (1),wii ,θi (1),θi (0)
n
o
≤ Pr |θi1 − θi1 (0) − θ̂i (1) + θi1 (0)| ≤ |Ii0 (1),wii ,θi1 (0)
n
o
≤ Pr |θi1 (1) − θ̂i1 (1)| ≤ |Ii0 (1),wii ,
(20)
where θ̂i1 (1) = θ̂i (1) − θi1 (0) can be viewed as one of the
estimation of θi1 (1). Since the initial states of nodes are
independent from each other and the topology information
is not available for estimating/inferring, there is at least one
variable included in θi1 (1) which is unknown to the other
nodes. Hence, θi1 (1) is viewed as a random variable in (20)
and its distribution is not available to the estimation. It follows

where we have used the assumption (9). Meanwhile, note that
one node can combine (14) and (17) together for estimation.
In this case, we have
Pr{x̂i (0) ∈ [xi (0) − , xi (0) + ]|Ii0 (1) }
Z t1 + Z t2 +
fθi0 ,θi1 (y, z)dzdy
≤ max
t1 ,t2 ∈Θ t −
t2 −
1
Z t1 + Z t2 +
fθi1 |θi0 (z|y)fθi0 (y)dzdy
≤ max
t1 ,t2 ∈Θ t −
t2 −
1
Z t+
fθi (0) (y)dy.
≤ max
t∈Θ

(22)

t−

From (18), (21) and (22), one concludes that (13) holds under
information Ii0 (1) at iteration k = 1.
Following the similar analysis, we can prove that (13) holds
under information set Ii0 (k) at any iteration k. It means that
δ(k) is not an increased function of iteration k, although there
are more information of Ii0 (k) than Ii0 (0) for k > 0.
We thus have completed the proof.
From the above proof, it is observed that the privacy is not
decreased with iteration when only the information set Ii0 (=
{Ii0 (k)|k = 0, 1, ..., ∞}) is available for estimation. The main
reason is that based on Ii0 , node j cannot know the neighbor
set information of node i, so that after one iteration there are
unknown information embedded into x+
i (k) for k ≥ 1. Hence,
after one iteration, using x+
(k)
for
k
≥
1 cannot improve the
i
estimation accuracy. Also, one can see that the value of δ does
not depend on the estimation approaches. Hence, we state the
following theorem.
Theorem 3.2: If Ii0 is the only information available to the
other nodes to estimate the value of xi (0), the GPAC algorithm
achieves (, δ)-data-privacy, where  and δ satisfy
Z θ̂i (0)+
δ = max
fθi (0) (y)dy
(23)
θ̂i (0)∈Θ

θ̂i (0)−

and lim→0 δ = 0.
Remark 3.3: It should be noticed that the results in the
above two theorems are obtained under the assumption that
the topology information is unknown to the nodes. If the
assumption is relaxed, the above results could not be true
for the GPAC algorithm in some cases. For example, if the
topology
is available and Ni ⊆ Nj , then x+
i (0)
P information
wij +
wil +
and
l∈Ni wii xl (0) = wii xj (0) in (17) are available to
node j. It leads to that the value of θi (1) is released, which
may decrease the uncertainty of θi (0) due to the correlation
between them. Then, fθi (0)|I0 (1) (y) in (18) will have a smaller
i
variance than fθi (0) (y), such that δ increases w.r.t. k in this
case. Therefore, (12) and (13) are no longer guaranteed.
From the above theorem, one sees that δ depends only on
fθi (0) (y) and  since the estimation θ̂i (0) can be any value in

5

the domain of θi (0). Thus, δ is a function of fθi (0) (y) and ,
i.e, δ = δ(fθi (0) (y), ). Based on Definition 2.2, a smaller δ
can provide a higher (, δ)-data-privacy for any given . Then,
we aim to find the optimal distribution for θi (0) such that the
algorithm can achieve the highest (, δ)-data-privacy.

Since f1 (y) is a uniform distribution satisfying (26),
f1 (y) − f2 (y) > 0, y ∈ [−1, 1].
It directly follows that
Z 1
Z
f1 (y)dy −
−1

B. Optimal Noise Distribution
In this subsection, we find an optimal distribution for the
noise adding process in the sense of achieving the highest
(, δ)-data-privacy for the GPAC algorithm. Note that a smaller
 means a higher accuracy estimation. It means that when 
becomes smaller, the value of δ is more important for the
privacy preservation. Hence, we define the optimal distribution
for privacy concerns as follows.
Definition 3.4: Let fθ∗i (0) (y) be the optimal distribution of
θi (0), it means that for any given distribution fθ1i (0) (y), there
exists an 1 such that δ(fθ∗i (0) (y), ) < δ(fθ1i (0) (y), ) holds
for ∀ ∈ (0, 1 ].
To obtain the optimal distribution described in Definition
3.4, we define arg minfθi (0) (y) δ = fθ∗i (0) (y). Then, we formulate the following minimization problem,
min

(24)

Var{θi (0)} = σ 2 .
The solution of (24) is the optimal distribution for the added
noises with a given mean and variance in terms of (, δ)-dataprivacy for the GPAC algorithm.
Theorem 3.5: If Ii0 is the only information available to node
j to estimate the value of xi (0), then the optimal solution of
problem (24) is that

√ √
 √1 , if y ∈ [− 3σ, 3σ],
∗
(25)
fθi (0) (y) = 2 3σ

0,
otherwise,
i.e., given the finite variance, the uniform distribution is
optimal.
Proof: We prove this theorem by contradiction. Without
loss of generality, we assume that σ 2 = 13 . Let f1 (y) and
f2 (y) be the PDF of two random variables with mean 0 and
variance σ 2 = 31 , and they follow a uniform and non-uniform
distribution, respectively. Clearly, we have

 1 , if y ∈ [−1, 1],
f1 (y) = 2
(26)
 0, otherwise.
Suppose that the non-uniform distribution f2 (y) is the
optimal distribution. From Definition 3.4, there exists an 2 ,
such that
Z t+
Z t+
max
f1 (y)dy > max
f2 (y)dy,
(27)
t∈R

t−

holds for ∀ ∈ (0, 2 ]. Since the above equation holds for
arbitrarily small value of , we infer that
max f1 (y) > max f2 (y).
y∈R

(28)

R1
From the definition of a PDF, we have −1 f1 (y)dy = 1. Then,
we infer from (28) that
Z 1
f2 (y)dy < 1.
(29)
−1

1
3,

Since both f1 (y) and f2 (y) have mean 0 and variance σ 2 =
we have
Z +∞
Z ∞
f1 (y)y 2 dy −
f2 (y)y 2 dy = 0,
(30)
−∞

−∞

which means that
Z
Z 1
(f1 (y) − f2 (y)) y 2 dy =
−1

−1

Z
+

−∞

+∞ 

f2 (y)y 2 dy.

1

(31)

s.t. E{θi (0)} = 0,

t−

f2 (y)dy > 0.

−1

δ

fθi (0) (y)

t∈R

1

y∈R

For the left hand side of (31), we have
Z 1
Z 1
(f1 (y) − f2 (y)) y 2 dy <
(f1 (y) − f2 (y)) dy
−1
−1
Z 1
=1−
f2 (y)dy.
(32)
−1

R +∞
For the right hand side of (31), since we have −∞ f2 (y)dy =
1 and (29), it holds that
Z −1 Z +∞ 
Z −1 Z +∞ 
+
f2 (y)y 2 dy >
+
f2 (y)dy
−∞
1
−∞
1
Z 1
=1−
f2 (y)dy.
(33)
−1

Combining (31), (32) and (33) renders a contradiction that
Z 1
Z 1
1−
f2 (y)dy <
(f1 (y) − f2 (y)) y 2 dy
−1
−1
Z 1
<1−
f2 (y)dy.
(34)
−1

Hence, we cannot find a non-uniform distribution f2 (y) such
that the value of δ is smaller than that under uniform distribution f1 (y). It means that, given the finite variance, the uniform
distribution is the optimal solution of (24). Then, based on the
definition of uniform distribution, it is not difficult to obtain
(25).
We thus have completed the proof.
We have known that for the existing PPAC algorithm
proposed in [16], the normal distribution noises is used in
the noise adding process. It follows from Theorem 3.2 that
the PPAC algorithm provides (, δ)-data-privacy with


Z 
1
y2
δ= √
exp − 2 dy.
2σ
σ 2π −

6

If we use the uniform distribution noises to substitute the
normal distribution noises, it can still provide (, δ)-dataprivacy, where δ = √3σ . Clearly, given a small  ( σ 2 ),
we have


Z 
1
y2

√
< √
exp − 2 dy,
2σ
3σ
σ 2π −
which means that the privacy of PPAC is enhanced.
C. Privacy Compromission
In this subsection, we reveal that for the GPAC algorithm,
when Ii1 (k) (including more information than Ii0 (k), e.g.,
the topology information and information used in consensus
process) is available to other nodes for estimation, the exact
initial state of node i can be perfectly inferred, and thus the
privacy of the initial state is compromised.
Theorem 3.6: If the information set Ii1 (k) of node i is
available to the other nodes for estimation, then
Z θ̂i (0)+
δ(k) ≥ max
fθi (0)|θi (1),...,θi (k) (y)dy, ∀k ≥ 0,
θ̂i (0)∈Θ

θ̂i (0)−

(35)
where fθi (0)|θi (1),...,θi (k) (y) is the conditional
P∞PDF of θi (0)
given conditions θi (1), ..., θi (k). Then, if
`=0 θi (`) = 0,
we have δ = 1, i.e., xi (0) is disclosed and the privacy is
compromised.
Proof: Based on the information set Ii1 (k), the information of weights and states used in (5) is available. That is
the state sequence xi (1), xi (2), ..., xi (k) of node i is released
to other nodes. Then, with (4), one obtains the values of
θi (1), θi (2), ...., θi (k). Thus, when k > 0, all the adding noises
and the states of node i are available to other nodes, except
xi (0) and θi (0).
Then, under information set Ii1 (k), using (14), we have
n
o
Pr |θ̂i (0) − θi0 | ≤ |Ii0 (k)
Z θ̂i (0)+
=
fθi (0)|I0 (k) (y)dy
i

θ̂i (0)−

Z

θ̂i (0)+

=

fθi (0)|θi (1),...,θi (k) (y)dy.

(36)

i.e., θi (0) is fixed and no longer a random variable given
θi (1), θi (2), ...., θi (∞). It follows that
Z θ̂i (0)+
lim max
fθi (0)|θi (1),...,θi (k) (y)dy = 1,
k→∞ θ̂i (0)∈Θ

θ̂i (0)−

which implies that δ = 1. Actually, when both x+
i (0) and
θi (0) in (14) are disclosed, xi (0) is disclosed.
We thus have completed the proof.
Consider the existing PPAC algorithms, e.g., [16], [21]. One
obtain the correlation of the added noises satisfies
k
X

θi (`) = θi (0) +

`=0

k
X



%` νi (`) − %`−1 νi (` − 1)

`=1

= νi (0) − %0 νi (0) + %1 νi (1) − %1 νi (1) + %2 νi (2)
− ... − %k−1 νi (k − 1) + %k νi (k)
= %k νi (k) = φi (k),

(39)

where νi (k) is a random variable with fixed mean (= 0)
2
and variance (= σP
). Given θi (1), ..., θP
i (k), we obtains that
k
k
θi (0) = φi (k) − `=1 θi (`), where
`=1 θi (`) is known.
Then, we have
n
o
Pr |θ̂i (0) − θi (0)| ≤ |Ii1 (k)
n
o
= Pr |φ̂i (k) − φi (k)| ≤ 
Z φ̂i (k)+
=
fφi (k) (y)dy,
(40)
φ̂i (k)−

and
Z

θ̂i (0)+

fθi (0)|θi (1),...,θi (k) (y)dy

max
θ̂i (0)∈Θ

θ̂i (0)−

Z

φ̂i (k)+

fφi (k) (y)dy,

= max
θ̂i (0)∈Θ

φ̂i (k)−

which satisfies (35). When k → ∞, we have
Z φ̂i (k)+
lim max
fφi (k) (y)dy = 1,
k→∞ θ̂i (0)∈Θ

φ̂i (k)−

since the variance of φ̂i satisfies limk→∞ %2k σ 2 = 0, and thus
δ = 1. Therefore, it further verifies the result given in Theorem
3.6.

θ̂i (0)−

According the definition of δ, it follows that
n
o
δ(k) ≥ max Pr |θ̂i (0) − θi0 | ≤ |Ii0 (k)

D. Further Discussion on Privacy

θ̂i (0)∈Θ

Z

θ̂i (0)+

≥ max
θ̂i (0)∈Θ

fθi (0)|θi (1),...,θi (k) (y)dy,

(37)

θ̂i (0)−

which means
P∞ that (35) holds.
When `=0 θi (`) = 0, we have
θi (0) = −

∞
X

θi (`).

(38)

`=1

Since θi (1), θi (2), ...., θi (k) are available under Ii1 (k) for
any integer k, θi (0) is inferred with (38) when k → ∞,

Differential privacy is a well-known and widely used privacy concept in computer and communication area [20], and
it has been employed in control and network systems recently
[23]. A differentially private algorithm promises that any two
similar/close inputs will have approximately the same outputs,
so that an adversary cannot infer from the data output with a
high probability whether the data are associated with a single
user or not. It has been proved by Nozari et al. in [14] that
nodes in the network system cannot simultaneously converge
to the average of their initial states and preserve differential
privacy of their initial states. This motivated us to develop the
definition of the (, δ)-data-privacy. The proposed (, δ)-data
privacy can be used to reveal the relationship between the

7

the maximum data disclosure probability (δ) under a given
estimation accuracy range ().
Consider the general noise adding mechanism that added
a random noise to the initial data for data publishing. It is
well known that when the adding noise is Laplacian noise,
the mechanism ensures differential privacy, but if the noise
is Gaussian or Uniform distribution, the differential privacy
cannot be guaranteed. Hence, the uniform noise is not good
in the sense of differential privacy. However, in term of
(, δ)-data-privacy, it is shown in this paper that both the
Gaussian and Uniform noise are (, δ)-data-private, and using
the Uniform noise can achieve the highest privacy. Clearly,
the privacy of (, δ)-data-privacy is different from that of
differential privacy. It is worth to investigate the relationship
between these two kinds of privacy definition in theory, which
beckons further investigation.
IV. OPAC A LGORITHM
In this section, we design an OPAC algorithm to achieve
the highest (, δ)-data-privacy, and at the same time to avoid
privacy to be compromised even if the information Ii1 (∞) of
each node i is available to other nodes.
A. Algorithm Design
From the privacy analysis in the above section, we note
that the uniform distribution is optimal for the added noise
in terms of achieving the highest (, δ)-data-privacy with δ =
√ (given variance σ). Hence, in each iteration of the OPAC
3σ
algorithm, we will use uniform distribution noise. We also
note that privacy is compromised when Ii1 (∞) is available.
It is because that the nodes can use Ii1 (∞) to obtain the real
values
P∞ of θi (1), θi (2), ...., θi (∞), and then use the correlation
k=0 θi (k) = 0 to infer θi (0), and thus the value of xi (0)
is revealed. To avoid the privacy compromission in this case,
we introduce a secret continuous function Fij (z) : R → R for
node i with respect to its neighbor node j. Suppose that Fij (z)
and Fji (z) are only available to nodes i and j, and Fij (z)
may or may not equal to Fji (z). Then, the OPAC algorithm
is described as follows.

Algorithm 1 : OPAC Algorithm
1: Initialization: Each node i selects
uniform distribution random
√ a√

variable νi (0) from interval [− 3σ, 3σ], and arbitrarily selects
a constant sequence zij (∈ R) for j ∈ Ni .
2: Let θi (0) = νi (0) and x+
i (0) = xi (0) + θi (0). Then, each node
i transmits x+
i (0) and zij to its neighbor node j.
3: Each node i calculates ν̃i (0) by
X
[Fij (zij ) − Fji (zji )] , ∀i ∈ V.
(41)
ν̃i (0) = νi (0) −
j∈Ni

4: Iteration: Each node updates its state with (5).
5: Each node generates
distribution random variable νi (k)
√ a uniform
√

(
θi (k) =

%νi (1) − ν̃i (0),

if k = 1;

%k νi (k) − %k−1 νi (k − 1),

if k ≥ 2,

(42)

where % ∈ (0, 1) is a constant for all nodes.

7: Each node i communicates with its neighbors with x+
i (k).
8: Let k = k + 1 and go to step 4.

difficult to infer that each θi (k) is bounded. Meanwhile, it
follows from (42) that
lim |θi (k)| ≤ lim |%k νi (k) − %k−1 νi (k − 1)|
k→∞
√
√
≤ lim [%k 3σ + %k−1 3σ] = 0,

k→∞

k→∞

which means that the noises are decaying and converge to 0.
Next, we prove that the sum of all nodes’ added noises
equals to zero. Note that
n X
∞
X

n
X

θi (k) =

i=1 k=0

+

θi (0) +

i=1
n X
∞
X

=

n
X
(%νi (1) − ν̃i (0))
i=1

i=1

+

θi (1)

(%k νi (k) − %k−1 νi (k − 1))

νi (0) +

n
X

n
X
i=1

i=1 k=2
n
X

=

B. Convergence and Privacy Analysis
In this subsection, we analyze the convergence and the
privacy of the OPAC algorithm.
Theorem 4.1: Using the OPAC algorithm, we have (3) holds
for ∀i ∈ V , i.e., an exact average consensus is achieved.
Proof: From Theorem 4.1 of [21], we know that if the
added noises in (4) are bounded and decaying, and the sum of
all nodes’ added noises equals zero, then average consensus
can be achieved. In the following, we prove that the added
noises used for the OPAC algorithm satisfy these conditions.
We first prove that the added noises are bounded
√ and
√ exponentially decaying. Clearly, θi (0) = νi (0) ∈ [− 3σ, 3σ] is
bounded. Since each Fij (z) is continuous function, its value
is bounded for any given z. Then, it follows from (41) that
ν̃i (0) is bounded.
√ √ For k ≥ 1, because νi (k) is selected from
interval [− 3σ, 3σ] and θi (k) is generated by (42), it is not

3σ] for k ≥ 1.

from interval [− 3σ,

6: Each node i uses θi (k) in (4) to get x+
i (k), where

(%∞ νi (∞) − %1 νi (1))

i=1
n
X

νi (0) −

i=1

n
X

ν̃i (0),

i=1

where we have used the fact that %∞ νi (∞) = 0. Substituting
(41) into the above equation yields that
n X
∞
X

θi (k) =

i=1 k=0

n
X

νi (0)

i=1

−

n
X


νi (0) −

i=1

=



n X
X

X

(Fij (zij ) − Fji (zji ))

j∈Ni

[Fji (zji ) − Fij (zij )] .

i=1 j∈Ni

Since for each pair of Fji (zji )−Fij (zij ) using in node i, there
exists a pair of Fij (zij ) − Fji (zji ) with negative value using

8

in node j, it follows that
n
X

X

V. P ERFORMANCE E VALUATION

[Fji (zji ) − Fij (zij )] = 0.

i=1 j∈Ni

Pn P∞
Hence, we have i=1 k=0 θi (k) = 0.
Thus, the proof is completed.
The following theorem can be obtained from Theorem 3.2
directly, since OPAC is one of the GPAC algorithm.
Theorem 4.2: If Ii0 is the only information available to the
other nodes to estimate the value of xi (0), then the OPAC
algorithm achieves (, δ)-data-privacy, where δ = √3σ and
lim→0 δ = 0.
Then, the following theorem shows that under Ii1 , the
privacy compromission can be avoided by OPAC.
Theorem 4.3: Suppose that the information set Ii1 of node
i is available to the other nodes and each node has at least
two neighbors (i.e., |Ni | ≥ 2 for all i ∈ V ). Then, the privacy
compromission can be avoided by OPAC.
Proof: It has been known that when Ii1 of node i is
available to other nodes, its neighbor node j can obtain
the
P∞real values of θi (1), θi (2), ...., θi (∞). Then, the value of
k=1 θi (k) is released. Note that
∞
X

θi (k) = (%1 νi (1) − ν̃i (0)) +

k=1

∞
X

θi (k)

k=2
∞

= (%1 νi (1) − ν̃i (0)) + (% νi (∞) − %1 νi (1))
= ν̃i (0).
It means that the value of ν̃i (0) is released and available to
node j. From (41), one sees that ν̃i (0) 6= θi (0)1 and
X
ν̃i (0) = θi (0) −
[Fij (zij ) − Fji (zji )] .
(43)
j∈Ni

Since |Ni | ≥ 2 and only Fij and Fji is known to node j, there
exists Fijo (zijo ) − Fjo i (zjo i ) for j0 ∈ Ni in (43) is not known
by node j. Meanwhile, Fijo (zijo ) −√Fjo i (z
√jo i ) has domain R,
thus one infers that for any c ∈ [− 3σ, 3σ],
Pr{θi (0) = c|ν̃i (0)} = Pr{θi (0) = c}.
Hence, even if the value of ν̃i (0) is released, node j cannot
increase the estimation accuracy of θi (0) with (43). One thus
concludes that based on the OPAC algorithm, the privacy
compromission is avoided.
We thus have completed the proof.
If node i has only one neighbor node j, node j can infer
the value of Fij (zij ) − Fji (zji ). Then, from (43), node j can
obtain the value of θi (0) and xi (0) when ν̃i (0) is known.
Remark 4.4: From the above two theorems, one sees that
using OPAC algorithm, we have δ = √3σ , which is the
optimal privacy that can be achieved from solving problem
(24). Furthermore, δ = √3σ can be guaranteed by OPAC
algorithm under Ii1 (∞). Thus, OPAC algorithm can achieve
much higher (, δ)-data-privacy than the existing PPAC.
1 This is the main difference between OPAC and PPAC algorithm, and the
main reason why OPAC can avoid privacy compromission.

In this section, we conduct simulations to verify the obtained theoretical results and evaluate the performance of the
proposed OPAC algorithm.
A. Simulation Scenario
Consider the network with 50 nodes which are randomly
deployed in a 100m × 100m area, and the maximum communication range of each node is 30m. We consider the
normal distribution and uniform distribution of the added
noises, respectively, where the mean and variance of them
are set 0 and σ 2 = 1. We set % = 0.9. The initial states
of the nodes are randomly selected from [0, 10]. The function,
d(t) = max |xi (t) − x̄|, is defined as the maximum difference
i∈V
between the nodes’ states and the average value.
B. Verification
Fig. 1(a) compares the convergence speed of the PPAC
algorithm using normal and uniform distribution noises, in
which the basic design is the same as PPAC proposed in [16].
It is observed that under the two different distributions, the
PPAC algorithm has the same convergence speed. This justifies
that the convergence speed only depends on the eigenvalues
of the weighted matrix W and the value of % as proved in
[16].
Fig. 1(b) compares the (, δ)-data-privacy under Ii0 with
normal and uniform distribution noises. In simulation, we
conduct 10, 000 simulation runs. For each run, one node first
generates a state θi (0) randomly with the given distribution,
and the other node generates 10, 000 random numbers with the
same distribution and use them as the estimation of θi (0) (i.e.,
θ̂i (0)). Then, one get the probability of |θ̂i (0) − θi (0)| ≤  in
each run, and we use the maximum probability among these in
all runs simulation as the value of δ. For the theoretical results,
we use (23) to calculate the value of δ under two different
distributions. Clearly, one can observe from Fig. 1(b) that
uniform distribution is much better than normal distribution
in the sense of (, δ)-data-privacy. It is also observed that δ in
simulation matches its value in theory.
Fig. 1(c) compares the (, δ)-data-privacy under Ii1 using
normal and uniform distribution noises. The simulations here
are conducted similarly as those in Fig. 1(b), except that
when the iteration increases, the variance of the noises will
be changed to σ 2 = %2k since (40) will be used for estimation
at iteration k. We use (23) to calculate the value of δ, and
the corresponding results are denoted as theoretical results.
Both in simulation and theory, we set  = 0.2. As shown in
Fig. 1(c), the maximum disclosure probability increases with
iteration and will converge to 1, i.e., the privacy decays with
iteration and will eventually be compromised.
C. Evaluation
In this subsection, we will evaluate the performance of the
OPAC algorithm. Using the same setting as the above subsection, the OPAC algorithm can guarantee the similar privacy
as the blue line shown in Fig. 1(b) under Ii1 . This is because

9

uniform distribution:simulation
normal distribution:simulation
uniform distribution:theorem
normal distribution:theorem

0.6
Disclosed Probability

Maximum Difference

4

3

2

1

0

1

0.7
Uniform Distribution
Normal Distribution

0.5
0.4
0.3
0.2
0.1
0

20

40

60

80
Iteration

100

120

0.2

140

0.4

0.6

0.8

ε

(b) privacy under Ii0

0.4
uniform distribution:simulation
normal distribution:simulation
uniform distribution:theorem
normal distribution:theorem

1

0

5

10

15
Iteration

20

25

30

(c) privacy under Ii1

The convergence and privacy comparison under different random noise distribution.

uniform distribution noise is used in OPAC and the secret
function makes the subsequent (k ≥ 1) information cannot
increase the disclosure probability. Therefore, the OPAC can
guarantee much stronger privacy than the GPAC, since it can
achieve the same data-privacy under Ii1 as the GPAC under
Ii0 .
12
x1(k)
x2(k)

States of Nodes

10

x3(k)

8

x4(k)
average

6
4
2
0

20

40

60

80

100

120

140

Iteration

(a) converge to average consensus
5
OPAC
PPAC

Maximum Difference

4

3

2

1

0

20

40

60

80

100

120

140

Iteration

(b) same covergence speed
Fig. 2.

0.6

0.2

(a) convergence
Fig. 1.

0.8
Disclosed Probability

5

The performance evaluation of the OPAC algorithm.

Then, we test the convergence of the OPAC algorithm. Set
Fij = i+2j
50 . As shown in Fig. 2(a), we find that the nodes’
states will converge to the exact average with the OPAC, which
means that an exact average consensus can be achieved by the

proposed algorithm. Fig. 2(b) compares the convergence speed
of the OPAC and PPAC, it is found that they almost have the
same convergence speed. Hence, added secret function will
not affect the convergence speed.
VI. C ONCLUSIONS
In this paper, we investigated the privacy of the GPAC algorithm. We proposed a novel privacy definition, named (, δ)data-privacy, to depict the relationship between privacy and
estimation accuracy, so that the degree of the privacy can be
well quantified. We proved that the GPAC algorithm achieves
(, δ)-data-privacy, and obtained the closed-form expression
of the relationship between  and δ. We also proved that the
noise with uniform distribution guarantee a highest privacy
when  is small enough. We revealed that the privacy will
be lost when the information used in each consensus iteration
is available to the other nodes. Then, to solve this problem
and achieve highest (, δ)-data-privacy, we proposed OPAC
algorithm, followed by the convergence and privacy analysis.
Lastly, simulations are conducted to demonstrate the efficiency
of the proposed algorithm.
R EFERENCES
[1] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, 95(1):
215–233, 2007.
[2] V. Blondel, J. M. Hendrickx, A. Olshevsky, and J. Tsitsiklis, “Convergence in multiagent coordination, consensus, and flocking,” in Proc. of
IEEE CDC, 2005.
[3] W. Ren, B. Randal., and A. Ella, “Information consensus in multivehicle
cooperative control: Collective group behavior through local interaction,”
IEEE Control Systems Magazine, 27(2): 71–82, 2007.
[4] F. Pasqualetti, R. Carli, A. Bicchi, and F. Bullo, “Distributed estimation
and detection under local information,” in Proc. of IFAC, 2010.
[5] G. Mateos, I. Schizas and G. Giannakis, “Distributed recursive leastsquares for consensus-based in-network adaptive estimation,” IEEE
Trans. Signal Processing, 57(11): 4583–4588, 2009.
[6] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor
fusion based on average consensus,” in Proc. of ISIPSN, 2005.
[7] C. Zhao, J. He, P. Cheng and J. Chen, “Consensus-based energy
management in smart grid with transmission losses and directed communication,” IEEE Trans. Smart Grid, DOI: 10.1109/TSG.2015.2513772.
[8] J. He, L. Duan, F. Hou, P. Cheng, and J. Chen, “Multi-period scheduling
for wireless sensor networks: A distributed consensus approach,” IEEE
Trans. Signal Processing, 63(7): 1651-1663, 2015.
[9] L. Schenato and F. Fiorentin, “Average timesynch: A consensus-based
protocol for clock synchronization in wireless sensor networks,” Automatica, 47(9): 1878–1886, 2011.

10

[10] R. Carli, and S. Zampieri, “Network clock synchronization based on the
second order linear consensus algorithm,” IEEE Trans. Automat. Contr.,
59(2): 409–422, 2014.
[11] J. He, P. Cheng, L. Shi, and J. Chen, “Time synchronization in WSNs:
A maximum value based consensus approach,” IEEE Trans. Automat.
Contr., 59(3): 660–674, 2014.
[12] J. Le Ny and G. Pappas, “Differentially private filtering,” IEEE Trans.
Automat. Contr., 59(2): 341–354, 2014.
[13] Z. Huang, S. Mitra, and G. Dullerud, “Differentially private iterative
synchronous consensus.” in Proc. ACM workshop on Privacy in the
electronic society, 2012.
[14] E. Nozari, P. Tallapragada, and J. Cortes, “Differentially private average
consensus: Obstructions, trade-offs, and optimal algorithm design.”
arXiv preprint arXiv:1512.09039, 2016.
[15] N. Manitara and C. Hadjicostis, “Privacy-preserving asymptotic average
consensus.” in Proc. of IEEE ECC, 2013.
[16] Y. Mo, and R. Murray, “Privacy preserving average consensus,” IEEE
Trans. Automat Contr., accepted and to appear, 2016.
[17] M. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, 69(345), 118–121, 1974.
[18] J. Lin, A. S. Morse, and B. D. Anderson, “The multi-agent rendezvous
problem,” in Proc. of IEEE CDC, 2003.
[19] A. Olshevsky and J. Tsitsiklis, “Convergence speed in distributed
consensus and averaging,” SIAM Review, 53(4): 747–772, 2011.
[20] C. Dwork, “Differential privacy,” in Automata, languages and programming, Springer, 1-12, 2006.
[21] J. He, L. Cai, P. Cheng, M. Xing, J. Pan and L. Shi.“Private
and accurate data aggregation against dishonest nodes,”
https://arxiv.org/pdf/1609.06381v2.pdf, 2016.
[22] P. Braca, R. Lazzeretti, S. Marano, and V. Matta. “Learning with privacy
in consensus + obfuscation,” IEEE Signal Processing Letters, 23(9):
1174-1178, 2016.
[23] J. Cortes, G. Dullerud, S. Han, J. Le Ny, S. Mitra, and G. Pappas.
“Differential privacy in control and network systems,” in Proc. of IEEE
CDC, 2016.

