# Network Consensus with Privacy: A Secret Sharing Method

Silun Zhang, Thomas Ohlson Timoudas, and Munther Dahleh *This work was
supported by the Knut and Alice Wallenberg Foundation, KAW 2018.0412. 1
Department of Electrical Engineering and Computer Science and Laboratory for
Information and Decision Systems (LIDS), Massachusetts Institute of
Technology, Cambridge, MA 02139 USA. (silunz@mit.edu)2 Division of network and
systems engineering, KTH Royal Institute of Technology, Sweden.
(ttohlson@kth.se)3 Department of Electrical Engineering and Computer Science
and Institute for Data, Systems, and Society, Massachusetts Institute of
Technology, Cambridge, MA 02139 USA<EMAIL_ADDRESS>
###### Abstract

In this work, inspired by secret sharing schemes, we introduce a privacy-
preserving approach for network consensus, by which all nodes in a network can
reach an agreement on their states without exposing the individual state to
neighbors. With the privacy degree defined for the agents, the proposed method
makes the network resistant to the collusion of any given number of neighbors,
and protects the consensus procedure from communication eavesdropping. Unlike
existing works, the proposed privacy-preserving algorithm is resilient to node
failures. When a node fails, the method offers the possibility of rebuilding
the lost node via the information kept in its neighbors, even though none of
the neighbors knows the exact state of the failing node. Moreover, it is shown
that the proposed method can achieve consensus and average consensus almost
surely, when the agents have arbitrary privacy degrees and a common privacy
degree, respectively. To illustrate the theory, two numerical examples are
presented.

###### Index Terms:

Network consensus, privacy-preserving consensus, cybersecurity, network
control, secret sharing scheme.

##  I Introduction

Several key information and communication technologies are now converging.
Internet of things (IoT), at the confluence of these, is already changing the
ways we gather data, process this data, and ultimately derive value from it.
The unprecedented scale of internet of things is forcing a shift towards
increased decentralization, autonomy, and distributed computing [1, 2, 3, 4].

Privacy and data ownership \- two hotly debated topics, and subject to several
regulations in the recent years, e.g., GDPR - are major concerns in many
internet of things applications [5, 6]. When sensitive data is exchanged
between parties, there are no guarantees that it stays private, or that it
isn’t used for nefarious purposes. For instance, smart meter data could be
used to infer the presence, absence, and even specific activities, of the
occupants in a house [7, 3]. Another example is location and navigation
services, which have become indispensable for today’s driving in increasingly
intricate transport networks. These location-aware services allow their
providers to track the customers’ movements, traveling intentions, and also
living habits from the real-time location information shared with them [8]. In
recent years, many new methods and algorithms have been developed to limit the
need to share data [9], or to preserve the sensitive components when data is
shared in a network [10, 11, 12].

Reliability is another important challenge in many IoT applications. The IoT
networks are often vulnerable to node and/or communication failures due to
various reasons, such as battery exhaustion, extreme environmental conditions,
unprecedented radio interference, or even malicious attacks [13]. Sometimes,
intermittent failures are even to be expected, especially in applications
involving low-energy devices in multi-hop networks, or employing network
protocols developed for scalability and performance, rather than reliability
[14, 15]. In particular, recovery and data reconstruction are big challenges
with such fragile network architectures [16, 17, 18, 19, 20]. Protocols need
to be aware of such situations, and be able to deal with them [21, 22, 23].

The aforementioned changes towards a decentralized network and computation
architecture, have brought with them renewed interest in consensus problems,
which often arise in decentralized decision making and computation. While
consensus problems have a long history, dating back to at least the 1960’s and
1970’s (see, e.g., [24]), they have perhaps never been as relevant as they are
today. The basic problem - namely, to device a method that allows a group of
individuals or agents to reach agreement about some parameters through a
decentralized communication protocol - naturally appears broadly in numerous
IoT contexts, such as sensor fusion [25, 26, 27, 28], load balancing [29, 30],
clock synchronization [31, 32], peak power load shedding [33] and resource
management [34] in smart grids, distributed optimization [35, 36], swarm
coordination [37, 38, 39, 40], distributed and federated learning [41], and
large scale peer-to-peer networks [42, 43].

Several methods have been developed to achieve, at least to some extent,
privacy-preserving consensus algorithms. Methods include masking the true
state by adding deterministic offsets to the messages [44, 45, 46, 47, 48,
49], adding random noise to the messages transmitted amongst nodes [50, 51,
52, 53, 46], and using various encryption schemes [54, 10, 55]. Another
interesting method for computing separable functions without disclosing nodes’
privacy appeared in [56], where agents exchange a set of samples drawn from a
distribution depending on their true state, and the number of these samples
can be tuned by a trade-off between the accuracy and privacy level of the
algorithm. While all of these methods have their own merits and drawbacks,
none of them address the issue of data recovery. In this context, we still
wish to mention [57], which considers the case in which a central server
collects data from all participating nodes, and computes their average, in a
privacy-preserving way. They introduce a mechanism for recovering data from
dropped nodes, but due to the presence of a central coordinator, both the task
of computing the average, and the task of handling dropped nodes, are
completely different from the decentralized situation.

In this paper, we present a network consensus algorithm which preserves
individuals’ privacy, using Shamir’s secret sharing scheme [58, 59]. In our
proposed method, rather than sending its true local state, each agent only
sends a secret share, generated from its true state, to its neighbors.
Moreover, these secret shares have the property that any less than a threshold
number of them cannot reveal any information about the true state, but a set
of more shares can reconstruct the true state exactly. This feature permits
the proposed algorithm to preserve the agent’s privacy even with a collusion
involving a certain number of neighbors, and also protects the network from
eavesdropping by an adversary. In turn, due to the reconstructability of the
true state, the overall information injected into the network is still
sufficient to reach network consensus but in a confidential way.

Furthermore, we introduce the privacy degree for each agent, which is the
threshold number of colluding neighbors that can be allowed without privacy
breach. We show that when all the agents share a common privacy degree, the
network can reach an average consensus (see Theorem 6), i.e., all agents’
states eventually reach an agreement on the average of their initial states.
On the contrary, in the scenario where different privacy degrees are employed
for the agents, in order to guarantee the security and reconstructability of
the true states, only consensus instead of average consensus can be obtained
(see Theorem 7).

Compared to existing works, a striking merit of the proposed approach is that
it is resilient to node failures, such as connection loss, memory loss and
even permanent damage. If at any moment a node fails, the proposed method
offers the possibility of rebuilding the lost node via the information kept in
its neighbors, even though none of the neighbors knows the exact state of the
failing node. Moreover, unlike methods based on random perturbations or
differential privacy techniques, such as [60, 52, 51], the proposed method can
reach average consensus with no errors when agents have a common privacy
degree. In addition, the privacy security adopted in this paper renders the
network immune to the collusion of any given number of neighbors. In contrast
to the existing deterministic methods, e.g., [45, 46, 47], where in order to
reach consensus, the sum (integral) of all the added disturbance over time
needs to be zero, and thus at least one neighbor of each agent must be honest.

The rest of this paper is organized as follows. Section II revisits some
preliminary knowledge on stochastic discrete-time systems and on secret
sharing schemes. Section III gives the detailed definition of the privacy
security, and the privacy-preserving consensus problem that will be
investigated in the work. Section IV presents the algorithms and the main
theorems that this paper proposes. In Section V, we analyze the convergence of
the proposed algorithms and prove the main theorems in the scenario of a
common privacy degree and different privacy degrees, respectively. Then,
Section VI presents two numerical examples to illustrate the implementation of
the proposed algorithms. Finally, we conclude in Section VII.

Notations: By the symbols $\mathbb{Z}$, $\mathbb{N}$, and $\mathbb{Z}^{+}$, we
denote the sets of all integers, nonnegative intergers, and positive integers,
respectively. Given any positive integer $M\in\mathbb{Z}^{+}$, set
$[M]=\\{1,2,\dots,M\\}$. In addition, we denote by $|S|$ the cardinality of a
given set $S$. For any event $\kappa$, define the indicator function
$\mathbbm{1}(\cdot)$ satisfying that $\mathbbm{1}(\kappa)=1$ when $\kappa$
happens, otherwise $\mathbbm{1}(\kappa)=0$. Moreover, we denote by
$\mathbf{1}_{n}\in\mathbb{R}^{n}$ and $\mathbf{1}_{m\times
n}\in\mathbb{R}^{m\times n}$ the vector and matrix composed of all one
entries, respectively. The symbol $I_{n}$ is reserved for the identity matrix
of dimension $n$. For any square matrix $A$, $\sigma(A)$ is the set consisting
of all eigenvalues of $A$.

##  II Preliminary

In this paper, we model the inter-agent connectivity in a networked system by
a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where the set of nodes is
$\mathcal{V}=\big{\\{}1,\ldots,N\big{\\}}$, and set
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ consisting of all edges in
the graph. A graph $\mathcal{G}$ is called undirected if
$(i,j)\in\mathcal{E}$, for any $(j,i)\in\mathcal{E}$. In the rest of this
paper, without further indication, we assume all graphs are undirected. With
the connectivity graph $\mathcal{G}$, agents $i$ and $j$ can send information
to each other if and only if $(i,j)\in\mathcal{E}$. Then the neighbor set of a
node $i$ is defined as
$\mathcal{N}_{i}=\big{\\{}j:(i,j)\in\mathcal{E}\big{\\}}$, and a node $j$ is
called a neighbor of $i$, if $j\in\mathcal{N}_{i}$. Moreover, we say an edge
is incident to a vertex $i\in\mathcal{V}$ if $i$ is one of the endpoints of
the edge, and two edges are adjacent if they are incident to a common node.

###  II-A Invariance principle for stochastic systems

We first revisit some results of the invariance principle for discrete-time
stochastic systems.

Let $\mathcal{S}$ be a subspace of $\mathbb{R}^{n}$. Given a complete
probability space $(\Omega,\mathcal{F},\mathbb{P})$, consider the stochastic
system

$\displaystyle x(t+1)=F(x(t),w_{t}),$ (1)

with $x(0)\in\mathcal{S}$, $F:\mathcal{S}\times\mathcal{W}\to\mathcal{S}$ a
Borel measurable function, and
$(w_{t})_{t\in\mathbb{N}}:\Omega\to(\mathcal{W})^{\mathbb{N}}$ a random
variable sequence defined on the probability space
$(\Omega,\mathcal{F},\mathbb{P})$. Assume that for any $\omega\in\Omega$, and
indices $i\neq j$, the marginal variables $w_{i}$ and $w_{j}$ are independent.

We choose a Lyapunov function as a sequence of measurable functions
$\\{V_{t}:\mathcal{S}\to\mathbb{R}^{+}\\}_{t\geq 0}$ such that $V_{t}(x)\geq
0$ for any $t\geq 0$, $x\in\mathcal{S}$. We say that the Lyapunov function
$\\{V_{t}\\}_{t\geq 0}$ is radially unbounded if

$\liminf_{x\in\mathcal{S},\|x\|\to\infty}V_{t}(x)=\infty,$

for all $t$. Define the distance of $x\in\mathbb{R}^{n}$ to a set
$\mathcal{M}\subset\mathbb{R}^{n}$ by

$\operatorname{dist}(x,\mathcal{M})=\inf_{p\in\mathcal{M}}\|x-p\|.$

Then we have the following invariance theorem showing that with certain
conditions of $\\{V_{t}\\}$, every solution of the stochastic system (1)
approaches an invariant set as $t\to\infty$ almost surely.

######  Lemma 1 (Developed from Prop. 3.1 in [61]).

If there exists a radially unbounded Lyapunov function $\\{V_{t}\\}_{t\geq
0}:\mathcal{S}\to\mathbb{R}^{+}$, and a real number $c\in(0,1)$ such that

$\mathbb{E}[V_{t+1}(F(x,w_{t}))]\leq cV_{t}(x),\quad\forall
x\in\mathcal{S},t\in\mathbb{N},$ (2)

