Computer Science – Information Theory
Scientific paper
2012-03-27
Computer Science
Information Theory
Scientific paper
In this paper, we study 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 $\epsilon$-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.
Johansson Karl Henrik
Johansson Mikael
Shi Guodong
No associations
LandOfFree
Randomized Gossip Algorithm with Unreliable Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Randomized Gossip Algorithm with Unreliable Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Gossip Algorithm with Unreliable Communication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-641302