American Institute of Mathematical Sciences

Advanced
June  2011, 6(2): 329-349. doi: 10.3934/nhm.2011.6.329

Consensus and synchronization in discrete-time networks of multi-agents with stochastically switching topologies and time delays

Wenlian Lu 1, , Fatihcan M. Atay 2, and  Jürgen Jost 2,

1. 

Center for Computational Systems Biology, Laboratory of Mathematics for Nonlinear Sciences, School of Mathematical Sciences, Fudan University, Shanghai, 200433
2. 

Max Planck Institute for Mathematics in theSciences, Inselstr. 22, 04103 Leipzig, Germany

Received  August 2010 Revised  February 2011 Published  May 2011

We analyze stability of consensus algorithms in networks of multi-agents with time-varying topologies and delays. The topology and delays are modeled as induced by an adapted process and are rather general, including i.i.d. topology processes, asynchronous consensus algorithms, and Markovian jumping switching. In case the self-links are instantaneous, we prove that the network reaches consensus for all bounded delays if the graph corresponding to the conditional expectation of the coupling matrix sum across a finite time interval has a spanning tree almost surely. Moreover, when self-links are also delayed and when the delays satisfy certain integer patterns, we observe and prove that the algorithm may not reach consensus but instead synchronize at a periodic trajectory, whose period depends on the delay pattern. We also give a brief discussion on the dynamics in the absence of self-links.
Keywords: Consensus, network of multi-agents, synchronization, adapted process, switching topology., delay.
Mathematics Subject Classification: Primary: 93C05, 37H10, 15A51, 40A20; Secondary: 05C50, 60J1.
Citation: Wenlian Lu, Fatihcan M. Atay, Jürgen Jost. Consensus and synchronization in discrete-time networks of multi-agents with stochastically switching topologies and time delays. Networks & Heterogeneous Media, 2011, 6 (2) : 329-349. doi: 10.3934/nhm.2011.6.329
References:
[1]

P.-A. Bliman and G. Ferrari-Trecate, Average consensus problems in networks of agents with delayed communications,, Automatica, 44 (2008), 1985.  doi: 10.1016/j.automatica.2007.12.010.  Google Scholar

[2]

M. Cao, A. S. Morse and B. D. O. Anderson, Reaching a consensus in a dynamically changing environment: A graphical approach,, SIAM J. Control Optim., 47 (2008), 575.  doi: 10.1137/060657005.  Google Scholar

[3]

S. Chatterjee and E. Seneta, Towards consensus: Some convergence theorems on repeated averaging,, J. Appl. Prob., 14 (1977), 89.  doi: 10.2307/3213262.  Google Scholar

[4]

O. Chilina, "f-Uniform Ergodicity of Markov Chains,'', Supervised Project, (2006).   Google Scholar

[5]

M. H. DeGroot, Reaching a consensus,, J. Amer. Statist. Assoc., 69 (1974), 118.  doi: 10.2307/2285509.  Google Scholar

[6]

D. V. Dimarogonasa and K. H. Johansson, Stability analysis for multi-agent systems using the incidence matrix: Quantized communication and formation control,, Automatica, 46 (2010), 695.  doi: 10.1016/j.automatica.2010.01.012.  Google Scholar

[7]

R. Durrett, "Probability: Theory and Examples," 3rd edition,, Belmont, (2005).   Google Scholar

[8]

F. Fagnani and S. Zampieri, Average consensus with packet drop communication,, SIAM J. Control Optim., 48 (2009), 102.  doi: 10.1137/060676866.  Google Scholar

[9]

L. Fang, P. J. Antsaklis and A. Tzimas, Asynchronous consensus protocols: Preliminary results, simulations and open questions,, Proceedings of the 44th IEEE Conf. Decision and Control, (2005), 2194.   Google Scholar

[10]

J. A. Fax and R. M. Murray, Information flow and cooperative control of vehicle formations,, IEEE Trans. Autom. Control, 49 (2004), 1465.  doi: 10.1109/TAC.2004.834433.  Google Scholar

[11]

C. Godsil and G. Royle, "Algebraic Graph Theory,", Springer-Verlag, (2001).   Google Scholar

[12]

J. Hajnal, The ergodic properties of non-homogeneous finite Markov chains,, Proc. Camb. Phil. Soc., 52 (1956), 67.  doi: 10.1017/S0305004100030991.  Google Scholar

[13]

J. Hajnal, Weak ergodicity in non-homogeneous Markov chains,, Proc. Camb. Phil. Soc., 54 (1958), 233.  doi: 10.1017/S0305004100033399.  Google Scholar

[14]

Y. Hatano and M. Mesbahi, Agreement over random networks,, IEEE Trans. Autom. Control, 50 (2005), 1867.  doi: 10.1109/TAC.2005.858670.  Google Scholar