then for any initial condition $x(0)\in\mathcal{S}$, the solution
$\\{x(t)\\}_{t\geq 0}$ of dynamics (1) fulfills

$\lim_{t\to\infty}\operatorname{dist}(x(t),\mathcal{M})=0,\quad a.s.,$

where $\mathcal{M}$ satisfies

$\mathcal{M}=\bigcup_{i=0}^{\infty}\bigcap_{j\geq
i}^{\infty}\big{\\{}x\in\mathcal{S}:V_{j}(x)=0\big{\\}}.$

###### Proof.

See Appendix -A. ∎

###  II-B Secret sharing schemes

The secret sharing schemes are encryption methods for sharing a confidential
message with multiple parties, such that even with the collusion of a certain
number of parties, the message should still not be disclosed.

In general, an $(n,p)$ secret sharing scheme often consists of two algorithms
called by $\big{(}$Share, Reconstruct$\big{)}$ with the forms that

  * •

Share takes as input a confidential message $S$ and outputs $n$ secret shares
$\\{S_{1},\dots,S_{n}\\}$;

  * •

Reconstruct takes as input $p$ different secret shares
$\\{S_{i}\\}_{i\in\mathcal{I}}$ for any index set $\mathcal{I}\subset[n]$ with
$|\mathcal{I}|=p$, and outputs $S$.

Then each generated share $S_{i}$ is distributed to one party $i$ for
$i\in[n]$. Moreover, the security of secret sharing requires that any
collusion of less than $p$ parties cannot reveal the message $S$. Secret
sharing schemes have been used in many applications, e.g., encryption keys,
distributed storage, missile launch codes, and numbered bank accounts (see
[62, 58, 63, 64], and the references therein). In these applications, each of
the generated pieces of information must keep the original message
confidential, as their exposure is undesirable, however, it is also critical
that the message should be reconstructable.

One celebrated secret sharing scheme is the Shamir’s scheme proposed by Adi
Shamir [59], in which the secret shares are generated by evaluation of a
$(p-1)$-order polynomial at $n$ different points. In particular, such a scheme
satisfies information-theoretic security, i.e., even any $p-1$ secret shares
reveal absolutely no information about the secret $S$. Inspired by the
Shamir’s scheme, in this paper, we will propose a privacy-preserving algorithm
that employs polynomials to mask the true state of each agent in network
consensus.

##  III Problem Formulation

We consider the problem of synchronizing agents’ states in a network, while
avoid the risk of disclosing the true state of each agent to their neighbors.
Based on secret sharing schemes, two algorithms are proposed to address such a
problem: One is for the case where all the agents are required to have a same
security level, i.e., have a common maximum number of neighbors allowed to
collude to pry into the agent’s privacy without a security breach. With the
proposed algorithm in this scenario, average consensus is achieved eventually
for all the agents. Another algorithm is applicable to the case where the
agents can have different security levels. The price to pay is that the
achieved consensus is not necessary being the average of the initial state any
more. In addition, it shows that both proposed algorithms are also able to
guarantee communication safety, and be robust to a node failure in network
consensus.

###  III-A Privacy degree

This subsection is devoted to provide a detailed definition for the privacy
security employed in this paper.

We recall that in network systems a distributed algorithm in general has the
form

$x_{i}(t+1)=\mathcal{F}_{i}\Big{(}\,x_{i}(t),\,\big{\\{}\mathcal{R}_{t}^{ij}\big{(}x_{j}(t)\big{)}\big{\\}}_{j\in\mathcal{N}_{i}},t\Big{)},$
(3)

for $i\in\mathcal{V}$, where $x_{i}(t)\in\mathbb{R}^{d}$ is the agent $i$’s
state, $\mathcal{F}_{i}(\cdot,\cdot,\cdot)$ is an iterative update law,
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ is the inter-agent topology,
$\mathcal{R}_{t}^{ij}(x_{j}(t))$ is the information that agent $j$ sends to
agent $i$ through the communication link $(i,j)\in\mathcal{E}$, and mapping
$\mathcal{R}_{t}^{ij}:\mathbb{R}^{d}\to\mathbb{R}^{m}$ is agent $j$’s encoding
function on edge $(i,j)$. Due to the fact that the update law
$\mathcal{F}_{i}$ depends on each agent’s own state and the information
received from its neighbors, the algorithm can run in a distributed manner.

Next, for a distributed algorithm given in (3), we define its privacy degree
to indicate each agent’s capacity of ensuring privacy in the algorithm.

######  Definition 2 (Privacy degree).

Given integer vector $p=(p_{1},p_{2},\dots,p_{N})\in\mathbb{N}^{N}$. We say
that a distributed algorithm (3) has a privacy degree $p$, if for each
$i\in\mathcal{V}$ and $t\in\mathbb{N}$, it holds that the messages
$\\{\mathcal{R}_{t}^{\ell i}(x_{i}(t))\\}_{\ell\in\mathcal{I}}$ do not
disclose the privacy $x_{i}(t)$, for any index set
$\mathcal{I}\subset\mathcal{N}_{i}$ with $|\mathcal{I}|\leq p_{i}$.

The above definition entitles a distributed algorithm with the ability that
even a certain number of an agent $i$’s neighbors collude or the communication
messages sent by it are disclosed, the agent $i$’s privacy $x_{i}(t)$ can
still stay confidential. The following remark provides more insights about
this definition.

######  Remark 1.

For an algorithm of privacy degree $p$, (i) if $p_{i}>0$, the state $x_{i}(t)$
stays confidential to each neighbor $j\in\mathcal{N}_{i}$. (ii) If
$p_{i}=|\mathcal{N}_{i}|-1$, then $x_{i}(t)$ is disclosed only when all
neighbors of agent $i$ collude. (iii) If $p_{i}\geq|\mathcal{N}_{i}|$, the
state $x_{i}(t)$ is totally confidential in the network.

Furthermore, we note that in an algorithm with positive private degree, the
communication links are also protected from eavesdropping, i.e., for any agent
$i$ with a privacy degree $p_{i}>0$, an adversary wiretapping on any $p_{i}$
or less communication links in edges $\\{(i,j):j\in\mathcal{N}_{i}\\}$ learns
nothing about $i$’s privacy $x_{i}(t)$.

In the existing methods, where the private state is masked by adding
deterministic offsets that vanish in average, e.g., [45], or the accumulation
of the added offsets goes to $0$ as $t\to\infty$, e.g., [46, 47], the privacy
degree $p_{i}=|\mathcal{N}_{i}|-1$, $\forall i\in\mathcal{V}$, i.e., the
privacy is preserved only if at least one neighbor is not malicious.

It is not hard to see that Definition 2 only indicates an upper bound for the
number of neighbors allowed to be attacked or collude without a privacy
breach. In order to make this bound tight, we introduce the following
definition of exact privacy degree for a distributed algorithm.

######  Definition 3 (Exact privacy degree).

A distributed algorithm (3) has an exact privacy degree $p\in\mathbb{N}^{N}$,
if

  1. (i)

it has a privacy degree $p$, and

  2. (ii)

for each $i\in\mathcal{V}$, $t\in\mathbb{N}$, and any index set
$\mathcal{I}\subset\mathcal{N}_{i}$, if $|\mathcal{I}|\geq p_{i}+1$, the state
$x_{i}(t)$ can be reconstructed from the messages $\\{\mathcal{R}_{t}^{\ell
i}(x_{i}(t))\\}_{\ell\in\mathcal{I}}$.

In Definition 3, the condition (ii) not only provides the tightness of the
degree of privacy, but also renders the network resilient to a node failure,
for example, the state of node $i$ is lost due to a blackout, or the node
$i$’s connections are permanently broken. More specific, at any moment when
node $i$ fails, the reconstructability requirement (ii) preserves the
possibility of rebuilding the lost node via the information kept in enough
number of its neighbors, even though none of the neighbors knows the exact
state of node $i$. As a result, we typically want to set the exact privacy
degree $p_{i}<|\mathcal{N}_{i}|$ to maintain such resilience to a node
failure.

###  III-B Problem of privacy preserving consensus

Now we are ready to raise the problem of privacy-preserving consensus that
will be solved in this paper.

######  Problem 1.

In a network consisting of $N$ agents, the privacy-preserving consensus with
an exact privacy degree $p\in\mathbb{N}^{N}$ is to achieve that

  1. (i)

the consensus algorithm has an exact privacy degree $p$, and

  2. (ii)

asymptotic consensus is reached, i.e., for any initial condition
$\\{x_{i}(0)\\}_{i\in\mathcal{V}}$, it holds that

$\lim_{t\to\infty}x_{i}(t)=x_{\infty},\qquad\forall i\in[N],$ (4)

where $x_{\infty}$ is given by some non-trivial function of the initial states
111Here we insist that $x_{\infty}$ can be expressed as a non-trivial function
of the initial states, i.e., $x_{\infty}=G(x_{1}(0),\dots,x_{N}(0))$, for some
given function $G:\mathbb{R}^{Nd}\to\mathbb{R}^{d}$. Because otherwise, there
are trivial solutions requiring no information exchange at all. For example,
when function $G(\cdot)=c$ with some pre-given constant $c$, consensus can be
solved by directly setting each node’s state $x_{i}(t)=c$..

We note that in Problem 1 the privacy-preserving requirement (i) only matters
before the consensus is achieved. After that, although the information
transmitted amongst agents still keeps confidential, the agent state
$x_{i}(t)$ is nevertheless already known to all the agents due to state
consensus.

Moreover, we say that an algorithm reaches average consensus with an exact
privacy degree $p$, if in Problem 1 the function
$x_{\infty}=\frac{1}{N}\sum_{i=1}^{N}x_{i}(0)$. In our previous work [49], we
address average consensus problem with a privacy degree instead of an exact
privacy degree, i.e., there is no guarantee that the privacy $x_{i}(t)$ can be
reconstructed from many enough messages $\\{\mathcal{R}_{t}^{\ell
i}(x_{i}(t))\\}_{\ell\in\mathcal{I}}$.

##  IV Algorithms and main results

The idea for solving Problem 1 is to employ an encoding function that splits
the agent’s local state $x_{i}(t)$ into $M$ distinct secret shares, and
sending each of these distinct shares to one of its neighbors
$j\in\mathcal{N}_{i}$. This ensures that no single neighbor has complete
knowledge of the privacy $x_{i}(t)$.

As the algorithm is expected to have an exact privacy degree of $p$, we must
further require that any $p_{i}$ or less of these shares leak no information
about the secret $x_{i}(t)$, but $x_{i}(t)$ becomes totally reconstructable
given any $(p_{i}+1)$ number of these shares. Inspired by Shamir’s secret
sharing scheme, we use polynomials as the encoding functions, which are both
simple and computationally inexpensive.

In the rest of paper, for succinct expression, we will without loss of
generality assume that the state dimension $d=1$. We note that in the paper
all the algorithms and results obtained can be easily extended to higher-
dimensional cases, (see Remark 7).

###  IV-A Encoding functions

Specifically, the encoding function used by agent $i$ is given by a polynomial
of degree $p_{i}$,

$f_{i}(\theta,t)=\sum_{\ell=1}^{p_{i}}a_{i\ell}(t)\theta^{\ell}+x_{i}(t),$ (5)

for $\theta\in\mathbb{R}$ and $t\in\mathbb{N}$, where
$a_{i\ell}(t)\in\mathbb{R}$ is some coefficient held by agent $i$, for
$\ell\in[p_{i}]$, and $x_{i}(t)$ is agent $i$’s state. Notice that the state
$x_{i}(t)$ of agent $i$ is given by $f_{i}(0,t)$. Since the coefficients
$\\{a_{i\ell}(t)\\}_{\ell\in[p_{i}]}$ and state $x_{i}(t)$ are only known by
agent $i$, the encoding function $f_{i}(\cdot,\cdot)$ is also kept secret from
the other agents.

Given a set of communication keys
$\\{s_{1},\dots,s_{M}\\}\subset\mathbb{Z}^{+}$, each agent $i\in\mathcal{V}$
can use its encoding polynomial (5) to generate $M$ encoded states
$\\{r_{i}^{k}(t)\\}_{k\in[M]}$ by setting

