# Convergence of Gossip Algorithms for Consensus in Wireless Sensor Networks with Intermittent Links and Mobile Nodes

Authors: Shaochuan Wu; Jiayan Zhang; Yuguan Hou; Xu Bai
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We study the convergence of pairwise gossip algorithms
and broadcast gossip algorithms for consensus with
intermittent links and mobile nodes. By nonnegative matrix
theory and ergodicity coefficient theory, we prove gossip algorithms
surely converge as long as the graph is partitionally
weakly connected which, in comparison with existing analysis, is
the weakest condition and can be satisfied for most networks.
In addition we characterize the supremum for the mean squared
error of convergence as a function associated with the initial states
and the number of nodes. Furthermore, on the condition that the
graph is partitionally strongly connected, the rate of convergence
is proved to be exponential and governed by the second largest
eigenvalue of expected coefficient matrix. For partitionally strongly
connected digraphs, simulation results illustrate that gossip
algorithms actually converge, and broadcast gossip algorithms
can converge faster than pairwise gossip algorithms at the cost
of larger error of convergence.


---

## Body

## 1. Introduction

As a prevalent research topic in wireless sensor networks, distributed consensus can be widely used for distributed synchronization [1], distributed load balancing [2], distributed data fusion [3], and distributed optimization [4–6]. Gossip algorithm is one of powerful competitors for this kind of application because it waives traditional end-to-end routing methods by random walking data dissemination, which can remarkably improve robustness and reduce protocol overheads. In addition, since gossip algorithms combine and compress data at each iteration, the amount of data transmitted is reduced which in turn prolongs battery life. Nowadays, pairwise gossip algorithms [7] and broadcast gossip algorithms [8–10] are two main branches of gossip algorithms. For pairwise gossip algorithms, one node exchanges state values with one of its randomly chosen neighbors at each iteration. This method cannot efficiently cope with directed links and utilize the broadcasting nature of wireless media. For this reason, some broadcast gossip algorithms were proposed recently. Most analysis is based on some strong assumptions that networks are static and links are ideal without any interference and collision. It is clear that these assumptions are too strict to be satisfied in real networks. In this paper, we study the convergence of gossip algorithms with intermittent links and mobile nodes. If the network is partitionally weakly connected, we prove that these algorithms converge to consensus. Our analysis combines tools and techniques from nonnegative matrix theory and ergodicity coefficient theory. Along this line, we derive a supremum on the error of convergence, and we derive that the expected rate of convergence is exponential if the network is partitionally strongly connected.Many literatures begin to analyze the performance of gossip algorithms with intermittent links or movement. In [11], authors study convergence rate of gossip algorithms with undirected topology. With the requirement that each node sends its current value to each neighbor at each iteration, this analysis indeed focuses on a type of synchronous gossip algorithms. The same assumption can also be found in [3]. Literature [12] studies the average consensus with random topologies, where the topologies are influenced by intermittent links. This analysis is based on assumption that the topology is undirected. In addition, the influence of movement is not considered in this literature. Ergodicity is first introduced to study the necessary and sufficient conditions for expected consensus in [13]. For this analysis, synchronous time model and independent identical distribution random graphs are two basic assumptions. In particular, the latter assumption requires random graphs to be mutually independent over time, which is difficult to be satisfied because the location of each node is strongly related with its previous location between iterations. Our research in this paper is strongly inspired by ergodicity coefficient theory as introduced in this literature. In [14], based on their previous algorithms, authors study the consensus of broadcast gossip algorithms with probabilistic broadcast. In this paper, the graph is supposed to be static and the reception probability for each node is inversely proportional with a power of the distance between the broadcasting node and itself. Although this assumption is simple and cannot take movement, packet collisions, shadow effect, and multipath channel into account, it is the first research to analyze convergence of broadcast gossip algorithms with dynamic topologies. In [15], authors study the average consensus problems in networks of agents with fixed and switching topology, and time-delays. They reveal that the average consensus problem can be expectedly solved if the graph is strongly connected and balanced. Although balanced graphs are too ideal to be satisfied in mobile networks, they illustrate the possibility that average consensus can be solved in mobile networks. Average consensus with random links is studied in [16], where all matrices are supposed to be i.i.d and the topology needs certain special structure so that the second largest eigenvalue of mean Laplacian satisfies certain special properties. In [17], two related broadcast gossip algorithms are studied if they are affected by interference. The analysis focuses on large Abelian Cayley networks and no movement is considered. A similar research can also be found in [18].Although above literatures begin to analyze the performance of gossip algorithms with intermittent links or movement, some special assumptions are still needed. Conditions are such as synchronization [11, 13], undirected graph [11, 12, 17, 18], nodes activated by i.i.d. [14, 16, 19, 20], and special movement model [21]. All these assumptions restrict the application of gossip algorithms in real networks.In addition, almost all of the above analysis focuses on the asymptotic behavior of gossip algorithms by mathematical expectation, which needs certain special assumptions such as synchronous time model or specific structure of graphs. In particular, some analyses cannot derive a specific upper bound for the error of convergence but an upper bound in expectation, which generally cannot predict the error of convergence for each specific realization. In this paper, we will directly analyze the convergence of infinite product of matrices instead of its expected behavior. Therefore, our method can surely guarantee convergence without any special assumption. As our statement in Section7, the rate of convergence may be slowed to an arbitrary degree. Therefore, we will analyze the expected rate of convergence, which is the only part in which expectation is utilized.The contributions of this paper are as follows. In this paper, the convergence of gossip algorithms for wireless sensor networks with dynamic topologies is given. We introduce pairwise gossip algorithms and broadcast gossip algorithms under dynamic topologies, including intermittent links and mobile nodes in Section2. In Section 3 we propose an ordinary time model that waives the i.i.d. assumption for each node’s clock. In addition, we define the partitionally weak connection and partitionally strong connection as the elementary assumption for subsequent discussion on convergence and the rate of convergence, respectively. All of the analysis is based on an assumption that the digraph is partitionally connected, which is the weakest assumption among all previous research and easily to be satisfied in real networks. We recall properties of ergodicity coefficient theory in Section 4. We then prove that gossip algorithms can converge and derive the supremum of error of convergence as long as the network is partitionally weakly connected in Sections 5 and 6, respectively. In Section 7, we determine that the expected rate of convergence is exponential with the assumption that the network is partitionally strongly connected. Simulation results, reported in Section 8, demonstrate that gossip algorithms actually converge as long as the network is partitionally strongly connected. We conclude in Section 9.


## 2. Gossip Algorithms with Intermittent Links and Mobile Nodes

### 2.1. Pairwise Gossip Algorithm

The pairwise gossip algorithm (PGA) [7] can be formulated as the following iterative algorithm. When a node k is randomly activated at time t, it will randomly choose a node j from its neighbors. Then these two nodes will exchange and update their state values as xk(t+1)=xj(t+1)=0.5xk(t)+0.5xj(t). All the other nodes will keep their state values unchanged. Therefore, we can formulate this algorithm as x(t+1)=Wk(t)x(t), where the subscript k of Wk(t) denotes that the active node is node k at time t. One can verify
(1)Wk(t)=I+0.5(ek-ej)(ejT-ekT),
where I is the identity matrix and ei is the ith canonical basis vector. For convenience, we omit the variable t of Wk(t). Obviously, Wk is doubly stochastic so pairwise gossip algorithms can preserve the average of initial state values at each iteration, and all nodes will not leave the convergent state if they can converge.If we take link failure or node movement into account, there are several implementation details that have to be considered. Firstly, when a nodek chooses its neighboring node j to exchange state values, it may fail to transmit its state value to node j. Therefore, j cannot realize that it has been chosen by node k to participate in state values exchange and update. In this case, state values of all nodes will stay unchanged, which is equivalent to that the matrix Wk is the identity matrix I and will not influence the convergent results but slow the rate of convergence. Secondly, if node k successfully transfers its state value to node j, there are two choices for node j to update and transmit its state value to node k. (1) Node j firstly updates its state value by convex combination xj(t+1)=0.5xj(t)+0.5xk(t) and transmits the combination result xj(t+1) to node k, and then node k updates its state value as xk(t+1)=xj(t+1). We name this method as BPGA-LF (biased PGA with link failure). (2) Node j does not update its state value xj(t+1) until it successfully transmits its current state value xj(t) to node k, and then these two nodes simultaneously and respectively update their state values as xk(t+1)=xj(t+1)=0.5xj(t)+0.5xk(t). We call this method UPGA-LF (unbiased PGA with link failure). For BPGA-LF, if the backward link lk,j fails, all-one column vector 1 is not the left 1-eigenvector of matrix Wk so the average of initial state values cannot be preserved. It is the reason that we call it biased PGA. For UPGA-LF, link failure will not influence the sum of initial state values at each iteration. Therefore, if UPGA-LF converges, it must converge to the average consensus. Comparing BPGA-LF and UPGA-LF, we can intuitively conclude that BPGA-LF converges faster than UPGA-LF because node j can update its state value as long as the forward link lj,k works. But, for UPGA-LF, only the forward link and backward link between nodes k and j are available; the update will be executed. In addition, UPGA-LF can preserve the average of initial state values at the cost of twice the size of memory that should be used, in comparison with BPGA-LF, to maintain two temporary state values xj(t) and xk(t) for each node.