[15]

R. A. Horn and C. R. Johnson, "Matrix Analysis,", Cambridge University Press, (1985).   Google Scholar

[16]

Y. Kuramoto, "Chemical Oscillations, Waves, And Turbulence,", Springer-Verlag, (1984).   Google Scholar

[17]

J. Lin, A. S. Morse and B. D. O. Anderson, The multi-agent rendezvous problem Part 2: The asynchronous case,, SIAM J. Control Optim., 46 (2007), 2120.  doi: 10.1137/040620564.  Google Scholar

[18]

B. Liu, W. Lu and T. Chen, Consensus in networks of multiagents with switching topologies modeled as adapted stochastic processes,, SIAM J. Control Optim., 49 (2011), 227.  doi: 10.1137/090745945.  Google Scholar

[19]

W. Lu, F. M. Atay and J. Jost, Synchronization of discrete-time networks with time-varying couplings,, SIAM J. Math. Analys., 39 (2007), 1231.  doi: 10.1137/060657935.  Google Scholar

[20]

W. Lu, F. M. Atay and J. Jost, Chaos synchronization in networks of coupled maps with time-varying topologies,, Eur. Phys. J. B, 63 (2008), 399.  doi: 10.1140/epjb/e2008-00023-3.  Google Scholar

[21]

N. A. Lynch, "Distributed Algorithms,", CA: Morgan Kaufmann, (1996).   Google Scholar

[22]

W. Ni and D. Z. Cheng, Leader-following consensus of multi-agent systems under fixed and switching topologies,, Systems & Control Letters, 59 (2010), 209.  doi: 10.1016/j.sysconle.2010.01.006.  Google Scholar

[23]

W. Michiels, C.-I. Morărescu and S.-I. Niculescu, Consensus problems with distributed delays, with application to traffic flow models,, SIAM J. Control Optim., 48 (2009), 77.  doi: 10.1137/060671425.  Google Scholar

[24]

L. Moreau, Stability of continuous-time distributed consensus algorithms,, 43rd IEEE Conference on Decision and Control, 4 (2004), 3998.   Google Scholar

[25]

L. Moreau, Stability of multiagent systems with time-dependent communication links,, IEEE Trans. Autom. Control, 50 (2005), 169.  doi: 10.1109/TAC.2004.841888.  Google Scholar

[26]

R. Olfati-Saber and J. S. Shamma, Consensus filters for sensor networks and distributed sensor fusion,, 44th IEEE Conference on Decision and Control 2005, (2005), 6698.  doi: 10.1109/CDC.2005.1583238.  Google Scholar

[27]

R. Olfati-Saber, J. A. Fax and R. M. Murray, Consensus and cooperation in networked multi-agent systems,, Proceedings of the IEEE, 95 (2007), 215.  doi: 10.1109/JPROC.2006.887293.  Google Scholar

[28]

R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays,, IEEE Trans. Autom. Control, 49 (2004), 1520.  doi: 10.1109/TAC.2004.834113.  Google Scholar

[29]

A. Pikovsky, M. Rosenblum and J. Kurths, "Synchronization: A Universal Concept in Nonlinear Sciences,", Cambridge University Press, (2001).  doi: 10.1017/CBO9780511755743.  Google Scholar

[30]

J. Shen, A geometric approach to ergodic non-homogeneous Markov chains,, Wavelet Anal. Multi. Meth., 212 (2000), 341.   Google Scholar

[31]

A. Tahbaz-Salehi and A. Jadbabaie, A necessary and sufficient condition for consensus over random networks,, IEEE Trans. Autom. Control, 53 (2008), 791.  doi: 10.1109/TAC.2008.917743.  Google Scholar

[32]

T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen and O. Shochet, Novel type of phase transition in a system of self-driven particles,, Phys. Rev. Lett., 75 (1995), 1226.  doi: 10.1103/PhysRevLett.75.1226.  Google Scholar

[33]

A. T. Winfree, "The Geometry of Biological Time,", Springer Verlag, (1980).   Google Scholar

[34]

J. Wolfowitz, Products of indecomposable, aperiodic, stochastic matrices,, Proceedings of AMS, 14 (1963), 733.   Google Scholar

[35]

C. W. Wu, Synchronization and convergence of linear dynamics in random directed networks,, IEEE Trans. Autom. Control, 51 (2006), 1207.   Google Scholar

[36]

F. Xiao and L. Wang, Consensus protocols for discrete-time multi-agent systems with time-varying delays,, Automatica, 44 (2008), 2577.   Google Scholar

[37]

F. Xiao and L. Wang, Asynchronous consensus in continuous-time multi-agent systems with switching topology and time-varying delays,, IEEE Transactions on Automatic Control, 53 (2008), 1804.   Google Scholar

[38]