$r_{i}^{k}(t)=f_{i}(s_{k},t),\qquad\forall k\in[M],$ (6)

where $k$ is called a channel index, and $r_{i}^{k}(t)$ the encoded state on
channel $k$. Since the degree of the polynomial $f_{i}(\cdot,t)$ is $p_{i}$,
it is possible to reconstruct the local state $x_{i}(t)$ from any combination
of $p_{i}+1$ distinct encoded states $r_{i}^{k}(t)$, provided that $p_{i}<M$.

From now on, let
$r_{i}(t)=(r_{i}^{1}(t),\dots,r_{i}^{M}(t))\in\mathbb{R}^{M}$,
$i\in\mathcal{V}$, and
$r^{k}(t)=(r_{1}^{k}(t),\dots,r_{N}^{k}(t))\in\mathbb{R}^{N}$, for any
$k\in[M]$. Furthermore, let

$d_{max}=\max_{i\in\mathcal{V}}|\mathcal{N}_{i}|,$ (7)

denote the maximal degree in the graph $\mathcal{G}$.

###  IV-B Channel selection

At each time $t\in\mathbb{N}$, all the agents will first launch a handshake
procedure, through which each edge $(i,j)\in\mathcal{E}$ is assigned with a
channel $c_{ij}(t)\in[M]$. Here $c_{ij}(t)$ is a channel indicator. This
handshake procedure is presented in Algorithm 1, and can be performed in an
asynchronous, decentralized manner.

The next lemma shows that the handshake Algorithm 1 fulfills that all adjacent
edges can be assigned with mutually different channels.

######  Lemma 4.

If $M\geq 2d_{max}-1$, at any time $t\in\mathbb{N}$, Algorithm 1 achieves that

  1. (i)

assign every edge with a channel, i.e., $c_{ij}(t)\in[M]$,
$\forall(i,j)\in\mathcal{E}$,

  2. (ii)

adjacent edges occupy different channels, i.e., the assigned channel
$c_{ij}(t)$ satisfies

$c_{ij}(t)\notin\bigg{(}\bigcup_{k\in\mathcal{N}_{i}\setminus\\{j\\}}\\{c_{ik}(t)\\}\bigg{)}\bigcup\bigg{(}\bigcup_{k\in\mathcal{N}_{j}\setminus\\{i\\}}\\{c_{jk}(t)\\}\bigg{)},$
(8)

for any $(i,j)\in\mathcal{E}$.

###### Proof.

To prove (i), we only need show that in Algorithm 1 the set
$K=[M]\setminus(R_{i}\cup R_{j})$ is nonempty at any time, where $R_{i}$ is
all the channels that have been assigned to the edges incident to $i$. When we
assign a channel to an unassigned edge $(i,j)\in\mathcal{E}$, there are at
most $(d_{max}-1)$ edges that have already been assigned in the edges incident
to $i$, and at most $(d_{max}-1)$ assigned edges in edges incident to $j$.
Because $M>2d_{max}-2$, set $K$ is nonempty. The argument (ii) follows the
fact that each channel $c_{ij}(t)$ is chosen from the set
$\Omega=[M]\setminus(R_{i}\cup R_{j})$. ∎

Algorithm 1 Handshake: channel selection at time $t$.

0: Graph $\mathcal{G}=(\mathcal{E},\mathcal{V})$; Number of channels $M$
satisfying $M\geq 2d_{max}-1$.

1: Initialization: For each edge $(i,j)\in\mathcal{E}$, initialize channel
indicator $c_{ij}(t)=0$.222The initialization $c_{ij}(t)=0$ indicates that an
edge $(i,j)$ has not been assigned with a channel yet. Set
$\mathcal{A}_{i}=\mathcal{N}_{i}$ be the set of $i$’s neighbors connected with
an unassigned edge.

2: Each agent $i$ preforms the following process in parallel:

  1. Step 1

(Edge selection):

Find the neighbor $j=\min_{\ell}\\{\ell\in\mathcal{A}_{i}\\}$.333Note that set
$\mathcal{A}_{i}$ is not empty whenever there exist edges in $\mathcal{N}_{i}$
not being assigned.

Ping node $j$, and wait until $j$ pings back.444Ping is an operation that a
node sends a specific message to its neighbor to notify that it is ready to
establish a connection.

  2. Step 2

(Connection establishment):

Once $j$ pings back, agents $i,j$ together choose an available channel $k$
uniformly at random from the set $\big{(}[M]\setminus(R_{i}\cup R_{j})\big{)}$
for the edge $(i,j)$, where

$\displaystyle R_{i}$
$\displaystyle=\big{(}\bigcup_{k\in\mathcal{N}_{i}}\\{c_{ik}(t)\\}\big{)}\setminus\\{0\\},$
$\displaystyle R_{j}$
$\displaystyle=\big{(}\bigcup_{k\in\mathcal{N}_{j}}\\{c_{jk}(t)\\}\big{)}\setminus\\{0\\}.$

Set $c_{ij}(t)=c_{ji}(t)=k$. Remove $j$ from $\mathcal{A}_{i}$, and remove $i$
from $\mathcal{A}_{j}$.

  3. Step 3

(Repeat):

If $\mathcal{A}_{i}$ is non-empty, go to Step 1. If it is empty, the agent
$i$’s handshake is done.

3: END: Handshake is done when all agents finish their own handshake
processes.

######  Remark 2.

In Step 1 of Algorithm 1, we assume all the agents are ordered according to
their index $i$. Alternatively, an order of agents can be specified by any
other nodes’ identification, e.g., the MAC address on the internet.

As to the complexity of Algorithm 1, suppose we consider Step 2 as the
elementary operation, then the time complexity of the whole algorithm is
$\mathcal{O}(N^{2})$. This is because the number of edges
$|\mathcal{E}|=\frac{1}{2}\sum_{i=1}^{N}|\mathcal{N}_{i}|\leq N^{2}$.
Therefore, it is guaranteed that the handshake procedure of all the agents can
be finished in a bounded time.

###  IV-C Synchronization update law

We are now ready to give the update law for privacy-preserving consensus. The
basic idea is to, for each separate channel $k\in[M]$, first perform an
average consensus step for the encoded states belonging to that channel,
through the edges with channels assigned in Section IV-B, and then conduct a
projection operator to update local states $x_{i}$ and coefficients $a_{i}$.

At each time $t$, once the handshake process in Algorithm 1 for an agent
$i\in\mathcal{V}$ is finished, i.e., $c_{ij}(t)\neq 0$ for all
$j\in\mathcal{N}_{i}$, the state of agent $i$ is then updated according to the
update law

$\displaystyle\widetilde{r}^{k}_{i}(t+1)$
$\displaystyle=r^{k}_{i}(t)\\!+\\!\gamma\\!\\!\sum_{j\in\mathcal{N}_{i}}l_{ij}^{k}(t)\Big{(}r_{j}^{k}(t)-r_{i}^{k}(t)\Big{)},\;\forall
k\in[M],$ (9a) $\displaystyle\begin{bmatrix}x_{i}(t+1)\\\
a_{i}(t+1)\end{bmatrix}$ $\displaystyle=T_{i}\;\widetilde{r}_{i}(t+1),$ (9b)
$\displaystyle r_{i}^{k}(t+1)$ $\displaystyle=f_{i}(s_{k},t+1),\;\forall
k\in[M],$ (9c)

with the initial condition $r_{i}^{k}(0)=f_{i}(s_{k},0)$ for every $k\in[M]$,
and the step size $\gamma>0$. Here, the communication weight
$l_{ij}^{k}(t)=\mathbbm{1}(c_{ij}(t)=k)$, vector
$\widetilde{r}_{i}(t)=(\widetilde{r}_{i}^{1}(t),\dots,\widetilde{r}_{i}^{M}(t))\in\mathbb{R}^{M}$,
$a_{i}(t)=(a_{i1}(t),\dots,a_{ip_{i}}(t))\in\mathbb{R}^{p_{i}}$ and
$f_{i}(\cdot,\cdot)$ is the encoding polynomial defined in (5). Furthermore,
the projection matrix
$T_{i}=(\Phi_{i}^{T}\Phi_{i})^{-1}\Phi_{i}^{T}\in\mathbb{R}^{(p_{i}+1)\times
M}$ with $\Phi_{i}$ being the Vandermonde matrix related to the key sequence
$S=(s_{1},\dots,s_{M})\in\mathbb{R}^{M}$, i.e.,

$\Phi_{i}=\begin{bmatrix}1&s_{1}&(s_{1})^{2}&\dots&(s_{1})^{p_{i}}\\\
1&s_{2}&(s_{2})^{2}&\dots&(s_{2})^{p_{i}}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&s_{M}&(s_{M})^{2}&\dots&(s_{M})^{p_{i}}\end{bmatrix}\in\mathbb{R}^{M\times(p_{i}+1)}.$
(10)

Note that if $s_{i}\neq s_{j},\forall i\neq j$ and $M\geq p_{i}+1$, then
$\operatorname{rank}(\Phi_{i})=p_{i}+1$.

The following remark indicates that the individual privacy is not disclosed in
the proposed algorithm (9).

######  Remark 3.

Due to the definition of $l_{ij}^{k}(t)$, in the update law (9), each agent
$i$ only accesses to one of neighbor $j$’s encoded states, i.e.,
$r_{j}^{c_{ij}(t)}(t)$.

More specifically, the update (9a) can be seen as a channel-wise consensus
process, by which encoded state $r_{i}^{k}(t)$ is averaged among the $i$’s
neighbors being assigned with channel $k$ at each time $t$. During this
consensus procedure, in order to maintain the updated encoded state
$r_{i}(t+1)$ being able to generate from a polynomial of order $p_{i}$, (9b)
is used to project the intermediate consensus variable
$\widetilde{r}_{i}(t+1)$ back to the subspace $\operatorname{span}(\Phi_{i})$.
Note that $\Phi_{i}$ is full column rank, and the update (9b) indeed solves
the optimization problem given by

$\begin{bmatrix}x_{i}(t+1)\\\
a_{i}(t+1)\end{bmatrix}=\operatorname*{argmin}_{v\in\mathbb{R}^{p_{i}+1}}\big{\|}\widetilde{r}_{i}(t+1)-\Phi_{i}v\big{\|}_{2},$

where $\|\cdot\|_{2}$ is the Euclidean norm.

Next, we have the following lemma to show that Algorithm (9) has an exact
privacy degree $p$, and more essentially provides a method to reconstructing
the agent $i$’s privacy from a certain number of its encoded states.

######  Lemma 5.

The distributed update law (9) has an exact privacy degree
$p\in\mathbb{N}^{N}$. Moreover, for any $i\in\mathcal{V}$ and an arbitrary
index set $\mathcal{I}\subset[M]$ satisfying $|\mathcal{I}|\geq p_{i}+1$, the
privacy $x_{i}(t)$ can be reconstructed by

$x_{i}(t)=\sum_{k\in\mathcal{I}}r_{i}^{k}(t)\frac{\prod_{\ell\in\mathcal{I}\setminus\\{k\\}}(-s_{\ell})}{\prod_{\ell\in\mathcal{I}\setminus\\{k\\}}(s_{k}-s_{\ell})},\quad\forall
t\in\mathbb{N}.$ (11)

###### Proof.

First we need show that for any $i\in\mathcal{V}$, the messages
$\\{r_{i}^{k}(t)\\}_{k\in\mathcal{I}}$ do not disclose $x_{i}(t)$, if the
index set $\mathcal{I}\subset\mathcal{N}_{i}$ satisfies $|\mathcal{I}|\leq
p_{i}$. This is because even an adversary know $p_{i}$ encoded state
$\\{r_{i}^{k}(t)\\}_{i\in\mathcal{I}^{\prime}}$, for each state candidate
$x_{i}^{\prime}(t)$ the adversary can construct one and only one polynomial
$f^{\prime}(\theta,t)$ of degree $p_{i}$ such that
$f^{\prime}(0,t)=x^{\prime}_{i}(t)$ and $f^{\prime}(s_{k},t)=r^{k}_{i}(t)$,
$k\in\mathcal{I}^{\prime}$. Moreover, each of these polynomials are equally
likely, therefore the adversary cannot learn the real privacy $x_{i}(t)$.

