Sample Greedy Gossip for Distributed Network-Wide Average Computation
Hyo-Sang Shin Shaoming He Antonios Tsourdos




Sample Greedy Gossip for Distributed Network-Wide Average Computation
    Hyo-Sang Shin*, Shaoming He and Antonios Tsourdos
Hyo-Sang Shin, Shaoming He and Antonios Tsourdos are with the School of Aerospace, Transport and Manufacturing, Cranfield University, Cranfield MK43 0AL, UK
(email: {h.shin,shaoming.he,a.tsourdos}@cranfield.ac.uk)
*Corresponding Author.
    December 30, 2023
==================================================================================================================================================================================================================================================================================================




This paper investigates the problem of distributed network-wide averaging and proposes a new  greedy gossip algorithm. Instead of finding the optimal path of each node in a greedy manner, the proposed approach utilises a suboptimal communication path by performing greedy selection among randomly selected active local nodes. Theoretical analysis on convergence speed is also performed to investigate the characteristics of the proposed algorithm. The main feature of the new algorithm is that it provides great flexibility and well balance between communication cost and convergence performance introduced by the stochastic sampling strategy. Extensive numerical simulations are performed to validate the analytic findings. 



Partially-connected network, Distributed averaging, Gossip process, Sample greedy






§ INTRODUCTION



Employment of multiple mobile robots to cooperatively perform complex tasks has become a viable option along with dramatic technical advancements in low-cost, lightweight and power efficient robots. Average computation or average agreement over a wireless agent network is recognised as a key enabler for the operation of such a multiple robot system <cit.>.  To this end, this paper investigates the problem of network-wide averaging, especially based on the distributed architecture.

With the development of network theory, the control-theoretic consensus algorithm <cit.> has become a popular and powerful tool in network-wide average computation. At each iteration, each local agent broadcasts its information to locally-connected neighbours and leverages the received information for update. Although average consensus provides a general framework for network-wide computation, the information exchange typically requires each local agent to be accessible by all its local agents <cit.>. In contrast, gossip message passing algorithms only utilise two local agents in information exchange at every iteration and thus shows practical attractiveness and robustness against topology variation <cit.>. 

One pioneering work of gossip algorithms was the randomised gossip, proposed in <cit.>. At each communication round, one local node randomly wakes up and randomly picks one of its neighbouring node for information exchange. These two agents then update their information as the average of their prior information. Although the randomised gossip guarantees asymptotic convergence, the convergence speed is very slow due to the randomised nature. An improvement over randomised gossip was geographic gossip <cit.>, which leverages the geographic routing to improve the convergence speed of randomised gossip. The basic idea behind geographic gossip is to utilise a multi-hop communication strategy with full knowledge of geographic property of the network. This communication structure, however, largely relies on the reliability of network communications over many hops and inevitably involves communication overhead due to geographic routing. Unlike geometric gossip, the broadcast gossip, proposed in<cit.>, makes use of the broadcast nature of wireless sensor networks. In other words, a local node is activated uniformly and broadcasts its information to connected neighbours at each iteration. These neighbouring nodes then update their information by a weighted average of their own and the broadcasted information. Although the convergence of broadcast gossip is relatively fast, this algorithm cannot guarantee the convergence to the true average, i.e., it introduces bias. In a recent noteworthy contribution <cit.>, the authors suggested a new variant of gossip process, termed as greedy gossip, for distributed averaging. Unlike randomised gossip, the greedy gossip finds the optimal communication path that provides the maximum information discrepancy for a random local agent. It has been theoretically proved that the greedy gossip can significantly improve the convergence speed at the price of higher communication burden, compared to randomised gossip.

The two types of gossip, randomised and greedy, algorithms exhibit complementary characteristics.  More specifically, the randomised gossip has lower computational burden at each gossip iteration, but its convergence rate is relatively slow due to the randomised nature. On the other hand, the greedy gossip approach enjoys faster convergence by leveraging a deterministic communication strategy, compared with the randomised gossip. However, it requires communications of each node with all its neighbouring nodes connected to find the optimal path. This consequently increases the communication burden, which might be against the main strength of the original randomised gossip, at each iteration. 

Based on these observations, this paper proposes a new variant of gossip process for distributed network-wide average computation. The algorithm developed is called sample greedy gossip (SGG) since it exploits stochastic sampling strategy. Unlike previous gossip algorithms, the proposed algorithm is a generalised version of randomised gossip and greedy gossip: it exhibits positive features of both randomised and greedy gossip. Different from randomised gossip, SGG takes the advantage of greedy gossip by applying the greedy node selection strategy to a randomly active node set. As the expected size of the active node set is smaller than the number of locally-connected neighbours, SGG can reduce the communication overload in the average sense. Therefore, the proposed SGG algorithm provides great flexibility and well balance between communication cost and convergence performance. Theoretical analysis reveals that the proposed SGG algorithm guarantees asymptotic convergence to the average state. The effect of the stochastic sampling strategy on the convergence rate of the proposed SGG algorithm is also theoretically analysed to demonstrate the tradeoff performance of SGG. To provide better insights into SGG, we derive the upper bound of its convergence rate, which relates the convergence performance of SGG to that of randomised gossip and greedy gossip. 

