{'fraction_non_alphanumeric': 0.044077961019490255, 'fraction_numerical': 0.010979125821704532, 'mean_word_length': 4.2054268219474125, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed design of deterministic discrete-time privacy preserving average consensus for multi-agent systems through network augmentation

Average consensus protocols emerge with a central role in distributed systems and decision-making such as distributed information fusion, distributed optimization, distributed estimation, and control. A key advantage of these protocols is that agents exchange and reveal their state information only to their neighbors. Yet, it can raise privacy concerns in situations where the agents' states contain sensitive information. In this paper, we propose a novel (noiseless) privacy preserving distributed algorithms for multi-agent systems to reach an average consensus. The main idea of the algorithms is that each agent runs a (small) network with a crafted structure and dynamics to form a network of networks (i.e., the connection between the newly created networks and their interconnections respecting the initial network connections). Together with a re-weighting of the dynamic parameters dictating the inter-agent dynamics and the initial states, we show that it is possible to ensure that the value of each node converges to the consensus value of the original network. Furthermore, we show that, under mild assumptions, it is possible to craft the dynamics such that the design can be achieved in a distributed fashion. Finally, we illustrate the proposed algorithm with examples.


Introduction
We are facing a growing interest in distributed computation, reflected by the increase of data being exchanged in large-scale systems that can be spatially distributed. Therefore, numerous systems have been developed to compute distributedly a function. The distributed function results from each agent computing a local function, using the neighbors' communicated information, and sharing the output with its neighbors, for instance, using consensus [1][2][3][4] or state retrieval [5]. Under the described setting, for security reasons, the agents may want to ensure that their information is not disclosed. This privacy requirement leads to what is called secure multi-party computation, the problem of a set of agents computing an agreed-upon function of their initial states in a private way [6].
Computer science literature often focus on the problem of shielding sensitive information. Techniques using cryptographic schemes provide ways of ensuring privacy-preserving information, such as Yao's garbled circuit [7], Shamir's secret sharing [8], secure multi-party computation [9], and homomorphic encryption (HE) [10]. In our work, we are interested in ensuring data privacy to reach an average consensus. There are mainly three research directions that aim tho reach this goal: (i) homomorphic encryption-based (HE-based); (ii) differential privacy-based (DP-based); (iii) observability-based (O-based).
The authors of [11][12][13][14][15][16] introduced HE-based average consensus methods. Notwithstanding, a major drawback of the HE-based approaches is that they require expensive computation and communication, making them (potentially) unsustainable to use in real-world applications that have computation power and communication limitations [17,18].
A different research path to ensure that data remains private is DP-based, which consists of leveraging differential privacy guarantees [19]. The main idea behind differential privacy is to add noise to the shared information. In the works of [20][21][22][23][24], average consensus algorithms are devised to ensure differential privacy, aiming to converge to the average, while keeping the agents' initial values private. However, the introduced noise does not ensure the exact average consensus. To circumvent this problem, in [21,[25][26][27], the authors propose to add correlated noise. However, from an implementation point of view, it is difficult to guarantee that the required assumptions hold, and therefore there will always be uncertainty in the final consensus value achieved. Furthermore, we observe that noise generation is typically achieved with a pseudo-random generation created, deterministically, from a seed. Therefore, the privacy guarantees depend on the seed that must be hidden from the other agents (i.e., personal or secret) or the use of an expensive random number generator device [28]. In contrast, it is possible to hide information without adding noise into the agents' states. The O-based approaches concept means there is a stream of observation/measurements of neighboring agents and the agent's own, generated by the underlying consensus protocol (assume to be known to all the agents). Thus, the notion of observability in dynamical systems describes necessary and sufficient conditions to obtain an algorithm (i.e., an estimator) to retrieve all agents' states [29]. We can categorize the methods of this line of research according to what it is proposed to be modified in the consensus dynamics, e.g.: • changing the dynamics, while maintaining the structure (i.e., the network topology); • editing the connections (i.e., adding/removing edges in the network and the associated weights); • augment the network by including more nodes/(i.e., agents) and connections between these (and, subsequently, the number of parameters specifying the dynamics); • adjusting the initial agents' states; • a combination of the previous.
In [30], the authors propose a distributed average information consensus algorithm that preserves each agent initial state confidentiality, without corrupting the state values of agents with noise. The authors ensure privacy with the help of concealing factors, which are assigned to the agents in the network before the initiation of the proposed consensus algorithm by a central authority (CA). Further, the method requires a balancing constraint, implying that the sum of the edges' weights that end in a node equals the sum of the edges' weights that start in that node. In this work, we do not need a central authority, and we further do not require a balancing constraint.
In [27], the authors obtained closed-form expressions of both the optimal distributed estimation and the privacy parameters. The work in [31] proposes a privacy-preserving approach, based on state decomposition, for the network average consensus problem, where each node decomposes its state into two substates with random initial values with a mean equal to the original state initial value. In [32], the authors proposed a dynamic average consensus algorithm that guarantees accuracy and preserves privacy of the initial values, under topological restrictions on the communication digraph. A main drawback is that the algorithm has to create a virtual network with O(n 2 ) nodes, where n is the number of agents in the original consensus network. This contrasts with the methods that we propose here, which require creating a virtual network with O(n) nodes.
The work in [33] analyzes the interplay between a specific network topologies and the observability subspace generated by the underlying dynamics. The authors propose a communication protocol to reach weighted average consensus on the initial network agents' states, but where each agent is only able to retrieve a small subset of the initial states of the agents that are not its neighbors. Finally, in [34], the authors use the concept of observability together with tools from graph theory and optimization to present an algorithm for network synthesis with privacy guarantees. The method selects the optimal weights for the communication graph to maximize the privacy of the network nodes. Notwithstanding, in the previous methods, the design is difficult to accomplish, and it is not guaranteed that all agents manage to keep their state private.
Our work aligns with an observability-based approach to achieve privacy in average consensus while ensuring the convergence to the exact average of the initial agents' values, and that no agent is able to retrieve other agents' initial state, which can be understood as full privacy. Moreover, contrarily to [32], our nodes can share information with their neighbors in a broadcast setting. In fact, in our scheme, we propose that an agent shares one of its states, and keep the remaining hidden from the network despite the local dynamics being publicly available (i.e., available to all the other agents). Therefore, in a sense, the secret key to each agent is the way that it splits its initial condition across its augmented states, which can be done arbitrarily as long as some of its states are not set to zero.
Main contributions We propose two network designs that consist in augmenting the agents' state and impose a given dynamics on it that allows a network of multi-agents to reach average consensus, while keeping the agents' initial states private. Specifically, the first network design that we propose achieves the objective by increasing the agents' univariate initial state to four states (i.e., the original one plus three more), and re-defining the obtained network's weights, including the original weights of the consensus network, such that consensus is possible while ensuring privacy. Furthermore, it is possible to proceed to a rescaling of the initial condition through the left-eigenvector associated with the eigenvalue one of the matrix described by the consensus protocol such that average consensus is possible.
Notwithstanding, the computation of such eigenvectors can only be approximated to a certain precision-level with polynomial-time algorithms. Therefore, we propose a secondly (mildly) constrained design, which requires the network to be bidirectional and time-reversible. We emphasize that it does not need to be symmetric (in terms of the weights). In this scenario, we need to increase the agents' univariate initial state to five states (i.e., the original one plus four more). This new construction allows, withal, computing exactly the left-eigenvector associated with the eigenvalue one of the described by the consensus protocol matrix with linear-time complexity and in a distributed fashion.
Paper structure In Section 2, we present the notation used in this paper. In Section 3, we formally state the two problem formulations addressed in this paper. In Section 4, we present solutions to the proposed problems. Lastly, in Section 5, we present several illustrative simulations that support the main results in the current paper.

Notation
We use lower case letters do denote vectors (e.g., x) and upper case letters to denote matrices (e.g., A and C). We use x k to denote the kth entry of vector x ∈ R N , with k ∈ {1, . . . , N }, A i to denote the ith row of matrix A ∈ R N ×M and A ij to denote the jth entry of the ith row of A, with i ∈ {1, . . . , N } and j ∈ {1, . . . , M }.
Given a matrix A ∈ R N ×N , we denote by span(A) the linear span of A, i.e., the smallest linear subspace that contains the set of column vectors of matrix A. Moreover, we denote by e N i the i-th canonical N -dimensional column vector, i.e., a vector of size N with all entries equal to zero, except the i-th entry that is one. We denote by I N the N × N identity matrix, and by I I We represent a (directed) network of agents by the graph G = X , E X ,X , where X = {1, . . . , n} are the nodes that denote the set of n > 2 agents, and E X ,X ⊂ X × X are the edges that correspond to pairs of agents (nodes). If (i, j) ∈ E X ,X then i transmits to j, and we can associate a weight w(i, j) = w ij given by a weight function w : E X ,X → R + . In the case where the edges do not have associated a weight, we simply denote them as pairs of nodes. If a digraph G = X , E X ,X , where X = {1, . . . , n} does not have weights associated with edges is such that (i, j) ∈ E X ,X if and only if (j, i) ∈ E X ,X , then we call it a graph. Similarly, if a digraph G = X , E X ,X , where X = {1, . . . , n} has weights associated with edges is such that ((i, j), w i,j ) ∈ E X ,X if and only if ((j, i), w j,i ) ∈ E X ,X (with possibly w i,j = w j,i ), then we call it a bidirected graph.
Additionally, a matrix A ∈ R N ×N , can induce a (weighted) network of agents through a digraph representation G(A) = X , E X ,X , where X = {1, . . . , N } and (i, j) ∈ E X ,X (or ((i, j), w) ∈ E X ,X ) if and only if A j,i = 0 (or A j,i = w = 0). Analogously, given a network of agents G = X , E X ,X , we define the matrix ∈ E X ,X ) and A j,i = 0 otherwise. When only the structure of the network is defined, the edges, but not the weights, we highlight this fact using a bar on top of the matrix (e.g.,Ā).
For a network of agents (communication graph) G = X , E X ,X and an agent i ∈ X in the network of agents G, we denote the neighborhood of agent i by N i , where N i = {i} ∪ {j : (i, j) ∈ E X ,X }. Finally, we say that a network is strongly connected if there is a path between each pair of nodes (i.e., if for each node x ∈ X there is a sequence of nodes x, x 1 , . . . , x k , y for all y ∈ X such that (x, x 1 ), (x k , y), (x i , x i+1 ) ∈ E X ,X for all i = 1, . . . , k − 1).