The reconstruction formula (11) follows the interpolation polynomial in the
Lagrange form. ∎

Now it is ready to present the main theorems related to convergence of the
proposed privacy-preserving consensus scheme, including Algorithm 1 and update
law (9). We consider two cases separately: one is when all the agents have a
same privacy degree, and another is for the case that the privacy degree is
individually set.

When all the agents share an identical privacy degree, the next theorem shows
that the agents can reach average consensus by the proposed method.

######  Theorem 6 (Common privacy degree).

Let $p=p_{0}\mathbf{1}_{N}$ for a given $p_{0}\in\mathbb{N}$. If the step size
$\gamma\in(0,1)$, and $M\geq 2d_{max}-1$, then update law (9) with the
handshake procedure in Algorithm 1 almost surely solves Problem 1 with average
consensus reached, i.e., the algorithm has an exact privacy degree $p$, and
for any initial condition $\\{x_{i}(0)\\}_{i\in\mathcal{V}}$,

$\lim_{t\to\infty}x_{i}(t)=\frac{1}{N}\sum_{j=1}^{N}x_{j}(0),\qquad\forall
i\in[N],$ (12)

almost surely.

######  Remark 4.

In Theorem 6, the almost sure convergence is with respect to probability
stemming from random channel selections in Algorithm 1.

Next, we continue with a more general case where agents are allowed to have
distinct privacy degrees. In this case, the algorithm proposed still
guarantees that agents reach consensus almost surely with the desired privacy
requirement, but the value agreed upon may not necessarily be the average of
the initial condition $\\{x_{i}(0)\\}_{i}$.

######  Theorem 7 (Different privacy degree).

Let vector $p\in\mathbb{N}^{N}$. If $\gamma\in(0,1)$ and $M\geq 2d_{max}-1$,
update law (9) with handshake Algorithm 1 almost surely solves Problem 1,
i.e., the algorithm has an exact privacy degree $p$, and for any initial
condition $\\{x_{i}(0)\\}_{i\in\mathcal{V}}$,

$\lim_{t\to\infty}x_{i}(t)=x_{\infty},\qquad\forall i\in[N],$ (13)

almost surely, for some real $x_{\infty}$.

######  Remark 5.

In Theorem 7, the steady state $x_{\infty}$ can be computed by equation (35),
(see also Remark 6).

##  V Convergence analysis

###  V-A Case of common privacy degree

First, according to update law (9), we can derive the stacked encoded state is
governed by following dynamics

$\displaystyle\widetilde{r}^{k}(t+1)$ $\displaystyle=r^{k}(t)-\gamma
L^{k}(t)r^{k}(t),\quad\forall k\in[M]$ (14a) $\displaystyle r_{i}(t+1)$
$\displaystyle=\overline{T}_{i}\widetilde{r}_{i}(t+1),\qquad\forall
k\in\mathcal{V}$ (14b)

where the projection matrix
$\overline{T}_{i}=\Phi_{i}(\Phi_{i}^{T}\Phi_{i})^{-1}\Phi_{i}^{T}=\Phi_{i}T_{i}\in\mathbb{R}^{M\times
M}$, vector
$\widetilde{r}^{k}(t)=(\widetilde{r}_{1}^{k}(t),\dots,\widetilde{r}_{N}^{k}(t))\in\mathbb{R}^{N}$,
$k\in[M]$, and the entry of matrix $L^{k}(t)\in\mathbb{R}^{N\times N}$ is

$(L^{k}(t))_{ij}=\begin{cases}-l_{ij}^{k}(t),\quad&\text{if }i\neq j,\\\
\sum_{\ell\in\mathcal{N}_{i}}l_{i\ell}^{k}(t),\quad&\text{otherwise}.\end{cases}$
(15)

Due to the above definition, the matrix $L^{k}(t)$ is doubly stochastic for
any $k\in[M],t\in\mathbb{N}$.

Moreover, as the weight $l_{ij}^{k}(t)=\mathbbm{1}(c_{ij}(t)=k)$ depending on
the random channel selection in the handshake procedure given by Algorithm 1,
the matrix $L^{k}(t)$ and encoded states $r_{i}^{k}(t)$ are therefore random
variables for each $k\in[M],i\in\mathcal{V},t\in\mathbb{N}$. Then the random
matrix $L^{k}(t)$ satisfies the following lemma.

######  Lemma 8.

The random matrix $L^{k}(t)$ constructed by Algorithm 1 satisfies that

$\displaystyle\mathbb{E}\left[L^{k}(t)\right]$
$\displaystyle=\frac{1}{M}\,L\,,$ (16a)
$\displaystyle\mathbb{E}\left[\big{(}L^{k}(t)\big{)}^{2}\right]$
$\displaystyle=\frac{2}{M}\,L\,,$ (16b)

for any $k\in[M]$, $t\in\mathbb{N}$, where $L$ is the Laplacian matrix of the
connectivity graph $\mathcal{G}$, and $M$ is the number of channels.

###### Proof.

First, for any channel selections $\\{c_{ij}(t)\\}_{(i,j)\in\mathcal{E}}$
given by Algorithm 1, we have $c_{ij}(t)\sim U\\{[M]\\}$, where $U(A)$ is the
uniform distribution supported on a finite set $A$. This is due to the channel
selection is invariant under any permutation among channels. Equivalently, it
holds that $\mathbb{P}\\{l^{k}_{ij}(t)=1\\}=\frac{1}{M}$, for any $k\in[M]$,
$(i,j)\in\mathcal{E}$. Therefore, we have for each $k$

$\mathbb{E}[l^{k}_{ij}(t)]=\begin{cases}\frac{1}{M},\quad&\text{if
}(i,j)\in\mathcal{E},\\\ 0,\quad&\text{otherwise}.\end{cases}$

According to definition (15), the assertion (16a) follows.

To prove (16b), we notice that according to Lemma 4, Algorithm 1 assigns any
adjacent edges with distinct channels. This further implies that except the
diagonal entries, there is at most one nonzero entry in each row of matrix
$L^{k}(t)$. So is in each column of matrix $L^{k}(t)$, since $L^{k}(t)$ is
symmetric.

In order to compute the entries of $\big{(}L^{k}(t)\big{)}^{2}$, we consider
the following cases:

  1. 1.

If $i\neq j$ and $c_{ij}(t)=k$,

$\displaystyle\left(\big{(}L^{k}(t)\big{)}^{2}\right)_{ij}$
$\displaystyle=\sum_{\ell=1}^{N}\left(L^{k}(t)\right)_{i\ell}\left(L^{k}(t)\right)_{\ell
j}$
$\displaystyle=\left(L^{k}(t)\right)_{ii}\\!\left(L^{k}(t)\right)_{ij}\\!+\\!\left(L^{k}(t)\right)_{ij}\\!\left(L^{k}(t)\right)_{jj}$
$\displaystyle=-2.$

  2. 2.

If $i\neq j$ and $c_{ij}(t)\neq k$,

$\displaystyle\left(\big{(}L^{k}(t)\big{)}^{2}\right)_{ij}$
$\displaystyle=\left(L^{k}(t)\right)_{ii}\\!\left(L^{k}(t)\right)_{ij}\\!+\\!\left(L^{k}(t)\right)_{i\ell}\\!\left(L^{k}(t)\right)_{\ell
j}$ $\displaystyle=0,$

where we use the fact that in $i$-th row only the diagonal entry and at most
one else entry (w.l.g we assume it is the $\ell$-th entry) could be nonzero.

  3. 3.

If $i=j$ and there exists $\ell$ such that $c_{i\ell}(t)=k$,

$\displaystyle\left(\big{(}L^{k}(t)\big{)}^{2}\right)_{ij}$
$\displaystyle=\left(L^{k}(t)\right)_{ii}\\!\left(L^{k}(t)\right)_{ij}\\!+\\!\left(L^{k}(t)\right)_{i\ell}\\!\left(L^{k}(t)\right)_{\ell
j}$ $\displaystyle=2.$

  4. 4.

If $i=j$ and $c_{i\ell}(t)=0$, $\forall\ell$, we can show
$\left(\big{(}L^{k}(t)\big{)}^{2}\right)_{ij}=0$.

Hence, taking expectation of each entry in matrix $\big{(}L^{k}(t)\big{)}^{2}$
gives

$\mathbb{E}\left[\left(\big{(}L^{k}(t)\big{)}^{2}\right)_{ij}\right]=\begin{cases}2\frac{|\mathcal{N}_{i}|}{M},\quad&\text{if
}i=j,\\\ -\frac{2}{M},\quad&\text{if }i\neq j,(i,j)\in\mathcal{E},\\\
0,\quad&\text{otherwise},\end{cases}$

which proves (16b). ∎

Denote by
$r(t)=\left(r^{1}(t)^{T},r^{2}(t)^{T},\dots,r^{M}(t)^{T}\right)\in\mathbb{R}^{MN}$
the stacked vector of all encoded states. Because all agents share a common
privacy degree $p_{0}$, in (9b) the project matrices of all the agents are
also same, i.e., $T_{i}=T_{0}=(\Phi_{0}^{T}\Phi_{0})^{-1}\Phi_{0}^{T}$ for all
$i\in\mathcal{V}$, where $\Phi_{0}$ is the Vandermonde matrix of order
$p_{0}$.

Then, according to the channel-wise and agent-wise updates given in (14), we
can derive the overall stacked state $r(t+1)$ satisfying

$r(t+1)=\big{(}\overline{T}_{0}\otimes
I_{N}\big{)}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}r(t),$ (17)

where project matrix $\overline{T}_{0}=\Phi_{0}T_{0}$, and matrix
$\overline{L}(t)$ has the form

$\overline{L}(t)=\begin{bmatrix}L^{1}(t)&&\\\ &\ddots&\\\
&&L^{M}(t)\end{bmatrix},$ (18)

with each diagonal block being $L^{k}(t)$ defined in (15).

We note that in overall dynamics (17) the matrix $\overline{T}_{0}$ is
symmetric and satisfies
$\left(\overline{T}_{0}\right)^{\ell}=\overline{T}_{0}$,
$\forall\ell\in\mathbb{Z}^{+}$, i.e., $\overline{T}_{0}$ is an idempotent
matrix. Therefore, it holds that any eigenvalue of matrix $\overline{T}_{0}$
is either $0$ or $1$. Moreover, we can verify that the matrix
$\overline{L}(t)$ satisfies

$\displaystyle\left(A\otimes\mathbf{1}_{N}^{T}\right)\,\overline{L}(t)$
$\displaystyle=0_{M\times MN},\quad\forall A\in\mathbb{R}^{M\times M},$ (19a)
$\displaystyle\overline{L}(t)\,\left(v\otimes\mathbf{1}_{N}\right)$
$\displaystyle=0_{MN\times 1},\quad\forall v\in\mathbb{R}^{M}.$ (19b)

for any $t\in\mathbb{N}$.

Next, the following proposition shows that on each channel $k$ the encoded
state of each agent converges almost surely to the average of the encoded
states at $t=0$.

######  Proposition 9.

Under the same assumptions as in Theorem 6, it holds that

$\lim_{t\to\infty}r^{k}_{i}(t)=\frac{1}{N}\sum_{j=1}^{N}r^{k}_{j}(0),\quad
a.s.,$

for each $i\in\mathcal{V}$, $k\in[M]$.

###### Proof.

We define $\overline{r}^{k}(t)=\frac{1}{N}\sum_{i=1}^{N}r^{k}_{i}(t)$ for
$k\in[M],t\in\mathbb{N}$, and denote the stacked vector by
$\overline{r}(t)=\left(\overline{r}^{1}(t),\dots,\overline{r}^{M}(t)\right)\in\mathbb{R}^{M}$.
Then according to the dynamics (17), we have

