# EDDA: An Efficient Distributed Data Replication Algorithm in VANETs
## 2 Related Work
### Average Consensus Problem  
In cooperative control, a critical problem is to design appropriate protocols such that the group of agents can reach consensus on the shared information in the fixed and dynamically-changing interaction topologies. A consensus problem means convergence to a common value in the literature [44]. As a special case, an average consensus problem means convergence to the average of initial values, which is important in distributed decision-making for multiagent systems [45]. Average consensus is a fundamental problem in both distributed ad hoc networks and wireless sensor networks. The consensus status can be achieved through an iterative process of data transmission. During the past few decades, the problem attracted increasing interest in various research fields, and many gossip-based algorithms have been proposed to solve the consensus problem in wireless sensor networks [46; 47]. [PERSON] et al. [48] presented a gossip-based broadcast framework for strongly-connected topologies such as sensor networks, to solve the average consensus problem in an asynchronous environment where the network members might have different clock rates. [PERSON] et al. [49] first showed convergence to consensus under a bounded delay condition and some connectivity and intercommunication conditions imposed on the multi-agent system and then provided a bound on the time required to reach the consensus. [PERSON] and [PERSON] [50] investigated the consensus algorithms in large-scale networks; different from average preserving algorithms, they allowed it to reach consensus at a point that may be different from the average of the initial states. The advantage of such algorithms was that they did not need bidirectional communication among agents, and thus, they applied to more general contexts. To overcome the drawbacks of the standard packet-based gossip algorithms, [PERSON] et al. [51] studied a broadcast-based gossiping algorithm for wireless sensor networks and proved that the random consensus value was the average of initial node measurements and that it could be made arbitrarily close to this value in the mean squared error sense under a balanced connectivity model and by trading off convergence speed with the accuracy of the computation. [PERSON] et al. [52] analyzed the averaging problem under the gossip constraint for an arbitrary network graph and proposed a distributed subgradient algorithm that solves the optimization problem over the network. More importantly, the authors established a tight relation between the averaging time of the algorithm and the mixing time of an associated random walk, which could be utilized to design fast averaging algorithms for two popular networks: wireless sensor networks, modeled as geometric random graphs, and the Internet graph under the preferential connectivity (PC) model. [PERSON] et al. [53] proposed and analyzed a family of broadcast gossip algorithms for strongly-connected directed graphs. If the network was symmetric (undirected) or if nodes knew their out-degree, these algorithms were guaranteed to converge to the average consensus both in expectation and in the mean-squared sense. [PERSON] et al. [54] assumed the underlying graph was the complete graph and that all the weights were equal; the convergence of the weighted-averaging dynamics was established only for double-stochastic weights. To improve the result of previous work in [54], the authors [55] investigated the properties of the weighted-averaging dynamic for the consensus problem and established convergence of the weighted-averaging algorithm for general time-varying graphs. [PERSON] et al. [56] studied finite-time convergence of deterministic gossiping and showed that there existed a symmetric gossip algorithm that converged in finite time if and only if the number of network nodes was a power of two. They also proved that there always existed an asymmetric gossip algorithm with finite-time convergence for any number of nodes with asymmetric updates.