The Performance of Multimessage Algebraic Gossip in a Random Geometric Graph

Abstract

Gossip algorithm has been widely regarded as a simple and efficient method to improve quality of service (QoS) in large-scale network which requires rapid information dissemination. In this paper, information dissemination based on algebraic gossip in a random geometric graph (RGG) is considered. The n nodes only have knowledge about their own contents. In every time slot, each node communicates with a neighbor partner chosen randomly. The goal is to disseminate all of the messages rapidly among the nodes. We show that the gain of the convergence time is $\text{O}\left(n^{1/2}\log {\epsilon }^{-1}/{log}^{1/2}n\right)$ with network coding. Simulation results show that these bounds are valid for the random geometric graph and demonstrate that network coding significantly improves the bounds with the number of users increasing.

1. Introduction

With the increased demand for network resources and the expansion of the variety of information resources, information dissemination based on gossip becomes an effective way to improve quality of service (QoS) in large-scale network environment. Gossip algorithm is a simple and efficient algorithm which has good extensibility and robustness to adapt to the large-scale network environment well; it also reduces the redundancy of the retransmission to disseminate information in a wide range of distributed applications. Recently, gossip algorithms have been proposed for many distributed applications, including peer-to-peer (P2P) network, broadcast and multicast [1, 2], adhoc network routing [3], and distributed computation and parameter estimation [4, 5].

Network coding [6] is first proposed by Ahlswede et al. in 2000 to change the traditional store-and-forward routing. Network coding brought many potential advantages like improving network throughput, balancing network load and high bandwidth utilization, and increasing the network robustness and adaptability for multicast network. Chen and Tseng [7] proposed a distributed algorithm with random linear network coding [8], which is developed to effectively detect, locate, and isolate the Byzantine attackers in a wireless ad-hoc network.

In 2006, Boyd et al. boldly proposed a randomized gossip algorithm [9]. They showed that the convergence time in the random geometric graph (RGG) was $\text{O}(r^{-\mathrm{2}}\log n)$ , where r is the transmission radius threshold and n is the number of nodes. Based on the advantage of random linear network coding, Deb et al. [10] suggested an algebraic gossip algorithm that innovatively integrated network coding with a gossip algorithm and proved that the convergence time of the information dissemination improved more quickly than in a randomized gossip algorithm, needing only $\text{O}(n\log n)$ time to disseminate the messages in a completed graph. Subsequently, Mosk-Aoyama and Shah in [11] generalized the results of [10] and obtained the convergence time bound $\text{O}(n\log n)$ in expectation using an algebraic gossip algorithm in an arbitrary graph. Vasudevan and Kudekar [12] developed a uniform strong bound of $\text{O}(n{\hspace{0.17em}\log }^{\mathrm{2}}n)$ with algebraic gossip for an arbitrary graph with high probability. Borokhovich et al. used queuing theory as a novel approach for analyzing algebraic gossip [13]. They obtained an upper bound of $\text{O}(n\mathrm{\Delta })$ rounds for a graph with a maximum degree of Δ for all-to-all communication. An average connectivity degree cluster (ACDC) scheme gossip algorithm to improve the convergence speed and the accuracy of the consensus is proposed in [14]. The proposed algorithm can yield results that are 50% closer to the real average value than the referenced standard gossip and grid cluster gossip algorithms.

However, realistic networks are so complex that traditional topology graphs cannot match them except with the RGG. We analyze the performance of multimessage algebraic gossip in the RGG. We utilize the concept of conductance [15] to analyze the convergence time bounds. The conductance of a graph is a measure of the connectivity of the graph, which determines how fast a random walk on a graph converges to a uniform distribution. Our results show that the gain of the convergence time is $\text{O}({(n}^{1/2}\log {\epsilon }^{-1})/{\log }^{1/2}n)$ with network coding.

The rest of this paper is structured as follows. In Section 2, we describe the model, the algorithm, and the protocols with a few preliminaries. We state our main theoretical results and also provide essential proofs of them in Section 3. In Section 4, simulation results and detailed analysis are given. Section 5 concludes this paper.

2. Preliminaries and Models

In this network model, there are n nodes, and each node has only one message. We assume that the set of messages is $\mathit{M}=\{m_1,m_2,\dots ,m_n\}$ , where node i stores the message in the initial time slot $t=0$ .

2.1. RGG Model

The RGG model ${\mathit{G}}^d(n,r)$ is formulated as follows [16].

• (i)

