Average Consensus Enhancements for Distributed Stopping and Privacy Enforcement

Abstract

In this thesis, we study important extensions to the problem of distributed average consensus in multi-agent systems. Distributed average consensus is a problem where each node (agent) has some initial value and the nodes need to compute, in a distributed manner and subject to communication restrictions among the nodes, the average of their values. In this thesis, we develop and analyze distributed algorithms that enable the nodes (while calculating the average of these initial values) to also determine when to stop (because approximate average consensus has been reached) and ensure that their privacy is preserved (in the sense that the initial value of a node is not fully exposed to other nodes). We focus on providing these enhancements to linear iterative strategies, in which each node updates its value as a weighted linear combination of its own previous value and the values of its neighbors. We develop and analyze a distributed privacy-preserving average consensus algorithm that enables all of the components of a distributed system, each with some initial value, to asymptotically reach average consensus on their initial values, without having to reveal the specific value they contribute to the average calculation. Specifically, we consider a set of components (nodes) that interact via directional communication links (edges) that form a generally directed communication topology (digraph). The proposed protocol can be followed by each node that does not want to reveal its initial value and, under certain conditions on the communication topology, all nodes can calculate the average of their initial values while maintaining privacy (i.e., without exposing the initial values they contribute to the average). We assume that malicious-curious nodes try to identify the initial values of other nodes but do not interfere in the computation in any other way. Accepting a worst case scenario that malicious-curious nodes know the predefined linear strategy and topology of the network (but not the actual values used by the nodes that want to preserve their privacy), we analyze their ability to infer the initial values of other nodes (which may or may not follow the privacy-preserving protocol). Apart from obtaining topological conditions that guarantee that the initial values of certain nodes are not exposed, we also study the ability of the malicious-curious nodes to estimate the initial values of other nodes and examine conditions that affect privacy preservation. We also consider how iterative strategies for asymptotic average consensus in undirected and directed graphs (digraphs) can be adapted so that the nodes can determine, in a distributed fashion, a stopping criterion that allows them to terminate the execution of the iteration when approximate average consensus has been reached. The nodes are said to have reached approximate average consensus when each of them has a value that is close (in a way that we precisely define) to the desirable average. The absence of bidirectional communication links makes this task particularly challenging in a digraph (for a pair of nodes, only one of them may be aware of a discrepancy and may have no direct way of informing the other). The proposed algorithms can be used to cap the number of transmissions that are required in order to reach (approximate) average consensus.