The rest of the paper is organised as follows. Sec. <ref> introduces of the proposed SGG algorithm. Sec. <ref> presents theoretical analysis of the SGG algorithm, followed by some numerical evaluations provided in Sec. <ref>. Finally, some conclusions are offered. 





§ ALGORITHM DEVELOPMENT



This section will develop a new SGG algorithm, which is a generalised version of the gossip algorithm, by exploiting the benefits of both randomised gossip <cit.> and greedy gossip<cit.>.  We consider a network of N agents and model the network topology as an undirected graph 𝒢 = (𝒱,ℰ), where 𝒱={1,2,⋯,N} represents the node set and ℰ⊂𝒱×𝒱 denotes the edge set. If agents s and t can directly communicate with each other, then (s,t) ∈ℰ. We assume the network is strongly-connected[Note that this condition is required for guaranteeing the asymptotic convergence of gossip algorithms. However, this dose not mean that gossip algorithms are only applicable to strongly-connected networks.], e.g., any two nodes can communicate with each other through a multi-hop path. Denote a_s as the available information from the sth node and is initialised as a_s(0). The objective of gossip algorithm is to enforce all local nodes to make an agreement on the initial average value ∑_s = 1^Na_s( 0 ) using only local information available from the connected neighbours. 

At the lth round of the randomised gossip iterations, a node s ∈𝒱 is randomly selected for communication. This can be accomplished by using an asynchronous time mode[Each node has a Poisson time clock with rate 1. At every gossip iteration, only one node is randomly picked up to communicate with one of its neighbours by clock ticking.] , as described in <cit.>. Then, node s randomly selects a neighbour node t ∈ N_s, where N_s represents the set of the nodes connected to the sth node (not including s), and performs information average as

    a_s( l ) = a_t( l ) = a_s( l-1 ) + a_t( l-1 )/2


For strongly-connected network, it was shown in <cit.> that the randomised gossip algorithm guarantees asymptotic convergence to the initial average value, that is lim_l →∞a_s( l ) = 1/N∑_s = 1^Na_s( 0 ). The main advantage of randomised gossip is that it has relatively low communication burden since each node only needs to communicate with one connected node during one iteration round. However, the randomised gossip algorithm might suffers from low convergence speed due to the randomised communication strategy. For this reason, a greedy gossip algorithm was proposed in <cit.> to accelerate the convergence rate, i.e., reduce the number of required gossip iterations to reach an agreement among all nodes. The greedy gossip algorithm employs a deterministic procedure to select the communication nodes, i.e., active nodes. More specifically, at the lth round of the gossip iterations, the sth node selects a node t^* ∈ N_s that has the largest information discrepancy, that is

    t^* =  max_t ∈𝒩_s[a_s( l ) - a_t( l )]^2


After finding t^*, the two agents perform information averaging using Eq. (<ref>). Compared with the original randomised gossip process, the greedy gossip algorithm is proved to provide improved convergence speed. However, this strategy requires each node to communicate with all nodes connected to find the optimal communication path and thus might increase the communication overhead. 

Motivated by the complementary properties of these two different gossip algorithms, this paper develops a new variant of gossip algorithm, called SGG. The proposed gossip algorithm enjoys the advantages of both randomised gossip and greedy gossip: relatively faster convergence speed and lower communication burden. The fundamental idea of SGG is to apply the greedy node selection strategy to the set of randomly active nodes, 𝒜_s, which is a subset of 𝒩_s, i.e., 𝒜_s ⊂𝒩_s.  For notational convenience, we define 𝒩_s Δ = { Sn(1),Sn(2),⋯,Sn(|𝒩_s|)  } with Sn(i) ∈{1,2,⋯,N } for all i ∈{ 1,2,⋯,|𝒩_s| }, where |𝒩_s| denotes the cardinality of set 𝒩_s. The active node set 𝒜_s is generated by randomly selecting nodes from 𝒩_s for communication based on a stochastic uniform sampling procedure. More specifically, all nodes in 𝒩_s generate a sample, i.e., q_i for all i ∈{1, 2, …, |𝒩_s|}, from uniform distribution 𝒰( 0,1). Each node from 𝒩_s is then activated with probability p ∈ [0,1]: if q_i ≤ p, node Sn(i) decides to actively communicate with node s. Once we have 𝒜_s, the sth node selects a suboptimal node for information exchange as

    t^* =  max_t ∈𝒜_s[a_s( l ) - a_t( l )]^2

and leverages Eq. (<ref>) for information update. If no node has been activated by the sampling strategy, i.e., 𝒜_s = ∅, we perform randomised gossip for update. The pseudo code of the proposed SGG algorithm is summarised in Algorithm <ref>.


