# Privacy-Preserving Overgrid: Secure Data Collection for the Smart Grid
## 2 Background and Related Work
### Overlay Networks  
Overlay networks are particular communication networks built on top of an existing network. With the advent of Internet and peer-to-peer (P2P) networks, overlay networks have attracted much attention for their flexibility and scalability. These networks are a great tool to create application sharing and distribution of large-scale data, multicast application layer services, distribution of On Demand video contents and video streaming, etc. Overlay networks are efficiently used to provide data redundancy, data identification, data search, data persistence guarantees, authentication, and anonymization. They also offer efficient, scalable and robust routing architectures, combined with fault tolerance, load balancing, and explicit geographical knowledge. Since energy systems are intrinsically distributed, the mapping between the energy grid and the network overlay is a straightforward and promising approach.  
A particular case of overlay networks are P2P networks, in which the nodes, the so-called peers, all have equivalent functionality. Each pair of nodes can communicate directly or via other peers using routing protocols, and there is no centralized control or hierarchical organization. Generally, P2P networks require no special administrative procedures to be realized and therefore can easily grow both in terms of nodes and data. They are particularly robust to errors and failures and have excellent performance thanks to their decentralized nature.  
There are two main classes of P2P overlay networks: structured and unstructured. In structured overlay networks, the network topology is rigidly controlled and the content is stored in specific locations of the network (not on random nodes) so that data search is more efficient. Structured P2P networks usually use distributed hash tables (DHTs) to organize data allocation. Unstructured overlays, instead, are based on looser protocols, where nodes do not have a priori knowledge of the topology, and use flooding mechanisms with limited range to search for content on the network. These mechanisms are highly efficient to locate popular and replicated content but are less efficient in contexts in which the data are sparse. Moreover, the load of each node grows linearly with the number of queries. Despite this, unstructured overlay networks suffer much less overhead than those based on DHTs. As a result, today they are more prevalent on the Internet than the former. For more information on P2P networks, see [12].  
A particular use case of overlay networks is the aggregation of distributed data. Data aggregation algorithms determine global properties in the network that can be used in other applications. Examples of aggregate functions are SUM, AVERAGE, MIN, MAX, quantile, etc. In recent years, various algorithms for distributed computation of these functions have been developed, with different advantages and disadvantages in terms of accuracy, robustness, computational complexity, and communication overhead, as discussed in [13]. As we will explain, we use such algorithms in the implementation of Overgrid: in particular, we exploit the Flow Updating [14] algorithm to monitor the average energy consumption of the nodes in the grid. The Flow Updating algorithm is an efficient scheme that has been proven to be fault-tolerant to both message loss and node crashes, and its convergence speed has been studied in [15].