$\displaystyle\overline{r}(t+1)$
$\displaystyle=\frac{1}{N}\left(I_{M}\otimes\mathbf{1}_{N}^{T}\right)r(t+1)$
$\displaystyle=\frac{1}{N}\left(I_{M}\otimes\mathbf{1}_{N}^{T}\right)\big{(}\overline{T}_{0}\otimes
I_{N}\big{)}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}r(t)$
$\displaystyle=\frac{1}{N}\big{(}\overline{T}_{0}\otimes\mathbf{1}_{N}^{T}\big{)}r(t)$
$\displaystyle=\overline{T}_{0}\overline{r}(t),$

where we employ (19a) in the third equality. Moreover, due to the fact that
$r_{i}(0)\in\operatorname{span}\\{\Phi_{0}\\}$, we have
$\overline{r}(0)=\frac{1}{N}\sum_{i=1}^{N}r_{i}(0)\in\operatorname{span}\\{\Phi_{0}\\}$.
Therefore, it holds that

$\overline{r}(t)=\left(\overline{T}_{0}\right)^{t}\overline{r}(0)=\overline{r}(0),$

for any $t\in\mathbb{N}$.

Next, define disagreement vector

$\delta^{k}(t)=r^{k}(t)-\overline{r}^{k}(0)\mathbf{1}_{N},$ (20)

for each $k\in[M]$, and we have $\mathbf{1}_{N}^{T}\delta^{k}(t)=0$.
Furthermore, the stack vector
$\delta(t)=\left(\delta^{1}(t)^{T},\dots,\delta^{M}(t)^{T}\right)\in\mathbb{R}^{MN}$
satisfies

$\displaystyle\delta(t+1)$
$\displaystyle=r(t+1)-(\overline{r}(0)\otimes\mathbf{1}_{N})$
$\displaystyle=\big{(}\overline{T}_{0}\otimes
I_{N}\big{)}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}r(t)-(\overline{r}(0)\otimes\mathbf{1}_{N})$
$\displaystyle=\big{(}\overline{T}_{0}\otimes
I_{N}\big{)}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}\big{[}r(t)-(\overline{r}(0)\otimes\mathbf{1}_{N})\big{]}$
$\displaystyle=\big{(}\overline{T}_{0}\otimes
I_{N}\big{)}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}\delta(t),$ (21)

where the third equality is due to (19b) and the fact that
$\overline{T}_{0}\overline{r}(0)=\overline{r}(0)$.

For any $z\in\mathbb{R}^{MN}$, denote vector $z^{k}\in\mathbb{R}^{N}$ such
that there is a partition satisfying
$z=\big{[}(z^{1})^{T},(z^{2})^{T},\dots,(z^{M})^{T}\big{]}^{T}$. Then define a
subspace

$\mathcal{S}=\left\\{z\in\mathbb{R}^{MN}:\mathbf{1}_{N}^{T}z^{k}(t)=0,k\in[M]\right\\}.$
(22)

For the dynamics (V-A), taking the Lyapunov functions
$V:\mathcal{S}\to\mathbb{R}^{+}$ defined by $V(z)=z^{T}z$, it holds that for
any $z\in\mathcal{S}$

$\displaystyle\,\mathbb{E}\Bigg{[}V\bigg{(}\big{(}\overline{T}_{0}\otimes
I_{N}\big{)}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}z\bigg{)}\Bigg{]}$
$\displaystyle\leq$
$\displaystyle\,\mathbb{E}\Bigg{[}\bigg{\|}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}z\bigg{\|}^{2}\Bigg{]}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{M}(z^{k})^{T}\mathbb{E}\Bigg{[}\big{(}I_{N}-\gamma
L^{k}(t)\big{)}^{T}\big{(}I_{N}-\gamma L^{k}(t)\big{)}\Bigg{]}z^{k}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{M}(z^{k})^{T}\bigg{(}I_{N}-\frac{2}{M}(\gamma-\gamma^{2})L\bigg{)}z^{k},$
(23)

where the first inequality follows the fact that
$\sigma(\overline{T}_{0})\subset\\{0,1\\}$, the last equality is due to Lemma
8.

As the connectivity graph is connected, its Laplacian matrix $L$ has a simple
smallest eigenvalue $0$ with the eigenvector $\mathbf{1}_{N}$. Moreover, by
the Courant-Fisher theorem, it holds that

$\displaystyle\max_{\begin{subarray}{c}z\in\mathbb{R}^{N}\setminus 0\\\
z^{T}\mathbf{1}_{N}=0\end{subarray}}\frac{z^{T}\bigg{(}I_{N}-\frac{2}{M}(\gamma-\gamma^{2})L\bigg{)}z}{z^{T}z}=1-\frac{2}{M}(\gamma-\gamma^{2})\lambda_{2},$

where $\lambda_{2}>0$ is the second smallest eigenvalue of matrix $L$. Because
$\mathbf{1}^{T}_{N}z^{k}=0$, $\forall k\in[M]$ in (V-A), we have

$\mathbb{E}\Bigg{[}V\bigg{(}\big{(}\overline{T}_{0}\otimes
I_{N}\big{)}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}z\bigg{)}\Bigg{]}\leq\overline{c}\,V(z),$
(24)

for any $z\in\mathcal{S}$, where
$\overline{c}=1-\frac{2}{M}(\gamma-\gamma^{2})\lambda_{2}$. Due to the ansatz
that $\gamma\in(0,1)$, we can show that

$\overline{c}\in\big{[}1-\frac{\lambda_{2}}{2M}\,,\,1\big{)}.$

In addition, by the Gershgorin theorem, the eigenvalue $\lambda_{2}$ is
located in the interval $(0,2d_{max}]$. Combining this with $M\geq
2d_{max}-1$, we have $\overline{c}\in[\frac{d_{max}-1}{2d_{max}-1},1)$.

In the end, by using Lemma 1, we have in the disagreement dynamics (V-A),

$\lim_{t\to\infty}\operatorname{dist}(\delta(t),\mathcal{M})=0,\quad a.s.,$

where $\mathcal{M}=\\{z\in\mathbb{R}^{MN}:z=0\\}$. According to (20), this
suggests that

$\lim_{t\to\infty}r^{k}_{i}(t)=\frac{1}{N}\sum_{j=1}^{N}r^{k}_{j}(0),\quad
a.s.,$

for each $i\in\mathcal{V}$, $k\in[M]$.

∎

Now we are ready to complete the proof of Theorem 6.

###### Proof of Theorem 6.

By Proposition 9, we have for each $k\in[M]$ and $i\in\mathcal{V}$,

$\displaystyle\lim_{t\to\infty}r^{k}_{i}(t)$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{N}f_{j}(s_{k},0),\quad a.s.$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{N}\left(\sum_{\ell=1}^{p_{0}}a_{j\ell}(0)(s_{k})^{\ell}+x_{j}(0)\right)$
$\displaystyle=\sum_{\ell=1}^{p_{0}}\left(\frac{1}{N}\sum_{j=1}^{N}a_{j\ell}(0)\right)(s_{k})^{\ell}+\left(\frac{1}{N}\sum_{j=1}^{N}x_{j}(0)\right)$
$\displaystyle=:f_{\infty}(s_{k}),$

where the polynomial
$f_{\infty}(\theta)=\sum_{\ell=1}^{p_{0}}b_{\ell}\theta^{\ell}+b_{0}$ with
$b_{0}=\frac{1}{N}\sum_{j}x_{j}(0)$, and
$b_{\ell}=\frac{1}{N}\sum_{j}a_{j\ell}(0)$.

Next, by using Lemma 5 with $\mathcal{I}=[M]$, we have for each
$i\in\mathcal{V}$,

$\displaystyle\lim_{t\to\infty}x_{i}(t)$
$\displaystyle=\sum_{k\in\mathcal{I}}\lim_{t\to\infty}r_{i}^{k}(t)\frac{\prod_{\ell\in\mathcal{I}\setminus\\{k\\}}(-s_{\ell})}{\prod_{\ell\in\mathcal{I}\setminus\\{k\\}}(s_{k}-s_{\ell})}$
$\displaystyle=\sum_{k\in\mathcal{I}}f_{\infty}(s_{k})\frac{\prod_{\ell\in\mathcal{I}\setminus\\{k\\}}(-s_{\ell})}{\prod_{\ell\in\mathcal{I}\setminus\\{k\\}}(s_{k}-s_{\ell})}\quad
a.s.$ $\displaystyle=b_{0},$

in which we use the Lagrange interpolation in the last equality. ∎

###  V-B Case of different privacy degree

Compared to the case in section V-A, the various privacy degree
$p\in\mathbb{N}^{N}$ makes the project matrices $T_{i}$ in (9b) different from
the agents. Then in order to find the dynamics for the overall state $r(t)$ as
in (17), we introduce a permutation matrix $G\in\mathbb{R}^{MN\times MN}$
defined by

$G=\begin{bmatrix}e_{\pi(1)}\\\ e_{\pi(2)}\\\ \vdots\\\
e_{\pi(MN)}\end{bmatrix},$

where $e_{i}$ is the $i$-th row of the identity matrix $I_{MN}$, and mapping
$\pi:[MN]\to[MN]$ is defined by

$\pi(\ell)=\left(\ell-M\left\lfloor\frac{\ell-1}{M}\right\rfloor-1\right)N+\left\lceil\frac{\ell}{M}\right\rceil.$
(25)

We note that $G$ is an orthogonal matrix. Denote by
$r_{a}(t)=\left(r_{1}(t)^{T},r_{2}(t)^{T},\dots,r_{N}(t)^{T}\right)\in\mathbb{R}^{MN}$
the stacked encoded state in the agent order. It can be verified that
$r_{a}(t)=Gr(t)$.

######  Example 10.

Take an example with $N=2$, $M=3$, then under the permutation mapping defined
in (25), we have

$r_{a}(t)=G\,r(t)=\begin{bmatrix}e_{\pi(1)}\\\ e_{\pi(2)}\\\ e_{\pi(3)}\\\
e_{\pi(4)}\\\ e_{\pi(5)}\\\
e_{\pi(6)}\end{bmatrix}r(t)=\begin{bmatrix}e_{1}\\\ e_{3}\\\ e_{5}\\\ e_{2}\\\
e_{4}\\\ e_{6}\end{bmatrix}\begin{bmatrix}r^{1}_{1}\\\ r^{1}_{2}\\\
r^{2}_{1}\\\ r^{2}_{2}\\\ r^{3}_{1}\\\ r^{3}_{2}\\\
\end{bmatrix}=\begin{bmatrix}r^{1}_{1}\\\ r^{2}_{1}\\\ r^{3}_{1}\\\
r^{1}_{2}\\\ r^{2}_{2}\\\ r^{3}_{2}\\\ \end{bmatrix}.$

Then it can be derived that the dynamics for overall encoded state $r(t)$ with
$p\in\mathbb{N}^{N}$ is

$r(t+1)=G^{T}\Pi\,G\,(I_{MN}-\gamma\overline{L}(t))\,r(t),$ (26)

where $\overline{L}(t)$ is defined in (18), and matrix
$\Pi\in\mathbb{R}^{MN\times MN}$ is the block diagonal matrix given by

$\Pi=\begin{bmatrix}\overline{T}_{1}&&&\\\ &\overline{T}_{2}&&\\\ &&\ddots&\\\
&&&\overline{T}_{N}\end{bmatrix},$

with $\overline{T}_{i}=\Phi_{i}T_{i}\in\mathbb{R}^{M\times M}$.

Next, we denote $\overline{p}=\min_{i\in\mathcal{V}}{p_{i}}$, and define
vector

$v_{i}=\left((s_{1})^{i-1},(s_{2})^{i-1},\dots,(s_{M})^{i-1}\right)\in\mathbb{R}^{M},$
(27)

for each $i\in[\overline{p}+1]$, where $s_{k}$ is the communication key given
in (6). Furthermore, denote