It can be clearly noted that the proposed algorithm only utilises a random subset of 𝒩_s to perform greedy node selection. The communication burden, therefore, depends on p, which determines the size of 𝒜_s. For example, if the node activation probability p is chosen as p=0.5, the communication burden is half in average sense at every gossip iteration, compared with the greedy gossip. Therefore, the proposed SGG can be viewed as a generalised version of the gossip algorithm that can trade-off between randomised gossip and greedy gossip: the proposed SGG becomes greedy gossip with p=1 and reduces to randomised gossip with p=0.







§ CONVERGENCE ANALYSIS



In this section, we provide detailed theoretical analysis of the proposed SGG algorithm, demonstrating its convergence performance and comparing its convergence rate with that of randomised gossip and greedy gossip. Note that the analysis carried out in this section is based on the asynchronous time mode. However, the extension to synchronous time model[Unlike asynchronous time model, all nodes in every gossip iteration communicate
simultaneously with one of their neighbour.] is straightforward and the qualitative/quantitative results are unaffected by the type of time model <cit.>.



 §.§ Asymptotic Convergence Analysis


This subsection analyses the asymptotic convergence of the proposed SGG algorithm. For notational convenience, we denote a(l)=[a_1(l),a_2(l),⋯,a_N(l)]^T and define a as a column vector with each element being 1/N∑_l = 1^N a_l( 0 ). The main results are presented in the following theorem.


The proposed SGG algorithm guarantees asymptotic convergence to the average state a̅.



Assume that agents s and the t perform gossip at the lth iteration of SGG, then the recursive update of SGG can be obtained as

    a(l)=a(l-1)-1/2 g(l)
 
