Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Randomized Gossiping with Unreliable Communication: Dependent or Independent Node Updates
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.
KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-9940-5929
2012 (English)In: 2012 IEEE 51st Annual Conference on Decision and Control (CDC), IEEE conference proceedings, 2012, 4846-4851 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper studies an asynchronous randomized gossip algorithm under unreliable communication. At each instance, two nodes are selected to meet with a given probability. When nodes meet, two unreliable communication links are established with communication in each direction succeeding with a time-varying probability. It is shown that two particularly interesting cases arise when these communication processes are either perfectly dependent or independent. Necessary and sufficient conditions on the success probability sequence are proposed to ensure almost sure consensus or ?-consensus. Weak connectivity is required when the communication is perfectly dependent, while double connectivity is required when the communication is independent. Moreover, it is proven that with odd number of nodes, average preserving turns from almost forever (with probability one for all initial conditions) for perfectly dependent communication, to almost never (with probability zero for almost all initial conditions) for the independent case. This average preserving property does not hold true for general number of nodes. These results indicate the fundamental role the node interactions have in randomized gossip algorithms.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2012. 4846-4851 p.
Series
IEEE Conference on Decision and Control. Proceedings, ISSN 0191-2216
Keyword [en]
Consensus, Convergence analysis, Gossip algorithms, Unreliable communication
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-111453DOI: 10.1109/CDC.2012.6426729ISI: 000327200405030Scopus ID: 2-s2.0-84874264946ISBN: 978-1-4673-2064-1 (print)OAI: oai:DiVA.org:kth-111453DiVA: diva2:586416
Conference
51st IEEE Conference on Decision and Control, CDC 2012; Maui, HI; United States; 10 December 2012 through 13 December 2012
Note

QC 20130215

Available from: 2013-02-15 Created: 2013-01-11 Last updated: 2013-12-19Bibliographically approved

Open Access in DiVA

fulltext(368 kB)212 downloads
File information
File name FULLTEXT02.pdfFile size 368 kBChecksum SHA-512
8aa90307f9b90182e95765f2a938b77101f11a39ee52b75670e12394f48e12890c9ab0eae660359a693d7ed593f3065375e0c55926ab2d11485c813301803d7b
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusIEEEXplore

Authority records BETA

Johansson, Karl Henrik

Search in DiVA

By author/editor
Shi, GuodongJohansson, MikaelJohansson, Karl Henrik
By organisation
Automatic ControlACCESS Linnaeus Centre
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 212 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 47 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf