# EDDA: An Efficient Distributed Data Replication Algorithm in VANETs
## 4 Speed of Convergence on Arbitrary Graph and Linear Graph
### Lower Bound for Linear Graph
Thus,  
\[= \frac{(\mathrm{MaxRec}(i-1,j-1)-\mathrm{MaxSnd}(i-1,j-1))}{2}\]4 \[= \frac{(\mathrm{MaxRec}(i-1,j-1)-\mathrm{MaxSnd}(i-1,j-1))}{2}\]5 \[= \frac{(\mathrm{MaxRec}(i-1,j-1)-\mathrm{MaxSnd}(i-1,j-1))}{2}\]6 \[= \frac{(\mathrm{MaxRec}(i-1,j-1)-\mathrm{MaxSnd}(i-1,j-1))}{2}\]7 \[= \frac{(\mathrm{MaxRec}(i-1,j-1)-\mathrm{MaxSnd}(i-1,j-1))}{2}\]8 \[= \frac{(\mathrm{MaxRec}(i-1,j-1)-\mathrm{MaxSnd}(i-1,j-1))}{2}\]9 \[+\frac{(\mathrm{MaxRec}(i,j-1)-\mathrm{MaxSnd}(i,j-1))}{2}\]0 \[+\frac{(\mathrm{MaxRec}(i,j-1)-\mathrm{MaxSnd}(i,j-1))}{2}\]1  
Thus, \(\mathrm{Rec}(i,j-1)\geq\mathrm{Rec}^{*}(i,j)\). A contradiction. (B) We assume \(\mathrm{Snd}(i,j)<\mathrm{MaxSnd}(i,j)\). Since \(\mathrm{Snd}(i,j)=\mathrm{Rec}(i+1,j)\) and \(\mathrm{MaxSnd}(i,j)=\mathrm{MaxRec}(i+1,j)\), it transforms into the problem \(\mathrm{Rec}(i+1,j)<\mathrm{MaxRec}(i+1,j)\), which is Case A, and a contradiction has been derived. Lemma 6: _For any constant \(\delta>0\), after \(n^{\delta}\) normalized stages, Node \(1\) has a value of at most \(\frac{n}{\sqrt{c\log n}}\) for some fixed \(c>0\)._  
Proof: Let \(f(n)=\sqrt{c\log n}\), where \(c\) will be determined later. After \(k\) stages, let \(n_{1}\geq n_{2}\geq n_{3}\cdots\geq n_{k^{\prime}}\) be all values of nodes greater than zero. Clearly, \(k^{\prime}\leq k\) since each stage can only make one node have a value of zero for a value greater than zero in the linear graph. Let \(d_{i}=n_{i}-n_{i+1}\). Assume that \(\sum_{i=1}^{k}d_{i}\geq\frac{n}{cf(n)}\). 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 normalized stages \(k-1\) and \(k\), the potential of the nodes is reduced by at least \(\sum_{i=1}^{k}(\frac{d_{i}}{2})^{2}\geq\frac{(\sum_{i=1}^{k}d_{i}/2)^{2}}{k} \geq\frac{n^{2}}{4 kf(n)^{2}}\) by the Cauchy-Schwarz inequality. After \(h=n^{\delta}\) stages, the potential is reduced by at least \(\sum_{k=1}^{h}\frac{n^{2}}{4 kf(n)^{2}}\geq\frac{n^{2}}{4f(n)^{2}}\cdot(\sum_{ k=1}^{h}\frac{1}{k})\geq\frac{n^{2}\log h}{4 df(n)^{2}}\) for some fixed positive real \(d\) since \(\sum_{k=1}^{h}\frac{1}{k}=\Phi(\log h)\). Therefore, for \(h=n^{\delta}\), \(\frac{\log h}{4 df(n)^{2}}\geq 1\) by selecting a fixed \(c\) to be small enough. Since the maximum potential is at most \(n^{2}\), which is the beginning of the system for \(n_{1}=n\) and \(n_{i}=0\) for all \(i>1\), after at most \(h=n^{\delta}\) normalized stages, the value at Node \(1\) is \(n_{1}=\sum_{i=1}^{k}d_{i}<\frac{n}{f(n)}\). Theorem 4.1: _It requires \(\Omega(\max(n,m)\sqrt{\log\max(n,m)})\) stages to enter an \(\epsilon\)-balance in a linear graph model._  
Proof: Assume that Node \(1\) starts with the largest value \(n\). Let \(m=n/8\). Let \(f(n)=\sqrt{c\log n}\), where \(c\) is the same as that in Lemma 6. By Lemma 6, after \(n^{\delta}<m/2\) normalized stages, we have \(n_{1}\leq\frac{n}{f(n)}\). We still have at least \(m/2\) nodes with zero values. We can assume that all stages are normalized stages by Lemma 5. This is because the normalized stages give the maximum flow from Node \(1\) to others. By Lemma 4, \(d_{1}\geq d_{2}\geq\cdots\). In the rest of the stages, each stage sends at most \(\frac{n_{1}}{m/2}\leq\frac{16}{f(n)}\) values to the area that contains the last \(\frac{m}{2}\) nodes with zero values. When the system enters \(\epsilon\)-balancefor \(\epsilon<1\), each node must have a value of at least four. Thus, the total number of stages is at least \(4\cdot\frac{m}{2}\cdot\frac{1}{\frac{16}{m}}=\frac{1}{8}\cdot mf(n)=\Omega(n \sqrt{\log n})=\Omega(\max(n,m)\sqrt{\log\max(n,m)})\).