# EDDA: An Efficient Distributed Data Replication Algorithm in VANETs
## 1 Introduction
### Main Contributions  
Graph theory is used to help understand the topological properties of VANETs, where the vehicles and their communication links can be modeled as vertices and edges in the graph, respectively. According to the network traffic density, we divide the VANET topology into three types of graphs: linear graph, arbitrary graph and complete graph. In urban areas, due to fast speed of the vehicles, the network topology changes from time to time, so do the communication links. We can treat this type of network topology as arbitrary graph. In the scenario of a highway, assume vehicles move at a constant velocity along the road and every vehicle has full knowledge of its neighbors right next to it. In this situation, the network topology can be seen as a special case of arbitrary graph, that is a linear graph. We talk about the cases of arbitrary graph and linear graph in this study, while the case of complete graph will be discussed in the future work. This paper investigates the problem of a vehicle node disseminating a message to a large number of recipients in a specific area in VANETs, and the objective is to disseminate the message to the destination area with low dissemination delay and reduced communication overhead. As shown in Figure 1, a message is generated at the source node, carried and forwarded by the passing vehicles to vehicles in the destination region. During the message transmission process, the message can be forwarded from one vehicle to another by V2V communications. When two vehicle nodes meet, they will update their values of the corresponding message after an average operation until the network consensus is reached. When the network reaches a consensus, we say that it is \(\epsilon\)-balanced. In this context, we propose a distributed data replication algorithm, EDDA, for arbitrary graph and linear graph. Before more details are given, we give a description of the \(\epsilon\)-balanced status to help understand the proposed idea. Assume each vehicle \(i\) in the region carries message \(M\) and a parameter \(n_{i}\geq 1\), which indicates how many message copies \(i\) can spread. After average operations, if \(n_{i}(i=1,\cdots,m)\) carried by vehicle \(i\) satisfies the conditions \(\sum_{i=1}^{m}n_{i}=n\) and \(|n_{i}-n_{j}|\leq\epsilon\), we say that the network is \(\epsilon\)-balanced. Here, \(n\) indicates the total number of copies, \(n_{i}\) indicates the number of copies held by node \(i\) and \(\epsilon\in(0,1]\). To speed up the dissemination process, the proposed data replication algorithm lets the sender distribute the data dissemination task to vehicles in the same network by allowing each vehicle node to randomly choose one of their neighbors and average their current values, which indicate the amount of their assigned dissemination tasks. The pair of nodes computes the pairwise average, which then becomes the new value for both nodes. By iterating this pairwise averaging operations, it is easy to show that all the nodes converge to the global average in a completely distributed manner. Then, the paper analyzes the replication algorithm from the perspective of the approximation of how many nodes can receive the message when the system enters into a balanced status. It also presents the convergence speed of the network in the cases of arbitrary graph and linear graph. More specifically, we measure the complexity of network convergence by the number of communication stages in a distributed computing environment. A communication stage indicates an average operation among a set of independent edges in the connected graph. In each stage, each node is involved in at most one average operation. Theoretical analysis and simulation results show that the proposed algorithm can improve the efficiency of data dissemination and make the network converge to consensus quickly. Besides, the dissemination delay and overhead can be measured respectively by network convergence speed and the number of communication stages needed by the network to be \(\epsilon\)-balanced.