$\overline{T}_{a}=\Phi_{\ell}{T}_{\ell}\in\mathbb{R}^{M\times M},$ (28)

in which $\ell$ satisfies $p_{\ell}=\overline{p}$. Then the next lemma reveals
the invariance owned by the projection matrix $G^{T}\Pi G$.

######  Lemma 11.

For any $p\in\mathbb{N}^{N}$, the following equalities hold

  1. i)

$G^{T}\Pi
G\left(v_{i}\otimes\mathbf{1}_{N}\right)=v_{i}\otimes\mathbf{1}_{N}$,

  2. ii)

$G^{T}\Pi
G\left(\overline{T}_{a}\otimes\mathbf{1}_{N}\right)=\overline{T}_{a}\otimes\mathbf{1}_{N}$,

for all $i\in[\overline{p}+1]$.

###### Proof.

Property i) follows the fact that $\overline{T}_{j}v_{i}=v_{i}$, for any
$j\in\mathcal{V}$, $i\in[\overline{p}+1]$. Take $\ell\in\mathcal{V}$ such that
$p_{\ell}=\overline{p}$, and we notice that the Vandermonde matrix defined in
(10) satisfies $\Phi_{\ell}=(v_{1},v_{2},\dots,v_{\overline{p}+1})$. This
leads to that $G^{T}\Pi
G\left(\Phi_{\ell}\otimes\mathbf{1}_{N}\right)=\Phi_{\ell}\otimes\mathbf{1}_{N}$.
Therefore, it holds that

$G^{T}\Pi G\left(\overline{T}_{a}\otimes\mathbf{1}_{N}\right)=G^{T}\Pi
G\left(\Phi_{\ell}\otimes\mathbf{1}_{N}\right)T_{\ell}=\overline{T}_{a}\otimes\mathbf{1}_{N},$

where we use the fact $\overline{T}_{a}=\Phi_{\ell}T_{\ell}$ twice. ∎

Next, define vector
$\overline{r}_{\infty}=\frac{1}{N}\left(\overline{T}_{a}\otimes\mathbf{1}_{N}^{T}\right)r(0)\in\mathbb{R}^{M}$.
The following proposition states that the encoded state
$r_{i}(t)\in\mathbb{R}^{M}$ of all the agents eventually achieve consensus as
$t\to\infty$.

######  Proposition 12.

Under the same assumptions with Theorem 7, it holds that

$\lim_{t\to\infty}r_{i}(t)=\overline{r}_{\infty},\quad a.s.,$

for each $i\in\mathcal{V}$.

###### Proof.

Define disagreement vector by

$\delta(t)=r(t)-\overline{r}_{\infty}\otimes\mathbf{1}_{N},$ (29)

and moreover we have the agreement goal
$\overline{r}_{\infty}\otimes\mathbf{1}_{N}$ satisfies

$\displaystyle\overline{r}_{\infty}\otimes\mathbf{1}_{N}$
$\displaystyle=\bigg{(}\frac{1}{N}\left(\overline{T}_{a}\otimes\mathbf{1}_{N}^{T}\right)r(0)\bigg{)}\otimes\mathbf{1}_{N}$
$\displaystyle=\frac{1}{N}\left(\overline{T}_{a}\otimes\mathbf{1}_{N\times
N}\right)r(0)$ (30)
$\displaystyle=\frac{1}{N}\left(\overline{T}_{a}\otimes\mathbf{1}_{N}\right)\left(I_{M}\otimes\mathbf{1}_{N}^{T}\right)r(0).$
(31)

Then the dynamics of disagreement $\delta(t)$ fulfills

$\displaystyle\delta(t+1)$ $\displaystyle=G^{T}\Pi
G(I_{MN}-\gamma\overline{L}(t))\,r(t)-\overline{r}_{\infty}\otimes\mathbf{1}_{N}$
$\displaystyle=G^{T}\Pi
G\bigg{(}(I_{MN}-\gamma\overline{L}(t))\,r(t)-\overline{r}_{\infty}\otimes\mathbf{1}_{N}\bigg{)}$
$\displaystyle=G^{T}\Pi G(I_{MN}-\gamma\overline{L}(t))\delta(t),$ (32)

where the second equality is due to (31) and ii) in Lemma 11, and the last
equality follows (19b).

Moreover, we can show that $(v_{i}\otimes\mathbf{1}_{N})^{T}\delta(t)=0$,
$\forall t$, where $v_{i}$ is defined in (27) for $i\in[\overline{p}+1]$. This
is because according to dynamics (V-B),

$\displaystyle(v_{i}\otimes\mathbf{1}_{N})^{T}\delta(t+1)$
$\displaystyle=(v_{i}\otimes\mathbf{1}_{N})^{T}G^{T}\Pi
G(I_{MN}-\gamma\overline{L}(t))\delta(t)$
$\displaystyle=(v_{i}\otimes\mathbf{1}_{N})^{T}\delta(t),$

where we use i) in Lemma 11 with $i=1$, and the fact that
$(v_{i}\otimes\mathbf{1}_{N})^{T}\overline{L}(t)=0$, $\forall t$. Then, this
further implies that

$\displaystyle(v_{i}\otimes\mathbf{1}_{N})^{T}\delta(t)$
$\displaystyle=(v_{i}\otimes\mathbf{1}_{N})^{T}\delta(0)$
$\displaystyle=(v_{i}\otimes\mathbf{1}_{N})^{T}\\!\left(\\!r(0)\\!-\\!\frac{1}{N}\left(\overline{T}_{a}\\!\otimes\\!\mathbf{1}_{N\times
N}\right)r(0)\\!\right)$ $\displaystyle=0,$

where we apply equation (30) and $\overline{T}_{a}v_{i}=v_{i}$. Therefore, we
know the dynamics (V-B) indeed evolves in subspace $\overline{\mathcal{S}}$,
where
$\overline{\mathcal{S}}=\\{z\in\mathbb{R}^{MN}:(v_{i}\otimes\mathbf{1}_{N})^{T}z=0,i\in[\overline{p}+1]\\}$.

Next, we construct an orthogonal matrix $U=[U_{1},U_{2}]\in\mathbb{R}^{M\times
M}$ with $U_{1}=[v_{1},v_{2},\dots,v_{\overline{p}+1}]$ and
$U_{2}=[u_{1},u_{2},\dots,u_{M-\overline{p}-1}]$. Then further denote subspace
$\mathcal{S}_{c}\\!=\\!\operatorname{span}\\{u_{1}\otimes\mathbf{1}_{N},\dots,u_{M-\overline{p}-1}\otimes\mathbf{1}_{N}\\}$,
and it holds that

$\overline{\mathcal{S}}=\mathcal{S}\oplus\mathcal{S}_{c},$ (33)

i.e., $\mathcal{S}_{c}$ is the orthogonal complement of subspace $\mathcal{S}$
in $\overline{\mathcal{S}}$, where subspace $\mathcal{S}$ is defined in (22).
In order to show (33), we only need verify that

  1. i)

$\mathcal{S}\subset\overline{\mathcal{S}}$ and
$\mathcal{S}_{c}\subset\overline{\mathcal{S}}$,

  2. ii)

$\dim(\mathcal{S}+\mathcal{S}_{c})=\dim(\overline{\mathcal{S}})$,

  3. iii)

$\mathcal{S}\perp\mathcal{S}_{c}$,

where i) follows the fact that $v_{i}^{T}u_{j}=0$, $\forall
i\in[\overline{p}+1],j\in[M-\overline{p}-1]$, ii) is due to
$\dim(\mathcal{S}+\mathcal{S}_{c})=\dim(\mathcal{S})+\dim(\mathcal{S}_{c})+\dim(\mathcal{S}\cap\mathcal{S}_{c})=(MN-M)+(M-\overline{p}-1)+0=MN-\overline{p}-1$,
and iii) is because for any $z_{s}\in\mathcal{S}$, and
$z_{s_{c}}\in\mathcal{S}_{c}$, we have $z_{s}^{T}z_{s_{c}}=0$.

Now we can define the Lyapunov function for the dynamics (V-B) as
$V:\overline{\mathcal{S}}\to\mathbb{R}^{+}$ with $V(z)=z^{T}z$. Then for any
$z\in\overline{\mathcal{S}}$ we have

$\displaystyle\,\mathbb{E}\left[V\bigg{(}G^{T}\Pi
G(I_{MN}-\gamma\overline{L}(t))z\bigg{)}\right]$ $\displaystyle\leq$
$\displaystyle\,\mathbb{E}\left[\bigg{\|}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}z\bigg{\|}^{2}\right]$
$\displaystyle=$
$\displaystyle\,\mathbb{E}\left[\bigg{\|}\big{(}I_{MN}-\gamma\overline{L}(t)\big{)}z_{s}+z_{s_{c}}\bigg{\|}^{2}\right]$
$\displaystyle=$
$\displaystyle\,\mathbb{E}\left[\bigg{\|}\big{(}I_{MN}\\!-\\!\gamma\overline{L}(t)\big{)}z_{s}\bigg{\|}^{2}\\!\\!\\!+\\!\left\|z_{s_{c}}\right\|^{2}\\!\\!\\!+\\!2z_{s}^{T}\big{(}I_{MN}\\!-\\!\gamma\overline{L}(t)\big{)}z_{s_{c}}\\!\right]$
$\displaystyle\leq$
$\displaystyle\,\overline{c}\left\|z_{s}\right\|^{2}+\left\|z_{s_{c}}\right\|^{2},$
(34)

where $z=z_{s}+z_{s_{c}}$ with $z_{s}\in\mathcal{S}$,
$z_{s_{c}}\in\mathcal{S}_{c}$ due to (33), and $\overline{c}$ is defined in
(24). Note that in (V-B) we use $\sigma(G^{T}\Pi G)\subset\\{0,1\\}$ in the
first inequality, apply $\overline{L}(t)z_{s_{c}}=0$ to the first equality and
the last inequality, and also apply a similar technique used in (24) to obtain
the last inequality.

In the end, as $\overline{c}\in[\frac{d_{max}-1}{2d_{max}-1},1)$, we have
$\mathbb{E}\left[V\left(G^{T}\Pi
G(I_{MN}-\gamma\overline{L}(t))z\right)\right]\leq\tilde{c}V(z)$ with
$\tilde{c}<1$, then the assertion follows by using Lemma 1. ∎

Next, we are ready to prove Theorem 7.

###### Proof of Theorem 7.

By combining Lemma 5 and Proposition 12, Theorem 7 follows with

$\lim_{t\to\infty}x_{i}(t)=x_{\infty},\qquad\forall i\in[N],$

almost surely, for any initial condition $\\{x_{i}(0)\\}_{i\in\mathcal{V}}$,
where

$x_{\infty}=\sum_{k\in[M]}[\overline{r}_{\infty}]_{k}\frac{\prod_{\ell\in[M]\setminus\\{k\\}}(-s_{\ell})}{\prod_{\ell\in[M]\setminus\\{k\\}}(s_{k}-s_{\ell})},$
(35)

with $[\overline{r}_{\infty}]_{k}$ is the $k$-th element of
$\overline{r}_{\infty}$. ∎

######  Remark 6.

For dynamics (26), we give in Appendix -B the intuition on how to find the
steady state
$\overline{r}_{\infty}=\frac{1}{N}\left(\overline{T}_{a}\otimes\mathbf{1}_{N}^{T}\right)r(0)$
on which each node reaches consensus.

######  Remark 7.

In Problem 1, if the agent’s state has a dimension $d>1$, a natural way to
extend the proposed method is to applying the update law (9) element-wise for
each dimension. It will result in a consensus problem for in total $(M\times
N\times d)$ encoded states.

##  VI Numerical examples

To illustrate the theory, in this section, two numerical examples are given.
In the first, we consider a network with all the nodes owning an identical
privacy degree, and in the second, each node is allowed to have a distinct
privacy degree.

###  VI-A Example with common privacy degree