Y. Zhang and Y.-P. Tian, Consentability and protocol design of multi-agent systems with stochastic switching topology,, Automatica, 45 (2009), 1195.   Google Scholar

show all references

References:
[1]

P.-A. Bliman and G. Ferrari-Trecate, Average consensus problems in networks of agents with delayed communications,, Automatica, 44 (2008), 1985.  doi: 10.1016/j.automatica.2007.12.010.  Google Scholar

[2]

M. Cao, A. S. Morse and B. D. O. Anderson, Reaching a consensus in a dynamically changing environment: A graphical approach,, SIAM J. Control Optim., 47 (2008), 575.  doi: 10.1137/060657005.  Google Scholar

[3]

S. Chatterjee and E. Seneta, Towards consensus: Some convergence theorems on repeated averaging,, J. Appl. Prob., 14 (1977), 89.  doi: 10.2307/3213262.  Google Scholar

[4]

O. Chilina, "f-Uniform Ergodicity of Markov Chains,'', Supervised Project, (2006).   Google Scholar

[5]

M. H. DeGroot, Reaching a consensus,, J. Amer. Statist. Assoc., 69 (1974), 118.  doi: 10.2307/2285509.  Google Scholar

[6]

D. V. Dimarogonasa and K. H. Johansson, Stability analysis for multi-agent systems using the incidence matrix: Quantized communication and formation control,, Automatica, 46 (2010), 695.  doi: 10.1016/j.automatica.2010.01.012.  Google Scholar

[7]

R. Durrett, "Probability: Theory and Examples," 3rd edition,, Belmont, (2005).   Google Scholar

[8]

F. Fagnani and S. Zampieri, Average consensus with packet drop communication,, SIAM J. Control Optim., 48 (2009), 102.  doi: 10.1137/060676866.  Google Scholar

[9]

L. Fang, P. J. Antsaklis and A. Tzimas, Asynchronous consensus protocols: Preliminary results, simulations and open questions,, Proceedings of the 44th IEEE Conf. Decision and Control, (2005), 2194.   Google Scholar

[10]

J. A. Fax and R. M. Murray, Information flow and cooperative control of vehicle formations,, IEEE Trans. Autom. Control, 49 (2004), 1465.  doi: 10.1109/TAC.2004.834433.  Google Scholar

[11]

C. Godsil and G. Royle, "Algebraic Graph Theory,", Springer-Verlag, (2001).   Google Scholar

[12]

J. Hajnal, The ergodic properties of non-homogeneous finite Markov chains,, Proc. Camb. Phil. Soc., 52 (1956), 67.  doi: 10.1017/S0305004100030991.  Google Scholar

[13]

J. Hajnal, Weak ergodicity in non-homogeneous Markov chains,, Proc. Camb. Phil. Soc., 54 (1958), 233.  doi: 10.1017/S0305004100033399.  Google Scholar

[14]

Y. Hatano and M. Mesbahi, Agreement over random networks,, IEEE Trans. Autom. Control, 50 (2005), 1867.  doi: 10.1109/TAC.2005.858670.  Google Scholar

[15]

R. A. Horn and C. R. Johnson, "Matrix Analysis,", Cambridge University Press, (1985).   Google Scholar

[16]

Y. Kuramoto, "Chemical Oscillations, Waves, And Turbulence,", Springer-Verlag, (1984).   Google Scholar

[17]

J. Lin, A. S. Morse and B. D. O. Anderson, The multi-agent rendezvous problem Part 2: The asynchronous case,, SIAM J. Control Optim., 46 (2007), 2120.  doi: 10.1137/040620564.  Google Scholar

[18]

B. Liu, W. Lu and T. Chen, Consensus in networks of multiagents with switching topologies modeled as adapted stochastic processes,, SIAM J. Control Optim., 49 (2011), 227.  doi: 10.1137/090745945.  Google Scholar

[19]

W. Lu, F. M. Atay and J. Jost, Synchronization of discrete-time networks with time-varying couplings,, SIAM J. Math. Analys., 39 (2007), 1231.  doi: 10.1137/060657935.  Google Scholar

[20]

W. Lu, F. M. Atay and J. Jost, Chaos synchronization in networks of coupled maps with time-varying topologies,, Eur. Phys. J. B, 63 (2008), 399.  doi: 10.1140/epjb/e2008-00023-3.  Google Scholar

[21]

N. A. Lynch, "Distributed Algorithms,", CA: Morgan Kaufmann, (1996).   Google Scholar

[22]

W. Ni and D. Z. Cheng, Leader-following consensus of multi-agent systems under fixed and switching topologies,, Systems & Control Letters, 59 (2010), 209.  doi: 10.1016/j.sysconle.2010.01.006.  Google Scholar

[23]

