Quantized consensus. (English) Zbl 1123.93090

Summary: We study the distributed averaging problem on arbitrary connected graphs, with the additional constraint that the value at each node is an integer. This discretized distributed averaging problem models several problems of interest, such as averaging in a network with finite capacity channels and load balancing in a processor network.
We describe simple randomized distributed algorithms which achieve consensus to the extent that the discrete nature of the problem permits. We give bounds on the convergence time of these algorithms for fully connected networks and linear networks.


93E25 Computational methods in stochastic control (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
93E03 Stochastic systems in control theory (general)
Full Text: DOI


[1] Aiello, W., Awerbuch, B., Maggs, B., & Rao, S. (1993). Approximate load balancing on dynamic and asynchronous networks. In Proceedings of the 25th ACM symposium on theory of computing (pp. 632-641). · Zbl 1310.68233
[2] Akar, M., & Shorten, R. (2006). Time synchronization for wireless sensor networks. In Proceedings of MTNS (pp. 221-225).
[3] Aspnes, J.; Herlihy, M.; Shavit, N., Counting networks, Journal of the ACM, 41, 5, 1020-1048, (1994) · Zbl 0813.68050
[4] Bertsekas, D.P.; Tsitsiklis, J.N., Parallel and distributed computation: numerical methods, (1997), Athena Scientific Belmont, MA
[5] Blondel, V. D., Hendrickx, J. M., Olshevsky, A., & Tsitsiklis, J. N. (2005). Convergence in multiagent coordination, consensus, and flocking. In Proceedings of IEEE conference on decision and control (pp. 2996-3000).
[6] Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2005). Gossip algorithms: Design, analysis and applications. In Proceedings of IEEE Infocom (pp. 1653-1664).
[7] Carli, R., Fagnani, F., Speranzon, A., & Zampieri, S. (2006). Communication constraints in coordinated consensus problems. In Proceedings of American control conference (pp. 4189-4194). · Zbl 1112.70311
[8] Cybenko, G., Dynamic load balancing for distributed memory multiprocessors, Journal of parallel and distributed computing, 7, 271-301, (1989)
[9] Ghosh, B.; Leighton, F.T.; Maggs, B.M.; Muthukrishnan, S.; Plaxton, C.G.; Rajaraman, R., Tight analyses of two local load balancing algorithms, SIAM journal of computing, 29, 1, 29-64, (1999) · Zbl 0937.68158
[10] Ghosh, B.; Muthukrishnan, S., Dynamic load balancing by random matchings, Journal of computer and system sciences, 53, 357-370, (1996) · Zbl 0864.68005
[11] Giridhar, A., & Kumar, P. R. (2006). Distributed clock synchronization over wireless networks: Algorithms and analysis. In Proceedings of IEEE conference on decision and control (pp. 4915-4920).
[12] Hartfiel, D.J., Markov set-chains, (1998), Springer Berlin · Zbl 0778.60048
[13] Hartfiel, D.J., Nonhomogenous matrix products, (2002), World Scientific Singapore
[14] Herlihy, M.; Tirthapura, S., Self-stabilizing smoothing and balancing networks, Distributed computing, 18, 5, 345-357, (2005) · Zbl 1266.68056
[15] Houle, M.E.; Symvonis, A.; Wood, D.R., Dimension-exchange algorithms for token distribution on tree-connected architectures, Journal of parallel and distributed computing, 64, 591-605, (2004) · Zbl 1101.68413
[16] Houle, M.E.; Tempero, E.; Turner, G., Optimal dimension-exchange token distribution on complete binary trees, Theoretical computer science, 220, 363-376, (1999) · Zbl 0954.68018
[17] Jadbabaie, A.; Lin, J.; Morse, A.S., Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE transactions on automatic control, 48, 6, 988-1001, (2003) · Zbl 1364.93514
[18] Kempe, D., Dobra, A., & Gehrke, J. (2003). Gossip-based computation of aggregate information. In IEEE symposium on the foundations on computer science (pp. 482-491).
[19] Meyer, C., Matrix analysis and applied linear algebra, (2001), SIAM Philadelphia, PA
[20] Moreau, L., Stability of multi-agent systems with time dependent communication links, IEEE transactions on automatic control, 50, 2, 169-182, (2005) · Zbl 1365.93268
[21] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge University Press Cambridge, UK · Zbl 0849.68039
[22] Olfati-Saber, R.; Murray, R.M., Consensus problems in networks of agents with switching topology and time-delays, IEEE transactions on automatic control, 49, 9, 1520-1533, (2004) · Zbl 1365.93301
[23] Poor, H.V., An introduction to signal detection and estimation, (1994), Springer New York · Zbl 0811.94001
[24] Rabani, Y., Sinclair, A., & Wanka, R. (1998). Local divergence of markov chains and the analysis of iterative load-balancing schemes. In Proceedings of IEEE conference on foundations of computer science (pp. 694-705).
[25] Savkin, A.V., Coordinated collective motion of groups of autonomous robots: analysis of Vicsek’s model, IEEE transactions on automatic control, 49, 6, 981-983, (2004) · Zbl 1365.93327
[26] Subramanian, R., & Scherson, I. D. (1994). An analysis of diffusive load balancing. In Proceedings of sixth ACM SPAA (pp. 220-225).
[27] Tsitsiklis, J. N. (1984). Problems in decentralized decision making and computation. Ph.D. thesis. Department of Electrical Engineering and Computer Science, MIT. 〈http://web.mit.edu/jnt/www/PhD-84-jnt.pdf〉.
[28] Xiao, L.; Boyd, S., Fast linear iterations for distributed averaging, Systems and control letters, 53, 1, 65-78, (2004) · Zbl 1157.90347
[29] Xiao, L., Boyd, S., & Lall, S. (2005). A scheme for robust distributed sensor fusion based on average consensus. In Proceedings of conference on information processing in sensor networks (pp. 63-70).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.