Change search
ReferencesLink to record
Permanent link

Direct link
Finite-Time Convergent Gossiping
KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-9940-5929
2016 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 24, no 5, 2814-2826 p.Article in journal (Refereed) Published
Abstract [en]

Gossip algorithms are widely used in modern distributed systems, with applications ranging from sensor networks and peer-to-peer networks to mobile vehicle networks and social networks. A tremendous research effort has been devoted to analyzing and improving the asymptotic rate of convergence for gossip algorithms. In this work we study finite-time convergence of deterministic gossiping. We show that there exists a symmetric gossip algorithm that converges in finite time if and only if the number of network nodes is a power of two, while there always exists an asymmetric gossip algorithm with finite-time convergence, independent of the number of nodes. For n = 2(m) nodes, we prove that a fastest convergence can be reached in nm = n log(2) n node updates via symmetric gossiping. On the other hand, under asymmetric gossip among n = 2(m) + rnodes with 0 <= r <= 2(m), it takes at least mn + 2r node updates for achieving finite-time convergence. It is also shown that the existence of finite-time convergent gossiping often imposes strong structural requirements on the underlying interaction graph. Finally, we apply our results to gossip algorithms in quantum networks, where the goal is to control the state of a quantum system via pairwise interactions. We show that finite-time convergence is never possible for such systems.

Place, publisher, year, edition, pages
IEEE, 2016. Vol. 24, no 5, 2814-2826 p.
Keyword [en]
Gossip algorithms, finite-time convergence, computational complexity, quantum algorithms
National Category
Control Engineering
URN: urn:nbn:se:kth:diva-196988DOI: 10.1109/TNET.2015.2484345ISI: 000386238600018ScopusID: 2-s2.0-84944535007OAI: diva2:1055925

QC 20161213

Available from: 2016-12-13 Created: 2016-11-28 Last updated: 2016-12-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Johansson, MikaelJohansson, Karl Henrik
By organisation
Automatic ControlACCESS Linnaeus Centre
In the same journal
IEEE/ACM Transactions on Networking
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 11 hits
ReferencesLink to record
Permanent link

Direct link