On Distributed Averaging Algorithms and Quantization Effects

被引:380
作者
Nedic, Angelia [1 ]
Olshevsky, Alex [2 ]
Ozdaglar, Asuman [2 ]
Tsitsiklis, John N. [2 ]
机构
[1] Univ Illinois, Ind & Enterprise Syst Engn Dept, Urbana, IL 61801 USA
[2] MIT, Dept Elect Engn & Comp Sci, Informat & Decis Syst Lab, Cambridge, MA 02139 USA
基金
美国国家科学基金会;
关键词
Decentralized and distributed control; multiagent systems; CONSENSUS; AGENTS;
D O I
10.1109/TAC.2009.2031203
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider distributed iterative algorithms for the averaging problem over time-varying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is available, and on the degradation of performance when only quantized information is available. We study a large and natural class of averaging algorithms, which includes the vast majority of algorithms proposed to date, and provide tight polynomial bounds on their convergence time. We also describe an algorithm within this class whose convergence time is the best among currently available averaging algorithms for time-varying topologies. We then propose and analyze distributed averaging algorithms under the additional constraint that agents can only store and communicate quantized information, so that they can only converge to the average of the initial values of the agents within some error. We establish bounds on the error and tight bounds on the convergence time, as a function of the number of quantization levels.
引用
收藏
页码:2506 / 2517
页数:12
相关论文
共 23 条
[1]  
Bertsekas D. P., 1989, Parallel and distributed computation
[2]  
Numerical methods
[3]  
Bliman PA, 2005, IEEE DECIS CONTR P, P7066
[4]  
Blondel VD, 2005, IEEE DECIS CONTR P, P2996
[5]  
Boyd S, 2005, IEEE INFOCOM SER, P1653
[6]  
Carli R., 2007, P IEEE AM CONTROL C, P4189
[7]  
CARLI R, 2005, 32 POL TOR
[8]   Analysis and design of distributed algorithms for χ-consensus [J].
Cortes, Jorge .
PROCEEDINGS OF THE 45TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14, 2006, :3363-3368
[9]   DYNAMIC LOAD BALANCING FOR DISTRIBUTED MEMORY MULTIPROCESSORS [J].
CYBENKO, G .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1989, 7 (02) :279-301
[10]   Toeplitz and Circulant Matrices: A Review [J].
Gray, Robert M. .
FOUNDATIONS AND TRENDS IN COMMUNICATIONS AND INFORMATION THEORY, 2006, 2 (03) :155-239