# Provably Private Distributed Averaging Consensus:
An Information-Theoretic Approach

Mohammad Fereydounian Department of Electrical and Systems Engineering,
University of Pennsylvania, Philadelphia, PA, USA. Emails: {mferey,
<EMAIL_ADDRESS>Aryan Mokhtari Department of Electrical and Computer
Engineering, University of Texas at Austin, Austin, TX, USA. Email:
<EMAIL_ADDRESS>Ramtin Pedarsani Department of Electrical and
Computer Engineering, University of California, Santa Barbara, CA, USA. Email:
<EMAIL_ADDRESS>Hamed Hassani11footnotemark: 1

###### Abstract

In this work, we focus on solving a decentralized consensus problem in a
private manner. Specifically, we consider a setting in which a group of nodes,
connected through a network, aim at computing the mean of their local values
without revealing those values to each other. The distributed consensus
problem is a classic problem that has been extensively studied and its
convergence characteristics are well-known. Alas, state-of-the-art consensus
methods build on the idea of exchanging local information with neighboring
nodes which leaks information about the users’ local values. We propose an
algorithmic framework that is capable of achieving the convergence limit and
rate of classic consensus algorithms while keeping the users’ local values
private. The key idea of our proposed method is to carefully design noisy
messages that are passed from each node to its neighbors such that the
consensus algorithm still converges precisely to the average of local values,
while a minimum amount of information about local values is leaked. We
formalize this by precisely characterizing the mutual information between the
private message of a node and all the messages that another adversary collects
over time. We prove that our method is capable of preserving users’ privacy
for any network without a so-called generalized leaf, and formalize the trade-
off between privacy and convergence time. Unlike many private algorithms, any
desired accuracy is achievable by our method, and the required level of
privacy only affects the convergence time.

##  1 Introduction

In this paper, we focus on a classic distributed computing problem in which a
group of connected agents aim to find the average of their local values, also
known as the consensus problem. Due to applications of the consensus problem
in many domains, such as sensor fusion [24, 30, 12], distributed energy
management [33], Internet of Things [5], and large-scale machine learning and
federated learning [3, 20], it has been widely studied in the literature [29,
23, 16].

A common feature in most classic consensus algorithms is the requirement for
sharing the local values with neighboring nodes. However, this approach is,
indeed, problematic in settings that nodes are not willing to share their
exact local value (opinion or belief) due to privacy concerns [21]. An example
would be in the case where members of a social network aim to compute their
common opinion on a subject, but want to keep their personal opinions secret
[7]. This issue has motivated a new line of research which focuses on the
possibility of achieving consensus in a fully decentralized manner without
disclosing the initial nodes’ value.

To provide privacy in the consensus problem, the first step is to define a
measure that quantifies it. Differential privacy [6, 8] is the most studied
measure of privacy for an algorithm running over a dataset. This notion
measures the privacy based on the statistical dependency of an algorithm’s
output to the perturbation of a single element of the input dataset. Noting
that the classic consensus method is a deterministic procedure, the most
common approach for a private consensus algorithm in the literature is that
each node perturbs its signals by some form of noise such that the resulting
stochastic algorithm is differentially private [15, 22, 9, 4, 2, 17, 14, 13,
21, 19]. However, these approaches suffer from some drawbacks. Adding
perturbing noises affects the convergence properties compared to non-private
consensus algorithms in two ways: (i) It leads to a non-exact limit, and (ii)
it compromises the convergence rate, i.e., it leads to slower convergence
rates, e.g., slower than the rates achieved by [29]. While some methods
address the non-exact limit by adding zero-sum correlated noise [13, 21], no
prior study has addressed both (i) and (ii) simultaneously. This issue
persists for any iterative method that perturbs in some way the communication
messages at each iteration either randomly or in a deterministic manner. This
includes works that use methods like output masking [1], state decomposition
[28], splitting messages into segments and adding noise to each segment [14],
observability methods [18, 25], edge-based perturbation methods [10, 31], and
Homomorphic encryption-based methods [11, 32, 27].

Indeed, differential-privacy is a powerful measure for indicating the level of
privacy of a learning algorithm running over a dataset. This is done by
quantifying the statistical dependency of the algorithm’s output to a
perturbation of a single input data point. This approach is best applicable
when a full list of data points is accessible by the adversary. Alas, in a
consensus setting, the data available at one user, i.e., the messages it
collects from its neighbors over time, is different from the data available at
other users. By injecting extra noise to all communication messages in a
consensus algorithm, the differential-privacy approaches mask the private
values against an adversary that can eavesdrop all messages. The cost to
defeat this adversary appears on convergence side as discussed above. However,
in a setting that the adversary can gain access to only a single node’s
information, such approaches provide more than necessary privacy with an
unwanted cost. Hence, to handle the consensus setting with such type of
adversary and asymmetric data distribution, differential privacy must be
replaced with a more compatible privacy measure.

Motivated by this point, we provide a novel information-theoretic scheme to
measure and analyze privacy leakage in consensus problems. We further provide
simple noise-aggregation methods to reach the exact consensus in a private
manner while achieving the fastest rate that a non-private consensus method
can achieve. These advantages are based on the fact that our proposed provably
private averaging consensus (PPAC) method only modifies the initial values of
the consensus dynamic and leaves the consensus procedure intact. Moreover, we
use a probabilistic model where the private values are random variables, which
makes our method fundamentally different from most of the prior work. In this
probabilistic framework, we introduce a new measure of privacy leakage based
on the mutual information between the initial value of a node and the set of
messages that is available at another node. In this way, we can capture how
private the initial value of a node is with respect to any other node in the
network. Most of our theoretical results hold regardless of the shape of the
distribution of noises and private values. Next, we state our contributions:

  1. 1.

Given a network structure and a consensus matrix, we propose an algorithm for
reaching consensus among the nodes, while keeping the initial values private
throughout the algorithm and preserving the fastest rate that a non-private
consensus method can achieve.

  2. 2.

We formalize a continuous notion based on the mutual information function that
measures the privacy leakage of any (victim) node at another (adversary) node
that can be (optimally) tuned by our adjustable noise parameters.

  3. 3.

We provide a precise characterization of the information flow of a private
value over the network over time. Having this, even in ill-shaped structures
that leak privacy, we can determine the amount of information that an
adversary receives as a function of time and compute the waiting time until
recovering a private value.

In summary, this paper has two main messages: (i) Privacy from a node’s
perspective can be measured and efficiently analyzed based on the concept of
mutual information. (ii) Splitting private messages into fragments prior to
running the classical consensus method maintains the convergence guarantees
and ensures the privacy for most structures. No further additive noise is
required.

Notation. Column vectors are denoted by small letters in bold font,
$\mathbf{a},\mathbf{b}$, while matrices are denoted by capital non-bold
letters, $A,B$, and scalars by small letters $a,b$. Moreover,
$\\{a_{i}\\}_{i\in I}$ is considered as an ordered sequence of mathematical
objects $a_{i}$, $i\in I$. Concatenation of ordered sequences is denoted by
Cartesian product and when the number of elements are finite, these ordered
sequences are considered as column vectors. For scalars $a_{i}$, the following
example illustrates these notations:

$\left\\{a_{i}\right\\}_{i\in\\{1,2\\}}\times(a_{3},a_{4})\times\left\\{a_{5}\right\\}=\left[a_{1},a_{2},a_{3},a_{4},a_{5}\right]^{\top}.$
(1)

The right-hand side of (1) indicates a column vector with elements
$a_{1},a_{2},a_{3},a_{4},a_{5}$. When $a_{i}\,$s in (1) are replaced with row
vectors, (1) refers to the matrix with rows $a_{1},a_{2},a_{3},a_{4},a_{5}$.
Moreover, note that $\left\\{a_{i}\right\\}_{i\in\\{1,2\\}}$ can be
interpreted as either $[a_{1},a_{2}]^{\top}$ or $[a_{2},a_{1}]^{\top}$. In
this paper, whenever the choice of order is not specified, the argument holds
regardless of the choice. The identity matrix of size $k$ is $I_{k}$ and all
ones (column) vector of length $k$ is $\mathds{1}_{k}$. We use both $A_{ij}$
and $[A]_{ij}$ to denote the $ij$-th element of the matrix $A$. Also, we use
$[A]_{i*}$ and $[A]_{*j}$ to represent the $i$-th row of $A$ as a row vector
and the $j$-th column of $A$ as a column vector. Similarly, $[\mathbf{v}]_{i}$
refers to the $i$-th coordinate of the vector $\mathbf{v}$. Further, $A\geq 0$
means $A_{ij}\geq 0$ for all $i,j$. Further, The notation
$\operatorname{diag}(a_{1},\ldots,a_{n})$ represents an $n\times n$ diagonal
matrix with $a_{i}$ as its $i$-th diagonal element. If
$A=\left\\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\right\\}\subset\mathbb{R}^{n}$,
then $\operatorname{span}(A)=\\{\sum_{i=1}^{k}t_{i}\mathbf{a}_{i}\mid
t_{1},\ldots,t_{k}\in\mathbb{R}\\}$. Further, $[n]=\\{1,\ldots,n\\}$ and
$A\setminus B$ represents set difference for sets $A$ and $B$. Finally, $|A|$
denotes the size of set $A$ and for (real or complex) scalar $a$, $|a|$
denotes the absolute value of $a$.

##  2 Preliminaries

In this section, we recap some basic concepts that we require for presenting
our framework.

Graph Theory. By $G=(V,E)$, we denote a simple graph where $V$ is the set of
nodes and $E$ is the set of (undirected) edges. The distinct nodes $i$ and $j$
are called neighbors if $\\{i,j\\}\in E$. Further, the neighborhood of node
$i$, denoted by $N_{i}$, is the set of all neighbors of node $i$. The degree
of node $i$ is $\deg_{G}(i)=|N_{i}|$. A walk of length $k$ between $i$ and
$j$, is the sequence of nodes $(\ell_{0},\ell_{1},\ldots,\ell_{k})$, where
$\ell_{0}=i$, $\ell_{k}=j$, and all consecutive nodes are neighbors. A graph
is called connected if for every node pair, there is a walk between them. The
minimum $k$ for which a walk of length $k$ exists between $i$ and $j$ is
called the distance between $i$ and $j$ and denoted by $d_{G}(i,j)$. The
eccentricity of node $i$ is the largest distance we can get from node $i$,
i.e., $\operatorname{ecc}_{G}(i)=\max_{j\in V}d_{G}(i,j)$ and the radius of
$G$ is defined as $r(G)=\min_{i\in V}\operatorname{ecc}_{G}(i)$. The adjacency
matrix of a graph $G$ with $n$ nodes is an $n\times n$ matrix denoted by
$A_{G}$, where $\left[A_{G}\right]_{ij}$ is $1$ if $\\{i,j\\}\in E$ and $0$
otherwise.

Matrix Theory. For matrices $A$ and $B$, we define $A\sim B$ if for every
$i\neq j$, $A_{ij}=0$ if and only if $B_{ij}=0$. Spectral radius of
$A\in\mathbb{R}^{n\times n}$ with eigenvalues $\lambda_{1},\ldots,\lambda_{n}$
is $\rho(A)=\max_{i\in[n]}\\{|\lambda_{i}|\\}$. For $A\in\mathbb{R}^{n\times
n}$, its minimal polynomial $\mu_{A}$ is defined as the unique monic
polynomial with minimum degree such that $\mu_{A}(A)=0$. By Cayley-Hamilton
theorem, $\deg(\mu_{A})\leq n$ (see [26]).

Given an infinite sequence of vectors $\\{\mathbf{a}_{i}\\}_{i=0}^{\infty}$,
where $\mathbf{a}_{i}\in\mathbb{R}^{n}$ and $\mathbf{a}_{0}\neq\mathbf{0}$, we
consider a basis pursuit procedure which constructs a finite subset $B$ of the
elements of the sequence $\left\\{\mathbf{a}_{i}\right\\}_{i=0}^{\infty}$ such
that the elements of $B$ are linearly independent and
$\mathbf{a}_{i}\in\operatorname{span}(B)$ for all $i$ and in this sense, it is
a called a basis for $\\{\mathbf{a}_{i}\\}_{i=0}^{\infty}$ and is denoted by
$B=\mathcal{B}(\\{\mathbf{a}_{i}\\}_{i=0}^{\infty})$. The procedure is as
follows: Add $\mathbf{a}_{0}$ to $B$. For $i>0$, if
$\mathbf{a}_{i}\notin\operatorname{span}(B)$, then add $\mathbf{a}_{i}$ to $B$
and go to the next iteration. We formally prove in the supplementary material
that this procedure results in a basis for
$\\{\mathbf{a}_{i}\\}_{i=0}^{\infty}$.

Information Theory. Consider continuous random variables $X$ and $Y$ which are
defined over spaces $\mathcal{X}$ and $\mathcal{Y}$ with probability density
functions (PDFs) $f_{X}$ and $f_{Y}$, respectively. Moreover, let
$f_{XY}(x,y)$ denote joint PDF of $X$ and $Y$, then their mutual information
$\mathcal{I}(X;Y)$ is defined as

$\mathcal{I}(X;Y)=\int_{\mathcal{X}\times\mathcal{Y}}f_{XY}(x,y)\log\left(\frac{f_{XY}(x,y)}{f_{X}(x)f_{Y}(y)}\right)dxdy.$
(2)

Classical Averaging Consensus. Consider a network represented by a simple
connected graph $G=(V,E)$ over a set of nodes $V=\left\\{1,\ldots,n\right\\}$
with $m=|E|$. We assume only adjacent nodes can exchange information with each
other. Moreover, suppose $u_{i}\in\mathbb{R}$ is the initial value of user
$i$. The main goal in the consensus problem is to reach a state that all nodes
in the network learn the average of initial vectors, i.e.,
$u^{*}=\frac{1}{n}\sum_{i=1}^{n}u_{i}$. Letting $v_{i}(t)$ be the value of
node $i$ at iteration $t$ which is initially set to $v_{i}(0)=u_{i}$, one can
consider a linear update given by

$v_{i}(t+1)=W_{ii}\,v_{i}(t)+\sum_{j\in N_{i}}\,W_{ij}v_{j}(t).$ (3)

Having this, the averaging consensus aims to have
$\lim_{t\to\infty}v_{i}(t)=u^{*}$ for all $i\in[n]$. The consensus matrix
$W\in\mathbb{R}^{n\times n}$ is formed by considering $W_{ij}$ as its $ij$-th
element. Letting $\mathbf{v}(t)=[v_{1}(t),\ldots,v_{n}(t)]^{\top}$, one can
write $\mathbf{v}(t)=W^{t}\mathbf{v}(0)$ seeking to have
$\lim_{t\to\infty}\mathbf{v}(t)=\mathbf{u}^{*}$, where
$\mathbf{u}^{*}=u^{*}\mathds{1}_{n}$. This is equivalent to

$\displaystyle\lim_{t\to\infty}W^{t}=\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}.$
(4)

It is known that Equation 4 holds if and only if (i)
$W\mathds{1}_{n}=W^{\top}\mathds{1}_{n}=\mathds{1}_{n}$ and (ii)
$\rho(W-{1}/{n}\mathds{1}_{n}\mathds{1}_{n}^{\top})<1$, where $\rho(\cdot)$
denotes the spectral radius of a matrix; see [29] for more details. Further,
the convergence rate of (4) can be computed as follows:

$\sup_{\mathbf{v}(0)\neq\mathbf{u}^{*}}\lim_{t\rightarrow\infty}\left(\frac{\|\mathbf{v}(t)-\mathbf{u}^{*}\|_{2}}{\|\mathbf{v}(0)-\mathbf{u}^{*}\|_{2}}\right)^{\frac{1}{t}}=\rho\left(W-\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\right).$
(5)

##  3 Problem Setup

We consider the averaging dynamic described in (3) under the constraint that
the original messages $u_{i}$ must be kept private from other nodes.
Satisfying this requirement rules out the naive initialization of
$v_{i}(0)=u_{i}$. Therefore, we seek new initializations $v_{i}(0)$ to fulfill
the privacy and convergence requirements while following the consensus dynamic
(3). Moreover, we assume that the initial values $u_{i}$ are independent
scalar-valued continuous random variables, but a similar argument is
applicable to a discrete case. Moreover, for a vector-valued $u_{i}$ with
independent coordinates, our results can be applied to each coordinate.

Adversary model. We assume all nodes are honest but curious, meaning that they
follow the protocols and communication principles of the network, but they
might be willing to recover the initial value of other nodes in the network.
This is equivalent to the situation in which an adversary obtains access to
the messages received by a single node. Moreover, we assume that nodes
(adversaries) do not collude in recovering private messages and the underlying
graph and the full consensus matrix are accessible by all nodes (adversaries).

Privacy model. Consider arbitrary distinct nodes $i$ and $j$ and suppose node
$i$ is curious about node $j$’s private value $u_{j}$. Node $i$ only has
access to the $u_{i}$ and all messages it sends to or receives from its
neighbors over time. Denote the concatenation of all these by
$\mathfrak{D}_{i}$. The privacy fails if node $i$ can deterministically
recover $u_{j}$ from $\mathfrak{D}_{i}$. Otherwise, it is important to know
how close node $i$ can statistically estimate $u_{j}$ using
$\mathfrak{D}_{i}$. This can be evaluated by finding how much information
$\mathfrak{D}_{i}$ reveals about $u_{j}$ which can be formalized by the mutual
information between the joint distribution of the elements of
$\mathfrak{D}_{i}$ and $u_{j}$, denoted by
$\mathcal{I}(\mathfrak{D}_{i}\,;u_{j})\in[0,\infty]$. Achieving zero mutual
information is impossible since the consensus goal $u^{*}$ itself reveals some
information about $u_{j}$. Upcoming sections reveal how tuning the model’s
parameters push $\mathcal{I}(\mathfrak{D}_{i}\,;u_{j})$ toward $0$ as much as
possible.