Place n vertices on the region which are in random uniformly and independently distribution.

(ii)

Connect two vertices $(u,v)$ if and only if the distance between them is less than or equal to a threshold; that is, $d(u,v)\le r$ , where r is a transmission radius threshold. Obviously, the connection probability between the nodes depends on their Euclidean distance.

We use adjacency matrix ${\mathit{A}}_{ij}(t)$ to represent graph structure, where if nodes i and j are in their neighborhood, ${\mathit{A}}_{ij}(t)=1$ , for $i\ne j$ , else ${\mathit{A}}_{ij}(t)=0$ . Moreover, ${\mathit{N}}_i=\{j\in \{\mathrm{1,2},\dots ,n\}:{\mathit{A}}_{ij}(t)\ne 0\}$ represents the set of neighbor nodes of node i, and $d_i=|{\mathit{N}}_i|$ represents the degree of node i, which means the number of neighbor nodes.

2.2. Synchronous Time Model

A time model determines the time of multimessage dissemination. We use the synchronous time model as in [11]. In the gossip algorithms, round is the time unit during which nodes exchange their messages with each other. Assume one round is divided into n consecutive time slots. In each time slot, each node selects one of its neighbor nodes randomly and independently and shares information with it.

2.3. Gossip Algorithm

In time slot t, any node i can select neighbor nodes uniformly, randomly and independently with the probability $p=1/d$ , where d represents a node's degree [13]. In the RGG, the transition probability matrix of the node [17] is

$$\begin{array}{cc}& P_{ij}=\{\begin{array}{cc}\frac{\mathrm{1}}{\mathrm{2}},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}j=i\text{,}\hfill \\ \frac{\mathrm{1}}{\mathrm{2}d},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}j\in {\mathit{N}}_i,\hfill \\ \mathrm{0},\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(1)

Here ${\mathit{N}}_i$ is the set of node i's neighbors. Equation (1) presents the transition probability in the RGG without network coding. When nodej is one neighbor of node i, (1) that ensures this neighbor is selected randomly and uniformly. The transition probability expectation of node j is equal to that of node i when chosen as a transmitted node. Then we can use it to derive the transition probability with network coding in the RGG.

There are three kinds of gossip algorithms—Push, Pull, and Exchange, which are defined as follows, respectively.

• (i)

Push: in this model, a message is transmitted from a transmitting node (the caller) to a receiving node (the called). Thus, the communication process is initiated by the transmitting node.

(ii)

Pull: in this model, a message is transmitted from a transmitting node (the called) to a receiving node (the caller). Thus, the communication process is initiated by the receiving node.

(iii)

Exchange: here, a message is transmitted from a transmitting node (the caller) to a receiving node (the called), and at the same time, the other message is transmitted from a transmitting node (the called) to a receiving node (the caller).

2.4. Gossip Protocol

Here we use the random linear network coding technology as the gossip protocol. Random linear network coding encodes each message before sending it. We take each message as a vector from the finite field ${\mathit{F}}_q$ of size q. So if the message size is m bits, the dimensions of message vector can be represented as $r=\lceil m/{\log }_{2}q\rceil$ . All the initial messages are linearly independent vectors in the finite field ${\mathit{F}}_q$ , and we take ${\mathit{A}}_i(t)$ to represent the matrix of a coding coefficient vector of nodes i in time slot t.

When coding coefficient vector of any node i increases to n, it indicates that node i can recover all the messages and also means that wireless communication process has achieved convergence.

In the rest of this paper, we integrate the exchange algorithm with random linear network coding to analyze the convergence time of multimessage dissemination.

2.5. Communication Criteria

First, consider the local convergence time ${\mathit{T}}_{\text{local}}^{\text{EX},\text{RLC}}(n)=\mathbf{m}\mathbf{i}\mathbf{n}\{t:\dim (\mathit{A}(t))=n,\exists i\in \mathit{V}\}$ , representing the shortest time that there is a node i containing all of the messages in the set M.

Second, consider the global convergence time [18] ${\mathit{T}}_{\text{global}}^{\text{EX},\text{RLC}}(n,\epsilon )=\mathbf{i}\mathbf{n}\mathbf{f}\{t:\mathbf{P}\mathbf{r}({\bigcup }_{i=\mathrm{1}}^n\{\dim (\mathit{A}(t))\ne n\})<\epsilon ,\hspace{0.17em}\exists i\in \mathit{V}\}$ , representing the time point at which all of the nodes receive all of the messages with high probability $\mathrm{1}-\epsilon$ , where $\epsilon >0$ .