### 2.2. Broadcast Gossip Algorithm

The broadcast gossip algorithm (BGA) [8] can be formulated as the following iterative algorithm. When a node is randomly activated, it will transmit its state value by broadcasting. If we take link failure or movement into account, the topology is time-varying and some nodes within the communication radius of this active node will not receive this broadcasting state value. In this case, the state values of all nodes will update as follows.(1)
Transmitter state update, nodek:
(2)xk(t+1)=xk(t).(2)
Receiver state update, nodej∈Nk-(t):
(3)xj(t+1)=γxj(t)+(1-γ)xk(t).(3)
Idle node,l∉k∪Nk-(t):
(4)xl(t+1)=xl(t).Therefore, we can also formulate the broadcast gossip algorithms asx(t+1)=Wk(t)x(t).For convenience, we ignore the variablet of Wk(t) in the following discussion. In this case, Wk of broadcast gossip algorithm can be written as
(5)Wk=I+(1-γ)∑j∈Nk-(t)(ejekT-ejejT)=I-(1-γ)Lk.Obviously, the matrixWk satisfies Wk1=1 but 1TWk=1T+δk-(1-γ)ekT-∑j∈Nk-‍(1-γ)ejT≠1T. Therefore matrix Wk is row stochastic matrix and this algorithm can guarantee that the network will not leave consensus state if it can converge. However, it cannot preserve the sum of all state values at each iteration. For short, we will use BGA-LF to denote broadcast gossip algorithms with link failure.From above introduction, one common property of these algorithms is that their coefficient matricesWk are all row stochastic, which is the basis for the subsequent analysis.


## 2.1. Pairwise Gossip Algorithm

The pairwise gossip algorithm (PGA) [7] can be formulated as the following iterative algorithm. When a node k is randomly activated at time t, it will randomly choose a node j from its neighbors. Then these two nodes will exchange and update their state values as xk(t+1)=xj(t+1)=0.5xk(t)+0.5xj(t). All the other nodes will keep their state values unchanged. Therefore, we can formulate this algorithm as x(t+1)=Wk(t)x(t), where the subscript k of Wk(t) denotes that the active node is node k at time t. One can verify
(1)Wk(t)=I+0.5(ek-ej)(ejT-ekT),
where I is the identity matrix and ei is the ith canonical basis vector. For convenience, we omit the variable t of Wk(t). Obviously, Wk is doubly stochastic so pairwise gossip algorithms can preserve the average of initial state values at each iteration, and all nodes will not leave the convergent state if they can converge.If we take link failure or node movement into account, there are several implementation details that have to be considered. Firstly, when a nodek chooses its neighboring node j to exchange state values, it may fail to transmit its state value to node j. Therefore, j cannot realize that it has been chosen by node k to participate in state values exchange and update. In this case, state values of all nodes will stay unchanged, which is equivalent to that the matrix Wk is the identity matrix I and will not influence the convergent results but slow the rate of convergence. Secondly, if node k successfully transfers its state value to node j, there are two choices for node j to update and transmit its state value to node k. (1) Node j firstly updates its state value by convex combination xj(t+1)=0.5xj(t)+0.5xk(t) and transmits the combination result xj(t+1) to node k, and then node k updates its state value as xk(t+1)=xj(t+1). We name this method as BPGA-LF (biased PGA with link failure). (2) Node j does not update its state value xj(t+1) until it successfully transmits its current state value xj(t) to node k, and then these two nodes simultaneously and respectively update their state values as xk(t+1)=xj(t+1)=0.5xj(t)+0.5xk(t). We call this method UPGA-LF (unbiased PGA with link failure). For BPGA-LF, if the backward link lk,j fails, all-one column vector 1 is not the left 1-eigenvector of matrix Wk so the average of initial state values cannot be preserved. It is the reason that we call it biased PGA. For UPGA-LF, link failure will not influence the sum of initial state values at each iteration. Therefore, if UPGA-LF converges, it must converge to the average consensus. Comparing BPGA-LF and UPGA-LF, we can intuitively conclude that BPGA-LF converges faster than UPGA-LF because node j can update its state value as long as the forward link lj,k works. But, for UPGA-LF, only the forward link and backward link between nodes k and j are available; the update will be executed. In addition, UPGA-LF can preserve the average of initial state values at the cost of twice the size of memory that should be used, in comparison with BPGA-LF, to maintain two temporary state values xj(t) and xk(t) for each node.


## 2.2. Broadcast Gossip Algorithm

The broadcast gossip algorithm (BGA) [8] can be formulated as the following iterative algorithm. When a node is randomly activated, it will transmit its state value by broadcasting. If we take link failure or movement into account, the topology is time-varying and some nodes within the communication radius of this active node will not receive this broadcasting state value. In this case, the state values of all nodes will update as follows.(1)
Transmitter state update, nodek:
(2)xk(t+1)=xk(t).(2)
Receiver state update, nodej∈Nk-(t):
(3)xj(t+1)=γxj(t)+(1-γ)xk(t).(3)
Idle node,l∉k∪Nk-(t):
(4)xl(t+1)=xl(t).Therefore, we can also formulate the broadcast gossip algorithms asx(t+1)=Wk(t)x(t).For convenience, we ignore the variablet of Wk(t) in the following discussion. In this case, Wk of broadcast gossip algorithm can be written as
(5)Wk=I+(1-γ)∑j∈Nk-(t)(ejekT-ejejT)=I-(1-γ)Lk.Obviously, the matrixWk satisfies Wk1=1 but 1TWk=1T+δk-(1-γ)ekT-∑j∈Nk-‍(1-γ)ejT≠1T. Therefore matrix Wk is row stochastic matrix and this algorithm can guarantee that the network will not leave consensus state if it can converge. However, it cannot preserve the sum of all state values at each iteration. For short, we will use BGA-LF to denote broadcast gossip algorithms with link failure.From above introduction, one common property of these algorithms is that their coefficient matricesWk are all row stochastic, which is the basis for the subsequent analysis.


## 3. Time Model and Network Model

### 3.1. Asynchronous Time Model

Similar to [8], this paper also adopts the asynchronous time model. Each node runs a clock which ticks according to an independent random process. When node k’s clock ticks it initiates a gossip update. Unlike time model in [8], it is not necessary for each node to have i.i.d. clock in this paper, which relieves the assumption from previous research. This kind of asynchronous time model often occurs in wireless sensor networks, where each node has different capabilities to deal with packets, different traffic loads, different stability, and so forth. For instance, one node may be out of work because of any hardware or software failure. In this case, it will reboot and take several minutes to recover, which will cause it miss several clock ticks. In addition, when a node encounters heavy traffic, it will also miss its clock ticks because it has to deal with packets in queue first. Additionally, if one node has very limited capacity to deal with packets, we expect it to lower the frequency of its clock ticks so that it can decrease the activated times. From above discussion, we would like to use the assumption that each node has an independent clock that is not needed with identical distribution. If we treat all nodes as an entirety, we can assume that there is a global clock. When this global clock ticks, it denotes that a node’s clock ticks at that time. In the sequel, we use the variable t∈{0,1,…} to index the ticks of this global clock. Each global clock tick corresponds to one update or iteration.


### 3.2. Network Model