##  4 Private Consensus

In this section, we first explain our method and then introduce a privacy
leakage measure in Section 4.1. As mentioned earlier, the regular averaging
consensus method reveals the private messages at $t=0$ due to the
initialization $v_{i}(0)=u_{i}$. We propose a new initialization for
$v_{i}(0)$ that preserves privacy while leaving most convergence properties
intact. The main idea behind the proposed method is the following: If we
modify the initial vectors $v_{i}(0)$ such that their sum preserves the sum of
the right local values $u_{i}$, i.e.,
$\sum_{i=1}^{n}v_{i}(0)=\sum_{i=1}^{n}u_{i}$, then by following the averaging
consensus dynamic all nodes converge to the optimal value
$u^{*}=\frac{1}{n}\sum_{i=1}^{n}u_{i}$. Now our goal is to select these values
so that they do not reveal the original values $\\{u_{i}\\}_{i\in[n]}$ or
minimize the amount of information that is revealed after a specific number of
communication rounds.

To do so, we proceed as follows. In the first round, which we call the
preparation phase, unlike the traditional consensus approach, each node $i$
does not send the same signal to all its neighbors. Instead, it splits its
private message $u_{i}$ into multiple pieces and distributes it among its
neighbors. All but one of these pieces are pure noise terms, independent from
$u_{i}$. More precisely, in the preparation phase, each node $i$ splits its
private value $u_{i}$ into fragments $\Gamma_{ij}$, where $j\in N_{i}$. Hence,
the number of fragments is equal to the number of neighbors of node $i$. These
elements are selected such that all of them except one are pure noise and
their sum recovers the original signal, i.e.,

$u_{i}=\sum_{j\in N_{i}}\Gamma_{ij}.$ (6)

Formally, to create such signals, node $i$ arbitrarily chooses one of its
neighbors, which we denote by $m_{i}$. For $j\neq m_{i}$, node $i$ sets
$\Gamma_{ij}$ to be a continuous random variable, independent from all other
randomness sources. Then, node $i$ sets $\Gamma_{i\,m_{i}}$ such that (6)
holds, i.e., it sets

$\displaystyle\Gamma_{i\,m_{i}}=u_{i}-\sum_{j\in
N_{i}\setminus\\{m_{i}\\}}\Gamma_{ij}.$ (7)

The following indexing set $S$ distinguishes all pairs $(i,j)$ such that
$\Gamma_{ij}$ is a pure noise term.

$S=\left\\{(i,j)\,\,\mid i\in[n],\,j\in
N_{i}\setminus\left\\{m_{i}\right\\}\right\\}.$ (8)

Note that $|S|=2m-n$, where $m=|E|$. Randomness sources in this model consist
of $n$ private values and $2m-n$ pure noisy messages. Next, we state the
independence requirement.

######  Assumption 4.1.

The concatenation of all $2m$ randomness sources in Algorithm 1, i.e.,
$\\{u_{i}\\}_{i\in[n]}\times\left\\{\Gamma_{ij}\right\\}_{(i,j)\in S}$, where
$S$ is defined as (8) consists of independent elements.

The choice of distribution for randomness sources is arbitrary among
continuous random variables with a valid PDF unless otherwise is specified.
However, it is beneficial to fix a notation for their mean and variances as
follows.

######  Definition 4.2.

For $i\in[n]$ and $(k,\ell)\in S$, let $\mu_{i}$ and $\sigma_{i}^{2}$ be the
mean and variance of $u_{i}$ and $\mu_{k\ell}$ and $\sigma_{k\ell}^{2}$ be the
mean and variance of $\Gamma_{k\ell}$, respectively. Moreover, let
$\mu_{\max}$ be the maximum of the absolute value of all $\mu_{i}$ and
$\mu_{k\ell}$, and define $\sigma_{\max}^{2}$ in a similar manner for
variances.

Algorithm 1 Provably Private Averaging Consensus (PPAC)

Preparation-Phase:

1: for $i\in[n]$ do

2: Node $i$ picks $m_{i}\in N_{i}$ arbitrarily.

3: For all $j\in N_{i}\setminus\left\\{m_{i}\right\\}$: node $i$ generates
noise $\Gamma_{ij}$ and sends it to node $j$

4: Node $i$ computes $\Gamma_{i\,m_{i}}=u_{i}-\sum_{j\in
N_{i}\setminus\\{m_{i}\\}}\Gamma_{ij}$ and sends it to node $m_{i}$.

5: end for

6: for $i\in[n]$ do

7: Node $i$ computes: $v_{i}{(0)}=\sum_{k\in N_{i}}\Gamma_{ki}$.

8: end for

Consensus-Phase:

1: Nodes follow the consensus dynamic in (3) with initial values
$\\{v_{i}{(0)}\\}_{i\in[n]}$.

Once the preparation phase is done and the messages $\Gamma_{ij}$ are
communicated, every node computes its consensus initialization by summing up
the messages that it has received in the preparation phase, that is,
$v_{i}{(0)}=\sum_{k\in N_{i}}\Gamma_{ki}$. After that, all nodes follow the
consensus dynamic described in (3). The steps of our proposed method (PPAC)
are summarized in Algorithm 1.

Note that PPAC preserves the sum property after the preparation phase, i.e.,
$\sum_{i=1}^{n}v_{i}(0)=\sum_{i=1}^{n}u_{i}$. To achieve the exact limit, it
is required to have $W\mathds{1}_{n}=W^{\top}\mathds{1}_{n}=\mathds{1}_{n}$.
This implies that the sum property is preserved during the consensus phase
too, i.e.,
$\sum_{i=1}^{n}v_{i}(t)=\sum_{i=1}^{n}v_{i}(0)=\sum_{i=1}^{n}u_{i}$.

###  4.1 Privacy Leakage Measure

We first provide a mathematical definition to formalize the notion of privacy
leakage that was earlier described in Section 3. Then, we rigorously analyze
this notion.

We start with mathematically formalizing the concatenation of all data that a
node $i$ collects, which was earlier denoted by $\mathfrak{D}_{i}$ in Section
3. The first data available at node $i$ is its own private value $u_{i}$.
Next, in the preparation phase, it generates $\\{\Gamma_{i\ell}\\}_{\ell\in
N_{i}\setminus\\{m_{i}\\}}$. Note that $\Gamma_{i\,m_{i}}$ is a redundant
data, since it is simply the subtraction of other pure noises from $u_{i}$. In
the preparation phase, node $i$ receives $\\{\Gamma_{\ell i}\\}_{\ell\in
N_{i}}$ from its neighbors. Moreover, when the consensus procedure starts, at
time $t\geq 0$, node $\ell\in N_{i}$ transmits $v_{\ell}(t)$ to node $i$ so
that it can compute its new update for the next iteration. Hence, up to time
$t$, node $i$ has received values $v_{\ell}(\tau)$ for all $\ell\in N_{i}$ and
$\tau\in\\{0,\ldots,t\\}$. Hence, the concatenation of node $i$’s observed
data up to time $t$ can be written as

$\displaystyle\mathfrak{D}_{i}(t)=\left\\{u_{i}\right\\}\times\left\\{\Gamma_{i\ell}\right\\}_{\ell\in
N_{i}\setminus\left\\{m_{i}\right\\}}\times\left\\{\Gamma_{\ell
i}\right\\}_{\ell\in N_{i}}\times\left\\{v_{\ell}(\tau)\right\\}_{\ell\in
N_{i},0\leq\tau\leq t}.$ (9)

The notation $\mathfrak{D}_{i}(\infty)$ is also applicable and represents all
the data that node $i$ can gather if the consensus runs forever. To measure
the privacy leakage of $u_{j}$ at node $i$ up to time $t$, we consider the
mutual information between $\mathfrak{D}_{i}(t)$ and $u_{j}$. This is
formalized in the following definition.

######  Definition 4.3 (Privacy Leakage Measure).

Considering the definition of $\mathfrak{D}_{i}(t)$ in (9), the privacy
leakage of node $j$ from the perspective of node $i$ up to time $t$ is defined
as

$\pi_{i}^{(j)}(t):=\mathcal{I}\left(\mathfrak{D}_{i}(t)\,;\,u_{j}\right)\in[0,\infty).$
(10)

Note that smaller $\pi_{i}^{(j)}(t)$ means $u_{j}$ is more private at node $i$
as less information is revealed about it.

##  5 Main Results

Based on the private consensus method in Section 4, our main results can be
stated informally in Theorem 5.1. Formal statements regarding privacy and
convergence are provided in Section 6 and Section 7, respectively.

######  Theorem 5.1 (informal).

Running Algorithm 1 (PPAC) over a network and assuming all randomness sources
are independent, we can conclude the following results:

  1. (i)

For each node $i$, there are only finitely many iterations
$t_{1},\ldots,t_{k}$ that the information of node $i$ about some private
values strictly increases (Theorem 6.2). For the latest of such iterations,
i.e., $t_{k}$, we find an upper-bound $t_{k}\leq n-1$, where $n$ is the number
of all nodes (Proposition 6.3), and a lower-bound
$\operatorname{ecc}_{G}(i)-2\leq t_{k}$, where $\operatorname{ecc}_{G}(i)$ is
the eccentricity of node $i$ (Proposition 6.4).

  2. (ii)

If the network contains a specific sub-structure called a generalized leaf,
defined in Definition 6.7, some nodes can deterministically recover the
private values of some other nodes in the first consensus iteration, i.e.,
privacy fails.

  3. (iii)

If the network does not contain a generalised leaf, no node can fully recover
a private value (Lemma 6.5 and Theorem 6.8). In this case, $\pi_{i}^{(j)}$,
defined in Definition 4.3, measures the amount of leakage of $u_{j}$ to node
$i$, statistically. We obtain a closed form
$\pi_{i}^{(j)}(t)=1/2\log(1+\sigma_{j}^{2}\,\mathbf{a}^{\top}\Sigma^{-1}\mathbf{a})$
for some vector $\mathbf{a}$ and matrix $\Sigma$ (Theorem 6.6). In Section 6,
we discuss the construction of $\mathbf{a}$ and $\Sigma$ through several
steps. In this construction, the quantities $\sigma_{k\ell}^{2}$, the
variances of noisy fragments $\Gamma_{k\ell},\,(k,\ell)\in S$, appear as
linear terms in the elements of $\Sigma$. This shows that $\pi_{i}^{(j)}$ is a
decreasing function in terms of $\sigma_{k\ell}^{2}$.

  4. (iv)

PPAC leaves the convergence limit and rate of the classical averaging
consensus intact. Moreover, the convergence time to achieve an
$\epsilon$-accurate solution by PPAC scales as $\mathcal{O}(\log(1/\epsilon))$
and it also increases proportional to the logarithm of noise parameters
(Theorem 7.2). This shows that tuning $\sigma_{k\ell}^{2}$ adjusts the trade-
off between privacy and convergence time.

Next, we discuss the novel techniques used to achieve the above results. The
baseline in obtaining our results is transforming the information-/graph-
theoretical formulation of the problem into a linear-algebraic form by writing
the data collection at each node as a matrix-vector decomposition
$\mathfrak{D}_{i}(t)=\mathfrak{R}_{i}(t)\mathbf{g}$, where $\mathbf{g}$ is the
vector consisting of the $2m$ randomness sources of the model. As we show
later, the possibility of leakage and properties of information flow over the
graph can be translated into constraints on $\mathfrak{R}_{i}(t)$.

While the size of $\mathbf{g}$ is fixed, each new iteration adds $\deg(i)$
rows to $\mathfrak{D}_{i}(t)$ and $\mathfrak{R}_{i}(t)$. The decomposition
$\mathfrak{D}_{i}(t)=\mathfrak{R}_{i}(t)\mathbf{g}$ reveals that, after
sufficiently many iterations, all new rows are linear combinations of previous
ones. This leads to the fact that finitely many iterations
$t_{1},\ldots,t_{k}$ have new information. Moreover, we constructively find
$t_{1},\ldots,t_{k}$ by running a basis-pursuit procedure on the rows of
$\mathfrak{R}_{i}(t)$. As a next step, we write each element
$\mathfrak{R}_{i}(t)$ as a function of the elements of $W^{t}$. Having this,
we then use Cayley-Hamilton theorem (see [26]) on matrix powers to show that
$t_{k}\leq n-1$. The aforementioned decomposition also paves the way to
translate the waiting time for node $i$ to receive the first message
containing non-redundant information about $u_{j}$ in terms of the distance
$d_{G}(i,m_{j})$, which leads to $\operatorname{ecc}_{G}(i)-2\leq t_{k}$.

Considering the data collection $\mathfrak{D}_{i}(t)$ on only non-redundant
data points corresponding to $t_{1},\ldots,t_{r}$ for $r\leq k$ gives
$\mathfrak{D}_{i}^{r}$ and accordingly $\mathfrak{R}_{i}^{r}$. The next tool
to obtain the results of Theorem 5.1 is the fact that we translated the
ability of deterministic recovery of $u_{j}$ by node $i$ into the rank-
deficiency of $\mathfrak{R}_{i}^{r}$ when its $j$-th column is removed. Having
this, the core technique in obtaining the main results of this paper is
transforming the aforementioned rank-deficiency condition into the existence
of a specific substructure in the graph called a _generalized leaf_. A
generalized leaf with head $j$ and tail $i$ consists of $i$ being connected to
all degree $2$ neighbors of $j$ (and possibly $j$ itself) which is illustrated
in Figure 1. While it is straightforward to see why in a generalized leaf with
head $j$ and tail $i$, node $i$ can fully recover $u_{j}$, it is far more
challenging to prove that this is indeed the only possible scenario for a full
recovery of some private value. We prove this fact based on a refined analysis
(see Section B.7) that shows, assuming there are no generalized leaves, the
$j$-th column of $\mathfrak{R}_{i}^{r}$ can be written in terms of other
columns and thus removing the $j$-th column does not decrease the rank of
$\mathfrak{R}_{i}^{r}$.

Figure 1: All possible forms of a generalized leaf with head $j$ and tail $i$:
(i) When node $i$ is the only neighbor of node $j$; (ii) When node $j$ is not
adjacent to node $i$ and only has neighbors of degree two and node $i$ is
adjacent to all of them; (iii) The situation of case (ii) while the edge
$\\{i,j\\}$ is also added.

By distinguishing the only case for a full (deterministic) recovery, the next
step is to analyse and reduce the partial (stochastic) recovery of private
values. Assuming that there are no generalized leaves in the graph, under
having Gaussian distribution for all randomness sources in the model, we then
show that joint distribution of the elements of $\mathfrak{D}_{i}^{r}$ is a
non-degenerate Gaussian distribution that has an invertible covariance matrix
and compute the mutual information between this joint distribution and
$u_{j}$. This leads to a closed-form expression for $\pi_{i}^{(j)}(t)$ and
shows how it can be decreased by the model’s tunable parameters.

##  6 Privacy Analysis

In this section, we first introduce a representation of $\mathfrak{D}_{i}(t)$
in the form of a matrix-vector decomposition (Section 6.1), and then use it to
formally state our results on privacy (Section 6.2).

###  6.1 Matrix-Vector Decomposition for $\mathfrak{D}_{i}(t)$

To obtain Theorem 5.1, we start by finding a representation of the elements of
$\mathfrak{D}_{i}(t)$ in terms of the randomness sources of our model. To this
aim, let $\Gamma\in\mathbb{R}^{n\times n}$ be the matrix whose $ij$-th element
is $\Gamma_{ij}$ defined in Algorithm 1. Based on the preparation phase, we
have $\mathbf{v}{(0)}=\Gamma^{\top}\mathds{1}_{n}$ which results in

$\mathbf{v}{(t)}=W^{t}\mathbf{v}{(0)}=W^{t}\Gamma^{\top}\mathds{1}_{n}\quad\Rightarrow\quad
v_{i}{(t)}=\left[\mathbf{v}(t)\right]_{i}=\left[W^{t}\Gamma^{\top}\mathds{1}_{n}\right]_{i}=\left[W^{t}\right]_{i*}\Gamma^{\top}\mathds{1}_{n}.$
(11)

Consider all the (independent) sources of randomness in our model which are
$\left\\{u_{i}\right\\}_{i\in[n]}$ and $\left\\{\Gamma_{ij}\right\\}_{(i,j)\in
S}$. Equation (11) implies that $v_{i}(t)$ can be written as a linear
combination of these quantities. The following expression suggests a notation
for this linear combination:

$v_{i}{(t)}=\sum_{j\in[n]}\alpha_{j}^{i}(t)\,u_{j}+\sum_{(k,\ell)\in
S}\beta_{k\ell}^{i}(t)\,\Gamma_{k\ell}.$ (12)

(11) implies that the coefficients in (12) can be obtained in terms of the
elements of $\left[W^{t}\right]_{i*}$ as

$\alpha_{j}^{i}(t)=\left[W^{t}\right]_{i\,m_{j}},\quad\beta_{k\ell}^{i}(t)=\left[W^{t}\right]_{i\,\ell}-\left[W^{t}\right]_{i\,m_{k}}.$
(13)

To express (12) in a vector-multiplication form, we define $\mathbf{g}$ to be
a $2m$-dimensional (column) vector that is the concatenation of all sources of
randomness and $\mathbf{p}_{i}(t)$ to be the concatenation of the coefficients
as follows: (Note that $\mathbf{g},\mathbf{p}_{i}(t)\in\mathbb{R}^{2m}$.)