3. Main Results

Based on the above model, we analyze the benefit of network coding in multimessage dissemination in the RGG.

Before transmission, each sender and receiver encodes the necessary messages stored in the buffer. At each time slot, each sender i randomly selects the encoded message to send to one of its neighbors j and receives the encoded message from node j at the same time.

Firstly, we use the following definitions similar to [17].

Definition 1.

The “Basic Class” $\mathit{B}(t)$ is the set of matrices satisfying the following properties.

• (i)

If $a_{ij}^i(t)\ne \mathrm{0}$ , then $a_{ij}^j(t)\ne \mathrm{0}$ , for all $a_{ij}^i(t)\in {\mathit{A}}_i(t)$ , $a_{ij}^i(t)\in {\mathit{A}}_i(t)$ ;

(ii)

nonzero submatrices of ${\mathit{A}}_i(t)$ and ${\mathit{A}}_j(t)$ satisfy column full rank.

If the matrices satisfy condition (i) but do not satisfy condition (ii), then the set of them can be defined as the “Virtual Class” denoted by $\tilde{\mathit{V}}(t)$ .

If neither of the conditions (i) or (ii) are satisfied, then the matrices belong to the set defined as the “Residue Class” denoted by $\mathit{R}(t)$ .

Let a node $j\in {\mathit{N}}_i$ . Suppose that $P_{ij}^{\prime }$ represents the transition probability of the nodes i, j that satisfy ${\mathit{A}}_i(t),{\mathit{A}}_j(t)\in \mathit{R}(t)$ and $\overline{P_{ij}}$ represents the transition probability of the nodes i, j that satisfy ${\mathit{A}}_i(t),{\mathit{A}}_j(t)\in \tilde{\mathit{V}}(t)$ . Therefore, the relation between $P_{ij}^{\prime }$ and $\overline{P_{ij}}$ satisfies the following.

Lemma 2.

Consider

$$\begin{array}{cc}& \begin{array}{c}\overline{P_{ij}}\approx \frac{\mathrm{2}}{\left(d_i-\mathrm{2}\right)P_{ij}^{\prime }}\end{array}.\end{array}$$

(2)

Proof of Lemma 2.

According to the definition of the RGG and (1), we can easily derive $\overline{P_{ij}}\approx ({\mathrm{\Delta }}_i(k)/(d_i-{\mathrm{\Delta }}_i(k)))P_{ij}^{\prime }$ , where ${\mathrm{\Delta }}_i(k)$ is the number of “Virtual Class” in the set ${\mathit{N}}_i$ and k is the maximum degree of node i.

Suppose the probability of ${\mathrm{\Delta }}_i(k)=1$ is $p_k$ ; therefore, the probability of ${\mathrm{\Delta }}_i(k)=2$ is $p_k^2$ . The rest may be deduced by analogy; the probability of ${\mathrm{\Delta }}_i(k)=k$ is $p_k^k$ . $p_k$ satisfies the equality ${p_k+\cdots +p}_k^k=1$ ; if k is large enough, then $p_k\approx 1/2$ and

$$\begin{array}{cc}& \mathit{E}\left({\mathrm{\Delta }}_i\left(k\right)\right)=\frac{\mathrm{1}}{\mathrm{2}}+\frac{\mathrm{2}}{{\mathrm{2}}^{\mathrm{2}}}+\cdots +\frac{k}{{\mathrm{2}}^k}\approx \mathrm{2}.\end{array}$$

(3)

Therefore, with the help of expectation of ${\mathrm{\Delta }}_i(k)$ , the transition probability $\overline{P_{ij}}\approx (\mathrm{2}/(d_i-2))P_{ij}^{\prime }$ is obtained.

Theorem 3.

For the RGG, the conductance of the static algebraic gossip algorithm with multimessage dissemination is $\widehat{\mathrm{\Phi }}(p)=O(n^{3/2}/({\log }^{1/2}n))$ .

Proof.

According to the definition of conductance, we can have k-conductance for any $k\in [1,n]$ as follows:

$$\begin{array}{l}{\mathrm{\Phi }}_k\left(p\right)=\underset{\mathit{S}\subset \mathit{V},\mathbf{0}<\pi \left(\mathit{S}\right)<k/n}{\mathbf{m}\mathbf{i}\mathbf{n}}\frac{\mathit{Q}\left(\mathit{S},\bar{\mathit{S}}\right)}{\mathit{\pi }\left(\mathit{S}\right)}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=\underset{\mathit{S}\subset \mathit{V},\mathbf{0}<\pi \left(\mathit{S}\right)<k/n}{\mathbf{m}\mathbf{i}\mathbf{n}}\frac{{\sum }_{x\in \mathit{S},y\in \bar{\mathit{S}}}\mathit{\pi }\left(x\right)P\left(x,y\right)}{\mathit{\pi }\left(\mathit{S}\right)}.\end{array}$$

(4)

Here $\mathit{\pi }(\mathit{S})$ is the probability density of S under the stationary distribution π and $\mathit{Q}(\mathit{S},\bar{\mathit{S}})$ is the sum of $\mathit{Q}(v,u)$ over all $(v,u)\in \mathit{S}\times \bar{\mathit{S}}$ .

According to the cut size between S and $\bar{\mathit{S}}{\mathbf{C}\mathbf{u}\mathbf{t}}_{\mathrm{\Phi }}(\mathit{S},\bar{\mathit{S}})=3n^2{r}^3$ in [19], (4) can be converted as follows:

$$\begin{array}{l}{\mathrm{\Phi }}_k\left(p\right)=\hspace{0.17em}\underset{\mathit{S}\mathbf{\subset }\mathit{V}\mathbf{,}\mathbf{0}<\pi \left(\mathit{S}\right)<k/n}{\mathbf{m}\mathbf{i}\mathbf{n}}\text{O}\left(\frac{n}{k}\right){\sum }_{x\in \mathit{S},y\in \bar{\mathit{S}}}\text{O}\left(\frac{\mathrm{1}}{n}\right)\text{O}\left(\frac{\mathrm{1}}{n{r}^{\mathrm{2}}}\right)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=\hspace{0.17em}\underset{\mathit{S}\mathbf{\subset }\mathit{V}\mathbf{,}\mathbf{0}<\pi \left(\mathit{S}\right)<k/n}{\mathbf{m}\mathbf{i}\mathbf{n}}\text{O}\left(\frac{\mathrm{1}}{kn{r}^{\mathrm{2}}}\right){\mathit{C}\mathit{u}\mathit{t}}_{\mathrm{\Phi }}\left(\mathit{S}\mathbf{,}\mathbf{\hspace{0.17em}}\bar{\mathit{S}}\right)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=\hspace{0.17em}\text{O}\left(\frac{nr}{k}\right).\end{array}$$

(5)

From [20], we can obtain the wireless transmission radius in the RGG of two dimensions as $r(n)=\text{O}(\sqrt{\log n/n})$ . Then, from (5) we can obtain k-conductance as follows:

$$\begin{array}{cc}& {\mathrm{\Phi }}_k\left(p\right)=\text{O}\left(\sqrt{\frac{n\log n}{k}}\right).\end{array}$$

(6)

Therefore, the conductance is

$$\begin{array}{cc}& \widehat{\mathrm{\Phi }}\left(p\right)=\sum _{k=\mathrm{1}}^{n-\mathrm{1}}\frac{k}{{\mathrm{\Phi }}_k\left(p\right)}=\sum _{k=\mathrm{1}}^{n-\mathrm{1}}\frac{k^{\mathrm{2}}}{\sqrt{n\log n}}=\text{O}\left(\frac{n^{\mathrm{3}/\mathrm{2}}}{{\log }^{\mathrm{1}/\mathrm{2}}n}\right).\end{array}$$

(7)

Theorem 4.

For any $\epsilon >0$ , the convergence time of the static algebraic gossip algorithm with multimessage dissemination is

$$\begin{array}{cc}& {\mathit{T}}_{global}^{EX,RLC}\left(n,\epsilon \right)=O\left(\frac{n^{\mathrm{3}/\mathrm{2}}\log {\epsilon }^{-\mathrm{1}}-n^{\mathrm{1}/\mathrm{2}}\log {\epsilon }^{-\mathrm{1}}}{{\log }^{\mathrm{1}/\mathrm{2}}n}\right).\end{array}$$

(8)

Proof.

Assume that in the initial time slot $t=0$ , $\mathrm{rank}({\mathit{A}}_i(t))=1$ , for all $i\in \mathbf{V}$ , where V is the set of all of the nodes, $t_k=\mathbf{i}\mathbf{n}\mathbf{f}\{t:\mathit{C}(t)\ge k\}$ and $\mathit{C}(t)$ is the largest cardinality in $\mathit{B}(t)$ . Our goal is to make $\mathrm{rank}({\mathit{A}}_i(t_n))=n$ , for all $i\in \mathit{V}$ .