LetG(t)=(V,E(t)) be a directed graph which represents the network connectivity, where V={1,…,n} is the constant set of nodes and E(t)⊆V×V is the time-varying set of directed edges. The network contains a directed edge li,j∈E(t) if and only if node i receives messages transmitted by node j at time t. Let Ni-(t)={k∈V:lk,i∈E(t)} and Ni(t)={k∈V:lk,i∈E(t) and li,k∈E(t)} denote the set of out-neighbors and bidirectional neighbors, respectively, of node i at time t. Let |N| denote the cardinality of a set N. Let δj-(t)=|Nj-(t)| denote the out-degree of node j, and let δj(t)=|Nj(t)| denote the degree of nodes j at time t, respectively.For gossip algorithms, not all links will be used at an iteration. Similar to literature [9], we model the interaction topology through a spanning subgraph G′(t) at time t. This spanning subgraph includes all nodes {1,2,…,n} but only includes links that are utilized at time t. We let Lk(t) denote the directional Laplacian matrix of this spanning subgraph G′(t), where the subscript k denotes the activated node which is node k.Intuitively, the convergence of gossip algorithms needs the network connected. Traditionally, there are two distinct notions of connectivity for a directed graph. A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected graph and strongly connected if there is a directed path between every pair of nodes. Obviously, this definition is suitable for static networks and is too strict to be satisfied for dynamic networks at any instant. With mobile nodes or intermittent links, network may not be always connected. Some nodes may be temporally separated with others, but intuitively it may not influence the convergence because the network will be connected again with node mobility or link recovery. For the rest of this paper we make two different definitions for connectivity.Definition 1.
The digraphG(t) is called jointly strongly connected, if there exists a time interval [i,j] so that the digraph whose edge set is the union of the edge sets of the digraphs {G′(i),G′(i+1),…,G′(j)} is strongly connected.Definition 2.
The digraphG(t) is called jointly weakly connected, if there exists a time interval [i,j] so that the digraph whose edge set is the union of the edge sets of the digraphs {G′(i),G′(i+1),…,G′(j)} is weakly connected.Furthermore, if the digraph set{G′(0),G′(1),…} can be partitioned into {GΣ0′,GΣ1′,…,GΣi′,…}, in which GΣi′={G′(ti),G′(ti+1),…,G′(ti+1-1)} and t0=0, so that each GΣi′ is jointly strongly (or weakly) connected in time interval [ti,ti+1-1]; the digraph G(t) is called partitionally strongly (or weakly) connected.For gossip algorithms, only the links between the transmitter and the receivers are activated in a moment. Accumulated by time, there is a link set consisting of all links that have been activated at least once. By Definition1 (or Definition 2), as long as the graph is jointly strongly connected (or jointly weakly connected), there must be a directed path (or undirected path by substituting undirected links for directed links) to connect any pair of nodes, where the links along this path are chosen from the digraph set. In what follows, we will prove that gossip algorithms can converge if the graph is partitionally weakly connected, and the rate of convergence is exponential in expectation if the graph is partitionally strongly connected. Therefore, as long as a link model and a mobility model can guarantee the digraph partitionally weakly connected or partitionally strongly connected, the convergence analysis in this paper will be effective. For this reason, we will not emphasize any particular link model or mobility model in this paper. Obviously, the assumption about partitionally strongly connected digraph and partitionally strongly connected digraph is the weakest assumption in convergence analysis for consensus. Intuitively, as long as link failure and mobility will not cause the graph G(t) to be permanently disconnected, gossip algorithms can converge as we will prove below.


## 3.1. Asynchronous Time Model

Similar to [8], this paper also adopts the asynchronous time model. Each node runs a clock which ticks according to an independent random process. When node k’s clock ticks it initiates a gossip update. Unlike time model in [8], it is not necessary for each node to have i.i.d. clock in this paper, which relieves the assumption from previous research. This kind of asynchronous time model often occurs in wireless sensor networks, where each node has different capabilities to deal with packets, different traffic loads, different stability, and so forth. For instance, one node may be out of work because of any hardware or software failure. In this case, it will reboot and take several minutes to recover, which will cause it miss several clock ticks. In addition, when a node encounters heavy traffic, it will also miss its clock ticks because it has to deal with packets in queue first. Additionally, if one node has very limited capacity to deal with packets, we expect it to lower the frequency of its clock ticks so that it can decrease the activated times. From above discussion, we would like to use the assumption that each node has an independent clock that is not needed with identical distribution. If we treat all nodes as an entirety, we can assume that there is a global clock. When this global clock ticks, it denotes that a node’s clock ticks at that time. In the sequel, we use the variable t∈{0,1,…} to index the ticks of this global clock. Each global clock tick corresponds to one update or iteration.


## 3.2. Network Model

LetG(t)=(V,E(t)) be a directed graph which represents the network connectivity, where V={1,…,n} is the constant set of nodes and E(t)⊆V×V is the time-varying set of directed edges. The network contains a directed edge li,j∈E(t) if and only if node i receives messages transmitted by node j at time t. Let Ni-(t)={k∈V:lk,i∈E(t)} and Ni(t)={k∈V:lk,i∈E(t) and li,k∈E(t)} denote the set of out-neighbors and bidirectional neighbors, respectively, of node i at time t. Let |N| denote the cardinality of a set N. Let δj-(t)=|Nj-(t)| denote the out-degree of node j, and let δj(t)=|Nj(t)| denote the degree of nodes j at time t, respectively.For gossip algorithms, not all links will be used at an iteration. Similar to literature [9], we model the interaction topology through a spanning subgraph G′(t) at time t. This spanning subgraph includes all nodes {1,2,…,n} but only includes links that are utilized at time t. We let Lk(t) denote the directional Laplacian matrix of this spanning subgraph G′(t), where the subscript k denotes the activated node which is node k.Intuitively, the convergence of gossip algorithms needs the network connected. Traditionally, there are two distinct notions of connectivity for a directed graph. A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected graph and strongly connected if there is a directed path between every pair of nodes. Obviously, this definition is suitable for static networks and is too strict to be satisfied for dynamic networks at any instant. With mobile nodes or intermittent links, network may not be always connected. Some nodes may be temporally separated with others, but intuitively it may not influence the convergence because the network will be connected again with node mobility or link recovery. For the rest of this paper we make two different definitions for connectivity.Definition 1.
The digraphG(t) is called jointly strongly connected, if there exists a time interval [i,j] so that the digraph whose edge set is the union of the edge sets of the digraphs {G′(i),G′(i+1),…,G′(j)} is strongly connected.Definition 2.
The digraphG(t) is called jointly weakly connected, if there exists a time interval [i,j] so that the digraph whose edge set is the union of the edge sets of the digraphs {G′(i),G′(i+1),…,G′(j)} is weakly connected.Furthermore, if the digraph set{G′(0),G′(1),…} can be partitioned into {GΣ0′,GΣ1′,…,GΣi′,…}, in which GΣi′={G′(ti),G′(ti+1),…,G′(ti+1-1)} and t0=0, so that each GΣi′ is jointly strongly (or weakly) connected in time interval [ti,ti+1-1]; the digraph G(t) is called partitionally strongly (or weakly) connected.For gossip algorithms, only the links between the transmitter and the receivers are activated in a moment. Accumulated by time, there is a link set consisting of all links that have been activated at least once. By Definition1 (or Definition 2), as long as the graph is jointly strongly connected (or jointly weakly connected), there must be a directed path (or undirected path by substituting undirected links for directed links) to connect any pair of nodes, where the links along this path are chosen from the digraph set. In what follows, we will prove that gossip algorithms can converge if the graph is partitionally weakly connected, and the rate of convergence is exponential in expectation if the graph is partitionally strongly connected. Therefore, as long as a link model and a mobility model can guarantee the digraph partitionally weakly connected or partitionally strongly connected, the convergence analysis in this paper will be effective. For this reason, we will not emphasize any particular link model or mobility model in this paper. Obviously, the assumption about partitionally strongly connected digraph and partitionally strongly connected digraph is the weakest assumption in convergence analysis for consensus. Intuitively, as long as link failure and mobility will not cause the graph G(t) to be permanently disconnected, gossip algorithms can converge as we will prove below.


## 4. Ergodicity Coefficient

### 4.1. Ergodicity

Ergodicity can describe the stationary distribution of infinite products of stochastic matrices [13]. There are two notions of ergodicity, weak ergodicity and strong ergodicity. For the sake of brevity, we only give the definition of ergodicity of left product for finite matrix set {Ak}, k∈{1,2,…,m}. Let PAr=Adr,…,Ad2Ad1 denote the left product of matrix set {Ak}, where di is freely chosen from {1,2,…,m}.Definition 3.
A sequence of infinite product ofn×n stochastic matrices {Ak}, k∈{1,2,…,m}, is weakly ergodic, if, for all i, j, s∈{1,2,…,n}, lim⁡r→∞[(PAr)i,s-(PAr)j,s]→0.Definition 4.
A sequence of infinite products ofn×n stochastic matrices {Ak}, k∈{1,2,…,m}, is strongly ergodic, if, for all i, s∈{1,2,…,n}, lim⁡r→∞(PAr)i,s→c, where c is a constant.According to Definition3, weak ergodicity denotes that the infinite product converges to a rank one matrix with form 1vT. According to Definition 4, strong ergodicity denotes that the infinite product converges to a matrix c11T. Obviously, weak ergodicity and strong ergodicity can guarantee the convergence of gossip algorithms, but strong ergodicity can further ensure that the consensus is the average of initial state values.


### 4.2. Ergodicity Coefficient