$\mathbf{g}=\left\\{u_{j}\right\\}_{j\in[n]}\times\left\\{\Gamma_{k\ell}\right\\}_{(k,\ell)\in
S},\quad\mathbf{p}_{i}(t)=\left\\{\alpha_{j}^{i}(t)\right\\}_{j\in[n]}\times\left\\{\beta_{k\ell}^{i}(t)\right\\}_{(k,\ell)\in
S}.$ (14)

Hence, $v_{i}{(t)}$ can be written as

$v_{i}{(t)}=\mathbf{p}_{i}^{\top}(t)\,\mathbf{g}.$ (15)

Similar to $v_{i}(t)$ in (15), other elements of $\mathfrak{D}_{i}(t)$ are
also linear combinations of the elements of $\mathbf{g}$ and can be written in
vector-multiplication forms in terms of $\mathbf{g}$. To this aim, we can
consider matrices $\Delta_{i}$ and $\Lambda_{i}$ (where both are of size
$\deg_{G}(i)\times 2m$) such that

$\displaystyle\left\\{u_{i}\right\\}\times\left\\{\Gamma_{i\ell}\right\\}_{\ell\in
N_{i}\setminus\left\\{m_{i}\right\\}}=\Delta_{i}\,\mathbf{g},\quad\quad\left\\{\Gamma_{\ell
i}\right\\}_{\ell\in N_{i}}=\Lambda_{i}\,\mathbf{g}.$ (16)

Putting together the representation of the elements of $\mathfrak{D}_{i}(t)$
in terms of $\mathbf{g}$ in (15), and (16), we obtain the matrix
$\mathfrak{R}_{i}(t)$ by vertically concatenating the matrices $\Delta_{i}$,
$\Lambda_{i}$, and appending vectors $\mathbf{p}_{\ell}(t)$ to the end. More
formally, to be compatible with our notation for concatenation of vectors, we
write

$\mathfrak{R}_{i}(t)=\left\\{\left[\Delta_{i}\right]_{s*}\right\\}_{s}\times\left\\{\left[\Lambda_{i}\right]_{s\ast}\right\\}_{s}\times\left\\{\mathbf{p}_{\ell}^{\top}(\tau)\right\\}_{\ell\in
N_{i},0\leq\tau\leq
t},\quad\mathfrak{D}_{i}(t)=\mathfrak{R}_{i}(t)\mathbf{g}.$ (17)

Recall that $[\cdot]_{s\ast}$ denotes the $s$-th row. Since we set the
notation only for the concatenation of vectors, to concatenate matrices
$\Delta_{i}$ and $\Lambda_{i}$, we first split them into their rows and then
concatenate the rows.

###  6.2 Formal Statement of Privacy Results

In this section, we formally state the privacy results using the linear-
algebraic representations obtained in Section 6.1. As the first step, we seek
to spot the iterations at which node $i$ receives a message that contains new
information. To do so, we define $\mathbf{a}_{s}$ as the $s$-th row of
$\mathfrak{R}_{i}(t)$ for some $t\geq s$. We then run a basis-pursuit
procedure over $\left\\{\mathbf{a}_{s}\right\\}_{s=0}^{\infty}$, as described
in Section 2. Suppose
$\mathcal{B}(\left\\{\mathbf{a}_{s}\right\\}_{s=0}^{\infty})$ is the basis
obtained by the basis-pursuit scheme. It is straightforward to confirm that
the elements $[\Delta_{i}]_{s*}$ and $[\Lambda_{i}]_{s*}$, for all $s$, are
all linearly independent and lie in this basis. Denote the rest of the
elements of the basis by
$\mathbf{p}_{j_{1}}(t_{1}),\ldots,\mathbf{p}_{j_{k}}(t_{k})$, where
$j_{1},\ldots,j_{k}\in N_{i}$ and $0\leq t_{1}\leq\ldots\leq t_{k}$. More
formally,

$\displaystyle\mathcal{B}(\left\\{\mathbf{a}_{s}\right\\}_{s=0}^{\infty})=\left\\{\left[\Delta_{i}\right]_{s*}:s\right\\}\cup\left\\{\left[\Lambda_{i}\right]_{s*}:s\right\\}\cup\left\\{\mathbf{p}_{j_{1}}^{\top}(t_{1}),\ldots,\mathbf{p}_{j_{k}}^{\top}(t_{k})\right\\}.$
(18)

We want to show that the elements of
$\mathcal{B}(\left\\{\mathbf{a}_{s}\right\\}_{s=0}^{\infty})$ are all the data
points at node $i$ that matter and the rest of data points are indeed
redundant. To this aim, we first need the following definition.

######  Definition 6.1.

Define $((j_{1},t_{1}),\ldots,(j_{k},t_{k}))$ in (18) to be the informative
sequence of node $i$. Moreover, for a given integer $0\leq t\leq\infty$,
define $q(t)$ to be the largest $r\in\\{1,\ldots,k\\}$ such that $t_{r}\leq
t$.

Next, let $\mathfrak{D}^{r}_{i}$ be the accumulated data that considers the
data points corresponding to the informative sequence at node $i$, i.e., the
messages coming from neighbors $j_{1},\ldots,j_{r}$ at times
$t_{1},\ldots,t_{r}$ for some $r\in\\{1,\ldots,k\\}$. More formally,

$\displaystyle\mathfrak{D}^{r}_{i}=\left\\{u_{i}\right\\}\times\left\\{\Gamma_{i\ell}\right\\}_{\ell\in
N_{i}\setminus\left\\{m_{i}\right\\}}\times\left\\{\Gamma_{\ell
i}\right\\}_{\ell\in
N_{i}}\times\left(v_{j_{1}}(t_{1}),\ldots,v_{j_{r}}(t_{r})\right).$ (19)

As a next step, we seek to formally show that the information content of
$\mathfrak{D}_{i}(t)$ equals that of $\mathfrak{D}^{q(t)}_{i}$, with $q(t)$
defined in Definition 6.1. This claim is proved in the following statement.

######  Theorem 6.2.

Consider Algorithm 1 with $n\geq 2$ under Assumption 4.1. Moreover, consider
$q(t)$ from Definition 6.1. Suppose $0\leq t\leq\infty$ is given and let
$r=q(t)$. Having $\mathfrak{D}_{i}^{r}$ defined in (19), for any $j\neq i$, we
have
$\mathcal{I}(\mathfrak{D}_{i}(t)\,;\,u_{j})=\mathcal{I}(\mathfrak{D}_{i}^{r}\,;\,u_{j}).$

Theorem 6.2 implies that
$\mathcal{I}\left(\mathfrak{D}_{i}(\infty)\,;\,u_{j}\right)=\mathcal{I}\left(\mathfrak{D}_{i}^{k}\,;\,u_{j}\right)$,
suggesting that all but finitely many messages are redundant. The following
proposition upperbounds the largest informative time instance $t_{k}$.

######  Proposition 6.3.

Consider Algorithm 1 under Assumption 4.1 and let
$((j_{1},t_{1}),\ldots,(j_{k},t_{k}))$ be the informative sequence at node
$i$. If $\mu_{W}$ is the minimal polynomial of matrix $W$, then

$t_{k}\leq\deg(\mu_{W})-1\leq n-1.$ (20)

Proposition 6.3 states that no more information about private values will be
exchanged after $n$ rounds of consensus and from then all the messages
throughout the network are redundant. Hence, up to $t=n$, it can be determined
whether or not an adversary is able to recover a private value. It is also
interesting to know how many consensus rounds a (curious) node $i$ must wait
to hear about $u_{j}$ for the first time. The following proposition is
dedicated to this result.

######  Proposition 6.4.

Consider Algorithm 1 under Assumption 4.1 and let
$((j_{1},t_{1}),\ldots,(j_{k},t_{k}))$ be the informative sequence at node $i$
from Definition 6.1. Further, suppose the underlying graph is connected and
for the consensus matrix, $W$, we have $W\geq 0$, and $W\sim A_{G}$. Let
$t=\tau_{j}^{(i)}$ be the minimum $t$ such that $\alpha_{j}^{i}(t)$ defined in
(13) is not zero. Then $\tau_{j}^{(i)}=d_{G}(i,m_{j})$ and
$r(G)-2\leq\operatorname{ecc}_{G}(i)-2\leq t_{k}$.

Analogous to (16), we can define the data collection on non-redundant data
based on the concept of the informative sequence at one node and its
representation in terms of $\mathbf{g}$ in a matrix-vector multiplication
format. To this aim, first consider the informative sequence
$((j_{1},t_{1}),\ldots,(j_{k},t_{k}))$ at node $i$ and for
$r\in\\{1,\ldots,k\\}$, define

$\mathfrak{R}_{i}^{r}=\left\\{\left[\Delta_{i}\right]_{s*}\right\\}_{s}\times\left\\{\left[\Lambda_{i}\right]_{s\ast}\right\\}_{s}\times\left\\{\mathbf{p}_{j_{\ell}}^{\top}(t_{\ell})\right\\}_{1\leq\ell\leq
r},\quad\mathfrak{D}_{i}^{r}=\mathfrak{R}_{i}^{r}\mathbf{g},$ (21)

and note that $\mathfrak{R}_{i}^{r}$ is a full row-rank matrix. Equation 21
represents all the informative data points at node $i$ in terms of the model’s
randomness sources, i.e., in terms of the elements of $\mathbf{g}$. In this
representation, each column of $\mathfrak{R}_{i}^{r}$ corresponds to the
coefficients of one randomness source for all data points. As we show later,
the difference between the rank of $\mathfrak{R}_{i}^{r}$ before and after
removing the column corresponding to a private value determines the privacy-
preserving properties of the network. Towards this argument, let
$\mathfrak{R}_{i,-j}^{r}$ be the matrix obtained by removing the column
corresponding to $u_{j}$. We use $-j$ to emphasize that this column is
removed. Two cases are possible in this situation:

$\displaystyle\text{Case
1:}\,\,\operatorname{rank}\left(\mathfrak{R}_{i,-j}^{r}\right)=\operatorname{rank}\left(\mathfrak{R}_{i}^{r}\right),$
(22) $\displaystyle\text{Case
2:}\,\,\operatorname{rank}\left(\mathfrak{R}_{i,-j}^{r}\right)=\operatorname{rank}\left(\mathfrak{R}_{i}^{r}\right)-1.$
(23)

We will show that under Case $2$, node $i$ can deterministically recover
$u_{j}$ while under Case $1$, this is not possible. We start by presenting the
following lemma stating that under Case $2$, the privacy fails.

######  Lemma 6.5.

Consider Algorithm 1 with $n\geq 2$ under Assumption 4.1. Moreover, consider
$r=q(t)$ from Definition 6.1 and suppose (23) holds for some $j\neq i$. Then
node $i$ can fully recover $u_{j}$ using $\mathfrak{D}^{r}_{i}$.

Lemma 6.5 shows that under Case $2$, node $i$ can deterministically recover
$u_{j}$, meaning that $u_{j}$ is a deterministic function of
$\mathfrak{D}_{i}(t)$. Since we assumed all the random variables in our model
are continuous random variables, this leads to $\pi_{i}^{(j)}(t)=\infty$.
Next, in Theorem 6.6, we obtain a closed-form expression for
$\pi_{i}^{(j)}(t)$ under Case $1$, which implies that $\pi_{i}^{(j)}(t)$ is
finite under Case $1$. This implies that $u_{j}$ is not a deterministic
function of $\mathfrak{D}_{i}(t)$ and thus node $i$ cannot fully recover
$u_{j}$ using $\mathfrak{D}_{i}(t)$. Thus, Case $2$ holds if and only if node
$i$ can deterministically recover $u_{j}$. To analyse Case $1$, we need to
define $\mathcal{S}_{-j}$ in the following, which is the covariance matrix of
$\mathbf{g}$ when the element $u_{j}$ is removed:

$\mathcal{S}_{-j}=\operatorname{diag}\left(\left\\{\sigma_{i}^{2}\right\\}_{i\in[n]\setminus\left\\{j\right\\}}\times\left\\{\sigma_{k\ell}^{2}\right\\}_{(k,\ell)\in
S}\right).$ (24)

Note that the parameters in (24) are previously defined in Definition 4.2. The
following theorem computes $\pi_{i}^{(j)}(t)$ under Case $1$, for a Gaussian
model.

######  Theorem 6.6.

Consider Algorithm 1 with $n\geq 2$ under Assumption 4.1. Suppose $0\leq
t\leq\infty$ is given and let $r=q(t)$ as defined in Definition 6.1. Moreover,
suppose Equation 22 holds and assume that all random variables
$u_{s},\,s\in[n]$, and $\Gamma_{k\ell},\,(k,\ell)\in S$, have Gaussian
distributions. Then, for $j\neq i$

$\pi_{i}^{(j)}(t)=\frac{1}{2}\log\left(1+\sigma_{j}^{2}\,\mathbf{a}^{\top}\Sigma^{-1}\mathbf{a}\right),$
(25)

where $\mathbf{a}=\left[\mathfrak{R}_{i}^{r}\right]_{*j}$, and
$\Sigma=\mathfrak{R}_{i,-j}^{r}\mathcal{S}_{-j}\mathfrak{R}_{i,-j}^{r\top}$.

Note that for $(k,\ell)\in S$, the quantity $\sigma_{k\ell}^{2}$, i.e., the
variance of the generated noise term $\Gamma_{k\ell}$ lies in the diagonal of
$\mathcal{S}_{-j}$. As a result, $\pi_{i}^{(j)}(t)$ is a decreasing function
of $\sigma_{k\ell}^{2}$. Since we are free to choose $\sigma_{k\ell}^{2}$, we
set them large enough to decrease $\pi_{i}^{(j)}(t)$ close to its minimum.
However, the cost of increasing $\sigma_{k\ell}^{2}$ appears in the
convergence time. This result is formalised in Theorem 7.2 and the effect of
increasing $\sigma_{k\ell}^{2}$ on $\pi_{i}^{(j)}(t)$ is also evaluated in the
simulations (see Appendix A).

As the next step, to avoid Case $2$, we investigate under what conditions Case
$1$ and Case $2$ hold. To this aim, the notion of a generalized leaf is
introduced.

######  Definition 6.7 (Generalized Leaf).

Consider graph $G=(V,E)$ with distinct vertices $i,j\in V$ where
$\left\\{i,j\right\\}$ may or may not be in $E$. Then, $G$ has a generalized
leaf with head $j$ and tail $i$ if for every $s\in
N_{j}\setminus\left\\{i\right\\}$, we have $\deg_{G}(s)=2$ and $s\in N_{i}$.

A generalized leaf is a generalization of a leaf (i.e., a node with degree
$1$). Figure 1 illustrates all possible forms of a generalized leaf with head
$j$ and tail $i$. For a generalized leaf of head $j$ and tail $i$, node $i$
can recover $u_{j}$ in the first iteration of the consensus. To see this,
suppose $s\in N_{j}$. Node $s$ receives $\Gamma_{is}$ and $\Gamma_{js}$ in the
preparation phase and initializes its consensus by $\Gamma_{is}+\Gamma_{js}$.
Node $i$ knows $\Gamma_{is}$ and has also received $\Gamma_{is}+\Gamma_{js}$
from node $s$ in the first iteration of the consensus, thus it obtains
$\Gamma_{js}$. Since node $i$ is adjacent to all neighbors of $j$, node $i$
recovers $\Gamma_{js}$ for all $s\in N_{j}$. Summing these reveals $u_{j}$ to
node $i$. Next theorem guarantees that this is the only troubling case.

######  Theorem 6.8.

Consider Algorithm 1 over a connected graph $G$. Then (22) holds for every
distinct pair $i,j\in[n]$ and all $r\in\\{1,\ldots,k\\}$ if $G$ does not
contain any generalized leaf.

##  7 Convergence Analysis

Next, we study the convergence properties of Algorithm 1. We first formalize
the notion of convergence time based on the waiting time required to achieve
an $\epsilon$-accurate estimation of the convergence limit. We denote this
quantity by $t_{\epsilon}$ and define it as follows.

######  Definition 7.1.

For $\epsilon>0$ and $\mathbf{v}(t)$ in (11), let $t_{\epsilon}$ be the
minimum time $t$ such that
$\left\|\mathbf{v}(t)-\mathbf{u}^{*}\right\|_{2}\\!\leq\\!\epsilon$.

Note that the convergence rate (5) is conceptually different from the
convergence time defined in Definition 7.1. While the rate represents the
”slope” of a convergence, the convergence time refers to the time when the
iterations arrive the vicinity of the solution. This for example, implies that
a larger distance between the initial values and the final solution leads to a
larger convergence time under the same convergence rate. Having this
definition, the convergence results of this paper is summarized in the
following theorem.

######  Theorem 7.2.

Consider Algorithm 1 (PPAC) under Assumption 4.1. Further, suppose
$W\mathds{1}_{n}=W^{\top}\mathds{1}_{n}=\mathds{1}_{n}$ and
$\rho(W-{1}/{n}\mathds{1}_{n}\mathds{1}_{n}^{\top})<1$. Then, we have:

  1. (i)

In the limit, PPAC converges to the exact solution, i.e.,
$\lim_{t\to\infty}\mathbf{v}(t)=\mathbf{u}^{*}$.

  2. (ii)

The convergence rate in part (i) is the same as the convergence rate of an
ordinary (non-private) consensus, meaning that (5) holds for PPAC too.

  3. (iii)

The expected convergence time for achieving an $\epsilon$-accurate solution is