where g(l) ∈ℝ^N is a column vector with its elements being

    g_i(l)={[    a_s(l-1)-a_t(l-1),              for  i=s; -(a_s(l-1)-a_t(l-1)),              for  i=t;                    0,             otherwise ].
 

Based on Eq. (<ref>), the recursive update of the squared error is determined as

    a(l)-a^2   =a(l-1)-1/2 g(l)-a^2
       =a(l-1)-a^2-[a(l-1)-a]^T g(l)+1/4g(l)^2
       =a(l-1)-a^2-1/2[a_s(l-1)-a_t(l-1)]^2
 

Note that both s and t are random in the proposed SGG. For this reason, we will examine the expected squared error, i.e., 𝔼[a(l)-a^2], in the following analysis. Taking the expectation on [a_s(l-1)-a_t(l-1)]^2 gives

    𝔼{[a_s(l-1)-a_t(l-1)]^2}=   1/N∑_s = 1^N ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
        +1/N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2

where 𝒩_s,m denotes a set of m nodes, randomly drawn from 𝒩_s and {𝒩_s,m} stands for the set that includes all possible 𝒩_s,m.

Note that the first term on the right hand side of Eq. (<ref>) refers to the case where 1 ≤ m ≤| 𝒩_s| nodes decide to communicate with the sth node, and the second term implies the case where no node has been activated by the sampling procedure. As stated in Algorithm <ref>, if no node decides to communicate with node s during the sampling phase, we perform the randomised gossip for update. From Eq. (<ref>), it is clear that 𝔼{[a_s(l-1)-a_t(l-1)]^2}≥0, where the equality holds if and only if a(l-1) = a̅. This means that, unless all nodes make agreement on the average state a̅, the proposed SGG algorithm will make progress in expectation towards the average state a̅. Moreover, by repeatedly applying recursion (<ref>) and taking the expectation, we have

    𝔼[a(l)-a^2]   =𝔼[a(l-1)-a^2]-1/2𝔼{[a_s(l-1)-a_t(l-1)]^2}
        = 𝔼[a(0)-a^2] - 1/2∑_i = 1^l 𝔼{[a_s(i-1)-a_t(i-1)]^2}
 

Since 𝔼[a(l)-a^2] ≥ 0, we have

    𝔼[a(0)-a^2] ≥1/2∑_i = 1^l 𝔼{[a_s(i-1)-a_t(i-1)]^2}
 
which implies that 𝔼{[a_s(l-1)-a_t(l-1)]^2}→ 0 as l →∞. As the solution a(l) = a̅ is the only stationary point of stochastic recursion (<ref>), the proposed SGG algorithm guarantees asymptotic convergence to the average state a̅.




 §.§ Convergence Rate Analysis


This subsection analyses convergence rate of the proposed SGG algorithm. We first investigates the effect of node activation probability p on the convergence speed and then derive the convergence bound. 



  §.§.§ Effect of Node Activation Probability p

The tradeoff performance of the proposed SGG algorithm highly depends on the node activation probability p. For this reason, we will theoretically analyse the effect of node activation probability p and the result is presented in the following theorem.


The convergence rate of the proposed SGG algorithm increases with the increase of node activation probability.



Define

    f_s(p)=   ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
        +( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2


From Eqs. (<ref>) and (<ref>), it is clear that the expected reduction of the square is given by


    𝔼[a(l-1)-a^2]-𝔼[a(l)-a^2] =  1/2N∑_s = 1^N f_s(p)
 

Taking the partial derivative of f_s(p) with respect to p gives

    ∂ f_s(p)/∂ p=   ∑_m = 1^| 𝒩_s|p^m-1( 1 - p)^| 𝒩_s| - m-1( m -| 𝒩_s| p )∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
        -( 1 - p)^| 𝒩_s| -1∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2


For a specific m, the number of possible 𝒩_s,m is given by

    C_| 𝒩_s|^m = | 𝒩_s|!/m!( | 𝒩_s| - m)!
 
Now let us define m^* = ⌊| 𝒩_s| p⌋. Then, it is trivial that


    ( m -| 𝒩_s| p )∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
               ≥  ( m -| 𝒩_s| p )C_| 𝒩_s|^m/C_| 𝒩_s|^m^*∑_𝒩_s,m^*∈{𝒩_s,m^*}max_t ∈𝒩_s,m^*[ a_s( l - 1) - a_t( l - 1)]^2



    ∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
               ≤| 𝒩_s|/C_| 𝒩_s|^m^*∑_𝒩_s,m^*∈{𝒩_s,m^*}max_t ∈𝒩_s,m^*[ a_s( l - 1) - a_t( l - 1)]^2


Substituting Eqs. (<ref>) and (<ref>) into Eq. (<ref>) yields 

    ∂ f_s(p)/∂ p≥   ∑_m = 1^| 𝒩_s|p^m-1( 1 - p)^| 𝒩_s| - m-1( m -| 𝒩_s| p )C_| 𝒩_s|^m/C_| 𝒩_s|^m^*∑_𝒩_s,m^*∈{𝒩_s,m^*}max_t ∈𝒩_s,m^*[ a_s( l - 1) - a_t( l - 1)]^2
        -( 1 - p)^| 𝒩_s| -1| 𝒩_s|/C_| 𝒩_s|^m^*∑_𝒩_s,m^*∈{𝒩_s,m^*}max_t ∈𝒩_s,m^*[ a_s( l - 1) - a_t( l - 1)]^2
    
    =   ∑_m = 0^| 𝒩_s|mp^m( 1 - p)^| 𝒩_s| - mC_| 𝒩_s|^m/p(1-p)C_| 𝒩_s|^m^*∑_𝒩_s,m^*∈{𝒩_s,m^*}max_t ∈𝒩_s,m^*[ a_s( l - 1) - a_t( l - 1)]^2
       -∑_m = 0^| 𝒩_s|| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - mC_| 𝒩_s|^m/(1-p)C_| 𝒩_s|^m^*∑_𝒩_s,m^*∈{𝒩_s,m^*}max_t ∈𝒩_s,m^*[ a_s( l - 1) - a_t( l - 1)]^2

Since

    ∑_m = 0^| 𝒩_s|mC_| 𝒩_s|^mp^m( 1 - p)^| 𝒩_s| - m =| 𝒩_s|p
       ∑_m = 0^| 𝒩_s|C_| 𝒩_s|^mp^m( 1 - p)^| 𝒩_s| - m =1

evaluating Eq. (<ref>) using Eq. (<ref>) gives

    ∂ f_s(p)/∂ p≥0

where the equality holds if and only if a(l-1)=a̅. From Eqs. (<ref>) and (<ref>), we have


    ∂( 𝔼[a(l-1)-a^2]-𝔼[a(l)-a^2] )/∂ p =  1/2N∑_s = 1^N ∂f_s(p)/∂ p≥ 0
 

where the equality again holds if and only if a(l-1)=a̅.



Theorem 2 demonstrates that the proposed SGG algorithm provides faster convergence rate with higher node activation probability. This clearly reveals that SGG is a tradeoff between randomised gossip (p=0) and greedy gossip (p=1).  In viewing of this fact, it can be concluded that the proposed SGG algorithm provides great flexibility and well balance between communication cost and convergence performance. If enough resource is available for communication, then a higher node activation probability can be chosen to increase the convergence rate; otherwise, a relatively small value of p is desirable.





  §.§.§ Convergence Bound

To analyse the bound on the convergence rate, we will first derive the lower and upper convergence bounds of each SGG iteration. The result is established in the following lemma.

The expected reduction of the square error of each SGG iteration is lower and upper bounded by

    𝔼[a(l-1)-a^2]-𝔼[a(l)-a^2] ≥1/2N∑_s = 1^N 1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
 

    𝔼[a(l-1)-a^2]-𝔼[a(l)-a^2]  ≤1/2N∑_s = 1^N max_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
 
where the equality holds if and only if a(l-1)=a̅.



Note that the probability that 𝒩_s,m contains one specific node t ∈𝒩_s is

    (t ∈𝒩_s∪𝒩_s,m) = m/| 𝒩_s|
 

Let M_s,m^t be the number of occurrences of one specific node t ∈𝒩_s that appears in {𝒩_s,m}[ Here, we provide an example to explain the notation M_s,m^t. Consider 𝒩_s = { 1,2,3,4 } and m=2. From the definition of 𝒩_s,m, it can be concluded that 𝒩_s,2 in this example has C_4^2 = 6 possibilities, i.e., { 1,2}, { 1,3}, { 1,4},  { 2,3}, { 2,4}, { 3,4}. Therefore, we have {𝒩_s,2} = {{ 1,2}, { 1,3}, { 1,4}, { 2,3}, { 2,4}, { 3,4}} and the number of occurrences of each node index in {𝒩_s,2} is given by M_s,2^1=M_s,2^2=M_s,2^3=M_s,2^4=2/4C_4^2=3.],  which is given by

    M_s,m^t=(t ∈𝒩_s∪𝒩_s,m)C_| 𝒩_s|^m = m/| 𝒩_s| C_| 𝒩_s|^m
 
Using Eq. (<ref>), we obtain

    ∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2   ≥∑_𝒩_s,m∈{𝒩_s,m}1/m∑_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
        = 1/m∑_t ∈𝒩_sM_s,m^t[ a_s( l - 1) - a_t( l - 1)]^2
       = 1/| 𝒩_s|C_| 𝒩_s|^m∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2

Substituting Eq. (<ref>) into Eq. (<ref>) yields

    𝔼{[a_s(l-1)-a_t(l-1)]^2}≥   1/N∑_s = 1^N ∑_m = 1^| 𝒩_s|C_| 𝒩_s|^mp^m( 1 - p)^| 𝒩_s| - m1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
        +1/N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
     
      =    1/N∑_s = 1^N 1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2∑_m = 0^| 𝒩_s|C_| 𝒩_s|^mp^m( 1 - p)^| 𝒩_s| - m
     
      =    1/N∑_s = 1^N 1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2

where the equality holds if and only if a(l-1)=a̅.

Also, 𝔼{[a_s(l-1)-a_t(l-1)]^2} can be upper bounded by

    𝔼{[a_s(l-1)-a_t(l-1)]^2}≤   1/N∑_s = 1^N ∑_m = 1^| 𝒩_s|C_| 𝒩_s|^mp^m( 1 - p)^| 𝒩_s| - mmax_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
        +1/N∑_s = 1^N ( 1 - p)^| 𝒩_s|max_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
    
    =   1/N∑_s = 1^N max_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2∑_m = 0^| 𝒩_s|C_| 𝒩_s|^mp^m( 1 - p)^| 𝒩_s| - m
    
    =   1/N∑_s = 1^N max_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2

where the equality holds if and only if a(l-1)=a̅. Combining the preceding two equations completes the proof.



Note that the right hand side of inequality (<ref>) is the expected reduction of square error of randomised gossip and the right hand side of inequality (<ref>) is the expected reduction of square error of greedy gossip. Lemma 1 relates the performance of the proposed SGG to that of randomised gossip and greedy gossip. From Lemma 1, it is clear that the expected reduction of the square error of the proposed SGG algorithm is lower bounded by the randomised gossip and upper bounded by the greedy gossip. With this in mind, it can be concluded that the convergence rate of SGG is faster than the randomised gossip but slower than the greedy gossip in expectation.



Now, let us directly examine the convergence speed of the proposed SGG algorithm in terms of the ϵ-average time <cit.>,

    T_ave(ϵ)=sup _a(0) ≠ 0inf{l : Pr(a(l)-a/a(0)-a≥ϵ) ≤ϵ}


For notational convenience, let W^SGG(l) be the update transition matrix of implementing SGG at the kth iteration of SGG, e.g., a(l)=W^SGG(l) a(l-1), and W^SGG(1 : l)=∏_j=1^l W^SGG(j) be the successive application of l SGG updates. Likewise, we denote the one-step update matrices of randomised gossip as W^RG(l) and define the application of k successive randomised gossip updates  as W^RG(1 : l)=∏_j=1^l W^RG(j). We further denote W=𝔼[W^RG(l)] as the expected value of the one-step update matrix in the randomised gossip, and let λ_2(W) be  the second largest eigenvalue of W. The following theorem establishes the theoretical upper bound of ϵ-average time of the proposed SGG algorithm.


The ϵ-average time of the proposed SGG algorithm is upper bounded by

    T_ave^SGG(ϵ) ≤3 logϵ^-1/log(λ_2(W)-min_i ∈ [l]{β_i})^-1

where 

    β_l = η_l/𝔼[W^SGG(1 : l-1) a(0)-a^2]≥ 0

with η_l = 0 if a(l-1)=a̅, and otherwise,

    η_l =    1/2N∑_s = 1^N ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
        +1/2N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
       -1/2N∑_s=1^n1/|𝒩_s|∑_t ∈𝒩_s(a_s(l-1)-a_t(l-1))^2
  



The recursive reduction of the expected square error of randomised gossip satisfies <cit.>

    𝔼[W^RG(1 : l) a(0)-a^2] =𝔼[W^R G(1 : l-1) a(0)-a^2]
              -1/2N∑_s=1^n1/|𝒩_s|∑_t ∈𝒩_s(a_s(l-1)-a_t(l-1))^2
           ≤λ_2(W) 𝔼[W^R G(1 : l-1) a(0)-a^2]
 

By implementing one step randomised gossip after applying l-1 steps of SGG updates and using the relationship of Eq. (<ref>), we have 

    𝔼[W^RG(k) W^SGG(1 : l-1) a(0)-a^2]=𝔼[W^SGG(1 : l-1) a(0)-a^2]  
              -1/2N∑_s=1^n1/|𝒩_s|∑_t ∈𝒩_s(a_s(l-1)-a_t(l-1))^2
           ≤λ_2(W) 𝔼[W^SGG(1 : l-1) a(0)-a^2]
 

Using Eq. (<ref>), the convergence of the proposed SGG can be obtained as

    𝔼[W^SGG(1 : l) a(0)-a^2] 
       =𝔼[W^SGG(1 : l-1) a(0)-a^2] -1/2N∑_s=1^n1/|𝒩_s|∑_t ∈𝒩_s(a_s(l-1)-a_t(l-1))^2
            -1/2N∑_s = 1^N ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
            -1/2N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
            +1/2N∑_s=1^n1/|𝒩_s|∑_t ∈𝒩_s(a_s(l-1)-a_t(l-1))^2
        = 𝔼[W^SGG(1 : l-1) a(0)-a^2] -1/2N∑_s=1^n1/|𝒩_s|∑_t ∈𝒩_s(a_s(l-1)-a_t(l-1))^2 - η_l
 

According to Lemma 1, it is clear that η_l ≥ 0 and the equality holds if and only if a(l-1)=a̅. With this in mind, substituting Eq. (<ref>) into Eq. (<ref>) gives the convergence bound of the proposed SGG as

    𝔼[W^SGG(1 : l) a(0)-a^2] 
               ≤[λ_2(W)-β_l] 𝔼[W^SGG(1 : l-1) a(0)-a^2]
 

Repeatedly using Eq. (<ref>) yields

    𝔼[W^SGG(1 : l) a(0)-a^2]    ≤a(0)-a^2∏_i=1^l(λ_2(W)-β_i)
       ≤a(0)-a^2(λ_2(W)-min_i ∈ [l]{β_i})^l
 
where the equality holds if and only if a(l-1)=a̅.

Using Eq. (<ref>) with the help of Markov's inequality, we have

    (W^SGG(1 : l) a(0)-a/a(0)-a≥ϵ)    = (W^SGG(1 : l) a(0)-a^2/a(0)-a^2≥ϵ^2)
       ≤𝔼[W^SGG(1 : l) a(0)-a^2]/ϵ^2a(0)-a^2
       ≤ϵ^-2(λ_2(W)-min_i ∈ [l]{β_i})^l
 
which means that the ϵ-averaging time for SGG is upper bounded by

    T_ave^SGG(ϵ) ≤3 logϵ^-1/log(λ_2(W)-min_i ∈ [l]{β_i})^-1




Theorem 3 provides a theoretical upper bound for the ϵ-averaging time of the proposed SGG algorithm. Note from Eqs. (<ref>) and (<ref>)  that η_l and f_s(p) have the same monotonicity with respect to p. This verifies that the upper bound of the ϵ-averaging time becomes smaller with higher node activation probability.




 §.§ Convergence Rate Comparison

This subsection will characterise the upper bound of ϵ-averaging time of SGG algorithm with respect to other gossip algorithms to provide better understandings and insights of the proposed algorithm. Similar to previous subsection, we denote the one-step update matrices of greedy gossip as W^GG(l); and define the application of k successive greedy gossip updates  as W^GG(1 : l)=∏_j=1^l W^GG(j). The main results of this subsection are provided in the following theorem.


The upper bound of ϵ-average time, denoted as 𝒰(ϵ), of the proposed SGG algorithm is smaller than that of the randomised gossip, but larger than that of the greedy gossip, i.e.,

    𝒰_GG(ϵ) ≤𝒰_SGG(ϵ) ≤𝒰_RG(ϵ)
 



Implementing one step SGG after applying l-1 steps of greedy gossip updates and using Eq. (<ref>), we have 

    𝔼[W^SGG(l) W^GG(1 : l-1) a(0)-a^2] =𝔼[W^GG(1 : l-1) a(0)-a^2]  
             -1/2N∑_s = 1^N ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
              - 1/2N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
           ≤[λ_2(W)-β_l] 𝔼[W^GG(1 : l-1) a(0)-a^2]
 

Note that the recursive reduction of the expected square error of greedy gossip satisfies <cit.>

    𝔼[W^GG(1 : l) a(0)-a^2] =𝔼[W^GG(1 : l-1) a(0)-a^2]
              -1/2N∑_s = 1^N max_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
 

From Eqs. (<ref>) and (<ref>), the convergence rate of the greedy gossip can be represented as

    𝔼[W^GG(1 : l) a(0)-a^2] =𝔼[W^GG(1 : l-1) a(0)-a^2] 
             -1/2N∑_s = 1^N ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
             -1/2N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
             +1/2N∑_s = 1^N ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
             +1/2N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
             -1/2N∑_s = 1^N max_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
           ≤[λ_2(W)-β_l-ξ_l] 𝔼[W^GG(1 : l-1) a(0)-a^2]
 
where

    γ_l=   1/2N∑_s = 1^N max_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
       -1/2N∑_s = 1^N ∑_m = 1^| 𝒩_s|p^m( 1 - p)^| 𝒩_s| - m∑_𝒩_s,m∈{𝒩_s,m}max_t ∈𝒩_s,m[ a_s( l - 1) - a_t( l - 1)]^2
       -1/2N∑_s = 1^N ( 1 - p)^| 𝒩_s|1/| 𝒩_s|∑_t ∈𝒩_s[ a_s( l - 1) - a_t( l - 1)]^2
 

    ξ_l = γ_l/𝔼[W^GG(1 : l-1) a(0)-a^2]
 

It follows from Lemma 1 that ξ_l ≥ 0 and the equality holds if and only if a(l-1)=a̅. Repeatedly applying Eq. (<ref>) gives

    𝔼[W^GG(1 : l) a(0)-a^2]    ≤a(0)-a^2∏_i=1^l(λ_2(W)-β_i-ξ_i)
       ≤a(0)-a^2(λ_2(W)-min_i ∈ [l]{β_i}-min_i ∈ [l]{ξ_i})^l
 

Using Eq. (<ref>) with the help of Markov's inequality, we have

    (W^GG(1 : l) a(0)-a/a(0)-a≥ϵ)    = (W^GG(1 : l) a(0)-a^2/a(0)-a^2≥ϵ^2)
       ≤𝔼[W^GG(1 : l) a(0)-a^2]/ϵ^2a(0)-a^2
       ≤ϵ^-2(λ_2(W)-min_i ∈ [l]{β_i}-min_i ∈ [l]{ξ_i})^l
 
which means that the ϵ-averaging time for greedy gossip is upper bounded by

    T_ave^GG(ϵ) ≤3 logϵ^-1/log(λ_2(W)-min_i ∈ [l]{β_i}-min_i ∈ [l]{ξ_i})^-1


Recall that the upper bound for the ϵ-averaging time of randomised gossip is given by <cit.>

    T_ave^RG(ϵ) ≤3 logϵ^-1/logλ_2(W)^-1


Combining Eqs. (<ref>), (<ref>) and (<ref>), it is easy to verify Eq. (<ref>), which completes the proof.



It follows from Eq. (<ref>) that η_l=0 if p=0, which implies that 𝒰_SGG(ϵ) = 𝒰_RG(ϵ) with zero node activation probability. Additionally, we can easily verify that γ_l=0 with unity node activation probability, i.e., p=1. This means that the convergence bound of the proposed SGG algorithm becomes the same as that of the greedy gossip, i.e., 𝒰_SGG(ϵ) = 𝒰_GG(ϵ). These results also clearly demonstrate the tradeoff performance of SGG in terms of convergence bound and coincide with previous analysis.



Note that Theorem 4 only provides theoretical comparison of the upper bound of ϵ-averaging time for different gossip algorithms. However, extensive numerical analysis shows that the proposed algorithm achieves very comparable performance to that of the greedy gossip with significantly reduced communication burden.



It is straightforward to verify that both β_i and ξ_i are trivial and can be ignored for sparse networks, compared to λ_2(W). To see this, let us consider a special network: each local node can only communicate with one local node. Under this condition, one can imply that β_l=0 and ξ_l=0, which indicates that 𝒰_GG(ϵ) = 𝒰_SGG(ϵ) = 𝒰_RG(ϵ). This also means that the performance of both greedy gossip and the proposed SGG is very close to that of randomised gossip for sparse network and only provide significant convergence speed improvement for dense network. This fact will be illustrated via numerical investigations in the next section.





§ NUMERICAL SIMULATIONS



This section evaluates performance the proposed SGG algorithm with comparison to randomised gossip and greedy gossip using Monte-Carlo simulations.  

As stated in <cit.>, the random geometric topology is widely-accepted as a general model to represent the connectivity of wireless networks for the purpose of analysing the characteristics of network-wide computation algorithms. For this reason, we choose the random geometric graph with 200 nodes as the network connection topology in performance evaluation. For the random geometric network, each agent is randomly placed inside a unit square region and two nodes are connected if their relative distance is less than r(N)=√(dlog N/N) with d being a scaling factor. It is clear that the random geometric network with higher d provides dense connection while with lower d represents sparse network topology. An example of the random geometric network topology with d=2 is presented in Fig. <ref>. Similar to <cit.>, we utilise four different initial conditions to examine the performance of all algorithms: (1) Gaussian bumps; (2) linear-varying field; (3) spike field; and (4) uniform random field. The distributions of Gaussian bumps and linear-varying field are shown in Fig. <ref>. The spike field  initialises all local agents by setting the value of one node as 1 and all others as 0. For the uniform random field, all nodes are initialised with a random value that is drawn from a normal distribution 𝒩(0,1). For performance evaluation of all tested gossip algorithms, we check the expected reduction of the relative error a( L ) - a̅/a( 0 ) - a̅ over 1000 Monte-Carlo runs.







 §.§ Effect of Communication Iterations


In gossip-based distributed computation, information transmission via multiple rounds of communication among locally-connected nodes are required and the performance highly depends on the number of iterations, L. In order to investigate the effect of the parameter L on the convergence speed, Monte-Carlo comparisons of different gossip algorithms are carried out with respect to different number of iterations. The main objective of the performance comparison in this subsection is to validate the analysis results of the gossip algorithm, which are presented in Sec. <ref>. The simulation results of average convergence error obtained from Monte-Carlo simulations are depicted in Fig. <ref>. In the simulations, the node activation probability for implementing SGG and the scaling factor d that models the network connectivity are set as p=0.5 and d=2, respectively. 

From Fig. <ref>, it can be noted that randomised gossip has the lowest convergence speed among these three different gossip algorithms. As greedy gossip process picks up the optimal communication path for every local node at each gossip iteration, it exhibits the fastest convergence rate at the expense of high communication burden. The proposed SGG only leverages a suboptimal communication path, e.g., performing greedy node selection within a  set of randomly-chosen active nodes. Therefore, the SGG provides tradeoff convergence performance between randomised gossip and greedy gossip. As the probability threshold in selecting the active node is p=0.5, the proposed algorithm only requires half communication burden in the average sense at each iteration, compared to the greedy gossip. These results conform with the analytic findings presented in Sec. <ref>. Interestingly, the performance of SGG is very comparable to that of the greedy gossip and its convergence rate is much faster than that of the randomised gossip even with p=0.5. 





 §.§ Effect of Node Activation Probability


Now, let us investigate the effect of the node activation probability on the tradeoff performance of the proposed SGG algorithm. For this purpose, the number of gossip iterations in each Monte-Carlo run and the scaling factor are set as L=1000 and d=2, respectively. Fig. <ref> presents the comparison results of average convergence error for different gossip algorithms with different node activation probabilities obtained from Monte-Carlo simulations.  

From Fig. <ref>, it can be observed that the greedy gossip provides the best convergence performance among all the tested algorithms. This can be attributed to the fact that the greedy gossip process finds the optimal local node for average computation. However, as stated before, this achievement requires each local node to communicate with all its connected neighbours at each iteration. As a comparison, the proposed SGG offers great flexibility and well balance between communication cost and convergence performance introduced by the stochastic sampling strategy. With the increase of node activation probability, SGG provides improved convergence performance and converges to that of greedy gossip when p=1. If the local node cannot provide enough bandwidth for communication, a relatively small node activation probability can be selected to save the communication cost. When p=0, the proposed algorithm becomes identical to randomised gossip. The results confirm that the proposed SGG algorithm is a generalised version of the randomised and greedy gossip algorithms. 





 §.§ Effect of Network Sparsity


Except for the node activation probability, another important factor that affects the performance of the proposed SGG algorithm is the network sparsity or connectivity. For this reason, this subsection empirically analyses the performance of difference gossip algorithms with different network sparsity. Fig. <ref> presents the comparison results of average convergence error for different gossip algorithms with different scaling factors obtained from Monte-Carlo simulations. In all simulation runs, the number of gossip iterations in each Monte-Carlo run and the node activation probability are set as L=1000 and p=0.5, respectively. 

It can be observed from Fig. <ref> that the performance discrepancy among all tested gossip algorithms is not much when for sparse network, i.e., smaller d. With the increase of the scaling factor d, both greedy gossip and the proposed SGG significantly improve the convergence performance. The reason of this fact is clear: the randomised gossip process randomly selects a local node in communication while the other two gossip algorithms either find an optimal or sub-optimal path in information exchange. Therefore, dense networks provide higher possibility to improve the convergence speed with an optimised communication path.







§ CONCLUSIONS



This paper proposed a sample greedy gossip algorithm for average computation over a partially connected network. Rigorous convergence analysis of the proposed sample greedy gossip algorithm is carried out to support its applications. The empirical investigation demonstrates the validity of the theoretical analysis results. Also, theoretical and numerical analysis indicates that the proposed algorithm can be viewed as a generalised version of the randomised and greedy gossip algorithms. The prominent feature of the proposed algorithm lies in that it allows tradeoff  between convergence speed and communication burden: our algorithm shows faster convergence speed, compared to the randomised gossip, and requires less communication burden, compared to the greedy gossip. 


IEEEtran