In order to evaluate the ergodic behavior, various ergodicity coefficients have been defined in [22]. Since all coefficient matrices Wk are stochastic, the ergodicity in the one norm is more suitable for the subsequent discussion, where the one norm ∥x∥1=∑i=1n‍|xi| for vector x is the absolute sum of the vector. The coefficient in the one norm applied to a stochastic matrix W is
(6)τ1(W)=max⁡∥x∥1=1xT1=0⁡∥WTx∥1.Proposition 5 (see [22], Theorem 3.4).
IfW is a stochastic matrix, then(1)
0≤τ1(W)≤1,(2)
τ1(W)=0⇔rank⁡(W)=1.Proposition 6 (see [22], Theorem 3.6).
IfW, W1, and W2 are stochastic, then(1)
|λ|≤τ1(W) for all eigenvalues λ≠1 of W.(2)
τ1(W1W2)≤τ1(W1)τ1(W2).In previous study of pairwise gossip algorithms and broadcast gossip algorithms, the authors generally utilized expectation to discuss the expected behavior of these two algorithms. By this method, each node should be independently activated with identical distribution. Unfortunately, the stability and capability of each node are often different and time-varying, so expected analysis method is not suitable. Therefore, we will directly analyze the convergence by ergodicity coefficients of the infinite product of matrices instead of expectation.Ergodicity coefficients, as introduced in Section4.2, can be used to analyze the stationary distribution of the infinite product of nonhomogeneous stochastic matrices. Traditionally, ergodicity coefficients need matrices satisfying two properties. First, all matrices should be stochastic. Second, the set of matrices should be finite. The first property is obviously satisfied as analyzed in Section 2.2. Now, we will study the second property in the next subsection and give a theorem to show that all gossip algorithms studied in this paper satisfy these two properties. Therefore, ergodicity coefficients can be used to analyze convergence.


### 4.3. Finite Set of Matrices

For the second property, we can claim that it also holds even if link failure and node movement are imposed. Intuitively, if a graph hasn nodes, the number of neighboring nodes for each node will not exceed n-1. In this case, the number of possible coefficient matrices corresponding to any active node will not be larger than n for PGA or 2n-1 for BGA. Note that identity matrix belongs to the set of coefficient matrices for any active node, and it presents that no node updates its state value. Since the number of nodes and the number of coefficient matrices for each node are all finite, the total number of possible coefficient matrices is also finite. Now, we will illustrate several lemmas to derive the exact number of matrices for each algorithm. For the sake of brevity, we use notation {Wi(k)} to denote the set of coefficient matrices corresponding to active node i, where the superscript k is the index of matrices. Let δi,max⁡- denote the possible maximum out-degree of node i. Then the following lemmas hold.Lemma 7.
With intermittent links or mobile nodes, the number of all coefficient matrices{Wi(k)} ofBGA-LF, k∈{1,2,…,2δi,max⁡-}, i∈{1,2,…,n}, is 1-n+∑i=1n‍2δi,max⁡-.Proof.
Since the maximum out-degree of any nodei is δi,max⁡-, the number of possible coefficient matrices is 2δi,max⁡- for any i. Note that each subset {Wi(k)} for any i contains a common identity matrix I, so the total number of these matrices is 1+∑i=1n‍(2δi,max⁡--1)=1-n+∑i=1n‍2δi,max⁡-.Lemma 8.
With intermittent links or mobile nodes, the number of all coefficient matrices{Wi(k)} of UPGA-LF, k∈{1,2,…,δi,max⁡+1}, i∈{1,2,…,n}, is 1+(1/2)∑i=1n‍δi,max⁡.Proof.
For UPGA-LF, the active nodei and its selected node j will update their state values only if the forward link lj,i and the backward link li,j are all available at this instant. Otherwise, if any link of lj,i and li,j fails, the coefficient matrix is identity matrix I at this moment since all nodes will keep their state values unchanged. Since only undirected links cause updates of state values, the number of coefficient matrices of UPGA-LF is the number of undirected links plus one, where the added matrix is the I.
Note that each subset{Wi(k)} for any i contains a common identity matrix I. In addition, since UPGA-LF only utilizes undirected links to exchange state values, there must exist Wj(p)=Wi(q) for some p and q as long as li,j and lj,i exist. Therefore, the total number of these matrices is 1+(1/2)∑i=1n‍δi,max⁡, which is also identical with the number of undirected links.Lemma 9.
With intermittent links or mobile nodes, the number of all coefficient matrices{Wi(k)} of BPGA-LF, k∈{1,2,…,1+2δi,max⁡}, i∈{1,2,…,n}, is 1+(3/2)∑i=1n‍δi,max⁡.Proof.
For BPGA-LF, the active nodei will choose a node from its bidirectional neighbors to exchange and update state values. Thus, we can take an iteration as two steps. First, the selected node j updates its state value as long as it receives state value from node i by the forward link lj,i. Otherwise, no nodes will update their state values, which corresponds to update all nodes’ state value by the identity matrix I. Second, after node j updates its state value, it will transmit the updated result to node i, which may succeeds or not. Therefore, we can conclude that an iteration corresponds to 3 possible situations. Firstly, if the forward link lj,i fails, the coefficient matrix is I. Secondly, if the forward link lj,i is available but the backward link li,j fails, the jth row vector of coefficient matrix is 0.5eiT+0.5ejT and all other row vectors are canonical basis row vectors. The number of possible matrices is δi,max⁡ in this case. Thirdly, if the forward link lj,i and the backward link li,j are all available, the ith row vector and the jth row vector of coefficient matrix is 0.5eiT+0.5ejT and all other row vectors are canonical basis row vectors. The number of possible matrices is also δi,max⁡ in this case. Therefore, for any i, the number of matrices in set {Wi(k)} is 1+2δi,max⁡. Based on this analysis, we turn to the proof of this lemma.
Note that each subset{Wi(k)} for any i contains a common identity matrix I. In addition, if two nodes i and j can utilize bidirectional links to exchange state values, there must exist Wj(p)=Wi(q) for some p and q as long as li,j and lj,i exist. In this case, the number of duplicate matrices in set {Wi(k)} is (1/2)∑i=1n‍δi,max⁡ equal to the number of bidirectional links. Otherwise, if only the forward links are available for each iteration, the number of corresponding matrices is δi,max⁡. Therefore, the total number of these matrices is 1+(3/2)∑i=1n‍δi,max⁡.Theorem 10.
If a graph hasn nodes, the number of coefficient matrices is finite and not larger than 1-n+n2n-1, 1+(1/2)n(n-1), and 1+(3/2)n(n-1) for BGA-LF, UPGA-LF, and BPGA-LF, respectively.Proof.
If a graph is complete or all nodes are allowed to move arbitrarily, the maximum out-degreeδi,max⁡ for any node i is n-1. By Lemmas 7, 8, and 9, we can derive that the maximum number of coefficient matrices is 1-n+n2n-1, 1+(1/2)n(n-1), and 1+(3/2)n(n-1) for BGA-LF, UPGA-LF, and BPGA-LF, respectively.According to Theorem10, the second property (i.e., finite set of matrices) for utilizing ergodicity coefficient holds. Without loss of generalization, we use Σ to denote set of possible coefficient matrices for any algorithm discussed in this paper. Furthermore, we define a left product of set Σ as
(7)PΣi→j=Wdj(fj)Wdj-1(fj-1)⋯Wdi(fi)=∏k=ij‍Wdk(fk),
where dk is the number freely drawn from {1,2,…,n} and fk is the number freely drawn from the indices of Σ.


## 4.1. Ergodicity

Ergodicity can describe the stationary distribution of infinite products of stochastic matrices [13]. There are two notions of ergodicity, weak ergodicity and strong ergodicity. For the sake of brevity, we only give the definition of ergodicity of left product for finite matrix set {Ak}, k∈{1,2,…,m}. Let PAr=Adr,…,Ad2Ad1 denote the left product of matrix set {Ak}, where di is freely chosen from {1,2,…,m}.Definition 3.
A sequence of infinite product ofn×n stochastic matrices {Ak}, k∈{1,2,…,m}, is weakly ergodic, if, for all i, j, s∈{1,2,…,n}, lim⁡r→∞[(PAr)i,s-(PAr)j,s]→0.Definition 4.
A sequence of infinite products ofn×n stochastic matrices {Ak}, k∈{1,2,…,m}, is strongly ergodic, if, for all i, s∈{1,2,…,n}, lim⁡r→∞(PAr)i,s→c, where c is a constant.According to Definition3, weak ergodicity denotes that the infinite product converges to a rank one matrix with form 1vT. According to Definition 4, strong ergodicity denotes that the infinite product converges to a matrix c11T. Obviously, weak ergodicity and strong ergodicity can guarantee the convergence of gossip algorithms, but strong ergodicity can further ensure that the consensus is the average of initial state values.


## 4.2. Ergodicity Coefficient

In order to evaluate the ergodic behavior, various ergodicity coefficients have been defined in [22]. Since all coefficient matrices Wk are stochastic, the ergodicity in the one norm is more suitable for the subsequent discussion, where the one norm ∥x∥1=∑i=1n‍|xi| for vector x is the absolute sum of the vector. The coefficient in the one norm applied to a stochastic matrix W is
(6)τ1(W)=max⁡∥x∥1=1xT1=0⁡∥WTx∥1.Proposition 5 (see [22], Theorem 3.4).
IfW is a stochastic matrix, then(1)
0≤τ1(W)≤1,(2)
τ1(W)=0⇔rank⁡(W)=1.Proposition 6 (see [22], Theorem 3.6).
IfW, W1, and W2 are stochastic, then(1)
|λ|≤τ1(W) for all eigenvalues λ≠1 of W.(2)
τ1(W1W2)≤τ1(W1)τ1(W2).In previous study of pairwise gossip algorithms and broadcast gossip algorithms, the authors generally utilized expectation to discuss the expected behavior of these two algorithms. By this method, each node should be independently activated with identical distribution. Unfortunately, the stability and capability of each node are often different and time-varying, so expected analysis method is not suitable. Therefore, we will directly analyze the convergence by ergodicity coefficients of the infinite product of matrices instead of expectation.Ergodicity coefficients, as introduced in Section4.2, can be used to analyze the stationary distribution of the infinite product of nonhomogeneous stochastic matrices. Traditionally, ergodicity coefficients need matrices satisfying two properties. First, all matrices should be stochastic. Second, the set of matrices should be finite. The first property is obviously satisfied as analyzed in Section 2.2. Now, we will study the second property in the next subsection and give a theorem to show that all gossip algorithms studied in this paper satisfy these two properties. Therefore, ergodicity coefficients can be used to analyze convergence.