$\mathbb{E}\left[t_{\epsilon}\right]=\mathcal{O}\left(\log\left(\frac{1+\mu_{\max}^{2}+\sigma_{\max}^{2}}{\epsilon}\right)\right),$
(26)

where $\mu_{\max}$ and $\sigma_{\max}^{2}$ are from Definition 4.2.

Note that the conditions
$W\mathds{1}_{n}=W^{\top}\mathds{1}_{n}=\mathds{1}_{n}$ and
$\rho(W-{1}/{n}\mathds{1}_{n}\mathds{1}_{n}^{\top})<1$, as mentioned in
Section 2 are essential for the fundamental convergence properties of the
classical averaging consensus. Further, we refer to Appendix A for simulation
results on convergence.

######  Remark 7.3.

The trade-off between privacy and the convergence time in our model can be
explained as follows. Earlier in this section, we mentioned that increasing
$\sigma_{k\ell}^{2}$ for $(k,\ell)\in S$ (or similarly $\sigma_{\max}^{2}$)
decreases the privacy leakage $\pi_{i}^{(j)}(t)$ due to Equation 25, while it
increases the convergence time due to Equation 26. Hence, the quantities
$\sigma_{k\ell}^{2}$ for $(k,\ell)\in S$ can be seen as the tuning parameters
that adjust the position in the trade-off between privacy and the convergence
time.

##  8 Conclusion

In this work, we introduced a novel private consensus averaging algorithm and
analyzed its privacy from an information-theoretic perspective. We
specifically used the mutual information function between all the information
available at the adversary node and the initial value of the victim to measure
how private the value of the victim is with respect to the attacker. Our
results show that the convergence rate of our proposed method is similar to
the convergence rate of a classic non-private consensus method, for any level
of privacy. More importantly, any level of accuracy can be achieved via our
proposed method. Our results also show that there exists a trade-off between
the level of information-theoretic privacy and convergence time.

## Acknowledgment

The work of M. Fereydounian and H. Hassani is funded by DCIST, NSF
CPS-1837253, and NSF CIF-1943064 and NSF CAREER award CIF-1943064, and Air
Force Office of Scientific Research Young Investigator Program (AFOSR-YIP)
under award FA9550-20-1-0111. The research of A. Mokhtari is supported in part
by NSF Grants 2019844 and 2112471, ARO Grant W911NF2110226, the Machine
Learning Lab (MLL) at UT Austin, and the Wireless Networking and
Communications Group (WNCG) Industrial Affiliates Program. The work of R.
Pedarsani is funded by NSF Grant 2003035.

## References

  * Altafini [2020] Claudio Altafini.  A System-Theoretic Framework for Privacy Preservation in Continuous-Time Multiagent Dynamics.  _Automatica_ , 122:109253, 2020.
  * Bassily et al. [2014] R. Bassily, A. Smith, and A. Thakurta.  Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds.  In _Proceedings of the 55th Annual Symposium on the Foundations of Computer Science (FOCS ’14)_ , October 18–21 2014.
  * Bekkerman et al. [2011] Ron Bekkerman, Mikhail Bilenko, and John Langford.  _Scaling up Machine Learning: Parallel and Distributed Approaches_.  Cambridge University Press, 2011.
  * Chaudhuri and Vinterbo [2013] K. Chaudhuri and S. A. Vinterbo.  A stability-Based Validation Procedure for Differentially Private Machine Learning.  In _Advances in Neural Information Processing Systems 26_ , December 2013.
  * Chen et al. [2017] Jiming Chen, Kang Hu, Qi Wang, Yuyi Sun, Zhiguo Shi, and Shibo He.  Narrowband Internet of Things: Implementations and Applications.  _IEEE Internet of Things Journal_ , 4(6):2309–2314, 2017.
  * Cortés et al. [2016] Jorge Cortés, Geir E Dullerud, Shuo Han, Jerome Le Ny, Sayan Mitra, and George J Pappas.  Differential Privacy in Control and Network Systems.  In _2016 IEEE 55th Conference on Decision and Control (CDC)_ , pages 4252–4272. IEEE, 2016.
  * DeGroot [1974] Morris H DeGroot.  Reaching a Consensus.  _Journal of the American Statistical Association_ , 69(345):118–121, 1974.
  * Dwork et al. [2014] Cynthia Dwork, Aaron Roth, et al.  The Algorithmic Foundations of Differential Privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Feldman and Xiao [2014] Vitaly Feldman and David Xiao.  Sample Complexity Bounds on Differentially Private Learning via Communication Complexity.  In _Conference on Learning Theory_ , pages 1000–1019. PMLR, 2014\.
  * Gupta et al. [2018] Nirupam Gupta, Jonathan Katz, and Nikhil Chopra.  Information-Theoretic Privacy in Distributed Average Consensus.  _arXiv preprint arXiv:1809.01794_ , 2018.
  * Hadjicostis [2018] Christoforos N Hadjicostis.  Privary Preserving Distributed Average Consensus via Homomorphic Encryption.  In _2018 IEEE Conference on Decision and Control (CDC)_ , pages 1258–1263. IEEE, 2018.
  * He et al. [2015] Jianping He, Lingjie Duan, Fen Hou, Peng Cheng, and Jiming Chen.  Multiperiod Scheduling for Wireless Sensor Networks: A Distributed Consensus Approach.  _IEEE Transactions on Signal Processing_ , 63(7):1651–1663, 2015.
  * He et al. [2018] Jianping He, Lin Cai, Chengcheng Zhao, Peng Cheng, and Xinping Guan.  Privacy-Preserving Average Consensus: Privacy Analysis and Algorithm Design.  _IEEE Transactions on Signal and Information Processing over Networks_ , 5(1):127–138, 2018.
  * Heikkilä et al. [2017] Mikko Heikkilä, Eemil Lagerspetz, Samuel Kaski, Kana Shimizu, Sasu Tarkoma, and Antti Honkela.  Differentially Private Bayesian Learning on Distributed Data.  _arXiv preprint arXiv:1703.01106_ , 2017.
  * Huang et al. [2012] Zhenqi Huang, Sayan Mitra, and Geir Dullerud.  Differentially Private Iterative Synchronous Consensus.  In _Proceedings of the 2012 ACM workshop on Privacy in the electronic society_ , pages 81–90, 2012.
  * Jadbabaie et al. [2003] Ali Jadbabaie, Jie Lin, and A Stephen Morse.  Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules.  _IEEE Transactions on automatic control_ , 48(6):988–1001, 2003.
  * Kamath et al. [2019] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman.  Privately Learning High-Dimensional Distributions.  In _Conference on Learning Theory_ , pages 1853–1902. PMLR, 2019\.
  * Kia et al. [2015] Solmaz S Kia, Jorge Cortés, and Sonia Martinez.  Dynamic Average Consensus Under Limited Control Authority and Privacy Requirements.  _International Journal of Robust and Nonlinear Control_ , 25(13):1941–1966, 2015.
  * Le Ny and Pappas [2013] Jerome Le Ny and George J Pappas.  Differentially Private Filtering.  _IEEE Transactions on Automatic Control_ , 59(2):341–354, 2013.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-Efficient Learning of Deep Networks From Decentralized Data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Mo and Murray [2016] Yilin Mo and Richard M Murray.  Privacy Preserving Average Consensus.  _IEEE Transactions on Automatic Control_ , 62(2):753–765, 2016.
  * Nozari et al. [2017] Erfan Nozari, Pavankumar Tallapragada, and Jorge Cortés.  Differentially Private Average Consensus: Obstructions, Trade-offs, and Optimal Algorithm Design.  _Automatica_ , 81:221–231, 2017.
  * Olfati-Saber and Murray [2004] Reza Olfati-Saber and Richard M Murray.  Consensus Problems in Networks of Agents with Switching Topology and Time-Delays.  _IEEE Transactions on automatic control_ , 49(9):1520–1533, 2004.
  * Olfati-Saber and Shamma [2005] Reza Olfati-Saber and Jeff S Shamma.  Consensus Filters for Sensor Networks and Distributed Sensor Fusion.  In _Proceedings of the 44th IEEE Conference on Decision and Control_ , pages 6698–6703. IEEE, 2005.
  * Pequito et al. [2014] Sérgio Pequito, Soummya Kar, Shreyas Sundaram, and A Pedro Aguiar.  Design of Communication Networks for Distributed Computation with Privacy Guarantees.  In _53rd IEEE Conference on Decision and Control_ , pages 1370–1376. IEEE, 2014.
  * Roman [2013] S. Roman.  _Advanced Linear Algebra_.  Graduate Texts in Mathematics. Springer New York, 2013.
  * Ruan et al. [2019] Minghao Ruan, Huan Gao, and Yongqiang Wang.  Secure and Privacy-Preserving Consensus.  _IEEE Transactions on Automatic Control_ , 64(10):4035–4049, 2019.
  * Wang [2019] Yongqiang Wang.  Privacy-Preserving Average Consensus via State Decomposition.  _IEEE Transactions on Automatic Control_ , 64(11):4711–4716, 2019.
  * Xiao and Boyd [2004] Lin Xiao and Stephen Boyd.  Fast Linear Iterations for Distributed Averaging.  _Systems & Control Letters_, 53(1):65–78, 2004\.
  * Xiao et al. [2005] Lin Xiao, Stephen Boyd, and Sanjay Lall.  A Scheme for Robust Distributed Sensor Fusion Based on Average Consensus.  In _IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks, 2005._ , pages 63–70. IEEE, 2005.
  * Xiong and Li [2021] Yi Xiong and Zhongkui Li.  Privacy-Preserved Average Consensus Algorithms with Edge-Based Additive Perturbations.  _arXiv preprint arXiv:2109.02192_ , 2021.
  * Yin et al. [2019] Tianjiao Yin, Yuezu Lv, and Wenwu Yu.  Accurate Privacy Preserving Average Consensus.  _IEEE Transactions on Circuits and Systems II: Express Briefs_ , 67(4):690–694, 2019.
  * Zhao et al. [2016] Chengcheng Zhao, Jianping He, Peng Cheng, and Jiming Chen.  Consensus-Based Energy Management in Smart Grid with Transmission Losses and Directed Communication.  _IEEE Transactions on smart grid_ , 8(5):2049–2061, 2016.

##  Appendix A Simulations

In this section, we provide simulations as a visualization to theoretical
results of this paper. Consider a private consensus problem with the
underlying graph $G$ consisting of $n=6$ nodes as shown in Figure 3. The
vector of private values is denoted by
$\mathbf{u}=[u_{1},\ldots,u_{6}]^{\top}$, where each component is
independently generated from the normal distribution with mean $0$ and
standard deviation $\sigma_{0}=10$, i.e.,
$u_{i}\sim\mathcal{N}(0,\sigma_{0}^{2})=\mathcal{N}(0,100)$ for all $i\in[6]$.
The specific realization of this example was
$u=[2.30,\,4.40,\,-6.17,\,2.75,\,6.01,\,0.92]^{\top}$ with average
$u^{*}=1.7$. We then ran Algorithm 1 (PPAC) over this model. For each node
$i$, we chose $m_{i}$ uniformly at random in $N_{i}$ and the realization for
this example is $(m_{1},\ldots,m_{6})=(2,4,4,3,4,1)$. All the pure noises are
independently generated from normal distribution with mean $0$ and standard
deviation $\sigma_{N}$, i.e., $\Gamma_{ij}\sim\mathcal{N}(0,\sigma_{N}^{2})$
for all $(i,j)\in S$. In all cases, we use the following consensus matrix:
$W=I_{n}-1/d_{\max}(D_{G}-A_{G})$, where $I_{n}$ is the identity matrix,
$D_{G}=\operatorname{diag}(\deg_{G}(1),\ldots,\deg_{G}(n))$ and
$d_{\max}=\max_{i\in[n]}\deg_{G}(i)$.

First, one might be interested in observing a realization of the pure noises
and the corresponding dynamics (convergence) of nodes’ messages for such a
realization. For this purpose, we set $\sigma_{N}=15$. Note that PPAC
generates new initial values for the consensus different from $\mathbf{u}$ but
with the same average. Under the aforementioned realization, the new initial
values were
$\mathbf{v}(0)=[v_{1}(0),\ldots,v_{6}(0)]^{\top}=[-12.57,\,16.49,\,-20.11,\,20.78,\,-23.08,\,28.70]^{\top}$.
Figure 3 shows the convergence of $v_{i}(t)$ for all nodes in terms of the
iteration number (time) $t$. As it can be seen, all nodes converge to the same
value, which is the true average $u^{*}=1.7$.

Figure 2: The graph $G$

Figure 3: One realization of the convergence of $v_{i}(t)$ in terms of $t$ for
all nodes using $\sigma_{N}=15$

The second plot of interest answers the following question: While the initial
values are kept fixed, how does the total convergence error over time behave
when we increase the variance of pure noises $\sigma_{k\ell}^{2}$ generated by
Algorithm 1? To this aim, we plot the total convergence error, i.e.,
$\left\|\mathbf{v}(t)-\mathbf{u}^{*}\right\|_{2}$ in terms of time $t$ for
different values of $\sigma_{N}$. We consider a wide range of values, that is
$\sigma_{N}=15,\,150,\,1500,\,15000,\,150000,\,1500000$. Recall that the
generated noises $\Gamma_{ij},\,i\in[n],j\neq m_{i}$ are realizations from the
normal distribution with mean zero and variance $\sigma_{N}^{2}$ and thus the
quantity $\left\|\mathbf{v}(t)-\mathbf{u}^{*}\right\|_{2}$ is affected by
particular realization of the values $\Gamma_{ij}$. To release the plots from
this randomness, we generated $100$ realizations of $\Gamma_{ij}$ and averaged
$\left\|\mathbf{v}(t)-\mathbf{u}^{*}\right\|_{2}$ for each $t$ over these
realizations. Figure 5 shows the resulted plots. As it can be seen, Figure 5
agrees with Theorem 7.2 and shows that increasing the variance of the
generated noises $\Gamma_{ij},\,(i,j)\in S$ affects the convergence time
$t_{\epsilon}$ of achieving a given error $\epsilon$ only by a logarithmic
factor. Note that the $y$-axis is in logarithmic scale.

Figure 4: The total convergence error
$\left\|\mathbf{v}(t)-\mathbf{u}^{*}\right\|_{2}$ in terms of iteration number
$t$ for a wide range of generated noises’ standard deviation $\sigma_{N}$,
i.e., for values $\sigma_{N}=15,\,150,\,1500,\,15000,\,150000,\,1500000$

Figure 5: The leakage of node $1$ at node $4$, i.e., $\pi_{4}^{(1)}(\infty)$
in terms of generated noises’ standard deviation $\sigma_{N}$ for values
$\sigma_{N}=15,\,150,\,1500,\,15000,\,150000,\,1500000$

Figure 6: The graph $G=C_{n}$

Figure 7: The leakage of node $2$ at node $1$ in $G=C_{n}$, i.e.,
$\pi_{1}^{(2)}(\infty)$ in terms of generated noises’ standard deviation
$\sigma_{N}$ for values
$\sigma_{N}=15,\,150,\,1500,\,15000,\,150000,\,1500000$ for values
$n=10,\,20,\,30,\,40$

As the next step, we run experiments to visualize our privacy results. Note
that graph $G$ in Figure 3 does not contain any generalized leaf that are
illustrated in Figure 1. More generally, it is interesting to know that any
graph over $n\geq 5$ nodes that has a cycle of length $n$ cannot contain a
generalized leaf and is therefore a private structure. Hence, due to Theorem
5.1, the privacy of every node is preserved at every other node in this
example. Having this, one might be interested in computing the leakage measure
$\pi_{i}^{(j)}(t)$ defined by Definition 4.3. This quantity can be computed
based on Theorem 6.6. We are interested in considering all the data that one
node can collect over all times through Algorithm 1. Therefore, we consider
$\pi_{i}^{(j)}(\infty)$, i.e., the maximum leakage of node $j$ at node $i$.
Here, we consider node $i=4$ is curious about $j=1$. Recall that in this
experiment, we let all the generated noises have a common variance
$\sigma_{N}^{2}$. Due to (25), we know that increasing $\sigma_{N}^{2}$
decreases
$\pi_{i}^{(j)}(\infty)=\mathcal{I}\left(\mathfrak{D}_{i}(\infty)\,;\,u_{j}\right)$
through a logarithmic function. This is plotted in Figure 5 for
$\pi_{1}^{(4)}(\infty)$. Note that the $x$-axis is in logarithmic scale. Few
important items are worth mentioning about this figure which are discussed in
the following:
First, as it can be observed, there is a ceiling on the achievable amount of
privacy. This is due to the fact that some amount of information will
unavoidably be transmitted by the construction of consensus model. For
instance, the average of private values to which all nodes will converge,
contains some amount of information about each private value. Second, since
the scale is logarithmic, choosing smaller values of $\sigma_{N}$ can provide
almost the same privacy level that extremely large values can but smaller
values of $\sigma_{N}$ provide better convergence time as discussed in Figure
5. Hence, one might choose $\sigma_{N}$ to be smallest value for which the
plot in Figure 5 is almost flat. $\sigma_{N}=1500$ seems a good option.

