# EDDA: An Efficient Distributed Data Replication Algorithm in VANETs
## 4 Speed of Convergence on Arbitrary Graph and Linear Graph
### Lower Bound for Linear Graph  
Following the result of the upper bound, we derive a nontrivial super linear lower bound for linear graph. It is derived based on some bottleneck properties for messages passing over a linear graph. We consider the linear graph for which Node 1 connects to Node 2, node \(i\) connects to both node \(i-1\) and node \(i+1\) for \(1<i<m\) and node \(m\) connects to node \(m-1\). For \(m=\frac{n}{g}\), it is trivial to see a linear lower bound to enter into \(\epsilon\)-balance since it takes \(\Omega(m)\) stages for a positive value to reach node \(m\) from Node 1 in a linear graph. Definition 9: Assume that, Node \(1\) has value \(n\), and all of the other nodes have zero in the beginning. A normalized process is that at stage \(j\) with odd \(j\), node \(2i-1\) takes the average with \(2i\) for \(i=1,2,\cdots\); and, at stage \(j\) with even \(j\), node \(2i\) takes the average with \(2i+1\) for \(i=1,2,\cdots\). Definition 10: Assume that \(m\) nodes have values \(n_{1}\geq n_{2}\geq\cdots\geq n_{m}\), respectively. The gap at node \(i\) is defined by \(n_{i}-n_{i+1}\). For a node \(i\) with a value of nine and its neighbor node \(i+1\) with a value of three, both nodes have a value of \(\frac{9+3}{2}=6\) after taking the average operation. Node \(i\) sends the \(9-6=3\) value to node \(i+1\), and node \(i+1\) receives three from this average operation. Each node can only take one average operation each moment. Average operations do not change the total values among the nodes. Definition 11: For each node \(i\), define \(\operatorname{Rec}(i,j)\) to be the amount that node \(i\) has received after \(j\) stages and \(\operatorname{Snd}(i,j)\) to be the amount that node \(i\) has sent after \(j\) stages. Definition 12: For each node \(i\), define \(\operatorname{MaxRec}(i,j)\) to be the largest amount that node \(i\) can receive after \(j\) stages and \(\operatorname{MaxSnd}(i,j)\) to be the amount that node \(i\) can send after \(j\) stages. Define \(\operatorname{Current}(i,j)\) to be the current value at node \(i\) right after stage \(j\). Lemma 4: _Let \(g_{1,j},g_{2,j},\cdots,g_{m^{t},j}\) be the positive gaps (see Definition 10) between two consecutive nodes in the linear graph from Node \(1\) to node \(m\) after stage \(j\). Using normalized processes, we always get \(g_{1,j}\geq g_{2,j}\geq\cdots\geq g_{m^{t},j}\)._  
Proof: This follows a simple induction. It is trivial at Stage \(0\) since we only have Node \(1\) with a value of \(n\), and all of the other nodes have a value of zero after Stage \(0\). Assume that this is true after stage \(j\)Consider stage \(j+1\). After stage \(j+1\) in the normalized process, every positive gap after stage \(j+1\) is equal to \(\frac{\delta_{i,j}+\delta_{i+1,j}}{2}\). For two consecutive gaps \(\frac{\delta_{i,j}+\delta_{i+1,j}}{2}\) and \(\frac{\delta_{i+1,j}+\delta_{i+2,j}}{2}\), we have \(\frac{\delta_{i,j}+\delta_{i+1,j}}{2}\geq\frac{\delta_{i+1,j}+\delta_{i+2,j}}{2}\) because \(g_{i,j}\geq g_{i+2,j}\) by the inductive hypothesis. Therefore, it is nondecreasing. Using the normalized stages, each node \(i\) has \(\mathrm{Rec}(i,j)=\mathrm{MaxRec}(i,j)\) and \(\mathrm{Snd}(i,j)=\mathrm{MaxSnd}(i,j)\) for all \(j\). We prove this by contradiction. Assume that \(\mathrm{Rec}(i,j)<\mathrm{MaxRec}(i,j)\) or \(\mathrm{Snd}(i,j)<\mathrm{MaxSnd}(i,j)\) for some \(i,j\). Let \((i,j)\) be the the tuple such that it satisfies the following conditions:  
* Either \(\mathrm{Rec}(i,j)<\mathrm{MaxRec}(i,j)\) or \(\mathrm{Snd}(i,j)<\mathrm{MaxSnd}(i,j)\),
* Integer \(j\) is the least, and \((\mathrm{Rec}(i,j)<\mathrm{MaxRec}(i,j)\) or \(\mathrm{Snd}(i,j)<\mathrm{MaxSnd}(i,j))\). (A) We assume \(\mathrm{Rec}(i,j)<\mathrm{MaxRec}(i,j)\). Let \(P^{*}\) be another process that has \(\mathrm{Rec}^{*}(. )\), \(\mathrm{Current}^{*}(. )\), \(\mathrm{Snd}^{*}(. )\), and it has \(\mathrm{Rec}*(i,j)=\mathrm{MaxRec}(i,j)\). Case 1. \(i=1\). It is trivial that \(\mathrm{Rec}(i,j)=\mathrm{MaxRec}(i,j)=n\) for all \(j\). Therefore, we have a contradiction. Case 2.