# EDDA: An Efficient Distributed Data Replication Algorithm in VANETs
## 4 Speed of Convergence on Arbitrary Graph and Linear Graph
### Upper Bound for Linear Graph  
Now, we discuss the convergence speed of linear graph that generally describes the traffic on a highway. We believe linear graph is an important special case that should be studied.  
**Definition 8**: _A lineargraph \(G(V,E)\) consists a list of nodes \(v_{1},v_{2},\cdots,v_{n}\), and the set of edges \(E=\{v_{1}v_{2},v_{2}v_{3},\cdots,v_{i}v_{i+1},\cdots,v_{n-1}v_{n}\}\). In other words, each edge connects two consecutive nodes in the list \(v_{1},v_{2},\cdots,v_{n}\), and every two consecutive nodes has an edge connecting them._  
**Theorem 3**: _Assume that the list of nodes in a linear graph \(G(V,E)\) starts with the initial values \(L:n,0,0,\cdots,0\). Then, it takes at most \(O(\frac{n^{2}}{e})\) stages of real average operations to reach the stage of \(\epsilon\)-balance for a linear graph._  
The total number of average operations \(A(n_{i},0)\) with \(n_{i}\geq 2\) is at most \(n\). We focus on the number of average operations \(A(n_{i},n_{i+1})\) with \(n_{i}\), \(n_{i+1}\geq 1\).  
Let \(n_{1}\geq n_{2}\geq n_{3}\cdots\geq n_{m}\) with \(m\leq n\) since there are at most \(m\) nodes with a value of at least one. Let \(d_{i}=n_{i}-n_{i+1}\).  
Let each node \(i\) take an average operation with one of the neighbors \(j\in\{i-1,i+1\}\) such that \(i\) and \(j\) do not take the average in the last stage. In two consecutive stages, we have made at least contribution \(\sum_{i=1}^{m-1}(\frac{d_{i}}{2})^{2}\geq\frac{(\sum_{i=1}^{m-1}d_{i}/2)^{2}}{ m-1}=\frac{(\sum_{i=1}^{m-1}d_{i})^{2}}{4(m-1)}\) to \(S(H)\) by the Cauchy-Schwarz inequality, where \(H\) is the set of all average operations.  
Let \(k\) be the minimum integer with \(\frac{n}{2^{k}}\leq\epsilon\). Divide \([\frac{n}{2^{k}},n]\) into \(O(\log n)\) intervals: \(I_{1}=(\frac{n}{2^{k}},n],l_{2}=(\frac{n}{2^{k}},\frac{n}{2}],\cdots,l_{k}=( \frac{n}{2^{k}},\frac{n}{2^{k-1}}]\). The region \(t\) represents the interval \(l_{t}\) such that \(n_{1}-n_{m}\in(\frac{n}{2^{k+1}},\frac{n}{2^{k}}]\). When the system enters into the balanced status, we have \(n_{1}-n_{m}\leq\frac{n}{2^{k}}\leq\epsilon\). To achieve the maximum potential, we assume there are \(2^{t}\) numbers, which are equal to \(\frac{n}{2^{t}}\) (which satisfies \(2^{t}\cdot\frac{n}{2^{t}}\geq n\)). According to the definition of potential \(P(L)=a_{1}^{2}+a_{2}^{2}+\cdots+a_{m}^{2}\), here\(a_{1}=\cdots=a_{m}=\frac{n}{2^{t}}\), \(m=2^{t}\), we can get that the maximum potential of a list in region \(t\) is at most \(2^{t}(\frac{n}{2^{t}})^{2}\) (see Part 2 of Lemma 1). Therefore, it takes at most \(2^{t}(\frac{n}{2^{t}})^{2}\cdot\frac{1}{\frac{(\frac{n}{2})^{t}}{4(m-1)}}\leq 4 (m-1)2^{t}\) stages in the region \(t\).  
The total number of stages is bounded by \(n+\sum_{t=1}^{k}4m2^{t}=O(\frac{n^{2}}{\epsilon})\).  
Theorem 4.1: _Let \(w\) be a parameter greater than zero. Assume that the list of nodes in a linear graph \(G(V,E)\) starts with the initial values \(L:n,0,0,\cdots,0\). Then, it takes at most \(O(\frac{n^{2}}{\epsilon}\cdot\min(m,\frac{n}{w}))\) stages of \(w\)-spread operations to reach the stage of \(\epsilon\)-balance for a linear graph._  
Proof: Since the total number of nodes is \(m\), there are at most \(m\) times that the average operation involves a node with zero value. There are at most \(\frac{n}{w}\) nodes to have a value of at least \(w\). This follows from Theorem 3.  
According to the above theorems, the list of nodes in a linear graph \(G(V,E)\) with initial values \(L:n,0,0,\cdots,0\) reaches the balance after certain stages. Assume a new node with value zero joins the list; it is obvious that the balance will be broken. As the values of the new list are smaller than the initial ones, it should take fewer real average operations for the system to enter into a new balanced status, which is relatively quicker than the previous balance process.