Following the above discussion, we know that the consensus problem inherently
reveals some amount of information. For instance, the limiting value $u^{*}$
which is achievable by all nodes partially reveal information about each
$u_{i}$. We know that part of the information is leaked due to achieving the
exact average $u^{*}$. This can be computed as
$\mathcal{I}(u^{*};u_{j})=0.5\log(1+1/(n-1))$ in the case where $u_{i}$ s are
Gaussian. This expression also suggests that when $n$ is large, less
information will be naturally be revealed by $u^{*}$. One might ask if PPAC
also provides a smaller leakage for a larger $n$ and thus higher levels of
privacy are achievable by PPAC as $n$ gets larger. It turns out that the
answer is a yes. To numerically evaluate this notion, we consider the
underlying graph to be a cycle of $n$ nodes $G=C_{n}$ (see Figure 7) and we
suppose one node is curious about its neighbor. For the sake of clarity choose
node $1$ as the curious node (attacker) and node $2$ as the victim. Any two
neighbors can be chosen due to the symmetry. Figure 7 shows a similar plot as
in Figure 5 for $G=C_{n}$, evaluating $\pi_{1}^{(2)}(\infty)$ in terms of
$\sigma_{N}$ when the total number of nodes $n$ is increasing, i.e.,
$n=10,\,20,\,30,\,40$. As it can be seen in Figure 7, larger networks provide
lower levels of privacy leakage.

##  Appendix B Proofs

###  B.1 Further Notations

  * •

For a matrix $A$, $|A|=|\det(A)|$ and for a set $A$, $|A|$ is the number of
elements of $A$.

  * •

For a matrix $A$, $A\succ 0$ means that $A$ is a positive definitive matrix.

  * •

For (column) vectors $\mathbf{a}_{1},\ldots,\mathbf{a}_{s}$,
$\left(\mathbf{a}_{1},\ldots,\mathbf{a}_{s}\right)$ denotes the matrix with
these columns.

  * •

For $a\in\mathbb{R}$, $\left\lceil a\right\rceil$ denotes the smallest integer
greater than or equal to $a$.

  * •

$X\perp Y$: $X$ and $Y$ are statistically independent.

  * •

For a multidimensional random variable $\mathbf{X}$:
$\Sigma_{\mathbf{X}}=\operatorname{Cov}(\mathbf{X})$ is the covariance matrix
of $\mathbf{X}$.

  * •

For a one-dimensional random variable $X$:
$\sigma_{X}^{2}=\operatorname{Var}(X)$ denotes the variance of $X$.

  * •

The indicator function with condition $C$ is denoted by $\mathbf{1}_{C}$.
Therefore, $\mathbf{1}_{C}=1$ if $C$ holds and $\mathbf{1}_{C}=0$ otherwise.

###  B.2 Theorem 6.2

We first formally prove the fundamental property of a basis-pursuit procedure.
Then we express a lemma stating that redundant data can be ignored when
computing mutual information. Equivalently, if there is a spanning set that
generates all other arguments of a mutual information function, considering
this spanning set is enough and other elements can be ignored. The proof is
based on the fact that the basis resulted from a basis-pursuit procedure is an
example of such spanning sets. We start by formally proving fundamental
properties of a basis-pursuit procedure.

######  Lemma B.1.

Consider $\left\\{\mathbf{a}_{i}\right\\}_{i=0}^{\infty}$ where
$\mathbf{a}_{i}\in\mathbb{R}^{n}$ with $\mathbf{a}_{0}\neq\mathbf{0}$ and let
$B=\mathcal{B}\left(\left\\{\mathbf{a}_{i}\right\\}_{i=0}^{\infty}\right)$ be
obtained from a basis pursuit procedure. Then, $|B|<\infty$ and the elements
of $B$ are linearly independent. Let
$B=\left\\{\mathbf{a}_{t_{1}},\ldots,\mathbf{a}_{t_{k}}\right\\}$ where
$0=t_{1}<t_{2}<\ldots<t_{k}$. Then for every $i\geq 0$, letting $r$ be the
largest number such that $t_{r}\leq i$, we have

$\mathbf{a}_{i}\in\operatorname{span}\left(\left\\{\mathbf{a}_{t_{1}},\ldots,\mathbf{a}_{t_{r}}\right\\}\right).$
(27)

###### Proof.

By construction of $\mathcal{B}(\cdot)$, any finite subset of $B$ is linearly
independent. Thus, $|B|\leq\dim\left(\mathbb{R}^{n}\right)=n$. Moreover, if
$t_{r}=i$, (27) trivially holds. Therefore, suppose $t_{r}<i$ and
$\mathbf{a}_{i}\notin\operatorname{span}\left(\left\\{\mathbf{a}_{t_{1}},\ldots,\mathbf{a}_{t_{r}}\right\\}\right)$,
then by construction of $\mathcal{B}(\cdot)$, we have $\mathbf{a}_{i}\in B$
and thus $i=t_{\ell}$ for some $\ell>r$ which contradicts the definition of
$r$. ∎

As the next step, we prove that a spanning subset of a dataset contains all
the information of that dataset.

######  Lemma B.2.

Suppose $\mathbf{Y}$ is an $n$-dimensional and $X$ is an arbitrary random
variable. Further, suppose
$\mathbf{a}_{1},\ldots,\mathbf{a}_{r}\in\mathbb{R}^{n}$ are constant and for
$s\leq r$, let
$\mathbf{a}_{1},\ldots,\mathbf{a}_{r}\in\operatorname{span}\left(\mathbf{a}_{1},\ldots,\mathbf{a}_{s}\right)$.
Then

