Search

Gossip protocols are popular methods for average consensus problems in distributed computing. We prove new convergence guarantees for a variety of such protocols, including path, clique, and synchronous pairwise gossip. These arise by exploiting the connection between these protocols and the block randomized Kaczmarz method for solving linear systems. Moreover, we extend existing convergence results for block randomized Kaczmarz to allow for a more general choice of blocks, rank-deficient systems, and provide a tighter convergence rate guarantee. Previous results for block randomized Kaczmarz assumed blocks formed a paving of the systems; our analysis, contrary to the title of our paper, generalizes to a broader class of blocks that we call coverings. We furthermore apply this analysis to inconsistent consensus models and obtain similar guarantees. An extensive empirical analysis of these methods is provided for a variety of synthetic and real networks. [ABSTRACT FROM AUTHOR]

In this work we present a new framework for the analysis and design of randomized gossip algorithms for solving the average consensus problem. We show how classical randomized iterative methods for solving linear systems can be interpreted as gossip algorithms when applied to special systems encoding the underlying network and explain in detail their decentralized nature. Our general framework recovers a comprehensive array of well-known gossip algorithms as special cases, including the pairwise randomized gossip algorithm and path averaging gossip, and allows for the development of provably faster variants. The flexibility of the new approach enables the design of a number of new specific gossip methods. For instance, we propose and analyze novel block and the first provably accelerated randomized gossip protocols, and dual randomized gossip algorithms. From a numerical analysis viewpoint, our work is the first that explores in depth the decentralized nature of randomized iterative methods for linear systems and proposes them as methods for solving the average consensus problem. We evaluate the performance of the proposed gossip protocols by performing extensive experimental testing on typical wireless network topologies. [ABSTRACT FROM AUTHOR]

The approximation of stable linear time-invariant (LTI) systems is studied for the Paley–Wiener space \mathcal PW\pi ^{1} of bandlimited functions with absolutely integrable Fourier transform. For pointwise sampling, it is known that there exist stable LTI systems and functions such that the approximation process diverges, regardless of the oversampling factor. Recently, it was shown that the divergence can be overcome by using more general measurement functionals that are based on a complete orthonormal system. However, this approach requires the approximation process to have an increased bandwidth. In this paper, a two channel approximation process is presented that is uniformly convergent for all stable LTI systems and all functions in \mathcal PW\pi ^{1} . An advantage of the two channel approach compared with the one channel approach is the reduction of the approximation bandwidth, which can be exactly the same as the input function bandwidth. [ABSTRACT FROM AUTHOR]

Any sequence of uniformly bounded N\times N Hermitian Toeplitz matrices \{H_{N}\} is asymptotically equivalent to a certain sequence of N\times N circulant matrices \CN\ derived from the Toeplitz matrices in the sense that \left \|{HN- CN }\right \|F = o(\sqrt {N}) as $N\rightarrow \infty $ . This implies that certain collective behaviors of the eigenvalues of each Toeplitz matrix are reflected in those of the corresponding circulant matrix and supports the utilization of the computationally efficient fast Fourier transform (instead of the Karhunen-Loève transform) in applications like coding and filtering. In this paper, we study the asymptotic performance of the individual eigenvalue estimates. We show that the asymptotic equivalence of the circulant and Toeplitz matrices implies the individual asymptotic convergence of the eigenvalues for certain types of Toeplitz matrices. We also show that these estimates asymptotically approximate the largest and smallest eigenvalues for more general classes of Toeplitz matrices. [ABSTRACT FROM AUTHOR]