## 4.3. Finite Set of Matrices

For the second property, we can claim that it also holds even if link failure and node movement are imposed. Intuitively, if a graph hasn nodes, the number of neighboring nodes for each node will not exceed n-1. In this case, the number of possible coefficient matrices corresponding to any active node will not be larger than n for PGA or 2n-1 for BGA. Note that identity matrix belongs to the set of coefficient matrices for any active node, and it presents that no node updates its state value. Since the number of nodes and the number of coefficient matrices for each node are all finite, the total number of possible coefficient matrices is also finite. Now, we will illustrate several lemmas to derive the exact number of matrices for each algorithm. For the sake of brevity, we use notation {Wi(k)} to denote the set of coefficient matrices corresponding to active node i, where the superscript k is the index of matrices. Let δi,max⁡- denote the possible maximum out-degree of node i. Then the following lemmas hold.Lemma 7.
With intermittent links or mobile nodes, the number of all coefficient matrices{Wi(k)} ofBGA-LF, k∈{1,2,…,2δi,max⁡-}, i∈{1,2,…,n}, is 1-n+∑i=1n‍2δi,max⁡-.Proof.
Since the maximum out-degree of any nodei is δi,max⁡-, the number of possible coefficient matrices is 2δi,max⁡- for any i. Note that each subset {Wi(k)} for any i contains a common identity matrix I, so the total number of these matrices is 1+∑i=1n‍(2δi,max⁡--1)=1-n+∑i=1n‍2δi,max⁡-.Lemma 8.
With intermittent links or mobile nodes, the number of all coefficient matrices{Wi(k)} of UPGA-LF, k∈{1,2,…,δi,max⁡+1}, i∈{1,2,…,n}, is 1+(1/2)∑i=1n‍δi,max⁡.Proof.
For UPGA-LF, the active nodei and its selected node j will update their state values only if the forward link lj,i and the backward link li,j are all available at this instant. Otherwise, if any link of lj,i and li,j fails, the coefficient matrix is identity matrix I at this moment since all nodes will keep their state values unchanged. Since only undirected links cause updates of state values, the number of coefficient matrices of UPGA-LF is the number of undirected links plus one, where the added matrix is the I.
Note that each subset{Wi(k)} for any i contains a common identity matrix I. In addition, since UPGA-LF only utilizes undirected links to exchange state values, there must exist Wj(p)=Wi(q) for some p and q as long as li,j and lj,i exist. Therefore, the total number of these matrices is 1+(1/2)∑i=1n‍δi,max⁡, which is also identical with the number of undirected links.Lemma 9.
With intermittent links or mobile nodes, the number of all coefficient matrices{Wi(k)} of BPGA-LF, k∈{1,2,…,1+2δi,max⁡}, i∈{1,2,…,n}, is 1+(3/2)∑i=1n‍δi,max⁡.Proof.
For BPGA-LF, the active nodei will choose a node from its bidirectional neighbors to exchange and update state values. Thus, we can take an iteration as two steps. First, the selected node j updates its state value as long as it receives state value from node i by the forward link lj,i. Otherwise, no nodes will update their state values, which corresponds to update all nodes’ state value by the identity matrix I. Second, after node j updates its state value, it will transmit the updated result to node i, which may succeeds or not. Therefore, we can conclude that an iteration corresponds to 3 possible situations. Firstly, if the forward link lj,i fails, the coefficient matrix is I. Secondly, if the forward link lj,i is available but the backward link li,j fails, the jth row vector of coefficient matrix is 0.5eiT+0.5ejT and all other row vectors are canonical basis row vectors. The number of possible matrices is δi,max⁡ in this case. Thirdly, if the forward link lj,i and the backward link li,j are all available, the ith row vector and the jth row vector of coefficient matrix is 0.5eiT+0.5ejT and all other row vectors are canonical basis row vectors. The number of possible matrices is also δi,max⁡ in this case. Therefore, for any i, the number of matrices in set {Wi(k)} is 1+2δi,max⁡. Based on this analysis, we turn to the proof of this lemma.
Note that each subset{Wi(k)} for any i contains a common identity matrix I. In addition, if two nodes i and j can utilize bidirectional links to exchange state values, there must exist Wj(p)=Wi(q) for some p and q as long as li,j and lj,i exist. In this case, the number of duplicate matrices in set {Wi(k)} is (1/2)∑i=1n‍δi,max⁡ equal to the number of bidirectional links. Otherwise, if only the forward links are available for each iteration, the number of corresponding matrices is δi,max⁡. Therefore, the total number of these matrices is 1+(3/2)∑i=1n‍δi,max⁡.Theorem 10.
If a graph hasn nodes, the number of coefficient matrices is finite and not larger than 1-n+n2n-1, 1+(1/2)n(n-1), and 1+(3/2)n(n-1) for BGA-LF, UPGA-LF, and BPGA-LF, respectively.Proof.
If a graph is complete or all nodes are allowed to move arbitrarily, the maximum out-degreeδi,max⁡ for any node i is n-1. By Lemmas 7, 8, and 9, we can derive that the maximum number of coefficient matrices is 1-n+n2n-1, 1+(1/2)n(n-1), and 1+(3/2)n(n-1) for BGA-LF, UPGA-LF, and BPGA-LF, respectively.According to Theorem10, the second property (i.e., finite set of matrices) for utilizing ergodicity coefficient holds. Without loss of generalization, we use Σ to denote set of possible coefficient matrices for any algorithm discussed in this paper. Furthermore, we define a left product of set Σ as
(7)PΣi→j=Wdj(fj)Wdj-1(fj-1)⋯Wdi(fi)=∏k=ij‍Wdk(fk),
where dk is the number freely drawn from {1,2,…,n} and fk is the number freely drawn from the indices of Σ.


## 5. Convergence of Gossip Algorithms