$\mathcal{I}\left(\mathbf{a}_{1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{r}^{\top}\mathbf{Y}\,;\,\,X\right)=\mathcal{I}\left(\mathbf{a}_{1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{s}^{\top}\mathbf{Y}\,;\,\,X\right).$
(28)

###### Proof.

If $s=r$ the statement is obvious. Suppose $s<r$ and note that since
$\mathbf{a}_{1},\ldots,\mathbf{a}_{r}\in\operatorname{span}\left(\mathbf{a}_{1},\ldots,\mathbf{a}_{s}\right)$,
for every $i\in\left\\{s+1,\ldots,r\right\\}$ there exits
$\lambda_{i1},\ldots,\lambda_{is}\in\mathbb{R}$ such that
$\mathbf{a}_{i}=\lambda_{i1}\mathbf{a}_{1}+\ldots+\lambda_{is}\mathbf{a}_{s}$.
Let $\Lambda$ denote the matrix with elements $\lambda_{ij}$ and write

$\left(\mathbf{a}_{s+1},\ldots,\mathbf{a}_{r}\right)=\left(\mathbf{a}_{1},\ldots,\mathbf{a}_{s}\right)\Lambda^{\top}.$
(29)

Hence,

$\displaystyle\left(\mathbf{a}_{s+1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{r}^{\top}\mathbf{Y}\right)$
$\displaystyle=\mathbf{Y}^{\top}\left(\mathbf{a}_{s+1},\ldots,\mathbf{a}_{r}\right)$
(30)
$\displaystyle=\mathbf{Y}^{\top}\left(\mathbf{a}_{1},\ldots,\mathbf{a}_{s}\right)\Lambda^{\top}$
(31)
$\displaystyle=\left(\mathbf{Y}^{\top}\mathbf{a}_{1},\ldots,\mathbf{Y}^{\top}\mathbf{a}_{s}\right)\Lambda^{\top}$
(32)
$\displaystyle=f\left(\mathbf{a}_{1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{s}^{\top}\mathbf{Y}\right).$
(33)

Let $\mathbf{Z}=\left(\mathbf{a}_{1},\ldots,\mathbf{a}_{s}\right)$. From (33),
$\left(\mathbf{a}_{s+1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{r}^{\top}\mathbf{Y}\right)=f(\mathbf{Z})$,
where $f(\cdot)$ is a deterministic function. This results in

$\displaystyle\mathcal{I}\left(\mathbf{a}_{1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{r}^{\top}\mathbf{Y}\,;\,\,X\right)$
$\displaystyle=\mathcal{I}\left(\mathbf{a}_{1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{s}^{\top}\mathbf{Y},\mathbf{a}_{s+1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{r}^{\top}\mathbf{Y}\,;\,\,X\right)$
(34) $\displaystyle=\mathcal{I}\left(\mathbf{Z},f(\mathbf{Z})\,;\,\,X\right)$
(35) $\displaystyle=\mathcal{I}\left(\mathbf{Z}\,;\,\,X\right)$ (36)
$\displaystyle=\mathcal{I}\left(\mathbf{a}_{1}^{\top}\mathbf{Y},\ldots,\mathbf{a}_{s}^{\top}\mathbf{Y}\,;\,\,X\right).$
(37)

∎

###### Proof of Theorem 6.2.

Consider $\mathfrak{R}_{i}(t)$ from (16). Then $\mathbf{a}_{s}$ is defined to
be the $s$-th row of $\mathfrak{R}_{i}(\infty)$ or more rigorously, the $s$-th
row of $\mathfrak{R}_{i}(t)$ for some $t\geq s$. Moreover, consider the
related basis from (18). When finding
$\mathcal{B}(\\{\mathbf{a}_{s}\\}_{s=0}^{\infty})$, the basis-pursuit
procedure adds to the basis all the rows of matrices $\Lambda_{i}$ and
$\Delta_{i}$. This holds because one can confirm that in the concatenation of
these two matrices, i.e.,

$\left[\begin{array}[]{c}\Delta_{i}\\\ \Lambda_{i}\end{array}\right],$ (38)

each column has at most $1$ non-zero value (the non-zero values are either $1$
or $-1$) and each row has at least one non-zero value. The basis pursuit then
continues by evaluating $\mathbf{p}_{\ell}(t)$ for $\ell\in N_{i}$ and $t\geq
0$ and chooses $\mathbf{p}_{j_{1}}(t_{1}),\ldots,\mathbf{p}_{j_{k}}(t_{k})$,
where $((j_{1},t_{1}),\ldots,(j_{k},t_{k}))$ is the informative sequence of
node $i$ (see Definition 6.1). Define

$A_{r}=\left\\{\left[\Delta_{i}\right]_{s*}:1\leq
s\leq\deg_{G}(i)\right\\}\cup\left\\{\left[\Lambda_{i}\right]_{s*}:1\leq
s\leq\deg_{G}(i)\right\\}\cup\left\\{\mathbf{p}_{j_{1}}^{\top}(t_{1}),\ldots,\mathbf{p}_{j_{r}}^{\top}(t_{r})\right\\}.$
(39)

Using the notation $\mathbf{a}_{s}$, $\mathfrak{D}_{i}(t)$ and
$\mathfrak{D}_{i}^{r}$ (for every $r\leq k$), can be written as

$\mathfrak{D}_{i}(t)=\left\\{\mathbf{a}_{s}^{\top}\mathbf{g}\right\\}_{s\in\\{0,\ldots,t+2\deg_{G}(i)\\}},\quad\mathfrak{D}_{i}^{r}=\left\\{\mathbf{a}_{s}^{\top}\mathbf{g}\right\\}_{\mathbf{a}_{s}\in
A_{r}}.$ (40)

Due to Lemma B.2, for $0\leq s\leq t+2\deg_{G}(i)$ and $r=q(t)$,

$\mathbf{a}_{s}\in\operatorname{span}\left(A_{r}\right).$ (41)

Having (40) and (41), the result follows by applying Lemma B.2 in which
$\mathbf{Y}=\mathbf{g}$ and $X=u_{j}$. ∎

###  B.3 Proposition 6.3

###### Proof.

Let $\kappa=\deg(\mu_{W})$ and denote the coefficients of the minimal
polynomial $\mu_{W}(\cdot)$ by

$\displaystyle\mu_{W}(X)=X^{\kappa}+a_{\kappa-1}X^{\kappa-1}+\ldots+a_{0}I.$
(42)

Having $\mu_{W}(W)=0$, $W^{\kappa}$ can be written as a linear combination of
$W^{0},\ldots,W^{\kappa-1}$. Using induction, this also holds for any $W^{t}$
when $t\geq\kappa$. Therefore, for every integer $t\geq 0$, there exists
$\tilde{a}_{0},\ldots,\tilde{a}_{\kappa-1}$ such that

$\displaystyle W^{t}=\sum_{s=0}^{\kappa-1}\tilde{a}_{s}W^{s}.$ (43)

Having (13) and (43), we conclude that for any $t\geq 0$ and every
$q,j,k,\ell\in[n]$ with $j\neq q$ and $(k,\ell)\in S$:

$\alpha_{j}^{q}(t)=\sum_{s=0}^{\kappa-1}\tilde{a}_{s}\alpha_{j}^{q}(s),\quad\beta_{k\ell}^{q}(t)=\sum_{s=0}^{\kappa-1}\tilde{a}_{s}\beta_{k\ell}^{q}(s).$
(44)

Having the definition of $\mathbf{p}_{q}(t)$ in (14), for every $q\in[n]$ and
$t\geq 0$, (44) results in

$\displaystyle\mathbf{p}_{q}(t)=\sum_{s=0}^{\kappa-1}\tilde{a}_{s}\mathbf{p}_{q}(s).$
(45)

Note that (45) holds for every $q\in[n]$, particularly when $q\in N_{i}$.
Considering $q\in N_{i}$, (45) leads to the fact that for very $t\geq 0$ and
$\ell\in N_{i}$,

$\mathbf{p}_{\ell}(t)\in\operatorname{span}\left(\left\\{\mathbf{p}_{q}(\tau):\,q\in
N_{i},\,0\leq\tau\leq\kappa-1\right\\}\right).$ (46)

Hence, $t_{k}\leq\kappa-1=\deg(\mu_{W})-1$. Moreover, due to Cayley-Hamilton
theorem, for any $n\times n$ square matrix $W$, we have $\deg(\mu_{W})\leq n$.
∎

###  B.4 Proposition 6.4

###### Proof.

The statement has two parts and the proof will be enumerated accordingly.

  1. (i)

For the adjacency matrix $A_{G}$ of a simple graph $G$,
$\left[A_{G}^{t}\right]_{ij}$ has a combinatorial meaning. It is equal to the
number of walks of length $k$ between the nodes $i$ and $j$. For a consensus
matrix $W\sim A_{G}$, $W$ can be obtained from $A_{G}$ by replacing the $1$s
and (possibly) the diagonal elements of $A$ with some non-negative numbers.
Similar to $\left[A_{G}^{t}\right]_{ij}$, $\left[W^{t}\right]_{ij}$ can also
be represented combinatorially. To this aim, define $\Omega_{t}(i,j)$ to be
the set of walks of length $t$ between $(i,j)$, that is

$\displaystyle\Omega_{t}(i,j)=\left\\{(s_{0},\ldots,s_{t})\in[n]^{t+1}\mid
s_{0}=i,s_{t}=j,\forall q\in[t]:\,\left\\{s_{q},s_{q-1}\right\\}\in
E\right\\}.$ (47)

Based on the definition of matrix multiplication, we can write

$\displaystyle\left[W^{t}\right]_{ij}=\sum_{(s_{0},\ldots,s_{t})\in\Omega_{t}(i,j)}\prod_{q=0}^{t-1}\left[W\right]_{s_{q}s_{q+1}}.$
(48)

Having (48), if $t<d_{G}(i,m_{j})$, then there is no walk of length $t$
between $i$ and $m_{j}$, i.e., $\Omega_{t}(i,m_{j})=\emptyset$ and
$\alpha_{j}^{i}(t)=\left[W^{t}\right]_{im_{j}}=0$. Now for $t=d_{G}(i,m_{j})$,
there exists at least one positive term (corresponding to each path of length
$d_{G}(i,m_{j})$) in (48) which results in
$\alpha_{j}^{i}(t)=\left[W^{t}\right]_{im_{j}}>0$. Thus, $\tau_{j}^{(i)}$
exists and equals $d_{G}(i,m_{j})$. This completes the first part.

  2. (ii)

Suppose $j_{0}=\arg\max_{s\in[n]}d_{G}(i,s)$ which leads to
$d_{G}(i,j_{0})=\max_{s\in[n]}d_{G}(i,s)=\operatorname{ecc}(i)$. If
$d_{G}(i,j_{0})\leq 2$, the result is trivial. Suppose $d_{G}(i,j_{0})\geq 3$.
It suffices to prove that $t_{k}\geq d_{G}(i,j_{0})-2$. Define
$i_{0}=\arg\min_{s\in N_{i}}d_{G}(s,m_{j_{0}})$. We claim that $t_{k}\geq
d_{G}(i_{0},m_{j_{0}})$. The claim then leads to $t_{k}\geq
d_{G}(i_{0},m_{j_{0}})\geq d_{G}(i,j_{0})-2$. The claim can be proved as
follows: When we run the basis pursuit over the sequence
$\\{\mathbf{a}_{s}\\}_{s}$ to obtain (18), consider the $j_{0}$-th coordinate.
For example, such a coordinate in $\mathbf{p}_{\ell}(t)$ is
$\alpha_{j_{0}}^{\ell}(t)$. Note that $\mathbf{p}_{i_{0}}(t)$ with
$t=d_{G}(i_{0},m_{j_{0}})$ lies in the basis because the $j_{0}$-th element of
$[\Delta_{i}]_{s*}$ and $[\Lambda_{i}]_{s*}$ for all $s$ are totally zero and
the first time in the basis pursuit that the $j_{0}$-th coordinate is not zero
occurs at $t=d_{G}(i_{0},m_{j_{0}})$ in $\mathbf{p}_{i_{0}}(t)$. Due to this,
$\mathbf{p}_{i_{0}}(t)$ does not lie in the span of the latest updated basis
and must be added to it. Note that $t_{k}$ is the time when the final vector
will be added to the basis, hence, $t_{k}\geq d_{G}(i_{0},m_{j_{0}})$.

∎

###  B.5 Lemma 6.5

###### Proof.

Suppose $\mathbf{g}_{-j}$ denotes $\mathbf{g}$ after removing the $j$-th
coordinate (which corresponds to $u_{j}$). Then, we can rewrite (21) in the
following way such that for every valid index $s$:

$\left[\mathfrak{D}^{r}_{i}\right]_{s}=\left[\mathfrak{R}_{i}^{r}\right]_{s*}\,\mathbf{g}=\left[\mathfrak{R}_{i}^{r}\right]_{sj}\,u_{j}+\left[\mathfrak{R}_{i,-j}^{r}\right]_{s*}\mathbf{g}_{-j}.$
(49)

Note that the notation $[\cdot]_{s*}$ denotes a row vector. Under Case 2 given
in (23), there exists a row $s_{0}$ of $\mathfrak{R}_{i,-j}^{r}$ that is a
linear combination of other rows of this matrix, i.e., there exist
coefficients $\beta_{s}\in\mathbb{R}$ such that

$\left[\mathfrak{R}_{i,-j}^{r}\right]_{s_{0}*}=\sum_{s\neq
s_{0}}\beta_{s}\,\left[\mathfrak{R}_{i,-j}^{r}\right]_{s*}.$ (50)

Multiply both sides of (49) by $\beta_{s}$ for all $s\neq s_{0}$, then sum
over all these values and subtract the corresponding equation for $s=s_{0}$
from it. This leads to:

$\displaystyle\left(\sum_{s\neq
s_{0}}\beta_{s}\left[\mathfrak{D}^{r}_{i}\right]_{s}\right)-\left[\mathfrak{D}^{r}_{i}\right]_{s_{0}}$
$\displaystyle=\underbrace{\left(\sum_{s\neq
s_{0}}\beta_{s}\left[\mathfrak{R}_{i}^{r}\right]_{sj}-\left[\mathfrak{R}_{i}^{r}\right]_{s_{0}j}\right)}_{\neq
0}\,u_{j}+\underbrace{\left(\sum_{s\neq
s_{0}}\beta_{s}\left[\mathfrak{R}_{i,-j}^{r}\right]_{sj}-\left[\mathfrak{R}_{i,-j}^{r}\right]_{s_{0}j}\right)}_{=0\text{
from \eqref{a28}}}\mathbf{g}_{-j}$ (51)

Note that the first term is definitely not zero because otherwise Case $1$
(22) holds rather than Case $2$ (23). From (51), $u_{j}$ can be obtained by
the observed data points of node $i$ up to $t=t_{r}$ as the following:

$\displaystyle u_{j}=\frac{\left(\sum_{s\neq
s_{0}}\beta_{s}\left[\mathfrak{R}_{i}^{r}\right]_{sj}\right)-\left[\mathfrak{R}_{i}^{r}\right]_{s_{0}j}}{\left(\sum_{s\neq
s_{0}}\beta_{s}\left[\mathfrak{D}^{r}_{i}\right]_{s}\right)-\left[\mathfrak{D}^{r}_{i}\right]_{s_{0}}}.$
(52)

Moreover, note that in (52), $\mathfrak{R}_{i}^{r}$ only depends to the
underlying graph $G$ and matrix consensus $W$ both of which are known to all
nodes. Hence, $u_{j}$ leaks before time exceeds $t$. ∎

###  B.6 Theorem 6.6

For the sake of clarity and ease of computation, we need to state and prove
two intermediate lemmas before proving Theorem 6.6. The first lemma is just a
formal computing of a combination of normal random variables.

######  Lemma B.3.

Suppose $\mathbf{X}$ is an arbitrary multi-dimensional non-degenerate random
variable i.e., $\Sigma_{\mathbf{X}}$ is invertible and
$A\in\mathbb{R}^{n\times n}$ is a constant matrix. Then
$\mathbb{E}[\left(\mathbf{X}-\mathbb{E}[\mathbf{X}]\right)^{\top}A\left(\mathbf{X}-\mathbb{E}[\mathbf{X}]\right)]=\operatorname{tr}(A\Sigma_{X})$.

###### Proof.

Letting
$\mathbf{Y}=\Sigma_{\mathbf{X}}^{-\frac{1}{2}}\left(\mathbf{X}-\mathbb{E}[\mathbf{X}]\right)$,
we have $\mathbb{E}[\mathbf{Y}]=\mathbf{0}$ and
$\Sigma_{\mathbf{Y}}=\Sigma_{\mathbf{X}}^{-\frac{1}{2}}\Sigma_{\mathbf{X}}\Sigma_{\mathbf{X}}^{-\frac{1}{2}}=\mathrm{I}_{n}$.
Hence,

$\displaystyle\mathbb{E}[\left(\mathbf{X}-\mathbb{E}[\mathbf{X}]\right)^{\top}A\left(\mathbf{X}-\mathbb{E}[\mathbf{X}]\right)]$
$\displaystyle=\mathbb{E}\left[\mathbf{Y}^{\top}\underbrace{\Sigma_{\mathbf{X}}^{\frac{1}{2}}A\Sigma_{\mathbf{X}}^{\frac{1}{2}}}_{B}\mathbf{Y}\right]$
(53) $\displaystyle=\mathbb{E}\left[\sum_{i,\,j}B_{ij}Y_{i}Y_{j}\right]$ (54)
$\displaystyle=\operatorname{tr}(B)=\operatorname{tr}\left(\Sigma_{\mathbf{X}}^{\frac{1}{2}}A\Sigma_{\mathbf{X}}^{\frac{1}{2}}\right)=\operatorname{tr}\left(A\Sigma_{\mathbf{X}}\right).$
(55)

∎

Lemma B.3 eases the proof of the following lemma that computes the mutual
information with specific form of arguments that will appear later in the
proof of Theorem 6.6.

######  Lemma B.4.

Suppose $(X,Y_{1},\ldots,Y_{k})$ is a multivariate normal where
$X\perp\mathbf{Y}=(Y_{1},\ldots,Y_{k})^{\top}$ and assume
$\Sigma_{\mathbf{Y}}$ is invertible. Then

$\mathcal{I}\left(X+a_{1}Y_{1},\ldots,X+a_{k}Y_{k}\,;\,\,X\right)=\frac{1}{2}\log\left(1+\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Y}}^{-1}\mathbf{a}\right),$
(56)

where $\mathbf{a}=\left[a_{1},\ldots,a_{k}\right]^{\top}$.

###### Proof.

Denote
$\mathcal{I}=\mathcal{I}\left(X+a_{1}Y_{1},\ldots,X+a_{k}Y_{k}\,;\,\,X\right)$
and $\mathbf{Z}=\mathbf{Y}+X\mathbf{a}=\left[Z_{1},\ldots,Z_{k}\right]^{\top}$
and note that $Z_{i}=X+a_{i}Y_{i}$ for $i\in\left\\{1,\ldots,k\right\\}$. By
definition,

$\mathcal{I}=\int
f_{X,\mathbf{Z}}\left(x,z_{1},\ldots,z_{k}\right)\log\frac{f_{X,\mathbf{Z}}\left(x,z_{1},\ldots,z_{k}\right)}{f_{X}(x)f_{\mathbf{Z}}(z_{1},\ldots,z_{k})}\mathrm{d}x\mathrm{d}z_{1}\ldots\mathrm{d}z_{k}.$
(57)

To obtain the joint distribution of $(X,\mathbf{Z})$, the following
transformation is useful:

$\left[\begin{array}[]{l}X\\\
\mathbf{Z}\end{array}\right]=J\left[\begin{array}[]{l}X\\\
\mathbf{Y}\end{array}\right],\quad J=\left[\begin{array}[]{ll}1&\mathbf{0}\\\
\mathbf{a}&\mathrm{I}_{k}\end{array}\right],\quad\operatorname{det}(J)=1,$
(58)

which results in

$f_{X,\mathbf{Z}}(x,\mathbf{z})=f_{X,\mathbf{Y}}(x,\mathbf{z}-\mathbf{a}x)=f_{X}(x)f_{\mathbf{Y}}(\mathbf{z}-\mathbf{a}x).$
(59)

By replacing (59) into (57) and cancelling out the term $f_{X}$, we get

$\mathcal{I}=\int
f_{X}(x)f_{\mathbf{Y}}(\mathbf{z}-\mathbf{a}x)\log\frac{f_{\mathbf{Y}}(\mathbf{z}-\mathbf{a}x)}{f_{\mathbf{Z}}(\mathbf{z})}\mathrm{d}x\mathrm{d}\mathbf{z}.$
(60)

To compute the terms in (60), we need a quick discussion. Letting
$\mathbf{Y}\sim\mathcal{N}\left(\mu_{\mathbf{Y}},\Sigma_{\mathbf{Y}}\right)$
and
$\mathbf{Z}\sim\mathcal{N}\left(\mu_{\mathbf{Z}},\Sigma_{\mathbf{Z}}\right)$,
we know that

$\mu_{\mathbf{Z}}=\mu_{\mathbf{Y}}+\mathbf{a}\mu_{X},$ (61)

and we can relate $\Sigma_{\mathbf{Z}}$ and $\Sigma_{\mathbf{Y}}$ as follows:

$\operatorname{Cov}\left(\left[\begin{array}[]{c}X\\\
\mathbf{Z}\end{array}\right]\right)=J\operatorname{Cov}\left(\left[\begin{array}[]{l}X\\\
\mathbf{Y}\end{array}\right]\right)J^{\top}=J\left[\begin{array}[]{cc}\sigma_{X}^{2}&\mathbf{0}\\\
\mathbf{0}&\Sigma_{\mathbf{Y}}\end{array}\right]J^{\top}=\left[\begin{array}[]{cc}\sigma_{X}^{2}&*\\\
&\Sigma_{\mathbf{Y}}+\sigma_{X}^{2}\,\mathbf{a}\mathbf{a}^{\top}\end{array}\right]$
(62)
$\Longrightarrow\Sigma_{\mathbf{Z}}=\Sigma_{\mathbf{Y}}+\sigma_{X}^{2}\,\mathbf{a}\mathbf{a}^{\top}.$
(63)

Since $\Sigma_{\mathbf{Y}}\succ 0$, from (63) we conclude that
$\Sigma_{\mathbf{Z}}\succ 0$ and thus $\Sigma_{\mathbf{Z}}$ is invertible.
Therefore, $\Sigma_{\mathbf{Y}}^{-1}$ and $\Sigma_{\mathbf{Z}}^{-1}$ exist.
Having this, we can write

$\frac{f_{\mathbf{Y}}(\mathbf{z}-\mathbf{a}x)}{f_{\mathbf{Z}}(\mathbf{z})}=\frac{\left|\Sigma_{\mathbf{Z}}\right|^{\frac{1}{2}}}{\left|\Sigma_{\mathbf{Y}}\right|^{\frac{1}{2}}}\exp\left(-\frac{1}{2}\left(\mathbf{z}-\mathbf{a}x-\mu_{\mathbf{Y}}\right)^{\top}\Sigma_{\mathbf{Y}}^{-1}\left(\mathbf{z}-\mathbf{a}x-\mu_{\mathbf{Y}}\right)+\frac{1}{2}\left(\mathbf{z}-\mu_{\mathbf{Z}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{z}-\mu_{\mathbf{Z}}\right)\right).$
(64)

Replacing (64) into (60) leads to the computation of (60) in three terms as
follows:

$\mathcal{I}=\mathcal{I}_{1}+\mathcal{I}_{2}+\mathcal{I}_{3},$ (65)

where the first term is

$\mathcal{I}_{1}=\int
f_{X}(x)f_{\mathbf{Y}}(\mathbf{z}-\mathbf{a}x)\log\frac{\left|\Sigma_{\mathbf{Z}}\right|^{\frac{1}{2}}}{\left|\Sigma_{\mathbf{Y}}\right|^{\frac{1}{2}}}\,\mathrm{d}x\mathrm{d}\mathbf{z}=\frac{1}{2}\log\frac{\left|\Sigma_{\mathbf{Z}}\right|}{\left|\Sigma_{\mathbf{Y}}\right|}.$
(66)

The second term is

$\displaystyle\mathcal{I}_{2}$ $\displaystyle=-\frac{1}{2}\int
f_{X}(x)f_{\mathbf{Y}}(\mathbf{z}-\mathbf{a}x)\left(\mathbf{z}-\mathbf{a}x-\mu_{\mathbf{Y}}\right)^{\top}\Sigma_{\mathbf{Y}}^{-1}\left(\mathbf{z}-\mathbf{a}x-\mu_{\mathbf{Y}}\right)\,\mathrm{d}\mathbf{z}\,\mathrm{d}x$
(67) $\displaystyle=-\frac{1}{2}\int
f_{X}(x)\mathbb{E}_{\mathbf{Y}}\left[\left(\mathbf{Y}-\mu_{\mathbf{Y}}\right)^{\top}\Sigma_{\mathbf{Y}}^{-1}\left(\mathbf{Y}-\mu_{\mathbf{Y}}\right)\right]\,\mathrm{d}x$
(68) $\displaystyle=-\frac{1}{2}\int
f_{X}(x)\operatorname{tr}\left(\Sigma_{\mathbf{Y}}^{-1}\Sigma_{\mathbf{Y}}\right)\,\mathrm{d}x\quad\quad\text{due
to Lemma~{}\ref{integ}}$ (69)
$\displaystyle=-\frac{\operatorname{tr}\left(\mathrm{I}_{k}\right)}{2}\int
f_{X}(x)\,\mathrm{d}x=-\frac{k}{2}.$ (70)

And the third term can be obtained as follows.

$\displaystyle\mathcal{I}_{3}$ $\displaystyle=\frac{1}{2}\int
f_{X}(x)f_{\mathbf{Y}}(\mathbf{z}-\mathbf{a}x)\left(\mathbf{z}-\mu_{\mathbf{Z}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{z}-\mu_{\mathbf{Z}}\right)\,\mathrm{d}\mathbf{z}\,\mathrm{d}x$
(71) $\displaystyle=\frac{1}{2}\int
f_{X}(x)\mathbb{E}_{\mathbf{Y}}\left[\left(\mathbf{Y}+\mathbf{a}x-\mu_{\mathbf{Z}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{Y}+\mathbf{a}x-\mu_{\mathbf{Z}}\right)\right]\,\mathrm{d}x.$
(72)

For each given $x\in\mathbb{R}$, we can compute the argument of the
integration in (72) as follows.

$\displaystyle\mathbb{E}_{\mathbf{Y}}\left[\left(\mathbf{Y}+\mathbf{a}x-\mu_{\mathbf{Z}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{Y}+\mathbf{a}x-\mu_{\mathbf{Z}}\right)\right]=\,$
$\displaystyle\mathbb{E}_{\mathbf{Y}}\left[\left(\mathbf{Y}-\mu_{\mathbf{Y}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{Y}-\mu_{\mathbf{Y}}\right)\right]+$
(73)
$\displaystyle\mathbb{E}_{\mathbf{Y}}\left[2\left(\mathbf{Y}-\mu_{\mathbf{Y}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{a}x+\mu_{\mathbf{Y}}-\mu_{\mathbf{Z}}\right)\right]+$
(74)
$\displaystyle\left(\mathbf{a}x+\mu_{\mathbf{Y}}-\mu_{\mathbf{Z}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{a}x+\mu_{\mathbf{Y}}-\mu_{\mathbf{Z}}\right).$
(75)

To compute the right-hand side of the latest equation, note that (73) can be
obtained using Lemma B.3 as follows:

$\displaystyle\mathbb{E}_{\mathbf{Y}}\left[\left(\mathbf{Y}-\mu_{\mathbf{Y}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{Y}-\mu_{\mathbf{Y}}\right)\right]$
$\displaystyle=\operatorname{tr}\left(\Sigma_{\mathbf{Z}}^{-1}\Sigma_{\mathbf{Y}}\right)$
(76)
$\displaystyle=\operatorname{tr}\left(\Sigma_{\mathbf{Z}}^{-1}\left(\Sigma_{\mathbf{Z}}-\sigma_{X}^{2}\,\mathbf{a}\mathbf{a}^{\top}\right)\right)\quad\text{due
to \eqref{sigma_rel}}$ (77)
$\displaystyle=\operatorname{tr}\left(\mathrm{I}_{k}\right)-\sigma_{X}^{2}\operatorname{tr}\left(\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}\mathbf{a}^{\top}\right)$
(78)
$\displaystyle=k-\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}.$
(79)

Having (79) together with the fact that (74) is zero and replacing
$\mu_{\mathbf{Y}}-\mu_{\mathbf{Z}}=-\mathbf{a}\mu_{X}$ in (75), we can put
together the three terms and write

$\displaystyle\mathbb{E}_{\mathbf{Y}}\left[\left(\mathbf{Y}+\mathbf{a}x-\mu_{\mathbf{Z}}\right)^{\top}\Sigma_{\mathbf{Z}}^{-1}\left(\mathbf{Y}+\mathbf{a}x-\mu_{\mathbf{Z}}\right)\right]=k-\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}+\left(x-\mu_{X}\right)^{2}\mathbf{a}^{\top}\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}.$
(80)

Replacing (80) in (72) leads to

$\displaystyle\mathcal{I}_{3}$
$\displaystyle=\frac{1}{2}\left(k-\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}\right)+\frac{1}{2}\mathbf{a}^{\top}\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}\int
f_{X}(x)\left(x-\mu_{X}\right)^{2}\mathrm{d}x$ (81)
$\displaystyle=\frac{k}{2}-\frac{1}{2}\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}+\frac{1}{2}\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Z}}^{-1}\mathbf{a}=\frac{k}{2}.$
(82)

Putting the values of $\mathcal{I}_{1}$, $\mathcal{I}_{2}$, and
$\mathcal{I}_{3}$ from (66), (70), and (82) into (65) results in

$\mathcal{I}=\mathcal{I}_{1}+\mathcal{I}_{2}+\mathcal{I}_{3}=\frac{1}{2}\log\frac{\left|\Sigma_{\mathbf{Z}}\right|}{\left|\Sigma_{\mathbf{Y}}\right|}-\frac{k}{2}+\frac{k}{2}=\frac{1}{2}\log\frac{\left|\Sigma_{\mathbf{Z}}\right|}{\left|\Sigma_{\mathbf{Y}}\right|}.$
(83)

To simplify further, note that from (63) and the fact that
$\Sigma_{\mathbf{Y}}$ is invertible, we have

$\left|\Sigma_{\mathbf{Z}}\right|=\left|\Sigma_{\mathbf{Y}}\right|\left(1+\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Y}}^{-1}\mathbf{a}\right).$
(84)

Therefore,

$\mathcal{I}=\frac{1}{2}\log\frac{\left|\Sigma_{\mathbf{Z}}\right|}{\left|\Sigma_{\mathbf{Y}}\right|}=\frac{1}{2}\log\left(1+\sigma_{X}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Y}}^{-1}\mathbf{a}\right).$
(85)

∎

Finally, the proof of Theorem 6.6 can be provided as follows using Lemma B.4.

###### Proof of Theorem 6.6.

Suppose $\mathbf{g}_{-j}$ denotes $\mathbf{g}$ after removing the $j$-th
coordinate (which corresponds to $u_{j}$). Then, we can rewrite (21) in the
following way such that for every valid index $s$:

$\left[\mathfrak{D}^{r}_{i}\right]_{s}=\left[\mathfrak{R}_{i}^{r}\right]_{s*}\,\mathbf{g}=\left[\mathfrak{R}_{i}^{r}\right]_{sj}\,u_{j}+\left[\mathfrak{R}_{i,-j}^{r}\right]_{s*}\mathbf{g}_{-j}.$
(86)

Note that the notation $[\cdot]_{s*}$ denotes a row vector. For ease of
notation, suppose $s_{\max}$ is the number of rows of of
$\mathfrak{D}^{r}_{i}$. We directly apply Lemma B.4 by considering $X=u_{j}$,
$Y_{s}=\left[\mathfrak{R}_{i,-j}^{r}\right]_{s*}\mathbf{g}_{-j}$,
$\mathbf{Y}=[Y_{1},\ldots,Y_{s_{\max}}]^{\top}$, and
$a_{s}=\left[\mathfrak{R}_{i}^{r}\right]_{sj}$ which also gives
$\mathbf{a}=[a_{1},\ldots,a_{s_{\max}}]^{\top}=\left[\mathfrak{R}_{i}^{r}\right]_{*j}$.
With these replacements, the conditions of Lemma B.4 hold because due to
Assumption 4.1, $u_{j}$ is independent of all other randomness sources, i.e.,
$u_{j}\perp\mathbf{g}_{-j}$ which leads to $X\perp\mathbf{Y}$ and also we
assumed in the statement of Theorem 6.2 that all randomnesses are Gaussian,
hence, $(X,\mathbf{Y})$ is multivariate normal. Further, with this assignment
of $\mathbf{Y}$, we need to compute the covariance matrix
$\operatorname{Cov}(\mathbf{Y})$ and show that it is invertible. Note that

$\mathbf{Y}=\mathfrak{R}_{i,-j}^{r}\mathbf{g}_{-j}\quad\Rightarrow\quad\Sigma_{\mathbf{Y}}=\operatorname{Cov}\left(\mathbf{Y}\right)=\mathfrak{R}_{i,-j}^{r}\operatorname{Cov}\left(\mathbf{g}_{-j}\right)\mathfrak{R}_{i,-j}^{r\top}=\mathfrak{R}_{i,-j}^{r}\mathcal{S}_{-j}\mathfrak{R}_{i,-j}^{r\top},$
(87)

where $\mathcal{S}_{-j}$ is defined in (24). Note that $\mathfrak{R}_{i}^{r}$
is a full row-rank matrix and under Case $1$ (i.e., (22)),
$\mathfrak{R}_{i,-j}^{r}$ is also full row-rank. Hence,

$\operatorname{rank}\left(\Sigma_{\mathbf{Y}}\right)=\operatorname{rank}\left(\mathcal{S}_{-j}\right)=2m-1.$
(88)

Since $\Sigma_{\mathbf{Y}}$ is a $(2m-1)\times(2m-1)$ matrix, (88) means
$\Sigma_{\mathbf{Y}}$ is invertible. So far, we showed that all the conditions
of Lemma B.4 hold under the above assignments. Therefore, the result also
holds and we have

$\mathcal{I}\left(\mathfrak{D}_{i}^{r}\,;\,u_{j}\right)=\frac{1}{2}\log\left(1+\sigma_{j}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Y}}^{-1}\mathbf{a}\right),$
(89)

