Randomized Gossiping with Unreliable Communication: Dependent or Independent Node Updates
2012 (English)In: 2012 IEEE 51st Annual Conference on Decision and Control (CDC), IEEE conference proceedings, 2012, 4846-4851 p.Conference paper (Refereed)
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.
, IEEE Conference on Decision and Control. Proceedings, ISSN 0191-2216
Consensus, Convergence analysis, Gossip algorithms, Unreliable communication
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-111453DOI: 10.1109/CDC.2012.6426729ISI: 000327200405030ScopusID: 2-s2.0-84874264946ISBN: 978-1-4673-2064-1OAI: oai:DiVA.org:kth-111453DiVA: diva2:586416
51st IEEE Conference on Decision and Control, CDC 2012; Maui, HI; United States; 10 December 2012 through 13 December 2012
QC 201302152013-02-152013-01-112013-12-19Bibliographically approved