W E CONSIDER the Laplacian average consensus algo- rithm
i ∈ V = {1, . . . , N}, over a strongly connected and weightbalanced digraph G(V, E, A), 1 which drives x i of each agent i to 1 agent i ∈ V. This algorithm lacks privacy preservation because the reference value r i is trivially revealed to all the in-neighbors of each agent i ∈ V and any external agent listening to the communication messages. Laplacian average consensus is a basic primitive algorithm that enables many other in-network distributed operations, e.g., sensor fusion [3] and distributed learning [4], [5]. Therefore, devising a privacy preservation augmentation for this algorithm is of importance in the literature.
Our aim is to investigate whether in a network of N ≥ 3 agents, the agents' reference value can be concealed from eavesdroppers by adding the obfuscation signals f i and g i to, respectively, the internal dynamics and the transmitted signal of each agent i ∈ V, i.e.,
y i (t) = x i (t) + g i (t), x i (0) = r i (2b) while still guaranteeing that x i → 1 N N j=1 r j as t → ∞. Definition 1 (eavesdropper): An eavesdropper is an agent inside (internal agent) or outside (external agent) the network that stores and processes the accessible interagent communication messages y j (t), t ∈ R ≥0 , of all agents j ∈ O ⊂ V in a network that implements (2) to obtain the private reference value of the other agents in the network, without interfering with the execution of algorithm (2). For an internal eavesdropper, O is the set of one-hop agents that communicate their outputs to the eavesdropper. For an external eavesdropper, O is the set of agents; it can intercept their outgoing messages.
The use of additive obfuscation signals has already been considered for privacy preservation for the average consensus algorithm, but there are some limiting assumptions. For example, adding a sequence of well-constructed vanishing stochastic obfuscation signals to the transmitted communication messages of the agents has been investigated in the literature for discrete-time implementation of (1) over connected undirected graphs [6], [7]. These results ensure the privacy preservation of the agents with respect to internal eavesdroppers that do not have access to at least one of the agent's transmitted-in signals. When deviation from the exact consensus value is tolerated, the authors in [8] and [9] have shown that the reference value of all the agents can be made private by perturbing the transmitted-out signal using a zero-mean randomly generated Gaussian or Laplacian noise. 1. Agent 1's (eavesdropper) maximum likelihood estimator's normalized error covariance when the method of [7] is used over graph of Fig. 2(b). Agent 4's privacy is not preserved because the estimator error covariance converges to zero. Even though agent 5's privacy is preserved due to the nonzero estimator error covariance, the privacy preservation might be limited because the estimator's error covariance is very small.
The deviation from the desired average is not quantified in [8], but is explained in [9] using the ϵ-differential privacy framework introduced in [10]. Additive obfuscation noises have also been used as a privacy preservation mechanism in other distributed algorithms such as distributed optimization [11]; distributed estimation [12], [13]; and distributed games [14]. Even though our focus in this article is on privacy preservation via additive obfuscation signals for alternative implementations of Laplacian average consensus algorithm (1), it is worth noting that the point-to-point gossip algorithm, secret massage passing, and encryption have also been used in the literature to provide privacy preservation for algorithm (1)'s discrete-time implementation [15], [16], [17], [18], [19], [20], [21], [22], [23]. Alternating communication signals using vanishing masking functions [24], as well as rewiring the graph and point-to-point communication to induce privacy preservation [25], [26], [27], [28], [29], [30], have also been explored in the literature. However, in practice, rewiring may be restrictive. The scheme of adding virtual nodes to the communication graph was also explored in [31].
The existing privacy preservation algorithms including our perliminary work [1] that use additive obfuscation signals are based on the assumption that the signals should be vanishing and zero-sum. These constraints are widely used as sufficient conditions to ensure the exact convergence of the algorithm. The existing results also use stochastic noise with shared parameters. These constrained choices can limit privacy guarantees. For example, the privacy guarantee in [7] is defined as a nonzero estimation covariance including relatively small nonzero values (see Fig. 1).
This article conducts a careful analysis of the use of admissible obfuscation signals for privacy preservation for the Laplacian average consensus algorithm (1) against internal and external eavesdroppers that know the network topology. We define the admissible obfuscation signals as integrable signals that do not perturb the algorithm's exact convergence. To make the study thorough, we add the obfuscation signals to the transmitted-out signals and also to the system dynamics, as shown in (2). A common trait of privacy preservation mechanisms that are intended not to perturb the exact convergence of the algorithm is that each uses a particular class of vanishing noises or perturbation functions [6], [7], [24]. One is then left to wonder whether stronger privacy preservation guarantees are achievable if a broader class of signals was considered. This article intends to answer this question. Thus, instead of using only a prespecified class of vanishing obfuscation signals, we investigate and obtain the necessary and sufficient conditions that define the set of admissible additive obfuscation signals that do not perturb the convergence point of the algorithm. A theoretical finding we arrive at is that the admissible obfuscation signals do not have to be necessarily vanishing. We conduct our study with respect to locally chosen signals from the admissible set. Understanding the nature of the admissible obfuscation signals is crucial in privacy preservation evaluations. It is rational to assume that the eavesdroppers are aware of the necessary conditions on such signals and use them to breach the privacy of the agents. We show that such knowledge enables the eavesdroppers that have access to all the transmitted-in and transmitted-out communication signals of a targeted agent to employ an observer to asymptotically reconstruct the targeted agent's reference value. Interestingly, we show that in this case, the privacy breach is inevitable even if the agent uses nonvanishing admissible obfuscation signals.
Our analysis leads to the necessary and sufficient condition for an agent to stay private that at least one of its transmitted-in signals is not available to the eavesdropper. We define our notion of privacy preservation as follows.
Definition 2 (Privacy preservation): Consider an eavesdropper, as defined in Definition 1, that has access to y j (t), t ∈ R ≥0 , of all agents j ∈ O ⊂ V in a network that implements (2) with locally chosen admissible perturbation signals (f l , g l ), l ∈ V. We say that the privacy of an agent i ∈ V is preserved if for any arbitrary large γ ∈ R >0 , there exists a tuple (x i ′ (0) = r i ′ , f i ′ (t), g i ′ (t)), with locally chosen admissible perturbations (f i ′ (t), g i ′ (t)) and |r i ′r i | > γ, such that y j (t) ≡ y j ′ (t), t ∈ R ≥0 , for all j ∈ O.
Adhering to this privacy definition means that the eavesdropper will be neither able to estimate the private reference value nor a finite set of values to which the private reference value of an agent belongs. This means that our approach to design admissible perturbation signals leads to a privacy preservation guarantee that is stronger than the privacy preservation in the stochastic approaches such as [7], where even though the exact reference value is concealed, an estimate with a quantifiable confidence interval on the reference value can be obtained; see Fig. 1 and Section V for more discussion.
The Euclidean norm of vector x ∈ R n is ∥x∥ = √ x ⊤ x, and the (essential) supremum norm of a signal f : R n → R ≥0 is ∥f ∥ ess = (ess) sup{∥f (t)∥, t ≥ 0}. The set of measurable essentially bounded functions f : R n → R ≥0 is denoted by L ∞ n . The set of measurable functions f : R n → R ≥0 that satisfy
To distinguish and emphasize that a variable in a network is local to an agent i ∈ V = {1, . . . , N}, we use superscripts, e.g., in (2), (f i , g i ) are the local obfuscation signals of agent i ∈ V.
Graph theory: a weighted directed graph (digraph) is a triplet G = (V, E, A), where V = {1, . . . , N} is the node set, E ⊆ V × V is the edge set and A = [a ij ] ∈ R N ×N is a weighted adjacency matrix with the property that a ij > 0 if (i, j) ∈ E and a ij = 0, otherwise. A weighted digraph is undirected if a ij = a ji for all i, j ∈ V. We follow [32] in definition of in-neighbor and out-neighbor: an edge from i to j, denoted by (i, j), means that agent i can read/obtain information from agent j; then, i is called an in-neighbor of j and j is called an out-neighbor of i. The set of the out-neighbors of an agent i ∈ V is N i out , i.e., the set of agents that agent i has access to their information, N i in is the set of in-neighbors of agent i, i.e., the set of agents that have access to agent i's information. We define
A digraph is called strongly connected if for every pair of vertices, there is a directed path connecting them. We refer to a strongly connected and undirected graph as a connected graph. The weighted out-degree and weighted in-degree of a node i, are respectively, d i in = N j=1 a ji and
For a strongly connected and weight-balanced digraph, rank(L) = N -1, rank(L + L ⊤ ) = N -1, and L has one zero eigenvalue λ 1 = 0 and the rest of its eigenvalues have positive real parts. We let R ∈ R N ×(N -1) be a matrix whose columns are normalized orthogonal complement of 1 N . Then
For a strongly connected and weight-balanced digraph, -L + is a Hurwitz matrix.
We start our study by determining the space of the admissible obfuscation signals f i (t) and g i (t). Understanding the nature of these admissible signals for which the desired convergence point of the algorithm is preserved is crucial in evaluating the privacy guarantees of algorithm (2).
We refer to the set of obfuscation signals
2) that does not perturb the convergence of the algorithm, i.e., lim t→∞ x i (t) = 1 N N j=1 x j (0) = 1 N N j=1 r j for any i ∈ V, as the admissible obfuscation signals.
The following theorem, whose proof is given in Appendix B, gives the necessary and sufficient conditions that define the set of the admissible obfuscation signals. We only require this set to be a subset of the integrable and essentially bounded signals so that the differential (2a) has a unique solution. Contrary to the common practice in the literature, the signals are not required to be vanishing.
for any R and L + as defined in (3).
The necessary and sufficient conditions (4) show that the choice of admissible signals is highly coupled among the agents. However, the agents must choose the admissible signals privately and without cooperation with others. The next theorem, whose proof is given in Appendix B, offers a way for each agent i ∈ V to choose its own admissible signals (f i , g i ) privately without revealing them explicitly to others.
Theorem 3.2 (Linear algebraic coupling): Consider algorithm (2) over a strongly connected and weight-balanced digraph. Let each agent i ∈ V choose its local obfuscation signals
where β i ∈ R. Then, the necessary and sufficient conditions to satisfy (4) are
By enforcing condition (5), Theorem 3.2 shows that the coupling between the agents is a set of linear algebraic constraints. Now, if we set up the modified algorithm (2) in a way that each agent i ∈ V for example uses β i = 0, and a common value α ∈ R, which can readily be α = 0, each agent can choose its admissible obfuscation signals locally/privately according to (5) and (6b) and still guarantee convergence to the exact average consensus.
For any given α and β i s satisfying (6a), P (β i ,α) , i ∈ V, denotes the set of integrable function tuples (f i , g i ) satisfying ( 5) and (6).
Choosing signals that satisfy condition (5) is rather easy. However, condition (6b) appears to be more complex. The result below, whose proof is given in Appendix B, identifies three classes of signals that are guaranteed to satisfy condition (6b).
Of theoretical interest, Lemma 3.1 reveals a relaxation on the commonly seen condition in the literature, which requires the additive signal to be vanishing. Lemma 3.1 shows that admissible obfuscation signals {(f j , g j ) ∈ P (β j ,α) } N j=1 should not necessarily be vanishing signals even for α = 0 and β i = 0, i ∈ V. For example, g 1 (t) = 0 and g 2 (t) = sin(φ 0 + 2π( c 2 tfoot_0 + ω 0 t)), which is a waveform with linear chirp function [33], where ω 0 is the starting frequency at time t = 0, c ∈ R is the chirpiness constant, and φ 0 is the initial phase, satisfy condition (b) of Lemma 3.1 with α = 0. When a nonzero α is used, the choices for nonvanishing g satisfying (6b) are much broader, e.g., according to condition (b) of Lemma 3.1, any function that asymptotically converges to α can be used.
We can discretize the continuous-time Laplacian consensus algorithm (2)
Similar argument to those in the proof of Theorem 3.1 leads to the following conditions on the admissible obfuscation signals
The algorithms in [6] and [7] are special cases of (7), which use f i (k) = g i (k). They choose the obfuscation signals from a particular class of zero sum, which trivially satisfies (8a), and vanishing, which satisfies (8b), stochastic signals.
In light of Theorem 3.2, our proposed privacy preservation mechanism is as follows.
Each agent i ∈ V implements (2), for which it chooses its own obfuscation signals (f i , g i ) locally/privately from P (β i ,α) .
α and β i s are the preset parameters of the modified algorithm (2). The complexity of choosing them is similar to choosing the algorithm parameters in [7], [18], [19], and [20]. As mentioned earlier, the straightforward choice is β i = 0, i ∈ V, and α = 0.
To start the privacy preservation analysis, we first explicitly define the knowledge set of an eavesdropper that it uses to infer the private reference value of the other agents. 2 Without loss of generality, we assume that the internal eavesdropper is agent 1 ∈ V and the external agent is agent ext.
The knowledge set of the internal eavesdropper agent 1 and external eavesdropper agent ext is
is the set of signals available to agent 1. Let and O ⊂ V be the set of agents that external eavesdropper ext has access to it. Thus,
. The reader should notice that parameters α and β i of every agent i ∈ V are part of the eavesdropper's knowledge set, indicating that the privacy preservation guarantees we provide do not depend on the lack of information on the value of these parameters. 3 For any given α and β i , P (β i ,α) is an infinite set of integrable function tuples (f i , g i ). Each agent i ∈ V decides locally/privately which (f i , g i ) it chooses from P (β i ,α) . Thus, the probability of an eavesdropper (internal or external) knowing what admissible pair of (f i , g i ) ∈ P (β i ,α) agent i has chosen locally converges to zero as the cardinality of the set P (β i ,α) is infinity. This is in contrast to the stochastic methods such as [7], which instruct the agents to choose their obfuscation signals from a specific probability distribution, limiting the privacy guarantees; see Section V for more discussions.
Identifying the initial condition of the agents in the presence of unknown additive obfuscation signals may appear to be related to the classical concept of strong observability/detectability in control theory [35], [36]. However, the necessary conditions on the unknown admissible obfuscation signals ( 5) and ( 6) provide additional information to the eavesdropper. Such information is not being captured by the strong observability/detectability framework, rendering it inadequate for our study.
Consider the internal eavesdropper, agent 1, when it intends to obtain the initial condition of one of the agents i ∈ V. The critical part of the knowledge set of an eavesdropper when it targets an agent is the signals that it has access to. Intuitively, when an eavesdropper agent does not have direct access to all the signals in {y j (t)} j∈N i out+i , a rational strategy appears to be that the eavesdropper agent estimates the states of the agents; it does not have access to their outputs. If those agents also have out-neighbors that their output signals are not available to the eavesdropper agent, then the eavesdropper agent should estimate the state of those agents as well, until the only inputs to the dynamics that it observes are the additive admissible perturbation signals. For example, in Fig. 2(a), to obtain the reference value of agent 6, agent 1 compensates for the lack of direct access to y 7 (t), which enters the dynamics of agent 6, by estimating the state of all the agents in subgraph G 1 3 . Our results below; however, show that this strategy is not effective. In fact, we show that an eavesdropper agent (internal or external) is able to uniquely identify the reference value of an agent i ∈ V if and only if it has direct access to {y j (t)} j∈N i out+i for all t ∈ R ≥0 . To study privacy preservation for agent i ∈ V, we partition the graph into islands whose nodes are classified into different groups based on their information exchange by the eavesdropper and its out-neighbors (see Fig. 2).
For that, note that removing eavesdropper agent 1 and its incident edges results in n1 ≥ 1 disjoint strongly connected subgraphs
k and including its incident edges to this subgraph results in an island graph G
Every island of agent 1 is connected to the rest of the digraph G only through agent 1 [see Fig. 2(c)]. Thus, any information coming out of or going into any island of the eavesdropper goes through the eavesdropper. To simplify the notation, without loss of generality, carry out the subsequent study for agents in island k = 1, e.g., G 1 1 . Based on how each agent interacts with agent 1, we divide the agents of island G 1 1 into the following three groups [see Fig. 2(c)
is the set of agents, in which agent 1 has direct access to all their communication signals, while V 1 1,2 and V 1 1,3 are the sets of agents, in which some of interagent communication between them is not available to agent 1. Without loss of generality, in what follows, we assume that the agents in the network are labeled according to the ordered set
. Similarly, we let the aggregated states and obfuscation signals of the agents in V\V
. We partition L, A, and D out , respectively, to subblock matrices L ij 's, A ij 's, and D out ij 's in a comparable manner to the partitioned aggregated state (x 1 , x 2 , x 3 , x 4 , x 5 ) (see [34,Lemma 4.2]). By definition, L ij = -A ij , i, j ∈ {1, . . . , 5}, i ̸ = j. With the right notation at hand, we present the following result that provides the privacy guarantee according to Definition 2 for the agents belonging to V
) be an island of agent 1 that satisfies V
, with the locally chosen admissible obfuscation signals (f i , g i )∈ P (β i ,α) . Consider also an alternative execution of (2) with {(x i ′ (0),
and
and
Then
Moreover
Notice that by virtue of ( 16), (f i ′ , g i ′ ), i ∈ V, generated by ( 11) and ( 12), satisfies the locally chosen admissible obfuscation signals conditions ( 5) and ( 6) for the same α and β i used to generate {f i , g i } N i=1 . Next, notice that according to (10) and L -1 33 being full rank and A 23 having rows with at least one none zero entry, for any arbitrary γ ∈ R ≥ , there always exists
, while signals received by the eavesdropper, as stated in (13), are identical for the execution of the algorithm using {(x i (0
. This means that the privacy of all the agents in (V
We can develop similar results, as stated in the following corollary, for an external eavesdropper that does not have direct access to the output signal of some of the out-neighbors of agent i ∈ V.
Let agent ext be the external eavesdropper whose knowledge set is as Definition 6 where the eavesdropper has access only to
in ⊂ O} be a nonempty set. Consider the modified static average consensus algorithm (2) over a strongly connected and weight-balanced digraph G, where the agents are implementing {x i (0) = r i , f i , g i } N i=1 , with the locally chosen admissible obfuscation signals (f i , g i )∈ P (β i ,α) . For any k ∈ Ō, consider also an alternative execution of (2)
and
and
The proof of Corollary 4.1 is given in Appendix B. A similar assertion to that of Remark 4.1 about privacy preservation compliance in accordance to Definition 2 can be made about the agents whose privacy is preserved by virtue of Corollary 4.1 with respect to an external eavesdropper.
Through Lemma 4.1 and Corollary 4.1, we have established that the privacy of agents when the eavesdropper, either internal or external, does not have access to at least one signal that is transmitted in to the agent is preserved. The next result, whose proof is given in Appendix B, shows that such a guarantee does not hold for agents whose incoming and outgoing signals are in the knowledge set of the eavesdropper. 9)): Consider the modified static average consensus algorithm (2) with a set of locally chosen admissible obfuscation signals (f i , g i ) ∈ P (β i ,α) , i ∈ V, over a strongly connected and weight-balanced digraph G. Let the knowledge set of the eavesdroppers be as in Definition 6. An external eavesdropper ext and internal eavesdropper agent 1 that has access to the output signals of agent i ∈ V and all its out-neighbors can employ, respectively, observer
and observer
to asymptotically obtain r i , i ∈ V, i.e., ν a → r i , a ∈ {ext, 1} as t → ∞. Moreover, at any time t ∈ R ≥0 , the estimation error of the observers, respectively, satisfies
and
The reader may have noticed the subtle difference between the computational cost of the observers for internal and external eavesdroppers. To construct observer (25), the internal eavesdropper uses its local state. To compensate for the lack of internal dynamics, the external eavesdropper is forced to employ a higher order observer (24) and invoke condition (6b), which the internal eavesdropper does not need.
Building on our results of eavesdropper observer design in Lemma 4.2 and indistinguishable reference values in Lemma 4.1 and Corollary 4.1, we establish the necessary and sufficient condition under which an eavesdropper with knowledge set (9) can discover the reference value of an agent i ∈ V.
Proof: Proof of statement (a): Lemma 4.1 shows that if i ̸ ∈ N 1 out or N i out ̸ ⊂ N 1 out+1 , then agent 1 cannot uniquely identify the reference value r i of agent i. Next, if i ∈ N 1 out and N i out ⊆ N 1 out+1 , Lemma 4.2 guarantees that agent 1 can employ an observer to obtain the reference value of agent i. Next, sup-
). Then, by virtue of Lemma 4.1, we know that there exists an infinite number of alternative admissible initial conditions and corresponding admissible obfuscation signals for any agents in
, for which the time histories of each signal transmitted to agent 1 are identical. Therefore, agent 1 cannot uniquely identify the initial condition of any agents in
In light of Corollary 4.1 and Lemma 4.2, the proof of statement (b) is similar to that of statement (a) and is omitted for brevity.
Theorem 4.1 is of value from a transparency perspective. In using algorithm (2), the agents now know what other agents may discover their reference value. If privacy preservation is a must and it is important to not to deviate from the exact average, one also knows that the solution is to make sure that every agent has an exclusive out-neighbor that is not the out-neighbor of its out-neighbors. There are several classes of undirected graphs for which any two agents on the graph have an exclusive neighbor with respect to the other. Thus, by Theorem 4.1, the privacy of all the agents is preserved from any internal eavesdropper when they implement algorithm (2). Examples include cyclic bipartite undirected graphs, 4-regular ring lattice undirected graphs with N > 5, planar stacked prism graphs, directed ring graphs, and any biconnected undirected graph that does not contain a cycle with three edges (see [37] for the formal definition of these graph topologies). Theorem 4.1 also presents an opportunity to make agents private with respect to a particular or all the other agents by rewiring the graph so that the conditions of the theorem are satisfied.
For any given admissible β i and α, the cardinality of P (β i ,α) is infinity. Each agent chooses its own (f i , g i ) privately from the infinite set P (β i ,α) . On the other hand, given any λ ∈ R >0 , according to the discussion in Remark 4.1, for any agent i ∈
ℓ → ∞ for which y j (t) ≡ y j ℓ (t) for all j ∈ N 1 out+1 . Now, let x ′ (0) be the estimate of eavesdropper on the reference value
). Given (28), agent 1 cannot have more confidence on x ′ (0) = x i (0) over x ′ (0) = x i ℓ (0). Therefore, the eavesdropper will not be able to estimate neither the state nor a finite set of values to which the initial value of an agent belongs. Similar argument can be made about privacy preservation with respect to external eavesdropper. It is important to note that Lemma 4.1 and consequently the stronger notion of the privacy that is established here are due to the use of obfuscation signals (f i , g i ) and would have not been possible if we had used f i = g i , where f i comes from a specific class of functions as in existing literature [7].
We close our study by pointing out that even though agent 1 cannot obtain the initial condition of the individual agents in
) a 1j be the out-degree of agent 1 in subgraph G 1 1 . Then, eavesdropper 1 with the knowledge set (9) can employ the observer
The proof is given in Appendix B.
The deterministic and stochastic approaches to privacy preservation withhold different definitions of a private agent. In our deterministic setup, privacy is preserved when an eavesdropper, despite its knowledge set, ends up in an underdetermined system of equations when it wants to obtain the reference value of an agent. Therefore, the eavesdropper is left with infinite guesses of a private agent's reference value, which it cannot favor any of them more than the other (see Remark 4.2). However, the stochastic privacy of an agent is preserved when the eavesdropper's estimate of the reference value yields a nonzero uncertainty. For example, in [7], a maximum likelihood estimator is used by the eavesdropper to estimate the reference value of the other agents. It is shown that the variance of P (k) of this estimator converges to a constant matrix P . The privacy statement determines that the agents' privacy whose corresponding component in P converges to zero is breached. More specifically, given a vector ζ, a space of the agents' initial condition ζ ⊤ x(0) is disclosed to the eavesdropper if ζ ⊤ P ζ = 0 and if ζ ⊤ P ζ > 0, it is interpreted as conserving the privacy of the subspace. In this setting, for an agent whose corresponding component of P is nonzero, the eavesdropper does not know the agent's exact reference value, but it has an estimate of it. Hence, we tend to favor the deterministic notion of privacy over stochastic as the deterministic approach reveals less information. Fig. 1 is the replicate of the result of an example study over the graph in Fig. 2(b) in [7], which shows the evolution of the covariance of the maximum likelihood estimator of the eavesdropper. As expected, P 44 converges to zero but P 22 and P 55 not. Even though P 22 and P 55 are nonzero, they are pretty small, indicating that the eavesdropper can have a good estimate of the reference values of these agents. In contrast, our privacy preservation ensures that for agents whose privacy is preserved, the eavesdropper neither can obtain the reference value nor establish an estimate.
Consider the network given in Fig. 2(b). To demonstrate over results, consider the following three implementations of the modified continuous-time Laplacian average consensus algorithm (2) with the reference values and the additive obfuscation signals as follows:
, log ee 0.1t (1 + sin(t))
10e -2t + 1 + e -t sin(10t) tanh(t), 1 + e -(t-1) 2 , 10e -2t + log ee 0.1t (1 + sin(t))
⊤ .
Let Case (1) correspond to the actual operation case, and let the other two cases be admissible alternative ones. Here, all the admissible obfuscation signals are smooth, uniformly continuous, and nonvanishing. They satisfy ( 5), (6a), and (6b) with α = 1 and β i = 0, i ∈ V = {1, 2, 3, 4, 5}. The plots in the top row of Fig. 3 confirms the convergence of the algorithm to the exact average, as guaranteed by Theorem 2. The plots in the second row of Fig. 3 show that the transmitted-out signal y i of each agent i ∈ V satisfies lim t→∞ y i (t) = 1 N N j=1 r j + α. Let δy i (t) be the communication signals difference between Case (j), j ∈ {2, 3} and Case (1). As seen in the two bottom plots in Fig. 3, only δy 2 (t) is nonzero. This means that agent 1, in all three cases, receives exactly the same transmission messages from its neighbors, agents 3-5. This result, as predicted by Theorem 2, shows that agent 1, the eavesdropper, cannot tell whether r 2 is equal to 5 of Case (1), 15 of Case (2), or 25 Case (3). Moreover, agent 1 is not able to say which one of these cases is more probable. A similar statement can be made about agents 3 and 5 whose privacy is guaranteed in our framework. While the privacy of agents 2, 3, and 5 is preserved, according to Lemma 4.2, agent 1 can employ an observer of form (25) to asymptotically estimate the reference value of agent 4. The response of this estimator is shown in Fig. 4. Here, to make a comparison study with respect to [7], we used the undirected graph of Fig. 2(b). See [34] for a numerical simulation study using a directed graph.
In this article, we studied the extent of privacy preservation that additive obfuscation signals can induce on the popular average consensus algorithm, when such signals are used to conceal the reference value of the agents from eavesdroppers. In the literature, a common trait of privacy preservation mechanisms that do not perturb the exact convergence of the algorithm is that each uses a particular class of vanishing noises or perturbation functions [6], [7], [24]. Our intent was to study whether stronger privacy preservation guarantees would be achievable if a broader class of signals was considered. To conduct a thorough study, we added obfuscation signals f i and g i to both the state equation and transmitted-out signal of each agent i ∈ V [see (2)]. Previous work [6] and [7] used f i = g i . Our study showed that privacy preservation still cannot be provided for agents, whose transmitted-out and all transmitted-in communication messages are available to the eavesdropper. However, using a broader class of admissible obfuscation signals and nonidentical obfuscation signals f i and g i for each agent i ∈ V, we established a privacy preservation analysis framework that led to a stronger notion of privacy in the sense that an eavesdropper will be able to estimate neither the state nor a finite set of values to which the initial value of an agent belongs. We characterized the class of admissible obfuscation signals with a set of functionals with parameters α and β i , i ∈ V. The existing results [6], [7], [24], which use zero-sum and vanishing signals, are in fact using α = β i = 0. Thus, α = β i = 0 are known to any eavesdropper, internal or external. One can imagine that not every external eavesdropper is fully informed. Our extended results in [34] on privacy preservation against eavesdroppers that have various degrees of knowledge about α and β i s reveal, for example, that if β i corresponding to the locally chosen admissible obfuscation signals of an agent i ∈ V is not known to an eavesdropper, the privacy of the agent i is preserved even if the eavesdropper knows all the transmitted input and output signals of agent i and the parameter α. Finally, notice that our study of the use of two obfuscation signals (f i , g i ) as opposed to f i = g i leads to the theoretical finding that the obfuscation signals can be nonvanishing. From a practical perspective, this finding can be interesting with respect to, for example, a naive eavesdropper without processing power. The use of nonvanishing signals conceals the final convergence value from this naive eavesdropper. The more interesting case; however, is the case of signals like chirp g i (t) = sin(φ 0 + 2π( c 2 t 2 + ω 0 t)) that we identified through the results of Lemma 3.1. These signals lose uniform continuity when t → ∞ and, thus, may be considered an impractical choice for an obfuscation signal. However, in practice, the consensus algorithms are terminated in finite time by tolerating some convergence error. As our example showed, the effect of this type of nonvanishing signals on x i (t) diminishes with time. Therefore, it is possible that we can have an acceptable convergence error but still be able to fully disguise the final convergence point even if the external eavesdropper knows α and β i . A formal study of the use of the chirp-type signals for privacy preservation when the consensus algorithm is terminated in finite time is left as our future work.
To provide proofs for our lemmas and theorems, we rely on a set of auxiliary results, which are given in this appendix.
Lemma 7.1 (Auxiliary result 1): Let L be the Laplacian matrix of a strongly connected and weight-balanced digraph.
Then
is guaranteed to hold if and only if
The trajectories t → ζ and t → η of these two dynamics for t ∈ R ≥0 are given by
Let e = ζη. Then, the error dynamics between (31) and ( 32) is given by
or equivalently
Let ( 29) hold. Since -L + is a Hurwitz matrix, we have lim t→∞ ζ(t) = 0. Moreover, since g is essentially bounded, the trajectories of ζ are guaranteed to be bounded. Therefore, considering error dynamics (35), by invoking the input-to-state stability results [38], we have the guarantees that lim t→∞ e(t) = 0 and, consequently, lim t→∞ η(t) = 0. As such, from (34), we obtain
The null space of R ⊤ L ∈ R (N -1)×N is spanned by 1 N ; therefore, lim t→∞ t 0 e -(t-τ ) g(τ )dτ = α1 N , α ∈ R, which validates (30). Now, let (30) hold. Then, using (34), we obtain lim t→∞ η(t) = 0. Since g is essentially bounded, the trajectories of ζ are guaranteed to be bounded. Thereby, considering error dynamics (36), by invoking the input-to-state stability results [38], we have the guarantees that lim t→∞ e(t) = 0 and, consequently, lim t→∞ η(t) = 0. Since -L + is a Hurwitz matrix, we obtain ( 29) from (33). Let G be a strongly connected and weight-balanced digraph. Then, every island of any agent i is strongly connected and weight-balanced.
Proof: Without loss of generality, we prove our argument by showing that the island G 1 1 of agent 1 is strongly connected and weight-balanced. By construction, we know that there is a directed path from every agent to every other agent in G
Let the nodes of G be labeled in accordance to (1, V 2 , V 3 ), respectively, and partition the graph Laplacian L accordingly as
Since G is strongly connected and weight-balanced, we have L1 N = 0 and 1 ⊤ N L = 0, which guarantee that
Therefore
which we can use to conclude that sum(A ⊤ 12 ) = sum(A 21 ). Let the Laplacian matrix of G 1 1 be L 1 1 . Partitioning this matrix according to order node set (1, V 2 ), we obtain L
, where d 1,1 out = j∈V 2 a 1j = sum(A ⊤ 12 ). To establish that G 1 1 is weight-balanced digraph, we next show that
Therefore, to prove G
We prove first necessity. We write the algorithm (2) in compact form
Left multiplying both sides of (42) by
Next, we apply the change of variable
where T is defined in (3), to write (42) in the equivalent form
The solution of (44) is
Given (4a), (45a) results in lim t→∞ p
Because for a strongly connected and weight-balanced digraph, -L + is a Hurwitz matrix, lim t→∞ e -L + t p 2:N (0) = 0. Then, the necessary condition for ( 46) is (4b).
The sufficiency proof follows from noting that under (4), the trajectories of (45) satisfy lim t→∞ p 1 (t) = 1 √ N N i=1 x i (0) and lim t→∞ p 2:N (t) = 0. Then, given (43) and x i (0) = r i , we obtain lim t→∞ x i (t) = 1 N N j=1 r j , i ∈ V. Proof of Theorem 3.2: Given (5), it is straightforward to see that (6a) is necessary and sufficient for (4a). Next, we observe that using (5), we can write lim t→∞
Given (47), by virtue of Lemma 7.1, (4b) holds if and only if (6b) holds.
Proof of Lemma 3.1: When condition (a) holds, the proof of the statement follows from statement (a) of Lemma 7.2. When condition (b) is satisfied, the proof follows from statements (a) and (b) of Lemma 7.2, which, respectively, give lim t→∞ t 0 e -(t-τ ) g 1 (τ )dτ = α and lim t→∞ t 0 e -(t-τ ) g 2 (τ )dτ = 0. When condition (c) is satisfied, the proof follows from statement (a) of Lemma 7.2, which gives lim t→∞ t 0 e -(t-τ ) g 1 (τ )dτ = α, and noting that t 0 e -(t-τ ) g 2 (τ )dτ is the zero state response of system ζ = -ζ + g 2 . Since g 2 (t) is essentially bounded, this system is ISS, and as a result, it is also integral ISS [38]. Then, t 0 e -(t-τ ) g 2 (τ )dτ = 0 follows from [38,Lemma 3.1].
Proof of Lemma 4.1: Let the error variables of the two execution of (2) described in the statement be δx
and
δg 2 (t) = -e -D out 22 t δx 2 (0), δf 2 (t) = -A 23 e -L 33 t δx 3 (0).
Given the interagent interactions across the network based on agent grouping in accordance to the definition of the island G 1 1
(see Fig. 2), the error dynamics pertained to the modified static average consensus algorithm (2) reads as
Since, for a strongly connected and weight-balanced digraph, we have rank(L) = N -1 and -(L + L ⊤ ) ≤ 0, the subblock matrices -L 33 and -L 44 and -L 55 satisfy -(L ii + L ⊤ ii ) < 0, i ∈ {1, . . . , 5}. Thereby, they are invertible and Hurwitz matrices.
To establish (21), we show that 1 ⊤ N δx(0) = 0 N . For this, note that taking into account (48), we can write
Comparing B with the block partitioned L in (50), it is evident that 1 ⊤ B = 0 follows from 1 ⊤ L = 0. Consequently, we can deduce from (51) that 1 ⊤ δx(0) = 0. Next, given (21), we validate (15) by invoking Theorem 3.2 and showing that the perturbation signals (f i ′ , g i ′ ), i ∈ V, satisfy the sufficient conditions in (6). For i ∈ V\V 1 1,2 , the sufficient conditions in (6) are trivially satisfied. To show (6a) for i ∈ V 1 1,2 , we proceed as follows. First note that since (f i , g i ), i ∈ V
, also satisfy the sufficient condition (6a). Establishing that g i ′ , i ∈ V 1 1,2 , satisfies that the sufficient condition (6b) follows from the admissibility of g i , i ∈ V 1 1,2 , which ensures that it satisfies (6b), and direct calculations as shown in the following: lim t→∞ t 0 e -(t-τ ) g i ′ (τ ) dτ = α + lim t→∞ t 0 e -(t-τ ) e -d i out τ δx i (0) dτ = α. Here, we used the fact that for a strongly connected digraph, we have d i out ≥ 1. Next, we assume that (13)
hold. Then, for the given initial conditions (48), we identify the perturbation signals that make the error dynamics (50) render such an output. As we show in the following, these perturbation signals are exactly the same as (49). Then, the proof is established by the fact that given a set of initial conditions and integrable external signals, the solution of any linear ordinary differential equation is unique. That is, if we implement the identified inputs, the error dynamics is guaranteed to satisfy (52). If (52) holds, then the error dynamics (50) reads as 25), we can write ψ + ẋi = f i + d i out g i , which, because of x i (0) = r i and ζ(0) = -β i , gives ψ(t) = -x i (t) + r i + t 0 (f i (τ ) + d i out g i (τ ))dτβ i , t ∈ R ≥0 . Then, using (2b) and (25b), we obtain (27) as the estimation error. Subsequently, because of (5) and since lim t→∞ (x 1 (t)x i (t)) = 0, from (27), we obtain lim t→∞ ν(t) = r i . For an external eavesdropper, given (2) and (24a), we can write ζ + ẋi = f i + d i out g i , which, given x i (0) = r i and ζ(0) = -β iα, for t ∈ R ≥0 , gives
On the other hand, using (2b), t → η(t) is obtained from (26b). Then, tracking error (26a) is readily deduced from (24c) and (57). Next, given ( 5) and (6b) and also lim t→∞ e -t η 0 = 0, we obtain lim t→∞ ν(t) = r i + lim t→∞ (-x i (t) + t 0 e -(t-τ ) x i (τ )dτ ). Subsequently, since lim t→∞ x i (t) = 1 N N j=1 r j , we can conclude our proof by invoking Lemma 7.2 that guarantees lim t→∞ t 0 e -(t-τ ) x i (τ )dτ = lim t→∞ x i (t) = 1 gives η + j∈V 1 1 \{1} x i = j∈V 1 1 \{1} (f j (t) + d j out g j (t)). Thereby, given η(0) = -j∈V 1 1 \{1} β i and x i (0) = r i , we obtain η(t) = j∈V 1 1 \{1} r j -j∈V 1 1 \{1} x j (t) + β i . Therefore, we can write n 2,3 µ(t)
t 0 (f j (τ ) + d j out g j (τ ))dτ + n 2,3 x 1 (t).
The proof then follows from the necessary condition (5) on the perturbation signals and the fact that lim t→∞ n 2,3 x 1 (t) -j∈(V 1 1,2 ∪V 1 1,3 ) x i (t) = 0 (recall that lim t→∞ x i (t) = lim t→∞ x j (t), ∀i, j ∈ V).
We conduct our privacy preservation analysis from a single eavesdropper's point of view. The extension of our theoretical results to multiple collaborative and noncollaborative eavesdroppers is straightforward.
The interested reader can find our extended results in[34] on privacy preservation against eavesdroppers that have various degrees of knowledge about α and β i s.Authorized licensed use limited to: Access paid by The UC Irvine Libraries. Downloaded on May 14,2024 at 23:52:56 UTC from IEEE Xplore. Restrictions apply.
Authorized licensed use limited to: Access paid by The UC Irvine Libraries. Downloaded on May 14,2024 at 23:52:56 UTC from IEEE Xplore. Restrictions apply.