We consider a network involving $N=6$ nodes, whose connection topology is
specified by an undirected graph as shown in Figure 1. To solve the problem of
privacy-perserving consensus raised in Problem 1 with all the nodes sharing a
common privacy degree $2$, i.e., $p=2\mathbf{1}_{N}$, we apply the proposed
Algorithm 1 and update law (9).

Figure 1: The interconnection graph of the network

According to the requirement in Theorem 6, we take the number of channels
$M=2d_{max}-1=7$, $\gamma=0.95$, and communication keys $S=(1,2,\dots,M)$.
Moreover, for each node $i\in[N]$, the initial encoding functions
$f_{i}(\theta,0)$ is constructed following (5) with a set of randomized and
privately known initial coefficients $\left\\{a_{i1}(0),\,a_{i2}(0)\right\\}$.
Then the initial encoded state can be accordingly computed as
$r_{i}^{k}(0)=f_{i}(s_{k},0)$, for $i\in\mathcal{V},k\in[M]$.

Figure 2: The trajectory of the encoded state on each channel $k\in[M]$ in the
case with a common privacy degree.

Next, we implement update law (9) with the channel selection variable
$c_{ij}(t)$ assigned through Algorithm 1 at the beginning of each time
instant. The trajectory of the encoded state on all the channels are shown in
Figure 2, and the state trajectory $x_{i}(t)$ is shown in Figure 3-(a). As can
be seen, both the encoded state corresponding to each channel and the state
$x_{i}(t)$ reach consensus eventually for all the nodes.

Furthermore, we compare the convergence speed of the proposed privacy-
preserving algorithm with that of the conventional consensus algorithm555 The
conventional consensus algorithm under the undirected communication topology
is given by
$x_{i}(t+1)=x_{i}(t)+\overline{\gamma}\sum_{j\in\mathcal{V}}\left(x_{j}(t)-x_{i}(t)\right),$
(36) where the step size $\overline{\gamma}\in(0,\frac{1}{d_{max}})$. More
details can be found in [65].  which is shown in Figure 3-(b). We see that the
privacy-preserving method compensates convergence speed for the secure of
individual privacy, which is actually a natural result of the fact that the
update law (9) proceeds a consensus operation between pairs of neighbors only
on one channel in each iteration.

Figure 3: The state trajectory of the privacy-preserving and conventional
consensus methods: (a) is the state trajectory given by the privacy-preserving
method. (b) shows the sate trajectory of the conventional consensus algorithm
(36) with $\overline{\gamma}=1/(d_{max}+1)$.

###  VI-B Example with various privacy degrees

We then consider the case of agents owing different privacy degree. The system
consists of also $N=6$ nodes with a same network topology as that given in
Figure 1. We set the privacy degree $p_{i}=|\mathcal{N}_{i}|-1$,
$i\in\mathcal{V}$, using which the privacy of a node $i$ is disclosed only if
all its neighbors collude, or all neighbors are attacked by an adversary.

The same number of channels $M$, step size $\gamma$, and communication keys
$S$ are selected as those in Section VI-A. Then the update law (9) with the
handshake procedure given in Algorithm 1 are simulated. The resulted
trajectory of the encoded state on each channel $k\in[M]$ and trajectory of
the state $x_{i}(t)$ are depicted in Figure 4 and Figure 5, respectively. We
can see that the consensus is eventually reached for all the nodes.

Figure 4: The trajectory of the encoded state on all channels in the case with
different individual privacy degrees. Figure 5: The state trajectory of the
privacy-preserving consensus method in the case with different individual
privacy degrees.

##  VII Conclusion and future work

In this work, we propose a privacy-preserving algorithm to solve the consensus
problem based on the secret sharing schemes, in which a network of agents
reach an agreement on their states without exposing their individual state
until an agreement is reached. Moreover, the proposed algorithm has an exact
privacy degree. As a result, the system not only preserves the individual
privacy, but also remains the reconstructability of individual states if more
than a threshold amount of communication information is given.

In future work, such an idea can be extended to more problems involving
network dynamics, such as formation control and distributed optimization. It
would be also interesting to see following study to exploit the proposed
algorithm in the relevant applications. One application is privacy-preserving
voting in networks, where a consensus problem is raised when each agents have
an initial state of either $0$ or $1$ representing its preference for two
candidates, and the majority can be found by averaging all the initial states.
The other applications involve opinion agreement, sensor network averaging,
survey mechanism, and distributed decision making.

###  -A Proof of Lemma 1

###### Proof.

First we denote $\mathcal{M}_{t}=\\{x\in\mathcal{S}:V_{t}(x)=0\\}$, then
$\mathcal{M}=\liminf_{t\to\infty}\mathcal{M}_{t}$. Moreover, due to the radial
undboundedness, function $V_{t}(x)$ is proper, i.e., for any compact set
$A\subset\mathbb{R}$, we have $V_{t}^{-1}(A):=\\{x\in\mathcal{S}:V_{t}(x)\in
A\\}$ is compact.

According to Prop. 3.1 in [61], the solution $\\{x(t)\\}_{t\geq 0}$ satisfies

$\lim_{t\to\infty}V_{t}(x(t))=0,\quad a.s.$

Then take the realization $(w^{*}_{t})_{t\geq 0}$ such that the corresponding
solution satisfies $\lim_{t\to\infty}V_{t}(x^{*}(t))=0$, where

$\displaystyle x^{*}(t+1)$ $\displaystyle=F(x^{*}(t),w^{*}_{t}),$
$\displaystyle x^{*}(0)$ $\displaystyle=x(0).$

Note that the probability of $(w^{*}_{t})_{t\geq 0}$ satisfying the above
condition is exactly $1$.

Due to the fact that $V_{t}(x)$ is proper, we have solution $\\{x^{*}(t)\\}$
is bounded. Then there is a positive limit set $L^{+}$ satisfying that for any
$p\in L^{+}$, there is a subsequence $\\{t_{\ell}\\}_{\ell}\subset\mathbb{N}$
with $t_{\ell}\to\infty$ and $x^{*}(t_{\ell})\to p$ as $\ell\to\infty$.
Further, as we know $\lim_{t\to\infty}V_{t}(x^{*}(t))=0$, it holds that
$\lim_{t\to\infty}V_{t}(p)=0$. This implies that

$L^{+}\subset\liminf_{t\to\infty}\mathcal{M}_{t},$

which proves the assertion. ∎

###  -B Intuition to determine $\overline{r}_{\infty}$ in Section V.B

Let $r_{\infty}\in\mathbb{R}^{MN}$ be the point to which the dynamics (26)
almost surely converges. We first notice that due to property i) in Lemma 11,
there are invariant variables in dynamics (26) being

$\displaystyle(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}r(t+1)$
$\displaystyle=(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}(I_{MN}-\gamma\overline{L}(t))r(t)$
$\displaystyle=(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}r(t)$
$\displaystyle=\dots=(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}r(0),$

for any $t\in\mathbb{N}$, where
$\widetilde{\Phi}=(v_{1},v_{2},\dots,v_{\overline{p}+1})\in\mathbb{R}^{M\times(\overline{p}+1)}$,
and $v_{i}$ is defined in (27). This further implies that

$(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}r_{\infty}=(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}r(0).$
(37)

Next, we assume the following Assumption holds.

######  Assumption 1.

$r_{\infty}$ is a consensus point, i.e.,
$r_{\infty}=\overline{r}_{\infty}\otimes\mathbf{1}_{N}$, for some vector
$\overline{r}_{\infty}\in\mathbb{R}^{M}$.

Moreover, as point $r_{\infty}$ is invariant under dynamics (26), i.e.,
$G^{T}\Pi\,G\,(I_{MN}-\gamma\overline{L}(t))\,r_{\infty}=r_{\infty}$, we have
under Assumption 1,

$\displaystyle
G^{T}\Pi\,G\,\left(\overline{r}_{\infty}\otimes\mathbf{1}_{N}\right)=\overline{r}_{\infty}\otimes\mathbf{1}_{N}.$

This further leads to that vector $\overline{r}_{\infty}$ satisfies

$\overline{T}_{i}\overline{r}_{\infty}=\overline{r}_{\infty},\quad\forall
i\in\mathcal{V}.$ (38)

As $\overline{T}_{i}$ is the projection matrix on subspace
$\operatorname{span}\Phi_{i}$, it holds that
$\overline{r}_{\infty}\in\operatorname{span}\widetilde{\Phi}$.

Then, let $\overline{r}_{\infty}=\widetilde{\Phi}\vartheta$, for some
$\vartheta\in\mathbb{R}^{\overline{p}+1}$. By using equation (37), we have

$(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}(\widetilde{\Phi}\otimes\mathbf{1}_{N})\vartheta=(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}r(0).$

Therefore, we can solve that
$\vartheta=\frac{1}{N}(\widetilde{\Phi}^{T}\widetilde{\Phi})^{-1}(\widetilde{\Phi}\otimes\mathbf{1}_{N})^{T}r(0)$.
Finally, we have

$\overline{r}_{\infty}=\widetilde{\Phi}\vartheta=\frac{1}{N}(\overline{T}_{a}\otimes\mathbf{1}_{N})^{T}r(0).$

In the end, as the convergence analysis in Section V.B is independent of any
assumption, we conclude that Assumption 1 indeed holds.