Problem statement
In this paper, we consider multi-agent systems whose goal is to reach consensus, through discrete-time linear time-invariant (DT-LTI) dynamics. In the context of multi-agents, the agents' interdependencies are described by a network, given by a digraph G = X , E X ,X , where each node corresponds to an agent state.
First, notice that every agent i is such that its dynamics are driven by inputoutput relations due to their state's exchange. Specifically, the agent's state x i [k] ∈ R at a given time k ∈ N evolves as follows: where u i ∈ R is the (external) input to agent i, which, in the context of the present paper, is given as a linear combination of the agent's incoming neighbors, i.e., From the perspective of agent i, it measures the state of agents j, for j ∈ N i . Therefore, we can describe the measured output y i [k] ∈ R N as where I Ni N denotes the N ×N matrix with columns given by the canonical vector e j N , for j ∈ N i , and x[k] is the vector gathering the agents' states. Henceforth, the external input to an agent i is a closed-loop dynamical system described as where w i is the combined set of weights.
Next, we explain how privacy can be understood as an observability-based (i.e., O-based) problem where the interdependencies between agents conditioning which states can be retrieved. Therefore, we can now pose the question: "Can agent i retrieve agent j's state x j [0] for all j = 1, . . . , N ?" If the answer is negative across all agents (i.e., for all i and for all j), then we can say that all states are private. Specifically, we notice that the dynamics is a consequence of input/output relations between the agents. Thus, to assess how many states an agent has access to over the entire dynamical network, we have where, for k ∈ Z + 0 , x[k] ∈ R N is the state, and y i [k] ∈ R N ×N is the output for agent i.
In particular, we focus on the problem of consensus. It is the decision-making process that strives to achieve agreement among members of a group. The consensus process is restricted by the communication between agents, delimited by the network topology. Hence, the consensus value of any agent is the outcome of a distributed algorithm. This problem is of distinguished importance due to its wide range of applications. Examples of applications are such as distributed optimization [35,36]; motion coordination tasks (e.g., flocking, leader following) [37,38]; rendezvous problems [39]; computer networks resource allocation [40]; and even in computing relative importance of webpages in the PageRank algorithm [41].
To determine the states that are retrievable when the system dynamics and measurements are available, we can invoke a system's property so-called observabilility. A system is observable if, for any possible evolution of state and control vectors, the current system's state can be estimated using only the information from the outputs. In the context of dynamical systems, it is possible to retrieve the agents' states from the model using estimators/observers (e.g., in the case of deterministic systems, we could use [42]) by using the measured output (i.e., the neighbors' states) and the knowledge of the system's dynamics. Therefore, we can view privacy as an observability-based problem.
Several criteria exist to assess if a system is observable [43]. In the context of this paper, we relay on the Popov-Belevitch-Hautus eigenvector criteria (PBH test) defined next.
Proposition 1 (The Popov-Belevitch-Hautus (PBH test) eigenvector observability test [43]). Consider the LTI system where C is the output matrix. We can refer to the system by the matrices that describe them, i.e., the pair (A,C). Given (A, C), with A ∈ R N ×N and C ∈ R M×N , consider the matrix Next, we can define privacy through an observability criterion.
and an agent i ∈ V, we say that the initial state of agent j ∈ V \ {i} is private to agent i (or, equivalently, agent i cannot recover the initial state of any • In other words, Definition 1 reflects that if an agent, by receiving information from its neighbors (observing its neighbors' states), can recover another agent's sate, then this other agent's state is not private to the first agent. Remark that, from this, it follows that the neighbors can always have access to the initial state of the neighbors, and, therefore, privacy in the strict sense above cannot be achieved. Thus, a new approach to the problem of ensuring privacy needs to be considered, as we detail hereafter.
Notwithstanding, it might be possible to augment the system dynamics to circumvent such implicit limitation, which is motivated by the following example.
Motivation example. Consider the star network of agents depicted in Figure 1 (a). For almost all parameters, it is possible to invoke the PBH test, to readily notice that the agent in the center of the star network can recover the initial state of every other agent. Therefore, we wonder if we can scramble the initial state of each agent in a network local to that agent such that the initial state is no longer recoverable by other agents, see Figure 1 (b), where the local network of each agent is depicted by the yellow nodes and gray edges. In this example, the state of agent 1, Observe that this may imply redesigning the original dynamics matrix not only to accommodate the local networks of each agent but also to re-scale the original weights, while keeping the original connections between agents.  In fact, the previous motivation example ( Figure 1) is sufficient to satisfy Proposition 1 such that Definition 1 holds. However, it is not sufficient to ensure that the network reaches consensus, as we will, later on, further notice.
In what follows, we do the following assumptions.
A 1 The structure of the network is available and cannot be changed (i.e., we cannot change which pairs of agents communicate), but we can choose its parameters. ⋄ The network of agents G is strongly connected, and it has at least three agents. ⋄ Observe that the first assumption (A 1 ) portrays diverse practical applications where it is impossible to change the interconnections naturally due to shortrange communications between agents or inherent infrastructure that is too costly to change. The second assumption (A 2 ) reflects that fact that with only two agents, after reaching average consensus, an agent can trivially recover the initial state of the other agent. Intuitively, the same reasoning applies if the network has N + 1 agents and N of them work in coalition, being also able to recover the other agent initial state.
Under these assumptions, we can formulate our formal problem statement as follows. (3a) such that the following holds

Privacy
• agent j cannot recover the initial state of any agent, i = j, according to (Definition 1) (3c) Notice that when d i = 0, the agents do not have augmented states and, therefore, the third condition, (3c), boils down to assess if the agent's state belongs to the unobservable subspace of the system. Furthermore, notice that we do not allow to change (add/remove) the connections between agents given in G, but we allow each node to have an internal subnetwork (which may be seen as having memory). Also, each agent does not require extra communication capabilities, and it continues to send a scalar value in each iteration.
That said, and briefly speaking, the proposed solution will be able to ensure privacy by crafting the augmented network dynamics and splitting the scalar initial state of an agent among its augmented states.
Additionally, we would like, if possible, to find a solution for P 1 that can be achieved distributively, which leads to the following. P D 1 consist of P 1 enforcing the solution to be distributed.

Roadmap of the main results
The rest of the paper focused on addressing the above mentioned problems. We achieve these solutions in a series of steps, focusing on various intermediate objectives and relaxed problem variants. In what follows we summarize the flow of the remainder of the paper by briefly reviewing these intermediate objectives and outlining their solution strategy by pointing to the corresponding key technical results that are developed in the subsequent sections.
Objective 1: Obtaining a solution to a relaxed version of P 1 , say P R 1 , by eliminating the consensus requirement (3b).
Solution Outline (Theorem 2): Consider two additional memory states with the connections depicted in Figure 2 (a), with dynamics matrix in Figure 2 (b), following the same color scheme as in the motivation example (for each node of the original network a similar design is conducted). The solution yields for almost all possible numerical realization of the dynamics matrix parameters. Additionally, the initial state is distributed among the different states such that non-zero initial condition is given to any of the two augmented states  Figure 3 (b). The parameter selection is a 2,1 = 2/Z 2 , a 1,2 = 1/Z 1 , a 1,4 = 1/Z 1 , a 3,1 = 1/Z 3 , and a 4,2 = 1/Z 4 , where Z i is the sum of the row i entries. In addition, because in this scenario the consensus value is (v 0 ) ⊺ 1, where v 0 is the left-eigenvector associated with the extended dynamics matrix, we need to distribute the initial value of the agent's state among the extended states, and scale it to account for the total number of nodes in the extended network and also to mitigate the weight imposed by v 0 . First, each agent distributes the initial condition across its augmented states (setting as 0 for the original state), the distribution can be tailored by each agent, and scaling it to make the new average of initial states equal to the original one, i.e., Second, each agent and augmented states re-scale the new initial condition, Because the computation of v 0 is centralized, and it may lead to numerical challenges, we also propose the following. . From this, we can compute the left-eigenvector using only local information, see details in Algorithm 3.

Deterministic privacy preserving average consensus for multi-agent systems
We first propose to address a restricted version P R 1 , where we do waive the consensus condition (Section 4.1). In particular, to build an intuition we show that simple solutions can be proposed to address P R 1 , but these are insufficient to address P 1 . Subsequently, by identifying the conditions that limit the achievement of consensus, we identify a class of augmented network structures and particular realizations of the dynamics that solve P 1 (Section 4.2). Lastly, we show that under some additional assumptions, it is possible to deploy a solution to P D 1 , i.e., a solution to P 1 that can be achieved in a distributed fashion (Section 4.3).

Achieving privacy in discrete-time LTI multi-agent systems
The first question that emerges is if it is possible to extend the network such that neighbors' states could be perceived as neighbors of neighbors, to guarantee that some of the new states are private -see Remark 1.
Remark 1. The neighbors can always have access to the initial state of the neighbors, and therefore privacy in the strict sense above cannot be achieved.
For instance, consider A as in Figure 5 (a), with digraph representation depicted in Figure 5 (b). In this network, it is trivial to see that any agent can recover the initial state of all the agents in the network. Using the Popov criteria, Theorem 1, we have that, for any agent, where C = I 3 . And we get and rank P λ O(A,C) is full for any λ ∈ C. Hence, the system is observable.
Intuitively, due to the structure, we may have agents in one place that guarantee that the relative position of the other agent is such that it cannot retrieve other agent's state. This property raises the question: Is it possible to extend the network by equipping the agents with memory such that such relative positions hold for the newly added states (at least two)? This way, we could distribute the initial state of the agent among the augmented states (memory) such that the sum is not retrieved. This intuition leads us to the problem below, a restricted version of problem P 1 , where we remove condition (3c). P R 1 consists of P 1 only with the privacy specification, i.e., satisfying (3a) and (3c).
Next, we propose a design following the procedure described in Algorithm 1 that attains the feasibility question posed in P R 1 , i.e., that constructs a matrix A P such thatx and the conditions of P R Algorithm 1 Construction of a privacy dynamics matrix A P that solves P R 1 1: input: network of agents G = X , E X ,X and initial state x[0] ∈ R N 2: output: dynamics matrix of the augmented network A P ∈ R 3N ×3N and augmented initial statex P [0] ∈ R 3N 3: set A ∈ R N ×N as the adjacency matrix of G 4: fill the entries of A P with zeros 5: set ⊲ The digraph representation is augmented placing two additional nodes per each original node that only connect bidirectly to the original node, setting some of the dynamics matrix entries to zero, and then the non-zero entries will be as follows. Copy the matrix A to the first n rows and n columns . . , N } and i = j 6: for i = 1, . . . , N ⊲ Set additional entries values Further, if we have the additional goal that the original initial state (distributed across the augmented states) cannot be recovered, i.e., if be the parametric matrix resulting from Algorithm 1 with input matrix A. We have that where 0 is the 2N × 2N matrix of zeros, the matrix and the matrix Next, we compute for all λ ∈ R the span of the P λ O(A P ,C) , with the output matrix C ∈ R N ×3N that consists in observing each state variable that is a neighbor node of i (including node i), Notwithstanding, we will do a proof that shows a stronger property, by placing an output in each state variable of the original A plus the two augmented states of node i. In other words, we do the proof using the an output matrix with more output capabilities than the required ones. Without loss of generality, suppose that i = N . If this is not the case, we may apply a permutation in the node labels and obtain this case. The output matrix is Therefore, we have that for all λ ∈ R. Now, we identify two possible scenarios for λ, which are λ = 0 or λ = 0. If λ = 0, we get However, when λ = 0, we obtain Hence, for all j ∈ {1, . . . , N }\{i}, we have that αe N +2j−1 3N +βe N +2j 3N ∈ span P λ O(A P ,C) , and from (4), with α = a j,N +2j−1 = 0 and β = a j,N +2j−1 = 0, it readily follows that e N +2j−1 3N , e N +2j 3N / ∈ span P λ O(A P ,C) . If we have the additional goal that e N +2j−1 3N + e N +2j 3N / ∈ span P λ O(A P ,C) then we further require that α = β.
If two or more agents form a coalition, will they be able to retrieve other agents' states? The answer is no, as noted in the following observation. The next step is to address P 1 by including the average consensus restriction (3b).

Solution to problem P 1
Next, our goal is to apply the previous strategy to achieve privacy in average consensus, using an LTI system. Given the initial states of N agents, x i [0] ∈ R, for i = 1, . . . , N and a matrix A, the state update of the agents at time k + 1 with k ∈ N is described as The following result from [44] states the required conditions so that Eq. (5) reaches asymptotic consensus.

Proposition 2 ([44]
). The LTI system described in (5)  Hence, if we start with the matrix A ∈ R N ×N and then apply Algorithm 1 to produce A P ∈ R 3N ×3N , we need to ensure that the A P entries' values ensure: (i) the conditions of Proposition 2; (ii) the additional condition in Theorem 2 that ∀j = 1, . . . , N a j,N +2j−1 = a j,N +2j−1 .
In other words, the matrix A P needs to be row-stochastic to ensure (1), and we can normalize the initial state of each agent , as envisioned.
The first result is a negative one, stating that the previous construction does not fulfill the necessary conditions to reach average consensus stated in Proposition 2.
In the next result, we show that any matrix with the same structure as the one of a matrix obtained from Algorithm 1 has period δ ≥ 2.
Let A be non-negative. Fix an index i and define the period of index i to be the greatest common divisor of all natural numbers m such that (A i,i ) m > 0. When A is irreducible, the period of every index is the same and is called the period of A. In fact, when A is irreducible, the period can be defined as the greatest common divisor of the lengths of the closed directed paths in G(A). Lemma 1. The construction of A P , obtained from a matrix A satisfying Proposition 2 with Algorithm 1 does not suffice to ensure consensus.

Proof. Consider the matrix
The matrix obtained with Algorithm 1 is with digraph representation G(A P ) depicted in Figure 6. It is easy to observe that the closed directed paths have sizes multiple of 2. Hence, the matrix is periodic, with period δ = 2. Hence, by the Perron-Frobenius theorem, there is more than one eigenvalue of A P with magnitude 1, and the system with this matrix does not reach consensus.
We further notice that, in the previous example, even if the agents were able to reach a consensus, an agent can infer the initial value of the other agent because it knows the values of its augmented states and the average consensus value. Hence, an agent can recover the sum of the other agent augmented states initial values, which is the initial value of the other agent.

Solution to Problem P 1
The first step is to overcome the limitations previously encountered. Therefore, we need to verify what are the augmented state networks that achieve the desired goal. We summarize this result in the following.
Lemma 2. The only networks (up to isomorphism) with three augmented states that satisfy the necessary conditions to address P 1 are the ones depicted in Figure 7.   Figure 7: Networks with one agent (node 1) and three augmented states that can be used to address problem P 1 . • Proof. We start by enumerating all the strongly connected networks with 4 agents (3 augmented states). Second, we filtered the obtained networks that satisfy the following: • do not correspond to periodic matrices; • are not observable by sensing only node 1 (the original node); • allow a parameterization (numerical instance of the nonzeros) of the adjacency matrix which ensures that an agent cannot recover the initial state of at least one of the other agents augmented states.
Last, we filtered the later list to have only one graph for each class of isomorphic graphs, obtaining the networks depicted in Figure 7.
Subsequently, without loss of generality, we focus on the first network of augmented states, Figure 7 (a), that allow to address problem P 1 , and we 1: input: network of agents G = X , E X ,X and initial agents state x[0] ∈ R N 2: output: dynamics matrix A P ∈ R 4N ×4N , and initial agents statex P [0] ∈ R 4N 3: set A ∈ R N ×N as the adjacency matrix of G 4: fill the entries of A P with zeros 5: set ⊲ Copy the matrix A to the first n rows and n columns . . , N } and i = j 6: for i = 1, . . . , N ⊲ Set additional entries values : normalize the rows of A P dividing by their sum 8: compute the left-eigenvector v 0 of A P associated with the eigenvalue 1 9: distribute the initial condition of each agent across its augmented states (setting as 0 for the original state), the distribution can be tailored by each agent, and scaling it to make the new average of initial states equal to the original one, i.e., select α i , β i , γ i = 0 10: re-scale, for each agent the new initial condition,x P j [0], to bẽ provide an algorithm that selects a parameterization of the nonzero values of the adjacency matrix to illustrate how we can ensure privacy in average consensus. Now, we use the running example of a bidirected cycle with 3 agents with Algorithm 2. We obtain the network of agents depicted in Figure 8 and the matrix A P is the following:  The network of agents depicted in Figure 8 is a repeated pattern for each agent. Hence, we can check what agent 1 can recover by observing its direct neighbors, i.e., with C = I 6 0 6×6 .
Using Theorem 1, we have that In other words, agent 1 cannot recover the original initial states of agents 2 and 3.
However, to reach average consensus, the initial state of the agents needs to be re-scaled according to the left-eigenvector associated with the eigenvalue 1, which is: v L = [ 5 Hence, another property that we have to ensure, is that agent 1 is not able to recover a combination of other agents augmented states that is given by the corresponding values in v L .
Regarding agent 2, the agent 1 can recover e 7 12 + e 8 12 + 1 2 e 9 12 with coefficients that are not multiple of the respective entries in v L . Analogously, regarding agent 3, the agent 1 can recover e 10 12 + e 11 12 + 1 2 e 12 12 with coefficients that are not multiple of the respective entries in v L .
In Figure 9 (a), we depict the agents state evolution under network G(A), weight matrix A, and initial agents' states x[0] = [ 1 2 1 3 1 5 ] ⊺ . In Figure 9 (b), we depict the agents state evolution under network G(A P ), weight matrix A P , and initial agents' states In Figure 9 (c), we depict the agents state evolution under network G(A P ), weight matrix A P , and re-scaled initial agents' states

Steps Agents evolution
Consensus evolution

Steps Agents evolution
Consensus evolution (b) State evolution of agents from network G(A P ) with weight matrix A P and initial states x ′ [0]. Steps Agents evolution Consensus evolution (c) State evolution of agents from network G(A P ) with weight matrix A P and re-scaled initial statesx P [0]. Figure 9: Privacy for bidirected cycle of size 3.
The previous example illustrates the following result.
Lemma 3. Let A ∈ R N ×N be a matrix such that G(Ā) is a strongly connected graph. Then, the systemx P [k + 1] = A PxP [k] and y[k] = Cx P [k] , where the matrix A P ∈ R 4N ×4N results from Algorithm 2 and has the following properties: Proof. We construct the observabillity matrix P 0 O(A P ,C) and compute its span.
v L is the left-eigenvector of A P obtained with Algorithm 2, associated with the eigenvalue 1, then the initial state of agent j that is distributed among its augmented states nodes is private. • Observe that a disadvantage of the solution is that we need to compute the left-eigenvector associated with the eigenvalue 1. In general, we can only compute an approximation of this eigenvector in polynomial-time. Further, notice that a similar path can be followed using any other of the augmented states networks depicted in Figure 7.
In the quest of eliminating the aforementioned drawback, we explore the situation where the considered network is bidirected but with possible distinct weights, modeled by a time-reversible transition matrix. This scenario will allow us to have an expedient and efficient way of computing the left-eigenvector of the dynamics matrix.

Solution to Problem P D 1
Let A ∈ R N ×N be the system dynamics matrix, the matrix A is said to be irreversible is there is s ∈ R such that N i=1 s i = 1 and Notice that, in this scenario, the network of agents has to be bidirected. The first result is that we cannot use solely three augmented states of each agent to both address P 1 and ensure a time-reversible transition matrix.
Lemma 4. Given a bidirected network of agents, we cannot use three augmented states of each agent connected by a bidirected network to address P 1 . • Proof. The previous result trivially follows from the fact that to ensure reversibility the network should be bidirected and there is not a bidirected network in Figure 7, i.e., the networks with three augmented states of an agent that allows to address P 1 . Therefore, we need to consider four augmented states of each agent, as detailed in the following.
Lemma 5. The only networks (up to isomorphism) with four augmented states that satisfy the necessary conditions to address P D 1 are the ones depicted in Figure 10. (p) Figure 10: Bidirected networks with one agent (node 1) and four augmented states that can be used to address problem P 1 and ensure time reversibility. • Next, we propose an algorithm to address problem P D 1 that produces a timereversible matrix A P corresponding to a bidirected graph whenever the input matrix A is row stochastic, time-reversible and corresponds to a bidirected graph. To this end we use the network of agent's augmented states depicted in Figure 10 (a). Notice that, in contrast with the previous solution, we require that the input is the matrix A, row stochastic, time-reversible and corresponding to a bidirected graph. Lemma 6. Let A ∈ R N ×N be a time-reversible matrix such that G(Ā) is a bidirected graph. Then, the matrix A P ∈ R 5N ×5N that results from Algorithm 3 is row stochastic. • Proof. To show that A P is row stochastic, we first analyse the first N rows of A P . The first N row columns of each of this rows sums up to 1 2 . This happens since the original A is row stochastic and in step 4 of Algorithm 3, we divide each element of A by 2. Subsequently, in row i, we further have that the entries different from 0 are A P i,N +4i−3 , A P i,N +4i−2 , A P i,N +4i−1 and A P i,N +4i−0 . The sum of those entries is 1 12 + 1 8 + 1 4 + 1 24 = 1 2 . Therefore, each of the N first rows sum up to 1. Finally, we have to check that the remaining rows also sum up to 1.
Lemma 7. Let A ∈ R N ×N be a time-reversible matrix such that G(Ā) is a bidirected graph. Then, the matrix A P ∈ R 5N ×5N that results from Algorithm 3 is time-reversible. • Proof. First, we can check That the submatrix of A P corresponding to the first N rows and first N columns is satisfies the equation r i A P ij = r j A P ji for all i = 1, . . . , N with r i ≥ 0. Notice that, for the original A, we have that for all it is also true that s i Aij 2 = s j Aji 2 which is the same as s i A P ij = s j A P ji . Next, we look at a block corresponding to the additional augmented states of node i. Given s i , we define: Now, replacing in the equation to check reversibility, we have that However, now we no longer have that Z = 5N i=1 s i = 1, but we can simply normalize each s i to becomes i = si Z so that 5N i=1s i = 1 without changing the previous equations (as it corresponds to divide both sizes by the same quantity).
Next, we show, without loss of generality, that agent 1, by observing all the agents in the original network and its own augmented states, cannot recover other agents' augmented states.
Lemma 8. Let A ∈ R N ×N be a time-reversible matrix such that G(Ā) is a bidirected graph. Then, the system x[k + 1] = A P x[k] and y[k] = Cx[k] , where the matrix A P ∈ R 5N ×5N results from Algorithm 3 and has the following properties: where v L is the left-eigenvector of A P associated with the eigenvalue 1. • Proof. We construct the observabillity matrix P 0 O(A P ,C) and compute its span. for all j = i, (2) holds. Finally, we have that the left-eigenvector v L associated with the eigenvalue 1 corresponds to the s obtained in Lemma 7. We have that find j ∈ N such that A P ij = 0 for some i ∈ Y Proof. By Lemma 8, the matrix obtained with Algorithm 3 ensures that an agent of the original system is not able to recover the initial state of other original agents nor the combination of other original agents with their augmented states. By Lemma 6, we have that the matrix obtained with Algorithm 3 is row stochastic. Moreover, by Lemma 8, we ensure that an agent cannot recover the initial value of other agents. Finally, by Proposition 2, we have ensured that the output dynamics matrix A P and the output new initial statex P [0] ensure that the system reaches average consensus. The next corollary follows immediately from the fact that the computation space-complexity cannot be larger than the time-complexity (see Section 4.1 of [45]).  The first example we use is a cycle graph with 3 agents, corresponding to the matrix A = ⊺ since A is also column stochastic.
Next, we apply Algorithm 4 and obtain the matrix which corresponds to the graph representation depicted in Figure   In Figure 13, we depict the agents state evolution under network G(A P ), weight matrix A P , and vector of initial agents' statesx P [0]. Furthermore, we verified that the required conditions of Lemma 8 hold, as envisioned.    In Figure 16, we depict the agents state evolution under network G(A P ), weight matrix A P , and vector of initial agents' statesx P [0]. Also, we verified that the required conditions of Lemma 8 hold, as envisioned.

Conclusions
In this paper, we tackled the problem of keeping the initial agents' states private in an average consensus network. We designed two algorithms to reach average consensus of a network of multi-agents that allows to keep their initial states private. The principal idea of the algorithms is to augment the state of each agent with a set of augmented states nodes that only interact locally. Then, each agent can choose how to distribute its initial state to the augmented states while ensuring that the other agents cannot recover the initial information.
The first proposed algorithm achieves the privacy goal by designing three local augmented states of each agent and the weights of the adjacency matrix. A computational step required is to compute the left-eigenvector associated with the eigenvalue 1 of the dynamics matrix, which in general may be only approximately computed with polynomial-time algorithms. Subsequently, to overcome this computational demanding task, we proposed a second algorithm that requires the additional assumption that the network of agents is bidirected.
The second algorithm designs four local augmented states of each agent and the weights of the adjacency matrix, but it further ensures that the designed final network is time-reversible. This additional property allows computing the lefteigenvector associated with the eigenvalue 1 of the dynamics matrix explicitly with linear-time complexity. We observe that we can increase the proposed methods robustness to attack using the general method proposed in [3].
Finally, we illustrated the proposed algorithms with examples. Future research directions include the design of the network parameters that ensures a faster convergence rate of the proposed methods.