According to the definition of $t_k$ , we divide the total convergence time into k time periods as follows:

$$\begin{array}{cc}& \left[t_{\mathrm{1}},t_{\mathrm{2}}\right),\left[t_{\mathrm{2}},t_{\mathrm{3}}\right),\dots ,\left[t_k,t_{k+\mathrm{1}}\right).\end{array}$$

(9)

Let $I_{ij}$ be a characteristic function which takes the value of one if node i transmits message to node j; otherwise it is zero. When node i exchanges messages with node j, we can obtain the inequality as follows:

$$\begin{array}{cc}& \mathit{E}\left(I_{ij}\right)+\mathit{E}\left(I_{ji}\right)\ge P_{ij}^{\prime }+\overline{P_{ij}}.\end{array}$$

(10)

Now consider the general time slot $t\in [t_k,t_{k+1})$ ; the accumulative rank $\mathrm{\Delta }(t)={\sum }_{i=1}^n(\mathrm{rank}({\mathit{A}}_i(t))-1)$ should satisfy the following inequality:

$$\begin{array}{cc}& \mathrm{\Delta }\left(t+\mathrm{1}\right)-\mathrm{\Delta }\left(t\right)\ge \sum _{i\in V}\hspace{0.17em}\sum _{j\in V,j\ne i}\left(I_{ij}+I_{ji}\right).\end{array}$$

(11)

By taking expectations on both sides of the above inequality and using (11), we have