With the knowledge of ergodicity coefficients, we will analyze the convergence of gossip algorithms in this section.Lemma 11.
For finite stochastic matrices setΣ, τ1(PΣi→j)≤τ1(Wdj(fj))τ1(Wdj-1(fj-1))⋯τ1(Wdi(fi))≤1.Proof.
This lemma is a directed corollary from Propositions5 and 6.Theorem 12.
τ
1
(
P
Σ
i
→
j
)
<
1 for a jointly weakly connected digraph.Proof.
In Lemma11, the equal mark can only be achieved if there is a vector y to satisfy
(8)∥(Wdj(fj))Ty∥1=∥(Wdj-1(fj-1))T(Wdj(fj))Ty∥1=⋯=∥(Wdi(fi))T⋯(Wdj-1(fj-1))T(Wdj(fj))Ty∥1=1,
where ∥y∥1=1 and yT1=0. Clearly, column vectors y, (Wdj(fj))Ty, (Wdj-1(fj-1))T(Wdj(fj))Ty, …, and (Wdi(fi))T⋯(Wdj-1(fj-1))T(Wdj(fj))Ty are all orthogonal to 1 and their absolute sums are all ones. Next, we would like to first prove that all these column vectors have the same sign for each corresponding entry. We will first prove that this theorem holds for BGA-LF. If we suppose that there is a vector y to hold the equal mark of Lemma 11 for BGA-LF, we have x=(Wdj(fj))Ty with
(9)x=(ydj+(1-γ)∑i∈Ndj(fj)-yi)edj+∑i∈Ndj(fj)-(γyiei)+∑i∉dj⋃‍Ndj(fj)-(yiei).
The one norm of vectorx is
(10)∥x∥1=|ydj+(1-γ)∑i∈Ndj(fj)-‍yi|+γ∑i∈Ndj(fj)-‍|yi|+∑i∉dj⋃‍Ndj(fj)-‍|yi|≤|ydj|+(1-γ)∑i∈Ndj(fj)-‍|yi|+γ∑i∈Ndj(fj)-‍|yi|+∑i∉dj⋃‍Ndj(fj)-‍|yi|=|ydj|+∑i∈Ndj(fj)-‍|yi|+∑i∉dj⋃‍Ndj(fj)-‍|yi|=∥y∥1.
Since∥x∥1=∥y∥1=1, we have to adopt the same sign for yk with k∈dj⋃‍Ndj(fj)-, so that the equal mark can hold. This phenomenon reveals two important properties. (1) If a link lk,l is used at time j, yk must have the same sign as yl. (2) The column vectors y, (Wdj(fj))Ty, (Wdj-1(fj-1))T(Wdj(fj))Ty, …, and (Wdi(fi))T⋯(Wdj-1(fj-1))T(Wdj(fj))Ty have the same sign for each corresponding entry. To prove the second property, let us first focus on the first iteration. One can notice that xk has the same sign as corresponding yk for each k. To prove this, we first figure out that xk has the same sign as corresponding yk for k∈dj⋃‍Ndj(fj)- because xk=γyk if k∈Ndj(fj)- and xk=ydj+∑l∈Ndj(fj)-‍(1-γ)yl if k=dj, combined with the truth that yk have the same signs for k∈dj⋃‍Ndj(fj)-. Furthermore, xk will also have the same signs as yk if k∉dj⋃‍Ndj(fj)- because xk=yk. Therefore, xk has the same sign as corresponding yk for each k. Recursively, the second property can be proved. The second property reveals that each entry yk of vector y for any k will not change its sign after each iteration. If a digraph is jointly weakly connected, there is an undirected path to connect any pair of nodes. Any two entries yk and yl, if their corresponding nodes k and l are neighboring along this path, must have the same sign. Therefore, for all nodes along this path, all corresponding entries in vector y must have the same signs. Since there is a path to connect any pair of nodes in a jointly weakly connected digraph, all entries in vector y must have the same signs, which contradict with the truth ∥y∥1=1 and yT1=0 that implies at least two entries in vector y with different signs.
By now, we have proven that Theorem12 holds for BGA-LF. For UPGA-LF and BPGA-LF, the proof process has no significant difference, so we omit their proof for the sake of brevity.Lemma 13.
For a partitionally weakly connected digraph,lim⁡j→∞τ1(PΣ0→j)=0.Proof.
Since the digraph is partitionally weakly connected, the digraph set{G′(0),G′(1),…} can be partitioned into {GΣ0′,GΣ1′,…,GΣi′,…}, in which GΣi′={G′(ti),G′(ti+1),…,G′(ti+1-1)} and t0=0, so that each GΣi′ is jointly weakly connected. According to Theorem 12, τ1(PΣti→ti+1-1)<1 for any i. Therefore, we have
(11)lim⁡j→∞τ1(PΣ0→j)=τ1(PΣ0→t1-1PΣt1→t2-1⋯)≤τ1(PΣ0→t1-1)τ1(PΣt1→t2-1)⋯=0.Theorem 14.
BGA-LF, UPGA-LF, and BPGA-LF converge in static networks or mobile networks as long as the digraph is partitionally weakly connected.Proof.
According to Proposition5 and Lemma 13, the infinite product lim⁡j→∞PΣ0→j of matrices in set Σ converges to a rank one matrix. Since 1 is the right 1-eigenvector for each matrix of Σ, the convergent matrix has the form 1vT, where vT1=1. Thus, we have
(12)lim⁡t→∞x(t)=lim⁡t→∞PΣ0→tx(0)=1vTx(0)
for BGA-LF, UPGA-LF, and BPGA-LF. Therefore, all nodes can surely reach a consensus, that is, vTx(0).


## 6. Error of Convergence

To be noted, according to Theorem14, the infinite left product of matrices in set Σ converges to a matrix 1vT, where vT1=1. One important fact is that v is nonnegative because all matrices and their infinite product in set Σ are nonnegative. For UPGA-LF, v=(1/n)1 because 1T is the left 1-eigenvector for each matrix in Σ. Therefore, UPGA-LF converges to the average of initial state values and no error of convergence exists. For this reason, we only analyze the error of convergence for BGA-LF and BPGA-LF in this section.Theorem 15.
Given the mean squared error function(13)m(j)=1n∥x(j)-1n11Tx(0)∥2=1n∥PΣjx(0)-1n11Tx(0)∥2
to evaluate the error of convergence, the upper bound of error of convergence in static networks or mobile networks is (n-1/n)∥x(0)∥2.Proof.
The limit of the mean squared error reflects the error of convergence. That is,(14)lim⁡j→∞m(j)=1n∥1vTx(0)-1n11Tx(0)∥2(15)=1n|(v-1n1)Tx(0)|≤1n∥v-1n1∥2∥x(0)∥2(16)≤1n1-1n∥x(0)∥2=n-1n∥x(0)∥2,
where the first inequality holds by Cauchy-Schwarz inequality. The second inequality holds because
(17)∥v-1n1∥2=∑i=1n‍(vi-1n)2=∑i=1n‍vi2-1n≤∥v∥12-1n≤1-1n,
where the second equality holds because vT1=1. The first inequality holds because v is nonnegative and vT1=1.For (15) and (17), one can verify that all equal marks hold if x(0)T1=0 and v is a canonical basis vector. Now, we illustrate an example to show that the upper bound can be the supremum. The topology graph is demonstrated in Figure 1.Figure 1
Path graph with 3 nodes.Suppose a special scenario where node1 and node 3 can receive state values from node 2, but node 2 cannot receive state values from node 1 or node 3 for a long time. This means node 2 always keeps its state value x2(0) unchanged and forces state values of other nodes to approach x2(0) by subsequent convex combination. If the period lasts long enough, all state values will be x2(0), which means the convergence has been achieved and the convergent matrix is 1[010]. Therefore, vector v=[010]T is exactly a canonical basis vector. Since the product has converged, the product will not change any more even if node 2 can recover to receive state values from node 1 and node 3. Obviously, this special scenario is still a partitionally weakly connected digraph so the convergence can be surely guaranteed. If the initial states of these nodes are x(0)=[-1/32/3-1/3]T, it is evident that x(0)T1=0. Replacing v=[010]T and x(0)=[-1/32/3-1/3]T into (14), we have lim⁡j→∞m(j)=23/9 that coincides with the upper bound of (16). Therefore, the upper bound (n-1/n)∥x(0)∥2 is the supremum. According to above analysis, the initial products essentially determine the infinite product; that is, whatever matrices are used, beyond some initial product, has little effect on the infinite product ([23], Sec. 7). Obviously, when the number of nodes approach infinity, the error of convergence will approach zero as illustrated in (16).


## 7. Rate of Convergence

If a left-convergent product setΣ whose limit function lim⁡j→∞PΣ0→j-1 is continuous, then all infinite products from Σ uniformly converge to a limit matrix at a geometric rate ([24], Corollary 4.2a). Unfortunately, the left-convergent product set Σ does not have a continuous limit function because all matrices Wi(k) in Σ do not have the same 1-eigenspace and this eigenspace is not always simple for all Wi(k) ([24], Theorem 4.2). In particular, identity matrix I exists in set Σ causing the convergence of the limit function to be no longer exponential in the general case; by inserting many extra copies of the identity matrix in an infinite product, the convergence rate to a limit matrix can be slowed to an arbitrary degree ([24], Sec. 5).For this reason, we cannot directly analyze the rate of convergence but analyze the rate of convergence by expectation. First of all, we will analyze the rate of convergence for static networks. Suppose each nodei is activated with probability pi and each link li,j fails with probability pi,j, where pi does not need i.i.d. and pi,j does not need to equal pj,i because of directed links. Therefore, for any matrix Wi(k) of BGA-LF with i∈{1,2,…,n} and k∈{1,2,…,2δi,max⁡-} in Σ, it occurs with probability
(18)pi∏i∈Nj(k)-(1-pj,i)∏i∈Nj(1)--Nj(k)-pj,i.Therefore, we can derive the expectation of all matrices as(19)E[Wi(k)]=∑i=1n‍∑k=12δi,max⁡-‍[pi∏i∈Nj(k)-(1-pj,i)∏i∈Nj(1)--Nj(k)-pj,i]Wi(k).If the digraph is partitionally strongly connected, the expected matrixE[Wi(k)] corresponds to a strongly connected digraph, where there is a directed link li,j in the digraph if E[Wi(k)]i,j≠0. Obviously, this property also holds for UPGA-LF and BPGA-LF as long as the digraph is partitionally strongly connected. To be noted, we allow self-loop li,i to exist for any i in this partitionally strongly connected digraph. According to Perron-Frobenius theorem, the largest eigenvalue ρ1 of E[Wi(k)] is simple with a positive eigenvector and the module of all other eigenvalues |ρ2|≥|ρ3|≥⋯≥|ρn| is strictly less than ρ1. Since all matrices Wi(k) are stochastic, the positive all-one vector 1 is the 1-eigenvector of matrix E[Wi(k)]. Therefore, 1 is the largest and simple eigenvalue of matrix E[Wi(k)], and all other eigenvalue of E[Wi(k)] are strictly less than 1 in module.Theorem 16.
If a network is static and partitionally strongly connected, the expected rate of convergence is exponential and is governed by|ρ2|j, where j is the iterative times.Proof.
We take expectation onPΣ0→j-1=∏i=0j-1‍Wdi(fi) and notice that each matrix Wi(k) is independent, where we do not need each matrix to have identical distribution. Then we have E[PΣ0→j-1]=E[Wi(k)]j. It is well known that the rate of convergence for the power of a matrix is governed by the second largest eigenvalue of this matrix if its largest eigenvalue is 1. Therefore, the rate of convergence satisfies exponential distribution |ρ2|j.Intuitively, the rate of convergence is governed by link failure probability, topology structure, movement method, and so forth. The second largest eigenvalueρ2 will be smaller, if links are more reliable, topology is more connected or nodes move more quickly. In this case, gossip algorithms can converge more quickly.Next, we analyze the expected rate of convergence for mobile networks.Theorem 17.
If a mobile network is partitionally strongly connected, the expected rate of convergence is exponential and is governed by|ρ2|j, where j is the iterative times.Proof.
The proof method is almost the same as Theorem16, except that the number of {Wi(k)} is different and the movement has effects on the expectation of Wi(k). Anyway, as long as the digraph is partitionally strongly connected, the corresponding digraph with E[Wi(k)] is strongly connected. Therefore, the largest eigenvalue of E[Wi(k)] is 1 and is simple; the module of all other eigenvalues is strictly less than 1. For this reason, the expected rate of convergence is exponential and is governed by |ρ2|j.