Finally, due to Theorem 6.2, we know that

$\mathcal{I}\left(\mathfrak{D}_{i}(t)\,;\,u_{j}\right)=\mathcal{I}\left(\mathfrak{D}_{i}^{r}\,;\,u_{j}\right).$
(90)

With (89) and (90) together, we conclude that

$\mathcal{I}\left(\mathfrak{D}_{i}(t)\,;\,u_{j}\right)=\frac{1}{2}\log\left(1+\sigma_{j}^{2}\,\mathbf{a}^{\top}\Sigma_{\mathbf{Y}}^{-1}\mathbf{a}\right).$
(91)

∎

###  B.7 Theorem 6.8

###### Proof.

Suppose $G$ does not contain any generalized leaf. We want to show that Case
$1$ (Equation 22) holds. To do so is, the main idea is that we show that under
such a condition, the $j$-th column (the column corresponding to $u_{j}$) in
$\mathfrak{R}_{i}^{r}$, i.e., the column to be removed to obtain
$\mathfrak{R}_{i,-j}^{r}$ is a linear combination of other columns of
$\mathfrak{R}_{i}^{r}$. Therefore, removing it does not change the rank. To
this aim, we need to setup a notation that we only use throughout this proof.
Recall from (21) that $\mathfrak{R}_{i}^{r}$ is a concatenation of three
matrices, $\Delta_{i}$, $\Lambda_{i}$, and $P_{i}^{r}$ as follows:

$P_{i}^{r}=\left[\begin{array}[]{c}\mathbf{p}_{j_{1}}^{\top}(t_{1})\\\
\vdots\\\
\mathbf{p}_{j_{r}}^{\top}(t_{r})\end{array}\right],\quad\mathfrak{R}_{i}^{r}=\left[\begin{array}[]{c}\Delta_{i}\\\
\Lambda_{i}\\\ P_{i}^{r}\end{array}\right],$ (92)

Thus, each column of $\mathfrak{R}_{i}^{r}$ consists of three sub-columns in
each of these matrices. A set of columns of $\mathfrak{R}_{i}^{r}$ are
linearly dependent if and only if the exact same linear combination holds for
the sub-columns in each of $\Delta_{i}$, $\Lambda_{i}$, and $P_{i}^{r}$.

Notation Setup. All the aforementioned matrices, i.e., $\mathfrak{R}_{i}^{r}$,
$\Delta_{i}$, $\Lambda_{i}$, and $P_{i}^{r}$ have $2m$ columns. Each column
corresponds to one randomness source in the model that are $u_{p}$ for
$p\in[n]$ and $\Gamma_{ps}$ for $(p,s)\in S$. We use index $u_{p}$ or
$\Gamma_{ps}$ to refer to those columns. For example,
$\left[\mathfrak{R}_{i}^{r}\right]_{*\Gamma_{ps}}$ denotes the column of
$\mathfrak{R}_{i}^{r}$ that corresponds to $\Gamma_{ps}$. To refer to rows, we
setup a notation for each sub-matrices $\Delta_{i}$, $\Lambda_{i}$, and
$P_{i}^{r}$. The rows of $\Delta_{i}$ correspond to $u_{i}$ and $\Gamma_{ip}$
for $(i,p)\in S$. We also use these as row-indices. For example,
$\left[\Delta_{i}\right]_{\Gamma_{ip}u_{q}}$ equals the coefficient of $u_{q}$
when we write $\Gamma_{ip}$ in terms of $\mathbf{g}$. This coefficient is zero
since $\Gamma_{ip}$ and $u_{q}$ are independent noises. The rows of
$\Lambda_{i}$ correspond to $\Gamma_{\ell i}$ for $\ell\in N_{i}$. Note that
here $(\ell,i)$ may or may not lie in $S$. The quantity $\Gamma_{\ell i}$ is
what neighbor $\ell$ sends to $i$ in the preparation phase. It may be a pure
noise (when $(\ell,i)\in S$) or in the form of $u_{\ell}-\sum_{s\in
N_{\ell}\setminus\left\\{m_{\ell}\right\\}}\Gamma_{\ell s}$. We also use these
$\Gamma_{\ell i}$ for $\ell\in N_{i}$ as row-indices. Finally, for the rows of
$P_{i}^{r}$, rows are characterized by pairs
$(j_{1},t_{1}),\ldots,(j_{k},t_{k})$, e.g., the row of $P_{i}^{r}$
corresponding to $(\ell,t)\in\\{(j_{1},t_{1}),\ldots,(j_{k},t_{k})\\}$ is
$\mathbf{p}_{\ell}^{\top}(t)$ and is denoted by $[P_{i}^{r}]_{(\ell,t)\ast}$.
When we want to refer to the element $u_{b}$ in this row, we write
$[P_{i}^{r}]_{(\ell,t)u_{b}}$. As we will see in the remaining of the proof,
our discussion here holds for each row identically. Hence, we refer to rows by
general pair $(\ell,t)$ and use this pair as a row-index.

Using the notation explained above, we can now state the proof. Recall that
node $i$ is the attacker and node $j$ is the victim and we want to show that
$\left[\mathfrak{R}_{i}^{r}\right]_{*u_{j}}$ can be generated as a linear
combination of other columns of $\mathfrak{R}_{i}^{r}$. Note that the
following arguments hold regardless of $r$ which means it holds for all
$r\in\\{1,\ldots,k\\}$. Therefore, we omit the superscript $r$ for simplicity.
Suppose the connected graph $G$ does not have any generalized leaf. Then $j$
must have a neighbor $s\neq i$. Considering all such neighbors, there exists
nodes $b,s$ such that $s\in N_{j}$, $s\neq i$, $b\in N_{s}$, and
$b\notin\\{i,j\\}$ because otherwise either the graph is not connected or we
have a generalized leaf in the graph. Now, we consider four cases based on
whether $s=m_{j}$ versus $s\neq m_{j}$ and $s=m_{b}$ versus $s\neq m_{b}$. The
proof in each case are provided in the following. Note that in obtaining the
elements of $P_{i}$, we are basically using (13). Again, note that the
superscript $r$ will be omitted for simplicity and we use $(\ell,t)$ subscript
to refer to the rows of $P_{i}$ where the choice of $\ell\in N_{i}$ and $t$
does not matter. Moreover, $\mathbf{0}$ denotes a vector with all zero
elements.

  1. (I)

Case $s=m_{j}$ and $s=m_{b}$:

$\displaystyle\left.\begin{array}[]{l}\left[P_{i}\right]_{(\ell,t)u_{j}}=\left[W^{t}\right]_{\ell
m_{j}}=\left[W^{t}\right]_{\ell s}\\\
\left[P_{i}\right]_{(\ell,t)u_{b}}=\left[W^{t}\right]_{\ell
m_{b}}=\left[W^{t}\right]_{\ell s}\\\
\end{array}\right\\}\Longrightarrow\quad\left[P_{i}\right]_{*u_{j}}=\left[P_{i}\right]_{*u_{b}},$
(95)
$\displaystyle\left[\Lambda_{i}\right]_{*u_{j}}=\left[\Lambda_{i}\right]_{*u_{b}}=\mathbf{0},$
(96)
$\displaystyle\left[\Delta_{i}\right]_{*u_{j}}=\left[\Delta_{i}\right]_{*u_{b}}=\mathbf{0}.$
(97)

Hence,

$\left[\mathfrak{R}_{i}\right]_{*u_{j}}=\left[\mathfrak{R}_{i}\right]_{*u_{b}}.$
(98)

  2. (II)

Case $s=m_{j}$ and $s\neq m_{b}$:

Note that $m_{b}$ might be $i$, $j$, or any other node other than $s$. Since
$s\neq m_{b}$, we have $(b,s)\in S$ meaning that $\Gamma_{bs}$ is a pure
noise. This means the relevant coefficient is computable based on
$\beta_{bs}^{\ell}(t)$ in (13).

$\displaystyle\left.\begin{array}[]{l}\left[P_{i}\right]_{(\ell,t)u_{j}}=\left[W^{t}\right]_{\ell
m_{j}}=\left[W^{t}\right]_{\ell s}\\\
\left[P_{i}\right]_{(\ell,t)u_{b}}=\left[W^{t}\right]_{\ell m_{b}}\\\
\left[P_{i}\right]_{(\ell,t)\Gamma_{bs}}=\left[W^{t}\right]_{\ell
s}-\left[W^{t}\right]_{\ell m_{b}}\\\
\end{array}\right\\}\Longrightarrow\quad\left[P_{i}\right]_{*u_{j}}=\left[P_{i}\right]_{*u_{b}}+\left[P_{i}\right]_{*\Gamma_{bs}},$
(102)

Moreover,

$\displaystyle\left[\Lambda_{i}\right]_{*u_{j}}=\mathbf{0},$ (103)
$\displaystyle\text{if }b\in
N_{i}:\left\\{\begin{array}[]{l}\left[\Lambda_{i}\right]_{bu_{b}}=\mathbf{1}_{m_{b}=i},\\\
\left[\Lambda_{i}\right]_{b\Gamma_{bs}}=-\mathbf{1}_{m_{b}=i},\\\ \text{ and
other elements of }\left[\Lambda_{i}\right]_{*u_{b}}\text{ and
}\left[\Lambda_{i}\right]_{*\Gamma_{bs}}\text{ are zero},\\\
\end{array}\right.$ (107) $\displaystyle\text{if }b\notin
N_{i}:\left[\Lambda_{i}\right]_{*u_{b}}=\left[\Lambda_{i}\right]_{*\Gamma_{bs}}=\mathbf{0}.$
(108)

Hence, we always get

$\left[\Lambda_{i}\right]_{*u_{j}}=\left[\Lambda_{i}\right]_{*u_{b}}+\left[\Lambda_{i}\right]_{*\Gamma_{bs}}.$
(109)

Further,

$\left[\Delta_{i}\right]_{*u_{j}}=\left[\Delta_{i}\right]_{*u_{b}}=\left[\Delta_{i}\right]_{*\Gamma_{bs}}=\mathbf{0}\quad\Longrightarrow\quad\left[\Delta_{i}\right]_{*u_{j}}=\left[\Delta_{i}\right]_{*u_{b}}+\left[\Delta_{i}\right]_{*\Gamma_{bs}}.$
(110)

Putting (102), (109), and (110), we conclude that

$\left[\mathfrak{R}_{i}\right]_{*u_{j}}=\left[\mathfrak{R}_{i}\right]_{*u_{b}}+\left[\mathfrak{R}_{i}\right]_{*\Gamma_{bs}}.$
(111)

  3. (III)

Case $s\neq m_{j}$ and $s=m_{b}$:

Since $s\neq m_{j}$, we have $(j,s)\in S$ meaning that $\Gamma_{js}$ is a pure
noise. This means the relevant coefficient is computable based on
$\beta_{js}^{\ell}(t)$ in (13).

$\displaystyle\left.\begin{array}[]{l}\left[P_{i}\right]_{(\ell,t)u_{j}}=\left[W^{t}\right]_{\ell
m_{j}}\\\ \left[P_{i}\right]_{(\ell,t)u_{b}}=\left[W^{t}\right]_{\ell
m_{b}}=\left[W^{t}\right]_{\ell s}\\\
\left[P_{i}\right]_{(\ell,t)\Gamma_{js}}=\left[W^{t}\right]_{\ell
s}-\left[W^{t}\right]_{\ell m_{j}}\\\
\end{array}\right\\}\Longrightarrow\quad\left[P_{i}\right]_{*u_{j}}=\left[P_{i}\right]_{*u_{b}}-\left[P_{i}\right]_{*\Gamma_{js}}.$
(115)

Now, for $\Lambda_{i}$ we have