W. Michiels, C.-I. Morărescu and S.-I. Niculescu, Consensus problems with distributed delays, with application to traffic flow models,, SIAM J. Control Optim., 48 (2009), 77.  doi: 10.1137/060671425.  Google Scholar

[24]

L. Moreau, Stability of continuous-time distributed consensus algorithms,, 43rd IEEE Conference on Decision and Control, 4 (2004), 3998.   Google Scholar

[25]

L. Moreau, Stability of multiagent systems with time-dependent communication links,, IEEE Trans. Autom. Control, 50 (2005), 169.  doi: 10.1109/TAC.2004.841888.  Google Scholar

[26]

R. Olfati-Saber and J. S. Shamma, Consensus filters for sensor networks and distributed sensor fusion,, 44th IEEE Conference on Decision and Control 2005, (2005), 6698.  doi: 10.1109/CDC.2005.1583238.  Google Scholar

[27]

R. Olfati-Saber, J. A. Fax and R. M. Murray, Consensus and cooperation in networked multi-agent systems,, Proceedings of the IEEE, 95 (2007), 215.  doi: 10.1109/JPROC.2006.887293.  Google Scholar

[28]

R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays,, IEEE Trans. Autom. Control, 49 (2004), 1520.  doi: 10.1109/TAC.2004.834113.  Google Scholar

[29]

A. Pikovsky, M. Rosenblum and J. Kurths, "Synchronization: A Universal Concept in Nonlinear Sciences,", Cambridge University Press, (2001).  doi: 10.1017/CBO9780511755743.  Google Scholar

[30]

J. Shen, A geometric approach to ergodic non-homogeneous Markov chains,, Wavelet Anal. Multi. Meth., 212 (2000), 341.   Google Scholar

[31]

A. Tahbaz-Salehi and A. Jadbabaie, A necessary and sufficient condition for consensus over random networks,, IEEE Trans. Autom. Control, 53 (2008), 791.  doi: 10.1109/TAC.2008.917743.  Google Scholar

[32]

T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen and O. Shochet, Novel type of phase transition in a system of self-driven particles,, Phys. Rev. Lett., 75 (1995), 1226.  doi: 10.1103/PhysRevLett.75.1226.  Google Scholar

[33]

A. T. Winfree, "The Geometry of Biological Time,", Springer Verlag, (1980).   Google Scholar

[34]

J. Wolfowitz, Products of indecomposable, aperiodic, stochastic matrices,, Proceedings of AMS, 14 (1963), 733.   Google Scholar

[35]

C. W. Wu, Synchronization and convergence of linear dynamics in random directed networks,, IEEE Trans. Autom. Control, 51 (2006), 1207.   Google Scholar

[36]

F. Xiao and L. Wang, Consensus protocols for discrete-time multi-agent systems with time-varying delays,, Automatica, 44 (2008), 2577.   Google Scholar

[37]

F. Xiao and L. Wang, Asynchronous consensus in continuous-time multi-agent systems with switching topology and time-varying delays,, IEEE Transactions on Automatic Control, 53 (2008), 1804.   Google Scholar

[38]

Y. Zhang and Y.-P. Tian, Consentability and protocol design of multi-agent systems with stochastic switching topology,, Automatica, 45 (2009), 1195.   Google Scholar

[1]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002
[2]

Leslaw Skrzypek, Yuncheng You. Feedback synchronization of FHN cellular neural networks. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021001
[3]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317
[4]

Alexander Dabrowski, Ahcene Ghandriche, Mourad Sini. Mathematical analysis of the acoustic imaging modality using bubbles as contrast agents at nearly resonating frequencies. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021005
[5]

Guangjun Shen, Xueying Wu, Xiuwei Yin. Stabilization of stochastic differential equations driven by G-Lévy process with discrete-time feedback control. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 755-774. doi: 10.3934/dcdsb.2020133
[6]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011
[7]

Huanhuan Tian, Maoan Han. Limit cycle bifurcations of piecewise smooth near-Hamiltonian systems with a switching curve. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020368
[8]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170
[9]

Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049
[10]

Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial & Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130
[11]

Bilel Elbetch, Tounsia Benzekri, Daniel Massart, Tewfik Sari. The multi-patch logistic equation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021025
[12]

Simone Göttlich, Elisa Iacomini, Thomas Jung. Properties of the LWR model with time delay. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020032
[13]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060
[14]

Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155
[15]

Liang Huang, Jiao Chen. The boundedness of multi-linear and multi-parameter pseudo-differential operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020291
[16]

Yukihiko Nakata. Existence of a period two solution of a delay differential equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1103-1110. doi: 10.3934/dcdss.2020392
[17]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077
[18]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364
[19]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[20]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109

2019 Impact Factor: 1.053

Tools

Metrics

  • PDF downloads (49)
  • HTML views (0)
  • Cited by (20)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences