Source-linked AI summary
Gossip consensus algorithms via quantized communication
Ruggero Carli, Fabio Fagnani, Paolo Frasca, Sandro Zampieri
TL;DR
The paper examines average consensus with quantized communication in gossip networks, asking which quantizer and update strategy best address finite-message exchange. It compares deterministic and probabilistic quantization with three update rules and analyzes their convergence and average-preservation properties. The results show finite-time consensus for the totally quantized rule, while compensating updates preserve the initial average without guaranteeing exact consensus.
Problem
The paper addresses how gossip agents can achieve average consensus when digital links provide quantized messages instead of precise neighbor states.
Method
The paper compares deterministic and probabilistic uniform quantizers and analyzes three update rules that use quantized and, in some cases, exact local-state information.
Results
The totally quantized rule reaches consensus almost surely in finite time with either quantizer, while the compensating rule preserves the initial average but does not guarantee consensus.
Takeaways & Limitations
Quantized gossip can approach consensus, but update-rule choice determines the trade-off between finite-time consensus and preservation of the initial average.
Takeaways & Limitations
The paper does not pursue convergence-time bounds because existing Markov-chain bounds are usually very conservative in their dependence on the number of agents.
Abstract
from arXiv · showhide
This paper considers the average consensus problem on a network of digital links, and proposes a set of algorithms based on pairwise ''gossip'' communications and updates. We study the convergence properties of such algorithms with the goal of answering two design questions, arising from the literature: whether the agents should encode their communication by a deterministic or a randomized quantizer, and whether they should use, and how, exact information regarding their own states in the update.
1 Introduction
The paper studies average consensus over digital communication links, where quantization and network constraints complicate information exchange. It focuses on gossip algorithms and compares deterministic versus probabilistic quantization while examining the role of exact local-state information.
- Average consensus requires agents starting from different estimates to agree on their initial average.
- Communication constraints include bandwidth limits, interference, erasures, packet losses, noise, and delays represented through the network graph.
- Gossip communication randomly selects a pair of agents to communicate and average their states, reducing communications and avoiding some fixed-topology issues.
- The paper addresses quantized communication among real-valued agents, rather than consensus among agents whose states are themselves quantized.
- Random time-dependence in gossip motivates probabilistic analysis and complicates the design of incremental or adaptive quantizers.
Statement of contributions
The paper compares quantizer types and three gossip update rules for consensus with finite-message communication. Its analyses characterize convergence, average preservation, and the trade-off between exact consensus and fidelity to the initial average.
- The paper compares deterministic and probabilistic uniform quantizers alongside three update rules using different amounts of exact local-state information.
- Two analyses are used: mean squared error with asymptotic convergence for compensating probabilistic quantization, and Markov-chain symbolic dynamics for finite-time convergence elsewhere.
- The totally quantized rule reaches consensus almost surely in finite time with either quantizer, but may fail to preserve the initial average.
- The compensating rule preserves the initial average at every iteration but does not guarantee exact consensus, instead bringing states close to average consensus.
2 Problem statement
The paper formulates gossip consensus over digital links, where agents receive quantized estimates rather than exact neighbor states. It defines deterministic and probabilistic quantizers and introduces totally quantized, partially quantized, and compensating updates.
- In the standard gossip algorithm, a randomly selected edge connects two agents that average their states on an undirected connected graph.
- The standard gossip update preserves the average because its update matrix is symmetric and doubly stochastic.
- Digital links replace precise neighbor states with symbolic messages, from which agents construct quantized state estimates.
- 2.1 Quantizers: A quantizer maps continuous states into a finite or countable discrete message alphabet; the paper focuses on uniform quantizers.
- 2.1 Quantizers: The deterministic quantizer maps each real number to its nearest integer, with quantization error bounded by 1.
- 2.1 Quantizers: The probabilistic quantizer randomly maps a real number to neighboring integers and also has quantization error bounded by 1.
- 2.2 Update rules: The totally quantized rule updates communicating agents using only their received estimates, whereas the partially quantized rule uses their exact real-valued states.
- 2.2 Update rules: The compensating rule combines exact and quantized self-information to address the average-preservation drawback of the other update rules.
3 Compensating update
The compensating update is analyzed through symbolic dynamics of quantized states, showing finite-time convergence to a two-level configuration. Its deterministic variant reaches consensus within a quantization-related error, while the probabilistic variant has bounded asymptotic mean-square error.
- Symbolic analysis: The analysis converts real-valued state dynamics into symbolic dynamics using n_i(t) = ⌊2x_i(t)⌋.This yields an iterative system involving only symbolic signals and enables asymptotic analysis of the original states.
- Deterministic quantizer: Almost surely, the deterministic compensating update eventually places the symbolic state in the recurrent set R.Theorem 3.2 states that this occurs after some finite random time for every initial symbolic state.
- Symbolic analysis: The symbolic process is a finite-state Markov chain whose recurrent set is invariant and reachable with positive probability.The proof uses independent edge selections, bounded state ranges, and monotonicity arguments to establish finite-time entry into the recurrent set.
- Deterministic quantizer: The deterministic update uses only quantized information and reaches consensus at a value within two consecutive quantization bins.The update does not preserve the initial average in general, and its convergence follows from the symbolic-state result.
- Deterministic quantizer: The adapted KBS algorithm guarantees finite-time consensus up to error one after initially quantizing the real states.Because initial quantization has worst-case error 1/2, the resulting bound is stated relative to the initial average.
- Probabilistic quantizer: The probabilistic compensating rule is evaluated by mean-square analysis, with asymptotic error bounded independently of agent count, graph topology, and edge-selection probabilities.The cost depends on the selection probabilities, while the reported bound is smaller than the quantization-bin size and does not require strict consensus.
4 Totally quantized update
The totally quantized update drives all agents almost surely to consensus at an integer value, using only quantized information. Deterministic and probabilistic quantizers both converge, but only probabilistic quantization preserves the average in expectation.
- Update rule: The update uses only quantized information, unlike the alternative that combines exact and quantized state information.This makes its analysis somewhat easier.
- Deterministic quantizer: The symbolic dynamics updates both selected agents to the same value through g2, with consensus states represented by A = {y ∈ Z^N | ∃α ∈ Z such that y = 2α1}.The dynamics is analyzed as a Markov process on finitely many states.
- Deterministic quantizer: Almost surely, the deterministic totally quantized algorithm reaches an integer consensus in finite time and remains there.The convergence follows from invariance, finite-state Markovianity, and positive-probability reachability of A.
- Probabilistic quantizer: Almost surely, the probabilistic totally quantized algorithm also reaches consensus at an integer value.Its random edge selection and random quantization require two sources of randomness in the analysis.
- Average deviation: The deterministic and probabilistic strategies generally do not preserve the initial average, although probabilistic quantization preserves it in expectation.The paper compares their deviation z from the initial average using simulations on increasingly large complete graphs.
- Average deviation: Simulations suggest that a deterministic correction reduces average perturbation but is less effective than randomization.Figure 1 reports averages over 1000 runs and substantial variance in the plotted values.
5 Partially quantized update
The partially quantized update is analyzed through symbolic dynamics. Deterministic quantization yields bounded disagreement and a bounded deviation from the initial average, while probabilistic quantization converges almost surely with the limiting integer having the initial average as its expectation.
- Deterministic quantizer: The partially quantized update does not preserve the continuous average, but deterministic quantization induces the same symbolic dynamics as the compensating strategy.This supports a convergence result with a larger possible deviation from the initial average.
- Deterministic quantizer: Eventually, deterministic quantization guarantees |x_i(t) − x_j(t)| ≤ 1 for all agents and times t ≥ T_con.The symbolic states preserve their pairwise update sum even though the continuous states do not preserve the average.
- Deterministic quantizer: The resulting continuous states satisfy ∥x(t) − x_ave(0)1∥_∞ ≤ 2.This bound follows from the disagreement bound and preservation of the symbolic-state average.
- Probabilistic quantizer: With probabilistic quantization, the symbolic process is connected to the deterministic dynamics g1 through random correction terms.The correction terms depend on each selected agent’s fractional state and quantizer outcome.
- Probabilistic quantizer: The limiting integer α has expectation E[α] = x_ave(0).Thus probabilistic quantization restores average preservation in expectation at the limiting consensus value.
- Probabilistic quantizer: Almost surely, the probabilistic partially quantized dynamics reaches the consensus symbolic set A and then converges to an integer α for every agent.After entering A, the remaining deterministic dynamics converges to α.
6 Discussion
The paper’s three quantized gossip rules differ in how they use exact self-state information and in their preservation and convergence properties. The discussion extends the quantizer analysis, notes limits of current convergence-speed understanding, and identifies weighted gains as a possible extension.
- Summary of results: The compensating rule preserves the global average but prevents exact consensus, whereas all proposed algorithms approach consensus up to quantizer precision.The totally quantized rule with a deterministic quantizer is the exception for small deviations from the initial average.
- Quantizer generality: Deterministic uniform-quantizer results extend to rounding-down and rounding-up quantizers through suitable symbolic dynamics.The rounding-up analysis follows from ⌈x⌉= −⌊−x⌋.
- Quantizer generality: Randomized uniform quantizers support the stated results for any probability p ∈(0, 1), while the mean-squared-error and Theorem 5.2 results require unbiasedness.The proof extension uses the same probabilistic structure as the original quantizer.
- Weighted averaging: The analysis fixes consensus gains at 1/2, while extensions to general weights are considered possible despite technical difficulties in defining and analyzing the corresponding symbolic dynamics.The compensating rule’s deterministic-quantizer extension has been proven for ε ∈(0, 1/2].
- Speed of convergence: Figure 2 compares squared distance from the initial average for the three proposed algorithms and standard gossip over 10 runs on a 20-node geometric graph.The simulations use random uniform initial states in [−100, 100].
- Speed of convergence: Quantized gossip eventually reaches a finite-time limit set because granularity effects become non-negligible, rather than maintaining the asymptotic exponential behavior known for non-quantized gossip.The paper leaves open a sharp characterization of when granularity matters and the convergence speed during that transition.