Tree Codes Improve Convergence Rate of Consensus Over Erasure Channels

Details Tree Codes Improve Convergence Rate of Consensus Over Erasure Channels Tree Codes Improve Convergence Rate of Consensus Over Erasure Channels

2012-04-02

arxiv.org/abs/1204.0301v1

Mathematics

Optimization and Control

Scientific paper

We study the problem of achieving average consensus between a group of agents over a network with erasure links. In the context of consensus problems, the unreliability of communication links between nodes has been traditionally modeled by allowing the underlying graph to vary with time. In other words, depending on the realization of the link erasures, the underlying graph at each time instant is assumed to be a subgraph of the original graph. Implicit in this model is the assumption that the erasures are symmetric: if at time t the packet from node i to node j is dropped, the same is true for the packet transmitted from node j to node i. However, in practical wireless communication systems this assumption is unreasonable and, due to the lack of symmetry, standard averaging protocols cannot guarantee that the network will reach consensus to the true average. In this paper we explore the use of channel coding to improve the performance of consensus algorithms. For symmetric erasures, we show that, for certain ranges of the system parameters, repetition codes can speed up the convergence rate. For asymmetric erasures we show that tree codes (which have recently been designed for erasure channels) can be used to simulate the performance of the original "unerased" graph. Thus, unlike conventional consensus methods, we can guarantee convergence to the average in the asymmetric case. The price is a slowdown in the convergence rate, relative to the unerased network, which is still often faster than the convergence rate of conventional consensus algorithms over noisy links.

Affiliated with

Also associated with

No associations

Rating

Tree Codes Improve Convergence Rate of Consensus Over Erasure Channels 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 Tree Codes Improve Convergence Rate of Consensus Over Erasure Channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree Codes Improve Convergence Rate of Consensus Over Erasure Channels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-509246