$\displaystyle\left[\Lambda_{i}\right]_{*u_{b}}=\mathbf{0},$ (116)
$\displaystyle\text{if }j\in
N_{i}:\left\\{\begin{array}[]{l}\left[\Lambda_{i}\right]_{ju_{j}}=\mathbf{1}_{m_{j}=i},\\\
\left[\Lambda_{i}\right]_{j\Gamma_{js}}=-\mathbf{1}_{m_{j}=i},\\\ \text{ and
other elements of }\left[\Lambda_{i}\right]_{*u_{j}}\text{ and
}\left[\Lambda_{i}\right]_{*\Gamma_{js}}\text{ are zero},\\\
\end{array}\right.$ (120) $\displaystyle\text{if }j\notin
N_{i}:\left[\Lambda_{i}\right]_{*u_{j}}=\left[\Lambda_{i}\right]_{*\Gamma_{js}}=\mathbf{0}.$
(121)

Hence, we always get

$\left[\Lambda_{i}\right]_{*u_{j}}=\left[\Lambda_{i}\right]_{*u_{b}}-\left[\Lambda_{i}\right]_{*\Gamma_{js}}.$
(122)

Further,

$\left[\Delta_{i}\right]_{*u_{j}}=\left[\Delta_{i}\right]_{*u_{b}}=\left[\Delta_{i}\right]_{*\Gamma_{js}}=\mathbf{0}\quad\Longrightarrow\quad\left[\Delta_{i}\right]_{*u_{j}}=\left[\Delta_{i}\right]_{*u_{b}}-\left[\Delta_{i}\right]_{*\Gamma_{js}}.$
(123)

Putting (115), (122), and (123), we conclude that

$\left[\mathfrak{R}_{i}\right]_{*u_{j}}=\left[\mathfrak{R}_{i}\right]_{*u_{b}}-\left[\mathfrak{R}_{i}\right]_{*\Gamma_{js}}.$
(124)

  4. (IV)

Case $s\neq m_{j}$ and $s\neq m_{b}$:

First note that since $s\neq m_{j}$ and $s\neq m_{b}$, we have $(j,s),(b,s)\in
S$ meaning that $\Gamma_{js}$ and $\Gamma_{bs}$ are pure noises. This means
the relevant coefficients are computable based on $\beta_{js}^{\ell}(t)$ and
$\beta_{bs}^{\ell}(t)$ in (13).

$\displaystyle\left.\begin{array}[]{l}\left[P_{i}\right]_{(\ell,t)u_{j}}=\left[W^{t}\right]_{\ell
m_{j}}\\\ \left[P_{i}\right]_{(\ell,t)u_{b}}=\left[W^{t}\right]_{\ell
m_{b}}\\\ \left[P_{i}\right]_{(\ell,t)\Gamma_{js}}=\left[W^{t}\right]_{\ell
s}-\left[W^{t}\right]_{\ell m_{j}}\\\
\left[P_{i}\right]_{(\ell,t)\Gamma_{bs}}=\left[W^{t}\right]_{\ell
s}-\left[W^{t}\right]_{\ell m_{b}}\\\
\end{array}\right\\}\Longrightarrow\quad\left[P_{i}\right]_{*u_{j}}=\left[P_{i}\right]_{*u_{b}}-\left[P_{i}\right]_{*\Gamma_{js}}+\left[P_{i}\right]_{*\Gamma_{bs}}.$
(129)

Now, for $\Lambda_{i}$ we have

$\displaystyle\text{if }j\in
N_{i}:\left\\{\begin{array}[]{l}\left[\Lambda_{i}\right]_{ju_{j}}=\mathbf{1}_{m_{j}=i},\\\
\left[\Lambda_{i}\right]_{j\Gamma_{js}}=-\mathbf{1}_{m_{j}=i},\\\ \text{ and
other elements of }\left[\Lambda_{i}\right]_{*u_{j}}\text{ and
}\left[\Lambda_{i}\right]_{*\Gamma_{js}}\text{ are zero},\\\
\end{array}\right.$ (133) $\displaystyle\text{if }j\notin
N_{i}:\left[\Lambda_{i}\right]_{*u_{j}}=\left[\Lambda_{i}\right]_{*\Gamma_{js}}=\mathbf{0},$
(134) $\displaystyle\text{if }b\in
N_{i}:\left\\{\begin{array}[]{l}\left[\Lambda_{i}\right]_{bu_{b}}=\mathbf{1}_{m_{b}=i},\\\
\left[\Lambda_{i}\right]_{b\Gamma_{bs}}=-\mathbf{1}_{m_{b}=i},\\\ \text{ and
other elements of }\left[\Lambda_{i}\right]_{*u_{b}}\text{ and
}\left[\Lambda_{i}\right]_{*\Gamma_{bs}}\text{ are zero},\\\
\end{array}\right.$ (138) $\displaystyle\text{if }b\notin
N_{i}:\left[\Lambda_{i}\right]_{*u_{b}}=\left[\Lambda_{i}\right]_{*\Gamma_{bs}}=\mathbf{0}.$
(139)

Hence, we always get

$\left[\Lambda_{i}\right]_{*u_{j}}=\left[\Lambda_{i}\right]_{*u_{b}}-\left[\Lambda_{i}\right]_{*\Gamma_{js}}+\left[\Lambda_{i}\right]_{*\Gamma_{bs}}.$
(140)

Further,

$\left[\Delta_{i}\right]_{*u_{j}}=\left[\Delta_{i}\right]_{*u_{b}}=\left[\Delta_{i}\right]_{*\Gamma_{js}}=\left[\Delta_{i}\right]_{*\Gamma_{bs}}=\mathbf{0}\quad\Longrightarrow\quad\left[\Delta_{i}\right]_{*u_{j}}=\left[\Delta_{i}\right]_{*u_{b}}-\left[\Delta_{i}\right]_{*\Gamma_{js}}+\left[\Delta_{i}\right]_{*\Gamma_{bs}}.$
(141)

Putting (129), (140), and (141), we conclude that

$\left[\mathfrak{R}_{i}\right]_{*u_{j}}=\left[\mathfrak{R}_{i}\right]_{*u_{b}}-\left[\mathfrak{R}_{i}\right]_{*\Gamma_{js}}+\left[\mathfrak{R}_{i}\right]_{*\Gamma_{bs}}.$
(142)

The equations (98), (111), (124), and (142) show that in all cases the column
$\left[\mathfrak{R}_{i}\right]_{*u_{j}}$ can be written as a linear
combination of other columns of $\mathfrak{R}_{i}$. Hence, removing it does
not change the rank, that is, for all $r\in\left\\{1,\dots,k\right\\}$.

$\operatorname{rank}\left(\mathfrak{R}_{i,-j}^{r}\right)=\operatorname{rank}\left(\mathfrak{R}_{i}^{r}\right).$
(143)

This means Case $1$, i.e., (22) holds for all
$r\in\left\\{1,\dots,k\right\\}$. ∎

###  B.8 Theorem 7.2

We start with a simple lemma that eases the computation of $t_{\epsilon}$.

######  Lemma B.5.

Let $\\{\mathbf{x}(t)\\}_{t=0}^{\infty}$ be an arbitrary sequence of vectors
over the integer $t$ that converges to $\mathbf{x}^{*}$ and suppose for every
$t\geq 0$

$\left\|\mathbf{x}(t+1)-\mathbf{x}^{*}\right\|_{2}\leq\alpha\left\|\mathbf{x}(t)-\mathbf{x}^{*}\right\|_{2},$
(144)

for some $\alpha\in(0,1)$ and define $t_{\epsilon}=\min\left\\{t\geq
0\mid\left\|\mathbf{x}(t)-\mathbf{x}^{*}\right\|_{2}\leq\epsilon\right\\}$.
Then

$t_{\epsilon}\leq\left\lceil\frac{1}{\log\frac{1}{\alpha}}\cdot\log\frac{1+\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}}{\epsilon}\right\rceil.$
(145)

###### Proof.

Note that

$\left\|\mathbf{x}(t)-\mathbf{x}^{*}\right\|_{2}\leq\alpha^{t}\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}.$
(146)

When one is not considering $t\geq 0$, we can let $\tilde{t}_{\epsilon}$ be
the minimum real number $t$ such that the right-hand side of (146) holds,
i.e.,

$\tilde{t}_{\epsilon}=\min\left\\{t\in\mathbb{R}\mid\alpha^{t}\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}\leq\epsilon\right\\}.$
(147)

Then by taking the logarithm of both sides of
$\alpha^{t}\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}=\epsilon$, we have

$\tilde{t}_{\epsilon}\log\alpha+\log\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}=\log\epsilon\quad\Longrightarrow\quad\tilde{t}_{\epsilon}=\frac{1}{\log\frac{1}{\alpha}}\cdot\log\frac{\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}}{\epsilon}.$
(148)

Note that here $\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}$ can go to
zero and cause a negative $\tilde{t}_{\epsilon}$. Hence, if we are interested
in minimum non-negative time, we can define

$t_{\epsilon}=\min\left\\{t\geq
0\mid\left\|\mathbf{x}(t)-\mathbf{x}^{*}\right\|_{2}\leq\epsilon\right\\}.$
(149)

Having $t\geq 0$ constraint and
$\left\|\mathbf{x}(t)-\mathbf{x}^{*}\right\|_{2}$ instead of
$\alpha^{t}\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}\leq\epsilon$ in the
definition of $t_{\epsilon}$, we have
$t_{\epsilon}\leq\left\lceil\tilde{t}_{\epsilon}\right\rceil$ if
$\tilde{t}_{\epsilon}\geq 0$ and $t_{\epsilon}=0$ otherwise. This fact
together with (148) leads to

$t_{\epsilon}\leq\left\lceil\frac{1}{\log\frac{1}{\alpha}}\cdot\log\frac{1+\left\|\mathbf{x}(0)-\mathbf{x}^{*}\right\|_{2}}{\epsilon}\right\rceil.$
(150)

∎

###### Proof of Theorem 7.2.

  1. (i)

Define $\mathbf{u}=[u_{1},\ldots,u_{n}]^{\top}$ and note that by construction,
Algorithm 1 preserves the summation of all values over all iterations. In
other words,
$\mathds{1}_{n}^{\top}\mathbf{v}(t)=\mathds{1}_{n}^{\top}\mathbf{u}=n\mathbf{u}^{*}$
for all $t\geq 0$. Due to [29], we know that the conditions
$W\mathds{1}_{n}=W^{\top}\mathds{1}_{n}=\mathds{1}_{n}$ and
$\rho(W-{1}/{n}\mathds{1}_{n}\mathds{1}_{n}^{\top})<1$ lead to (4). Therefore,

$\lim_{t\to\infty}\mathbf{v}(t)=\lim_{t\to\infty}W^{t}\mathbf{v}(0)=\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\mathbf{v}(0)=\mathds{1}_{n}^{\top}\mathbf{u}=\mathbf{u}^{*}.$
(151)

  2. (ii)

Since Algorithm 1 only changes $\mathbf{v}(0)$ compared to an ordinary
consensus, (5) trivially holds.

  3. (iii)

We use Lemma B.5 to compute $t_{\epsilon}$ for our problem. Note that for
$t\geq 0$, we have

$\displaystyle\mathbf{v}(t+1)-\mathbf{u}^{*}=W\mathbf{v}(t)-W\mathbf{u}^{*}-\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\mathbf{v}(t)+\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\mathbf{u}^{*}=\left(W-\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\right)\left(\mathbf{v}(t)-\mathbf{u}^{*}\right).$
(152)

In obtaining (152), we used the following facts:

$\displaystyle
W\mathbf{u}^{*}=W\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\mathbf{u}^{*}=\frac{1}{n}W\mathds{1}_{n}\mathds{1}_{n}^{\top}\mathbf{u}^{*}=\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\mathbf{u}^{*}=\mathbf{u}^{*}\quad\text{and}\quad\mathds{1}_{n}^{\top}\mathbf{v}(t)=\mathds{1}_{n}^{\top}\mathbf{u}^{*}\,\text{
for all }\,\,t\geq 0.$ (153)

From (152), we conclude that for all $t\geq 0$

$\displaystyle\left\|\mathbf{v}(t+1)-\mathbf{u}^{*}\right\|_{2}\leq\left\|W-\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\right\|_{2}\left\|\mathbf{v}(t)-\mathbf{u}^{*}\right\|_{2}.$
(154)

Comparing (154) with (144), by putting

$\alpha=\left\|W-\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\right\|_{2},$
(155)

and noting that $\alpha<1$ (because we assumed
$\rho(W-{1}/{n}\mathds{1}_{n}\mathds{1}_{n}^{\top})<1$), the quantity
$t_{\epsilon}$ can be obtained from (145) as follows:

$t_{\epsilon}\leq\frac{1}{\log\frac{1}{\alpha}}\cdot\log\frac{1+\left\|\mathbf{v}(0)-\mathbf{u}^{*}\right\|_{2}}{\epsilon}+1\leq\frac{1}{\log\frac{1}{\alpha}}\cdot\log\left(2\cdot\frac{1+\left\|\mathbf{v}(0)-\mathbf{u}^{*}\right\|^{2}_{2}}{\epsilon}\right)+1.$
(156)

Here, the quantity $\mathbf{v}(0)-\mathbf{u}^{*}$ is a random variable. We
take the expectation of both sides of (156) and apply the Jensen inequality
due to the concavity of the logarithm function (Jensen inequality states that
for a concave function $f$ and random variable $X$, $\mathbb{E}[f(x)]\leq
f(\mathbb{E}[X])$). Hence,

$\mathbb{E}\left[t_{\epsilon}\right]\leq\frac{1}{\log\frac{1}{\alpha}}\cdot\log\left(2\cdot\frac{1+\mathbb{E}\left[\left\|\mathbf{v}(0)-\mathbf{u}^{*}\right\|^{2}_{2}\right]}{\epsilon}\right)+1.$
(157)

In the remaining of the proof, we compute
$\mathbb{E}\left[\left\|\mathbf{v}(0)-\mathbf{u}^{*}\right\|^{2}_{2}\right]$
and replace it into (157). To do so, we start by writing

$\displaystyle\mathbb{E}\left[\left\|\mathbf{v}(0)-\mathbf{u}^{*}\right\|^{2}_{2}\right]\leq
n\cdot\max_{i\in[n]}\mathbb{E}\left[\left(v_{i}(0)-u^{*}\right)^{2}\right]=n\cdot\max_{i\in[n]}\left(\mathbb{E}\left[v_{i}(0)-u^{*}\right]\right)^{2}+\operatorname{Var}\left(v_{i}(0)-u^{*}\right).$
(158)

To compute the right-hand side of (158), we denote the maximum degree of a
node in $G$ by $d_{\max}$, the indicator function by $\mathbf{1}$, and the
number of elements of a set $A$ by $|A|$ and continue as follows:

$\displaystyle\left|\mathbb{E}\left[v_{i}(0)-u^{*}\right]\right|$
$\displaystyle=\left|\mathbb{E}\left[\sum_{j\in
N_{i}}\left(u_{j}-\sum_{\ell\in
N_{j}\setminus\left\\{m_{j}\right\\}}\Gamma_{j\ell}\right)\mathbf{1}_{i=m_{j}}+\Gamma_{ji}\mathbf{1}_{i\neq
m_{j}}-\frac{1}{n}\left(u_{1}+\ldots+u_{n}\right)\right]\right|$ (159)
$\displaystyle\leq\left|\left\\{j\in
N_{i}:i=m_{j}\right\\}\right|\cdot\mu_{\max}d_{\max}+\left|\left\\{j\in
N_{i}:i\neq m_{j}\right\\}\right|\cdot\mu_{\max}+\mu_{\max}$ (160)
$\displaystyle\leq\left(d_{\max}^{2}+1\right)\mu_{\max}.$ (161)

To compute $\operatorname{Var}\left(v_{i}(0)-u^{*}\right)$, we write

$\displaystyle\operatorname{Var}\left(v_{i}(0)-u^{*}\right)$
$\displaystyle=\operatorname{Var}\left(\sum_{j\in
N_{i}}\left(u_{j}-\sum_{\ell\in
N_{j}\setminus\left\\{m_{j}\right\\}}\Gamma_{j\ell}\right)\mathbf{1}_{i=m_{j}}+\Gamma_{ji}\mathbf{1}_{i\neq
m_{j}}-\frac{1}{n}\left(u_{1}+\ldots+u_{n}\right)\right)$ (162)
$\displaystyle\leq\left|\left\\{j\in
N_{i}:i=m_{j}\right\\}\right|\cdot\left(\left(1-\frac{1}{n}\right)^{2}\sigma_{\max}^{2}+\left(d_{\max}-1\right)\sigma_{\max}^{2}\right)$
(163) $\displaystyle\quad\quad+\left|\left\\{j\in N_{i}:i\neq
m_{j}\right\\}\right|\cdot\sigma_{\max}^{2}+\left|\left\\{j\in[n]:i\neq
m_{j}\right\\}\right|\cdot\frac{\sigma_{\max}^{2}}{n^{2}}$ (164)
$\displaystyle\leq\left|\left\\{j\in N_{i}:i=m_{j}\right\\}\right|\cdot
d_{\max}\sigma_{\max}^{2}+\left|\left\\{j\in[n]:i\neq
m_{j}\right\\}\right|\cdot\frac{\sigma_{\max}^{2}}{n^{2}}$ (165)
$\displaystyle\leq
d_{\max}^{2}\sigma_{\max}^{2}+\left(n-d_{\max}\right)\frac{\sigma_{\max}^{2}}{n^{2}}$
(166) $\displaystyle\leq\left(d_{\max}^{2}+1\right)\sigma_{\max}^{2}$ (167)

Putting (158), (161), and (167) together results in

$\displaystyle\mathbb{E}\left[\left\|\mathbf{v}(0)-\mathbf{u}^{*}\right\|^{2}_{2}\right]\leq
n\cdot\left(\left(d_{\max}^{2}+1\right)^{2}\mu_{\max}^{2}+\left(d_{\max}^{2}+1\right)\sigma_{\max}^{2}\right)\leq
n\left(d_{\max}^{2}+1\right)^{2}\left(\mu_{\max}^{2}+\sigma_{\max}^{2}\right).$
(168)

Finally, replace (155) and (168) into (157) to obtain

$\displaystyle\mathbb{E}\left[t_{\epsilon}\right]$
$\displaystyle\leq\frac{1}{\log\frac{1}{\left\|W-\frac{1}{n}\mathds{1}_{n}\mathds{1}_{n}^{\top}\right\|_{2}}}\cdot\log\left(2\cdot\frac{1+n\left(d_{\max}^{2}+1\right)^{2}\left(\mu_{\max}^{2}+\sigma_{\max}^{2}\right)}{\epsilon}\right)+1.$
(169)

∎