## 8. Numerical Analysis

In this section, we will first analyze the performance of gossip algorithms in various static graphs with intermittent links. Then we will further consider the performance of these algorithms in mobile networks with intermittent links.In this section, we will only study the performance of various gossip algorithms with partitionally strongly connected digraphs instead of partitionally weakly digraphs. The reasons can be concluded as follows.(1) The convergence of gossip algorithms with partitionally strongly (or weakly) connected digraphs has been sufficiently proved by theoretical analysis in Section 5. In that section, we have proven that gossip algorithms can converge with partitionally weakly connected digraph. Since a digraph is partitionally weakly connected, it is also partitionally strongly connected. Therefore, gossip algorithms can converge if the digraph is partitionally strongly (or weakly) connected. As theoretical analysis is more accurate than simulation analysis, it is not necessary to discuss the convergence of gossip algorithms in this section again. (2) The rate of convergence can only be analyzed with partitionally strongly connected digraphs. Although we have proven that gossip algorithms can converge as long as the digraph is partitionally weakly connected, partitionally weakly connected digraphs cannot guarantee gossip algorithms converge in finite time. Instead, as mentioned in Section 7, only partitionally strongly connected digraphs can ensure that gossip algorithms converge with exponential rate in expectation. Since we can only analyze the rate of convergence for gossip algorithms with partitionally strongly connected digraphs instead of partitionally weakly connected digraphs, simulation analysis will evaluate the performance, especially the rate of convergence, of various gossip algorithms with partitionally strongly connected digraphs by Monte Carlo method. In short, this section will not analyze the convergence of various gossip algorithms, which has been sufficiently discussed in Section 5, but will discuss the error of convergence and the rate of convergence. Since the rate of convergence for gossip algorithms can only be analyzed with partitionally strongly connected digraphs, this section will only utilize partitionally strongly connected digraphs to execute numerical analysis.The key metrics to evaluate gossip algorithms are the deviation of convergence and the rate of convergence. The former can be assessed by standard deviation (or called mean squared error) as (13). Obviously, standard deviation shows how much variation exists from the average of initial state values at time j, so it is competent for evaluating the deviation of convergence. For the rate of convergence, we define variance to evaluate as
(20)q(j)=1n∥x(j)-1n11Tx(j)∥22.Intuitively, if a gossip algorithm can converge faster than others, its state values will achieve consensus faster than others. Therefore, we can gracefully utilize variance to evaluate the rate of convergence.In the sequel, BGA and PGA denote broadcast gossip algorithms without link failure and pairwise gossip algorithms without link failure, respectively, which is the criterion to evaluate the effect of link failures on the error of convergence and the rate of convergence.


### 8.1. Static Networks

#### 8.1.1. Mean Squared Error

The simulation parameters are chosen as follows. There are 50, 100, or 500 nodes uniformly distributed in a unit square. The connectivity radius is chosen asR=2(log⁡n)/n so that the graph is connected with probability of at least 1-1/n2. For each link, the failure probability is uniformly chosen in [0,0.5] or [0,0.2]. With these parameters, it is evident that the graph is partitionally strongly connected. Every node has an initial value according to uniform distribution in interval [0,1].Figures2 and 3 show the mean squared error of various gossip algorithms with maximum possible failure probability of each link 0.2 and 0.5, respectively. We concentrate on Figure 2 first. Obviously, PGA and UPGA-LF can converge to the average of initial state values at the cost of the slow rate of convergence, which coincide with our previous analysis. For a given number of iterations, we are not surprised to find that UPGA-LF has larger MSE than PGA because link failure will cause packet loss which in turn restricts some nodes to participate in state update at each iteration. For BGA and BGA-LF, they cannot converge to the average of initial state values but they converge very fast because there are more than 2 nodes that are allowed to update their state values at each iteration. One interesting thing is that there is no significant difference between BGA and BGA-LF in the performance of MSE. This phenomenon can be explained as BGA cannot converge to the average on initial state values even if links are realistic. Therefore, BGA-LF will not significantly change error of convergence since it will influence the error of convergence in uncertain method. Now, we turn to compare performance of MSE with different link failure probabilities by Figures 2 and 3. Since BGA and BGA-LF cannot converge to the average consensus, the MSE will not be significantly influenced by different link failure probabilities, which can be explained by the same reason as mentioned above. For UPGA-LF, it is clear to find that higher link failure probability will cause UBGA-LF to converge slower because fewer nodes can participate in the update in this case. We conclude that UBGA-LF has best performance in MSE, but all gossip algorithms can converge as long as the graph is partitionally strongly connected.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.2] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


#### 8.1.2. Variance

Figure4 shows that BGA and BGA-LF converge fastest because more nodes can update state values at each iteration. In addition BPGA-LF and UPGA-LF converge slower than PGA because link failure will cause fewer nodes to participate update. The same explanation can also be used to clarify the reason that UPGA-LF converges slower than BPGA-LF and larger link failure probability will cause slower rate of convergence as illustrated in Figures 4 and 5.The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.2] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


### 8.2. Mobile Networks

In this subsection, we further impose node movement and link failure together to analyze the performance of various gossip algorithms. In order to evaluate the influence of movement for convergence, we have to utilize real world clock model and actual size of region, rather than discrete clock model and normalized size of region, so that the speed of nodes and the moving distance can be taken into account to generate a time-varying topology. For this reason, we set simulation parameters as follows. There are 50, 100, or 500 nodes uniformly distributed in a1000m×1000m area. The connectivity radius is chosen as R=1000m×2(log⁡n)/n so that the graph is connected with high probability. We will also evaluate the performance of mobile networks with uniform initial values. Waypoint model is widely used to simulate the movement of nodes. Based on waypoint model, each node will move to a desired destination with a constant speed. When a node arrives at its destination, it will randomly choose another destination in the region and move to the new destination again. In this subsection, we utilize waypoint model to simulate two types of movement. (1) Each node moves with constant speed 2 m/s, which denotes slow mobile networks with walking speed. (2) Each node moves with constant speed 20 m/s, which denotes fast mobile networks with vehicle speed. For sake of brevity, we set link failure probability uniformly distributed in [0,0.5]. Each node will be individually activated according as the exponential distribution with mean 1/n. Obviously, a graph with these simulation parameters is partitionally strongly connected.


#### 8.2.1. Slow Movement

If all nodes move with slow speed, the characteristics of gossip algorithms have no significant difference with static networks as illustrated in Figures6 and 7, except that movement can help gossip algorithms converge faster. Indeed, the rate of convergence mainly influenced by the number of nodes to participate in update at each iteration and the difference of state values between neighboring nodes. Since movement can help a node diverse its state value to more others in a given time period, it will improve the rate of convergence.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 2 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 2 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


#### 8.2.2. Fast Movement

As illustrated in Figures8 and 9, it is interesting to notice that fast movement can further assist gossip algorithms to converge, in comparison with slow mobile networks. This phenomenon is based on the same reason as explained above.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 20 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 20 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


## 8.1. Static Networks

### 8.1.1. Mean Squared Error