$$\begin{array}{l}\mathit{E}\left(\mathrm{\Delta }\left(t+\mathrm{1}\right)-\mathrm{\Delta }\left(t\right)\right)\ge \sum _{\begin{array}{l}i,j\in \mathit{V},j\ne i\\ {\mathit{A}}_i\left(t\right),{\mathit{A}}_j\left(t\right)\in \mathit{R}\left(t\right)\end{array}}{P}_{ij}^{\prime }+\sum _{\begin{array}{l}i,j\in \mathit{V},j\ne i\\ {\mathit{A}}_i\left(t\right),{\mathit{A}}_j\left(t\right)\in \tilde{\mathit{V}}\left(t\right)\end{array}}^{}\overline{P_{ij}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\sum _{\begin{array}{l}i,j\in \mathit{V},j\ne i\\ {\mathit{A}}_i\left(t\right),{\mathit{A}}_j\left(t\right)\in \mathit{R}\left(t\right)\end{array}}{P}_{ij}^{\prime }+\sum _{\begin{array}{l}i,j\in \mathit{V},j\ne i\\ {\mathit{A}}_i\left(t\right),{\mathit{A}}_j\left(t\right)\in \mathit{R}\left(t\right)\end{array}}^{}\frac{\mathrm{2}{P}_{ij}^{\prime }}{d_i-\mathrm{2}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\ge \sum _{\begin{array}{l}i,j\in \mathit{V},j\ne i\\ {\mathit{A}}_i\left(t\right),{\mathit{A}}_j\left(t\right)\in \mathit{R}\left(t\right)\end{array}}{P}_{ij}^{\prime }\left(\mathrm{1}+\frac{\mathrm{2}}{k-\mathrm{2}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\ge \left(\mathrm{1}+\frac{\mathrm{2}}{k-\mathrm{2}}\right)n{\mathrm{\Phi }}_k\left(p\right).\end{array}$$

(12)

For the convenience of our analysis, we use $g(t)=\mathrm{\Delta }(t+1)-\mathrm{\Delta }(t)-(1+\mathrm{2}/(k-2))n{\mathrm{\Phi }}_k(p)$ . Therefore, we quote the definition of $Z_k(t)$ in [20] $Z_k(t)={\sum }_{i=t_k}^{t-1}g(i){\mathit{1}}_{\{\mathit{i}<t_{k+1}\}}$ ; then we can easily get $Z_k(t_k)=0$ .

At the same time, we can conclude that

$$\begin{array}{l}\mathit{E}\left(Z_k\left(t+\mathrm{1}\right)\hspace{0.17em}|\hspace{0.17em}{Z}_k\left(t\right)\right)\\ \hspace{1em}\hspace{1em}=\mathit{E}\left(\sum _{i=t_k}^{t}g\left(i\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\hspace{0.17em}|\hspace{0.17em}\sum _{i=t_k}^{t-\mathrm{1}}g\left(i\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\right)\\ \hspace{1em}\hspace{1em}=\mathit{E}\left(\sum _{i=t_k}^{t-\mathrm{1}}g\left(i\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\hspace{0.17em}|\hspace{0.17em}\sum _{i=t_k}^{t-\mathrm{1}}g\left(i\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\mathit{E}\left(g\left(t\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\hspace{0.17em}|\hspace{0.17em}\sum _{i=t_k}^{t-\mathrm{1}}g\left(i\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\right)\\ \hspace{1em}\hspace{1em}\mathbf{=}{Z}_k\left(t\right)+\mathit{E}\left(g\left(t\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\hspace{0.17em}|\hspace{0.17em}\sum _{i=t_k}^{t-\mathrm{1}}g\left(i\right){\mathbf{1}}_{\left\{\mathit{i}<t_{k+\mathrm{1}}\right\}}\right)\\ \hspace{1em}\hspace{1em}\mathbf{\ge }{Z}_k\left(t\right).\end{array}$$

(13)

Equation (13) showed that $Z_k(t)$ is submartingale. Moreover, according to the property of submartingale, $\mathit{E}(Z_k(t+1))\ge \mathit{E}(Z_k(t+1))=0$ is obtained.

We unfold the above inequality to get the result as

$$\begin{array}{l}\mathit{E}\left(\sum _{i=t_k}^{t_{k+\mathrm{1}}-\mathrm{1}}\left(\mathrm{\Delta }\left(i+\mathrm{1}\right)-\mathrm{\Delta }\left(i\right)\right)\right)\\ \hspace{1em}\hspace{1em}\mathbf{\ge }\mathit{E}\left(\sum _{i=t_k}^{t_{k+\mathrm{1}}-\mathrm{1}}\left(\mathrm{1}+\frac{\mathrm{2}}{k-\mathrm{2}}\right)n{\mathrm{\Phi }}_k\left(p\right)\right),\\ \mathit{E}\left(\mathrm{\Delta }\left(t_{k+\mathrm{1}}\right)-\mathrm{\Delta }\left(t_k\right)\right)\\ \hspace{1em}\hspace{1em}\mathbf{\ge }\left(\frac{\mathrm{1}+\mathrm{2}}{k-\mathrm{2}}\right)n{\mathrm{\Phi }}_k\left(p\right)\mathit{E}\left(t_{k+\mathrm{1}}-t_k\right).\end{array}$$

(14)

According to (14) and Theorem 5 in [11], (12) can be derived as follows

$$\begin{array}{l}\mathit{E}\left(t_n\right)\le \frac{k-\mathrm{2}}{k}\sum _{k=\mathrm{2}}^{n-\mathrm{1}}\frac{\mathit{E}\left(\mathrm{\Delta }\left(t+\mathrm{1}\right)-\mathrm{\Delta }\left(t\right)\right)}{n{\mathrm{\Phi }}_k\left(\mathit{p}\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\frac{\mathit{E}\left(\mathrm{\Delta }\left(t+\mathrm{1}\right)-\mathrm{\Delta }\left(t\right)\right)}{n{\mathrm{\Phi }}_k\left(\mathit{p}\right)}\hspace{0.17em}|\hspace{0.17em}{k}_{=\mathrm{1}}\\ \hspace{1em}\hspace{1em}\le \sum _{k=\mathrm{1}}^{n-\mathrm{1}}\frac{\mathrm{2}k}{n{\mathrm{\Phi }}_k\left(\mathit{p}\right)}-\sum _{k=\mathrm{2}}^{n-\mathrm{1}}\frac{\mathrm{2}}{n{\mathrm{\Phi }}_k\left(\mathit{p}\right)}\\ \hspace{1em}\hspace{1em}=\frac{\mathrm{2}}{n}\widehat{\mathrm{\Phi }}\left(\mathbf{p}\right)-\frac{\mathrm{4}}{n}\sum _{k=\mathrm{2}}^{n-\mathrm{1}}\frac{\mathrm{1}}{n{\mathrm{\Phi }}_k\left(\mathit{p}\right)}.\end{array}$$

(15)

By Markov's inequality, (15) implies that

$$\begin{array}{cc}& \mathit{P}\left(t_n>\frac{\log {\epsilon }^{-\mathrm{1}}}{n}\left(\widehat{\mathrm{\Phi }}\left(\mathbf{p}\right)-\sum _{k=\mathrm{2}}^{n-\mathrm{1}}\frac{\mathrm{1}}{{\mathrm{\Phi }}_k\left(\mathit{p}\right)}\right)\right)<\epsilon .\end{array}$$

(16)

Therefore we can conclude that the convergence time of the static algebraic gossip network model is expressed as

$$\begin{array}{cc}& {\mathit{T}}_{\text{global}}^{\text{EX},\text{RLC}}\left(n,\epsilon \right)=\text{O}\left(\frac{\widehat{\mathrm{\Phi }}\left(\mathbf{p}\right)\mathbf{-}{\sum }_{k=\mathrm{2}}^{n-\mathrm{1}}\mathrm{1}/\left({\mathrm{\Phi }}_k\left(\mathit{p}\right)\right)}{n}\log {\epsilon }^{-\mathrm{1}}\right).\end{array}$$

(17)

According to (6) and (7), we can conclude that the convergence time of the mobile algebraic gossip model is

$$\begin{array}{cc}& {\mathit{T}}_{\text{global}}^{\text{EX},\text{RLC}}\left(n,\epsilon \right)=\text{O}\left(\frac{n^{\mathrm{3}/\mathrm{2}}\log {\epsilon }^{-\mathrm{1}}-n^{\mathrm{1}/\mathrm{2}}\log {\epsilon }^{-\mathrm{1}}}{{\log }^{\mathrm{1}/\mathrm{2}}n}\right).\end{array}$$

(18)

Because the conductance is the same as in (6), we conclude that the convergence time of the static gossip algorithm is as follows.

Corollary 5.

For any $\epsilon >0$ , the convergence time of the static gossip network model is

$$\begin{array}{cc}& {\mathit{T}}_{global}^{EX,RLC}\left(n,\epsilon \right)=\mathrm{\hspace{0.17em}\hspace{0.17em}}O\left(\frac{n^{\mathrm{3}/\mathrm{2}}\log {\epsilon }^{-\mathrm{1}}}{{\log }^{\mathrm{1}/\mathrm{2}}n}\right).\end{array}$$

(19)

The results are summarized in Tables 1 and 2 for clarity. From these tables, we observe that network coding directly affects the convergence time. Next, we will check and verify these results by simulation.

Table 1

Comparison of algorithms in the RGG.

	k-conductance	Conductance	Convergence time
Static gossip	$\text{O}\left(\sqrt{\frac{n\log n}{k}}\right)$	$\text{O}\left(\frac{n^{5/2}}{{\log }^{1/2}n}\right)$	$\text{O}\left(\frac{n^{3/2}}{{\log }^{1/2}n}\right)$
Static algebraic gossip	$\text{O}\left(\sqrt{\frac{n\log n}{k}}\right)$	$\text{O}\left(\frac{n^{5/2}}{{\log }^{1/2}n}\right)$	$\text{O}\left(\frac{n^{3/2}\log {\epsilon }^{-1}-n^{1/2}\log {\epsilon }^{-1}}{{\log }^{1/2}n}\right)$

Table 2

Gossip in different graph models.

Graph	Complete	Star	Ring	Bounded degree	RGG
Convergence time	$\text{O}\left(n\log n\right)$	$\text{O}\left(n\log n\right)$	$\text{O}\left(n\right)$	$\text{O}\left(n\right)$	$\text{O}\left(\frac{n^{3/2}\log {\epsilon }^{-1}-n^{1/2}\log {\epsilon }^{-1}}{{\log }^{1/2}n}\right)$

4. Simulation

In this section, simulation results are presented to support our theoretical analysis. In our RGG simulation, it is assumed that the maximal communication range for each node is set to $\text{O}(\sqrt{\log n/n})$ . All the nodes do not perform as the message relay any more, because they are outside of the communication radius. The simulation network is implemented in a fully distributed way, which guarantees that nodes have no knowledge of the other's state (e.g., location, caller/called state, etc.). Therefore, both successful and unsuccessful communication attempt are added to the convergence time.

The simulation parameters are set as follows:

• (i)

simulation software: MATLAB R2010b,

(ii)

simulation area: unit square,

(iii)

number of nodes: 100–200 with step 10,

(iv)

maximum number of rounds for each case: 2000,

(v)

runs for each case: 100,

(vi)

time unit: round number.

Here, the meanings of the abbreviations are set as follows:

• (i)

SAG: static algebraic gossip,

(ii)

SG: static gossip,

(iii)

GCT: global convergence time, and its time unit is a round number,

(iv)

LCT: local convergence time, and its time unit is a round number,

(v)

W.H.P: with high probability.

To analyze the performance of the static algebraic gossip algorithm, we built, simulator to investigate the relation between convergence time and other typical parameters. The simulation results are as follows.

Firstly, we analyze the relation between the global convergence time and W.H.P $1-\epsilon$ . From Figure 1, it can be observed that the global convergence time increases as the parameter ε decreases. Moreover, GCT for each algorithm rapidly grows as W.H.P $1-\epsilon$ increases from 0.1 to 1. Obviously, when W.H.P $1-\epsilon$ is less than or equal to 0.7, the gap of the global convergence time between two algorithms in Figure 1 becomes smaller as W.H.P $1-\epsilon$ increases, which proves that network coding has great advantages for the convergence time in this condition. However, when W.H.P $1-\epsilon$ is greater than or equal to 0.7, the gap maintains relatively stable, meaning that network coding has little influence on the convergence time in this condition.

Figure 1

The relation between GCT and W.H.P $1-\epsilon$ .

Thus, we can choose an appropriate value of $\epsilon =0.1$ for the convenience and the precision of the next simulations.

Secondly, we analyze the relation between the global convergence time, the local convergence time, and the number of nodes in Figures 2 and 3.

Figure 2

The relation between GCT and the number of nodes.

Figure 3

The relation between LCT and the number of nodes.

As shown in Figures 2 and 3, both the global convergence time and local convergence time go up with the increasing number of nodes. As the number of nodes increases, the global convergence time and local convergence time of static algebraic gossip algorithm are less than those of static gossip algorithm. This phenomenon results from the network coding, which effectively and obviously reduces the GCT and LCT when the number of nodes becomes larger. It can be observed from Figure 2 and Figure 3 that network coding has a relatively larger benefit on the local convergence time than the global convergence time.

Finally, we can conclude some relations from the figures. In the beginning periods of communication, network coding significantly lowers the retransmission probability. It can explain why the gap is relatively larger in the initial phase in Figure 1 and why network coding has a relatively larger impact on the local convergence time than the global convergence time in Figures 2 and 3. However, in the subsequent periods of communication, new messages are increasingly difficult to transmit, so network coding has less help to improve the performance. The constant gap in the later phase shown in Figure 1 and the differences between the global convergence time and local convergence time in Figures 2 and 3, respectively, can illustrate network coding has less help to improve the performance.

5. Conclusion and Future Work

In this paper, we studied the performance of multimessage dissemination based on the algebraic gossip algorithm in the RGG. We considered the network with n nodes which only have knowledge about their own contents. In every time slot, each node communicates with a randomly chosen neighbor partner by the exchange algorithm. Our goal is to disseminate all of the messages rapidly among the nodes. We utilized the concept of conductance to analyze the convergence time bounds. The results showed that the bounds are significantly improved from $\text{O}(n^{3/2}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\log \epsilon }^{-1}/{\log }^{1/2}n)$ to $\text{O}(n^{3/2}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\log \epsilon }^{-1}-n^{1/2}{\log \epsilon }^{-1}/{\log }^{1/2}n)$ . Next, through the simulations, we verified that these bounds are valid for the random geometric graph and network coding significantly improves the convergence time bounds of multimessage dissemination in the RGG.

However, there are still a number of open questions that require further research and improvement. One is to find a quantitative description of the local convergence time in a specific network environment and compare it to the global convergence time. There are still no related literatures about local convergence time quantitatively expressed so far. Compared to global convergence time, local convergence time is more susceptible to external factors. The bound of the local convergence time is not easy as $1/n$ of the bound of the global convergence time. Once the external factors change, the impact on local convergence time is relatively large. Comparing and analyzing the simulation of local convergence time and global convergence time in different topologies to conclude some related rules may be a feasible step. The other important direction is to research the influence of nodes' mobility. Due to the static network environment, the connectivity between nodes is fixed. That may lead to the problem where some neighbors of a node have very low transition probabilities, resulting in a sharp increase in the propagation times. Nodes' mobility could bring a lot of potential opportunities, like improving the network throughput, increasing network coverage and so on. There are more and more researches about nodes' mobility to solve the problem of information dissemination. Therefore, we will analyze the case with nodes' mobility in future work. The start point is if nodes' mobility can help change the connectivity between nodes over time to impact transition probability.