# EDDA: An Efficient Distributed Data Replication Algorithm in VANETs
## 3 Bounded Number of Data Replication in Message Passing
### Definitions and Model  
Assume vehicle \(i\) in the region carries message \(M\) and a parameter \(n_{i}\geq 1\), where \(n_{i}\) indicates the number of copies assigned to be spread by vehicle \(i\). The total dissemination tasks of all the participant vehicles should meet the condition, which is \(\sum_{i=1}^{m}n_{i}=n\). Here, \(n\) indicates the maximum number of copies that \(M\) can be replicated and spread in the network. If \(n_{i},n_{j}(i,j\in 1,\cdots,m)\) carried by any two vehicles \(i\) and \(j\) satisfy the condition \(|n_{i}-n_{j}|\leq\epsilon\), we say the system is \(\epsilon\)-balanced. An \(\epsilon\)-balanced status will be obtained after a series of average operations. We define some concepts in this section. When a node carries message \(M\) and it controls at most \(a\) copies of message \(M\) to be distributed in the network, it must have \(a\geq 1\), and each node with a nonzero value is at least one. We need to define the concept of potential (energy) in order to analyze the number of stages for the system entering into a balanced status and need the following lemma. Lemma 1: _Assume that \(a,b,c\), and \(d\) are real numbers with \(a+b=c+d\). Then, we have (1) \((a^{2}+b^{2})-(c^{2}+d^{2})=2(b-d)(b-c)\) and (2) \((a^{2}+b^{2})-(c^{2}+d^{2})\geq 0\) if \(a\leq c\leq d\leq b\)._  
Proof: By the condition of the lemma, we have \(b-d=c-a\) and \(b-c=d-a\). Thus, \((a^{2}+b* _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 formalize 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 linear graph._  
Definition 2: Let \(M\) be a message. Let \(G(V,E)\) be the connected graph for a set of vehicles. If each node \(i\) has a parameter \(n_{i}\) to control the number of copies of message \(M\) that \(i\) can replicate, then \(G(V,E)\) associated with \(n_{i}\) becomes a graph with a bounded number of message copies. Definition 3: Let \(G(V,E)\) be a connected graph. Each node of \(G\) is assigned a nonnegative number \(n_{i}\). The nodes of \(G\) are \(\epsilon\)-balanced in the corresponding bounded message graph if the following conditions are satisfied:  
* Each node of \(G\) with \(n_{i}>0\) satisfies \(n_{i}\geq 1\). * For every two nodes with \(n_{i},n_{j}>0\), \(|n_{i}-n_{j}|\leq\epsilon\), and
* There is no edge between nodes of values \(n_{i}\) and \(n_{j}\) in \(G\), respectively, such that \(n_{i}\geq 2\) and \(n_{j}=0\). Definition 4: Let \(\mathbb{R}\) be the set of real numbers and \(\mathbb{N}\) be the set of nonnegative integers. Define the following concepts:  
* _A real average function_ \(A(.,. )\) _is a mapping_ \(\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}\times\mathbb{R}\)_, such that for two numbers_ \(a\leq b\)_,_ \(A(a,b)=(\frac{a+b}{2},\frac{a+b}{2})\) _if_ \(a+b\geq 2\)_, or_ \(A(a,b)=(a,b)\) _if_ \(a+b<2\)_._
* _An integer average function_ \(A(.,. )\) _is a mapping_ \(\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}\) _such that for two numbers_ \(a\leq b\)_,_ \(A(a,b)=(k,k)\) _if_ \(a+b=2k\geq 2\)_,_ \(A(a,b)=(k,k+1)\) _if_ \(a+b=2k+1\geq 2\)_, or_ \(A(a,b)=(a,b)\) _if_ \(a+b<2\)_._
* _For a list_ \(L:a_{1},a_{2},\cdots,a_{m}\) _of numbers, define the potential of_ \(L\) _to be_ \(P(L)=a_{1}^{2}+a_{2}^{2}+\cdots+a_{m}^{2}\)_._
* _For an average function_ \(A(.,. )\)_, define_ \(S_{A}(\langle a,b\rangle)=2(b-d)(b-c)\)_, where_ \(A(a,b)=(c,d)\)_. Number_ \(b\) _is considered a bar of length_ \(b\)_._ \(S_{A}(\langle a,b\rangle)\) _can be considered a small piece of length_ \(b-d\) _from the bar of length_ \(b\) _to go down by_ \((b-c)\)_. Function_ \(S_{A}(. )\) _gives the potential change after an average operation (See Lemma_ 1_)._
* _Let_ \(A(.,. )\) _be an average function.