The simulation parameters are chosen as follows. There are 50, 100, or 500 nodes uniformly distributed in a unit square. The connectivity radius is chosen asR=2(log⁡n)/n so that the graph is connected with probability of at least 1-1/n2. For each link, the failure probability is uniformly chosen in [0,0.5] or [0,0.2]. With these parameters, it is evident that the graph is partitionally strongly connected. Every node has an initial value according to uniform distribution in interval [0,1].Figures2 and 3 show the mean squared error of various gossip algorithms with maximum possible failure probability of each link 0.2 and 0.5, respectively. We concentrate on Figure 2 first. Obviously, PGA and UPGA-LF can converge to the average of initial state values at the cost of the slow rate of convergence, which coincide with our previous analysis. For a given number of iterations, we are not surprised to find that UPGA-LF has larger MSE than PGA because link failure will cause packet loss which in turn restricts some nodes to participate in state update at each iteration. For BGA and BGA-LF, they cannot converge to the average of initial state values but they converge very fast because there are more than 2 nodes that are allowed to update their state values at each iteration. One interesting thing is that there is no significant difference between BGA and BGA-LF in the performance of MSE. This phenomenon can be explained as BGA cannot converge to the average on initial state values even if links are realistic. Therefore, BGA-LF will not significantly change error of convergence since it will influence the error of convergence in uncertain method. Now, we turn to compare performance of MSE with different link failure probabilities by Figures 2 and 3. Since BGA and BGA-LF cannot converge to the average consensus, the MSE will not be significantly influenced by different link failure probabilities, which can be explained by the same reason as mentioned above. For UPGA-LF, it is clear to find that higher link failure probability will cause UBGA-LF to converge slower because fewer nodes can participate in the update in this case. We conclude that UBGA-LF has best performance in MSE, but all gossip algorithms can converge as long as the graph is partitionally strongly connected.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.2] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


### 8.1.2. Variance

Figure4 shows that BGA and BGA-LF converge fastest because more nodes can update state values at each iteration. In addition BPGA-LF and UPGA-LF converge slower than PGA because link failure will cause fewer nodes to participate update. The same explanation can also be used to clarify the reason that UPGA-LF converges slower than BPGA-LF and larger link failure probability will cause slower rate of convergence as illustrated in Figures 4 and 5.The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.2] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


## 8.1.1. Mean Squared Error

The simulation parameters are chosen as follows. There are 50, 100, or 500 nodes uniformly distributed in a unit square. The connectivity radius is chosen asR=2(log⁡n)/n so that the graph is connected with probability of at least 1-1/n2. For each link, the failure probability is uniformly chosen in [0,0.5] or [0,0.2]. With these parameters, it is evident that the graph is partitionally strongly connected. Every node has an initial value according to uniform distribution in interval [0,1].Figures2 and 3 show the mean squared error of various gossip algorithms with maximum possible failure probability of each link 0.2 and 0.5, respectively. We concentrate on Figure 2 first. Obviously, PGA and UPGA-LF can converge to the average of initial state values at the cost of the slow rate of convergence, which coincide with our previous analysis. For a given number of iterations, we are not surprised to find that UPGA-LF has larger MSE than PGA because link failure will cause packet loss which in turn restricts some nodes to participate in state update at each iteration. For BGA and BGA-LF, they cannot converge to the average of initial state values but they converge very fast because there are more than 2 nodes that are allowed to update their state values at each iteration. One interesting thing is that there is no significant difference between BGA and BGA-LF in the performance of MSE. This phenomenon can be explained as BGA cannot converge to the average on initial state values even if links are realistic. Therefore, BGA-LF will not significantly change error of convergence since it will influence the error of convergence in uncertain method. Now, we turn to compare performance of MSE with different link failure probabilities by Figures 2 and 3. Since BGA and BGA-LF cannot converge to the average consensus, the MSE will not be significantly influenced by different link failure probabilities, which can be explained by the same reason as mentioned above. For UPGA-LF, it is clear to find that higher link failure probability will cause UBGA-LF to converge slower because fewer nodes can participate in the update in this case. We conclude that UBGA-LF has best performance in MSE, but all gossip algorithms can converge as long as the graph is partitionally strongly connected.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.2] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


## 8.1.2. Variance

Figure4 shows that BGA and BGA-LF converge fastest because more nodes can update state values at each iteration. In addition BPGA-LF and UPGA-LF converge slower than PGA because link failure will cause fewer nodes to participate update. The same explanation can also be used to clarify the reason that UPGA-LF converges slower than BPGA-LF and larger link failure probability will cause slower rate of convergence as illustrated in Figures 4 and 5.The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.2] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on random geometric graphs with uniform initial values and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


## 8.2. Mobile Networks

In this subsection, we further impose node movement and link failure together to analyze the performance of various gossip algorithms. In order to evaluate the influence of movement for convergence, we have to utilize real world clock model and actual size of region, rather than discrete clock model and normalized size of region, so that the speed of nodes and the moving distance can be taken into account to generate a time-varying topology. For this reason, we set simulation parameters as follows. There are 50, 100, or 500 nodes uniformly distributed in a1000m×1000m area. The connectivity radius is chosen as R=1000m×2(log⁡n)/n so that the graph is connected with high probability. We will also evaluate the performance of mobile networks with uniform initial values. Waypoint model is widely used to simulate the movement of nodes. Based on waypoint model, each node will move to a desired destination with a constant speed. When a node arrives at its destination, it will randomly choose another destination in the region and move to the new destination again. In this subsection, we utilize waypoint model to simulate two types of movement. (1) Each node moves with constant speed 2 m/s, which denotes slow mobile networks with walking speed. (2) Each node moves with constant speed 20 m/s, which denotes fast mobile networks with vehicle speed. For sake of brevity, we set link failure probability uniformly distributed in [0,0.5]. Each node will be individually activated according as the exponential distribution with mean 1/n. Obviously, a graph with these simulation parameters is partitionally strongly connected.


### 8.2.1. Slow Movement

If all nodes move with slow speed, the characteristics of gossip algorithms have no significant difference with static networks as illustrated in Figures6 and 7, except that movement can help gossip algorithms converge faster. Indeed, the rate of convergence mainly influenced by the number of nodes to participate in update at each iteration and the difference of state values between neighboring nodes. Since movement can help a node diverse its state value to more others in a given time period, it will improve the rate of convergence.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 2 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 2 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


### 8.2.2. Fast Movement

As illustrated in Figures8 and 9, it is interesting to notice that fast movement can further assist gossip algorithms to converge, in comparison with slow mobile networks. This phenomenon is based on the same reason as explained above.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 20 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 20 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


## 8.2.1. Slow Movement

If all nodes move with slow speed, the characteristics of gossip algorithms have no significant difference with static networks as illustrated in Figures6 and 7, except that movement can help gossip algorithms converge faster. Indeed, the rate of convergence mainly influenced by the number of nodes to participate in update at each iteration and the difference of state values between neighboring nodes. Since movement can help a node diverse its state value to more others in a given time period, it will improve the rate of convergence.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 2 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 2 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


## 8.2.2. Fast Movement

As illustrated in Figures8 and 9, it is interesting to notice that fast movement can further assist gossip algorithms to converge, in comparison with slow mobile networks. This phenomenon is based on the same reason as explained above.The standard deviation of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 20 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500The variance of BGA, PGA, BGA-LF, UPGA-LF, and BPGA-LF with respect to the number of iterations on mobile graphs with speed 20 m/s, uniform initial values, and[0,0.5] uniform link failure probability.
(a)
n
=
50
(b)
n
=
100
(c)
n
=
500


## 9. Conclusion and Future Work

By theoretical analysis, we prove that pairwise gossip algorithms and broadcast gossip algorithms can converge as long as digraphs are partitionally weakly connected, which is the weakest assumption among all previous related literatures. According to this research result, these gossip algorithms can be used for dynamic networks, even if nodes are activated with different probability distribution or each link has different stability. Furthermore, we derive the supremum on error of convergence for these gossip algorithms. To be noted is that the supremum of convergence error is the upper bound that cannot be exceeded for each specific realization. In contrast, almost all previous study is based on mathematical expectation, so the upper bound of convergence error can only be given in expectation, which can only describe an expected behavior and cannot ensure that the error will not exceed the bound for a specific realization. In addition, we show that these gossip algorithms cannot be guaranteed to converge in finite time. By theoretical analysis, we further prove that these gossip algorithms can converge with exponential rate in expectation if the digraph is partitionally strongly connected.In the near future, we will try to analyze the rate of convergence for partitionally weakly connected digraphs. So far, we have utilized Perron-Frobenius theorem to derive the rate of convergence for partitionally strongly connected digraphs. For partitionally weakly connected digraphs, Perron-Frobenius theorem cannot be utilized because the digraph corresponding to the expectation of all matrices is not strongly connected. Therefore, we will try to find a new method to analyze this problem. In addition, we will take the stable probability of each link or mobile models into account. Intuitively, more stable links will cause for identity matrixI to occur less in the infinite product, so the rate of convergence will increase. Therefore, we will further study the relation between stable probability of each link and the rate of convergence. Furthermore, as illustrated by simulation results, movement can assist gossip algorithms convergence because it helps each node diverse its state value to more nodes in a given time period. We will engage in the impact analysis of movement on the rate of convergence in the future.In addition, we have proposed another kind of broadcast gossip algorithms in previous research [10]. In the near future, we will engage in the convergence analysis of these algorithms for intermittent links and mobile nodes. Since the coefficient matrices of these broadcast gossip algorithms have some negative entries, which invalidate the use of ergodicity coefficient, we have to adopt different methods to analyze convergence, which is more challenging and requires further investigation.



---

*Source: 836584-2014-10-29.xml*