## References

  * [1] K. Ashton et al., “That ‘internet of things’ thing,” RFID journal, vol. 22, no. 7, pp. 97–114, 2009.
  * [2] S. Chen, H. Xu, D. Liu, B. Hu, and H. Wang, “A vision of iot: Applications, challenges, and opportunities with china perspective,” IEEE Internet of Things Journal, vol. 1, no. 4, pp. 349–359, 2014.
  * [3] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE Internet of Things Journal, vol. 3, no. 5, pp. 637–646, 2016.
  * [4] Q. Wu, G. Ding, Y. Xu, S. Feng, Z. Du, J. Wang, and K. Long, “Cognitive internet of things: A new paradigm beyond connection,” IEEE Internet of Things Journal, vol. 1, no. 2, pp. 129–143, 2014.
  * [5] Y. Yang, L. Wu, G. Yin, L. Li, and H. Zhao, “A survey on security and privacy issues in internet-of-things,” IEEE Internet of Things Journal, vol. 4, no. 5, pp. 1250–1258, 2017.
  * [6] A. Zanella, N. Bui, A. Castellani, L. Vangelista, and M. Zorzi, “Internet of things for smart cities,” IEEE Internet of Things Journal, vol. 1, no. 1, pp. 22–32, 2014.
  * [7] G. W. Hart, “Nonintrusive appliance load monitoring,” Proceedings of the IEEE, vol. 80, no. 12, pp. 1870–1891, 1992.
  * [8] A. R. Beresford and F. Stajano, “Location privacy in pervasive computing,” IEEE Pervasive computing, vol. 2, no. 1, pp. 46–55, 2003.
  * [9] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (A. Singh and J. Zhu, eds.), vol. 54 of Proceedings of Machine Learning Research, pp. 1273–1282, PMLR, 2017\.
  * [10] M. Ambrosin, P. Braca, M. Conti, and R. Lazzeretti, “Odin: O bfuscation-based privacy-preserving consensus algorithm for d ecentralized i nformation fusion in smart device n etworks,” ACM Transactions on Internet Technology (TOIT), vol. 18, no. 1, pp. 1–22, 2017.
  * [11] J. Cortés, G. E. Dullerud, S. Han, J. Le Ny, S. Mitra, and G. J. Pappas, “Differential privacy in control and network systems,” in 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 4252–4272, IEEE, 2016.
  * [12] Y. Liu, J. Wu, I. R. Manchester, and G. Shi, “Dynamical privacy in distributed computing–part i: Privacy loss and ppsc mechanism,” arXiv preprint arXiv:1902.06966, 2019.
  * [13] L. M. S. De Souza, H. Vogt, and M. Beigl, “A survey on fault tolerance in wireless sensor networks,” Interner Bericht. Fakultät für Informatik, Universität Karlsruhe, 2007.
  * [14] T. Korkmaz and K. Sarac, “Characterizing link and path reliability in large-scale wireless sensor networks,” in 2010 IEEE 6th International Conference on Wireless and Mobile Computing, Networking and Communications, pp. 217–224, IEEE, 2010.
  * [15] E. Sisinni, A. Saifullah, S. Han, U. Jennehag, and M. Gidlund, “Industrial internet of things: Challenges, opportunities, and directions,” IEEE Transactions on Industrial Informatics, vol. 14, no. 11, pp. 4724–4734, 2018\.
  * [16] A. A. Abbasi, M. F. Younis, and U. A. Baroudi, “Recovering from a node failure in wireless sensor-actor networks with minimal topology changes,” IEEE Transactions on vehicular technology, vol. 62, no. 1, pp. 256–271, 2012.
  * [17] L. Ang, K. P. Seng, A. M. Zungeru, and G. K. Ijemaru, “Big sensor data systems for smart cities,” IEEE Internet of Things Journal, vol. 4, no. 5, pp. 1259–1271, 2017.
  * [18] M. A. Di Muro, C. E. La Rocca, H. E. Stanley, S. Havlin, and L. A. Braunstein, “Recovery of interdependent networks,” Scientific reports, vol. 6, no. 1, pp. 1–11, 2016.
  * [19] A. Majdandzic, B. Podobnik, S. V. Buldyrev, D. Y. Kenett, S. Havlin, and H. E. Stanley, “Spontaneous recovery in dynamical networks,” Nature Physics, vol. 10, no. 1, pp. 34–38, 2014.
  * [20] N. Shahriar, R. Ahmed, S. R. Chowdhury, A. Khan, R. Boutaba, and J. Mitra, “Generalized recovery from node failure in virtual network embedding,” IEEE Transactions on Network and Service Management, vol. 14, no. 2, pp. 261–274, 2017.
  * [21] M. Chiang and T. Zhang, “Fog and iot: An overview of research opportunities,” IEEE Internet of Things Journal, vol. 3, no. 6, pp. 854–864, 2016.
  * [22] J. A. Stankovic, “Research directions for the internet of things,” IEEE Internet of Things Journal, vol. 1, no. 1, pp. 3–9, 2014.
  * [23] M. Weiner, M. Jorgovanovic, A. Sahai, and B. Nikolié, “Design of a low-latency, high-reliability wireless communication system for control applications,” in 2014 IEEE International conference on communications (ICC), pp. 3829–3835, IEEE, 2014.
  * [24] M. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.
  * [25] W. Li, Z. Wang, G. Wei, L. Ma, J. Hu, and D. Ding, “A survey on multisensor fusion and consensus filtering for sensor networks,” Discrete Dynamics in Nature and Society, vol. 2015, p. 12, 2015.
  * [26] R. Olfati-Saber and J. S. Shamma, “Consensus filters for sensor networks and distributed sensor fusion,” in Proceedings of the 44th IEEE Conference on Decision and Control, pp. 6698–6703, 2005.
  * [27] J. Choi, S. Li, X. Wang, and J. Ha, “A general distributed consensus algorithm for wireless sensor networks,” in 2012 Wireless Advanced (WiAd), pp. 16–21, 2012.
  * [28] W. Yu, G. Chen, Z. Wang, and W. Yang, “Distributed consensus filtering in sensor networks,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 39, no. 6, pp. 1568–1577, 2009.
  * [29] N. Amelina, A. Fradkov, Y. Jiang, and D. J. Vergados, “Approximate consensus in stochastic networks with application to load balancing,” IEEE Transactions on Information Theory, vol. 61, no. 4, pp. 1739–1752, 2015\.
  * [30] Z. Wang, M. M. Hayat, M. Rahnamay-Naeini, Y. Mostofi, and J. E. Pezoa, “Consensus-based estimation protocol for decentralized dynamic load balancing over partially connected networks,” in 2011 50th IEEE Conference on Decision and Control and European Control Conference, pp. 4572–4579, 2011.
  * [31] J. He, H. Li, J. Chen, and P. Cheng, “Study of consensus-based time synchronization in wireless sensor networks,” ISA Transactions, vol. 53, no. 2, pp. 347–357, 2014.
  * [32] L. Schenato and F. Fiorentin, “Average timesynch: A consensus-based protocol for clock synchronization in wireless sensor networks,” Automatica, vol. 47, no. 9, pp. 1878–1886, 2011.
  * [33] Y. Xu, W. Liu, and J. Gong, “Stable multi-agent-based load shedding algorithm for power systems,” IEEE Transactions on Power Systems, vol. 26, no. 4, pp. 2006–2014, 2011.
  * [34] T. Zhao and Z. Ding, “Distributed agent consensus-based optimal resource management for microgrids,” IEEE Transactions on Sustainable Energy, vol. 9, no. 1, pp. 443–452, 2018.
  * [35] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
  * [36] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1245–1260, 2017.
  * [37] W. Song, J. Markdahl, S. Zhang, X. Hu, and Y. Hong, “Intrinsic reduced attitude formation with ring inter-agent graph,” Automatica, vol. 85, pp. 193–201, 2017.
  * [38] S. Zhang, W. Song, F. He, Y. Hong, and X. Hu, “Intrinsic tetrahedron formation of reduced attitude,” Automatica, vol. 87, pp. 375–382, 2018.
  * [39] S. Zhang, F. He, Y. Hong, and X. Hu, “An intrinsic approach to formation control of regular polyhedra for reduced attitudes,” Automatica, vol. 111, p. 108619, 2020.
  * [40] S. Zhang, A. Ringh, X. Hu, and J. Karlsson, “Modeling collective behaviors: A moment-based approach,” IEEE Transactions on Automatic Control, 2020.
  * [41] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” IEEE Signal Processing Magazine, vol. 37, pp. 50––60, May 2020.
  * [42] M. Jelasity, W. Kowalczyk, and M. van Steen, “An approach to massively distributed aggregate computing on peer-to-peer networks,” in 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2004\. Proceedings., pp. 200–207, 2004.
  * [43] D. Kempe, A. Dobra, and J. Gehrke, “Gossip-based computation of aggregate information,” in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp. 482–491, 2003.
  * [44] C. Altafini, “A dynamical approach to privacy preserving average consensus,” in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 4501–4506, IEEE, 2019.
  * [45] N. Gupta, J. Katz, and N. Chopra, “Privacy in distributed average consensus,” IFAC-PapersOnLine, vol. 50, no. 1, pp. 9515–9520, 2017.
  * [46] N. Manitara and C. Hadjicostis, “Privacy-preserving asymptotic average consensus,” in 2013 European Control Conference (ECC), pp. 760–765, IEEE, 2013.
  * [47] N. Rezazadeh and S. Kia, “Privacy preservation in a continuous-time static average consensus algorithm over directed graphs,” in 2018 Annual American Control Conference (ACC), pp. 5890–5895, IEEE, 2018.
  * [48] Y. Wang, “Privacy-preserving average consensus via state decomposition,” IEEE Transactions on Automatic Control, vol. 64, no. 11, pp. 4711–4716, 2019.
  * [49] S. Zhang, T. O. Timoudas, and M. Dahleh, “Consensus with preserved privacy against neighbor collusion,” arXiv preprint arXiv:2011.09646, 2020.
  * [50] J. He, L. Cai, C. Zhao, P. Cheng, and X. Guan, “Privacy-preserving average consensus: privacy analysis and algorithm design,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 1, pp. 127–138, 2018.
  * [51] M. Kefayati, M. Talebi, B. Khalaj, and H. Rabiee, “Secure consensus averaging in sensor networks using random offsets,” in 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, pp. 556–560, IEEE, 2007.
  * [52] 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, pp. 81–90, 2012.
  * [53] Y. Mo and R. Murray, “Privacy preserving average consensus,” IEEE Transactions on Automatic Control, vol. 62, no. 2, pp. 753–765, 2016.
  * [54] A. B. Alexandru, M. S. Darup, and G. J. Pappas, “Encrypted cooperative control revisited,” in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 7196–7202, IEEE, 2019.
  * [55] M. Ruan, H. Gao, and Y. Wang, “Secure and privacy-preserving consensus,” IEEE Transactions on Automatic Control, vol. 64, no. 10, pp. 4035–4049, 2019\.
  * [56] O. Ayaso, D. Shah, and M. A. Dahleh, “Information theoretic bounds for distributed computation over networks of point-to-point channels,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6020–6039, 2010.
  * [57] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, (New York, NY, USA), pp. 1175––1191, Association for Computing Machinery, 2017.
  * [58] A. Beimel, “Secret-sharing schemes: a survey,” in International Conference on Coding and Cryptology, pp. 11–46, Springer, 2011.
  * [59] A. Shamir, “How to share a secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, 1979.
  * [60] 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.
  * [61] W. Zhang, X. Lin, and B. Chen, “Lasalle-type theorem and its applications to infinite horizon optimal control of discrete-time nonlinear stochastic systems,” IEEE Transactions on Automatic Control, vol. 62, no. 1, pp. 250–261, 2016.
  * [62] N. Al Ebri, J. Baek, and C. Y. Yeun, “Study on secret sharing schemes (sss) and their applications,” in 2011 International Conference for Internet Technology and Secured Transactions, pp. 40–45, IEEE, 2011.
  * [63] S. Iftene, “Secret sharing schemes with applications in security protocols.,” Sci. Ann. Cuza Univ., vol. 16, pp. 63–96, 2006.
  * [64] B. Schoenmakers, “A simple publicly verifiable secret sharing scheme and its application to electronic voting,” in Annual International Cryptology Conference, pp. 148–164, Springer, 1999.
  * [65] R. Olfati-Saber, A. Fax, and R. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, vol. 95, no. 1, pp. 215–233, 2007.

|  Silun Zhang (S’16–M’20) received his B.Eng. and M.Sc. degrees in Automation
from Harbin Institute of Technology, China, in 2011 and 2013, respectively,
and the PhD degree in Optimization and Systems Theory from Department of
Mathematics, KTH Royal Institute of Technology, Sweden, in 2019. Dr. Zhang is
currently a Wallenberg postdoctoral fellow with the Laboratory for Information
and Decision Systems (LIDS), MIT, USA. His main research interests include
nonlinear control, networked systems, rigid-body attitude control, security
and privacy in multi-party computation, and modeling large-scale systems.
---|---
|  Thomas Ohlson Timoudas received his PhD degree in Mathematics in October
2018 from KTH Royal Institute of Technology, Sweden, and his MSc (2013) and
BSc (2012) degrees in Mathematics from Stockholm university, Sweden. He is
currently a postdoctoral researcher with the Department of Network and Systems
Engineering at KTH Royal Institute of Technology, Sweden. His main research
interests include dynamical systems, networked systems, internet of things,
and distributed algorithms.
---|---
|  Munther A. Dahleh (S’84–M’87–SM’97–F’01) received his Ph.D. degree from
Rice University, Houston, TX, in 1987 in Electrical and Computer Engineering.
Since then, he has been with the Department of Electrical Engineering and
Computer Science (EECS), MIT, Cambridge, MA, where he is now the William A.
Coolidge Professor of EECS. He is also a faculty affiliate of the Sloan School
of Management. He is the founding director of the newly formed MIT Institute
for Data, Systems, and Society (IDSS). Previously, he held the positions of
Associate Department Head of EECS, Acting Director of the Engineering Systems
Division, and Acting Director of the Laboratory for Information and Decision
Systems. He was a visiting Professor at the Department of Electrical
Engineering, California Institute of Technology, Pasadena, CA, for the Spring
of 1993. He has consulted for various national research laboratories and
companies. Dr. Dahleh is interested in Networked Systems with applications to
Social and Economic Networks, financial networks, Transportation Networks,
Neural Networks, and the Power Grid. Specifically, he focuses on the
development of foundational theory necessary to understand, monitor, and
control systemic risk in interconnected systems. He is four-time recipient of
the George Axelby outstanding paper award for best paper in IEEE Transactions
on Automatic Control. He is also the recipient of the Donald P. Eckman award
from the American Control Council in 1993 for the best control engineer under
35. He is a fellow of IEEE and IFAC.
---|---