Search Advanced

Networks and Heterogeneous Media

2011, Volume 6, Issue 2: 329-349. doi: 10.3934/nhm.2011.6.329
Previous Article Next Article

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

  • 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
  • Received: 01 August 2010 Revised: 01 February 2011

  • Primary: 93C05, 37H10, 15A51, 40A20; Secondary: 05C50, 60J10.

  • 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.

    Citation: Wenlian Lu, Fatihcan M. Atay, Jürgen Jost. Consensus and synchronization in discrete-time networks ofmulti-agents with stochastically switching topologies and timedelays[J]. Networks and Heterogeneous Media, 2011, 6(2): 329-349. doi: 10.3934/nhm.2011.6.329

    Related Papers:

    [1] 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 and Heterogeneous Media, 2011, 6(2): 329-349. doi: 10.3934/nhm.2011.6.329
    [2] Yilun Shang . Group pinning consensus under fixed and randomly switching topologies with acyclic partition. Networks and Heterogeneous Media, 2014, 9(3): 553-573. doi: 10.3934/nhm.2014.9.553
    [3] Yipeng Chen, Yicheng Liu, Xiao Wang . The critical delay of the consensus for a class of multi-agent system involving task strategies. Networks and Heterogeneous Media, 2023, 18(2): 513-531. doi: 10.3934/nhm.2023021
    [4] Zhuchun Li, Xiaoping Xue, Seung-Yeal Ha . A revisit to the consensus for linearized Vicsek model under joint rooted leadership via a special matrix. Networks and Heterogeneous Media, 2014, 9(2): 335-351. doi: 10.3934/nhm.2014.9.335
    [5] Tingting Zhu . Synchronization of the generalized Kuramoto model with time delay and frustration. Networks and Heterogeneous Media, 2023, 18(4): 1772-1798. doi: 10.3934/nhm.2023077
    [6] Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang . Periodic consensus in network systems with general distributed processing delays. Networks and Heterogeneous Media, 2021, 16(1): 139-153. doi: 10.3934/nhm.2021002
    [7] Yuntian Zhang, Xiaoliang Chen, Zexia Huang, Xianyong Li, Yajun Du . Managing consensus based on community classification in opinion dynamics. Networks and Heterogeneous Media, 2023, 18(2): 813-841. doi: 10.3934/nhm.2023035
    [8] Luca Schenato, Sandro Zampieri . On rendezvous control with randomly switching communication graphs. Networks and Heterogeneous Media, 2007, 2(4): 627-646. doi: 10.3934/nhm.2007.2.627
    [9] GuanLin Li, Sebastien Motsch, Dylan Weber . Bounded confidence dynamics and graph control: Enforcing consensus. Networks and Heterogeneous Media, 2020, 15(3): 489-517. doi: 10.3934/nhm.2020028
    [10] Yunhua Liao, Mohamed Maama, M. A. Aziz-Alaoui . Consensus dynamics and coherence in hierarchical small-world networks. Networks and Heterogeneous Media, 2025, 20(2): 482-499. doi: 10.3934/nhm.2025022
  • 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.


    [1] P.-A. Bliman and G. Ferrari-Trecate, Average consensus problems in networks of agents with delayed communications, Automatica, 44 (2008), 1985-1995. doi: 10.1016/j.automatica.2007.12.010
    [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-600. doi: 10.1137/060657005
    [3] S. Chatterjee and E. Seneta, Towards consensus: Some convergence theorems on repeated averaging, J. Appl. Prob., 14 (1977), 89-97. doi: 10.2307/3213262
    [4] O. Chilina, "f-Uniform Ergodicity of Markov Chains,'' Supervised Project, Unversity of Toronto, 2006.
    [5] M. H. DeGroot, Reaching a consensus, J. Amer. Statist. Assoc., 69 (1974), 118-121. doi: 10.2307/2285509
    [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-700. doi: 10.1016/j.automatica.2010.01.012
    [7] R. Durrett, "Probability: Theory and Examples," 3rd edition, Belmont, CA: Duxbury Press, 2005.
    [8] F. Fagnani and S. Zampieri, Average consensus with packet drop communication, SIAM J. Control Optim., 48 (2009), 102-133. doi: 10.1137/060676866
    [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, the Europ. Control Conference (2005), 2194-2199.
    [10] J. A. Fax and R. M. Murray, Information flow and cooperative control of vehicle formations, IEEE Trans. Autom. Control, 49 (2004), 1465-1476. doi: 10.1109/TAC.2004.834433
    [11] C. Godsil and G. Royle, "Algebraic Graph Theory," Springer-Verlag, New York, 2001.
    [12] J. Hajnal, The ergodic properties of non-homogeneous finite Markov chains, Proc. Camb. Phil. Soc., 52 (1956), 67-77. doi: 10.1017/S0305004100030991
    [13] J. Hajnal, Weak ergodicity in non-homogeneous Markov chains, Proc. Camb. Phil. Soc., 54 (1958), 233-246. doi: 10.1017/S0305004100033399
    [14] Y. Hatano and M. Mesbahi, Agreement over random networks, IEEE Trans. Autom. Control, 50 (2005), 1867-1872. doi: 10.1109/TAC.2005.858670
    [15] R. A. Horn and C. R. Johnson, "Matrix Analysis," Cambridge University Press, 1985.
    [16] Y. Kuramoto, "Chemical Oscillations, Waves, And Turbulence," Springer-Verlag, New York, 1984.
    [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-2147. doi: 10.1137/040620564
    [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-253. doi: 10.1137/090745945
    [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-1259. doi: 10.1137/060657935
    [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-406. doi: 10.1140/epjb/e2008-00023-3
    [21] N. A. Lynch, "Distributed Algorithms," CA: Morgan Kaufmann, San Francisco, 1996.
    [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-217. doi: 10.1016/j.sysconle.2010.01.006
    [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-101. doi: 10.1137/060671425
    [24] L. Moreau, Stability of continuous-time distributed consensus algorithms, 43rd IEEE Conference on Decision and Control, 4 (2004), 3998-4003.
    [25] L. Moreau, Stability of multiagent systems with time-dependent communication links, IEEE Trans. Autom. Control, 50 (2005), 169-182. doi: 10.1109/TAC.2004.841888
    [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, and 2005 European Control Conference CDC-ECC '05. 6698-6703. doi: 10.1109/CDC.2005.1583238
    [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-233. doi: 10.1109/JPROC.2006.887293
    [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-1533. doi: 10.1109/TAC.2004.834113
    [29] A. Pikovsky, M. Rosenblum and J. Kurths, "Synchronization: A Universal Concept in Nonlinear Sciences," Cambridge University Press, 2001. doi: 10.1017/CBO9780511755743
    [30] J. Shen, A geometric approach to ergodic non-homogeneous Markov chains, Wavelet Anal. Multi. Meth., LNPAM, 212 (2000), 341-366.
    [31] A. Tahbaz-Salehi and A. Jadbabaie, A necessary and sufficient condition for consensus over random networks, IEEE Trans. Autom. Control, 53 (2008), 791-795. doi: 10.1109/TAC.2008.917743
    [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-1229. doi: 10.1103/PhysRevLett.75.1226
    [33] A. T. Winfree, "The Geometry of Biological Time," Springer Verlag, New York, 1980.
    [34] J. Wolfowitz, Products of indecomposable, aperiodic, stochastic matrices, Proceedings of AMS, 14 (1963), 733-737.
    [35] C. W. Wu, Synchronization and convergence of linear dynamics in random directed networks, IEEE Trans. Autom. Control, 51 (2006), 1207-1210.
    [36] F. Xiao and L. Wang, Consensus protocols for discrete-time multi-agent systems with time-varying delays, Automatica, 44 (2008), 2577-2582.
    [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-1816.
    [38] Y. Zhang and Y.-P. Tian, Consentability and protocol design of multi-agent systems with stochastic switching topology, Automatica, 45 (2009), 1195-1201.

  • This article has been cited by:

    1. Fatihcan M. Atay, 2014, Network consensus under distributed transmission delays, 978-3-9524269-1-3, 1110, 10.1109/ECC.2014.6862593
    2. Yujuan Han, Wenlian Lu, Tianping Chen, Consensus analysis of networks with time-varying topology and event-triggered diffusions, 2015, 71, 08936080, 196, 10.1016/j.neunet.2015.08.008
    3. Bo Liu, Wenlian Lu, Licheng Jiao, Tianping Chen, Products of Generalized Stochastic Matrices With Applications to Consensus Analysis in Networks of Multiagents With Delays, 2020, 50, 2168-2267, 386, 10.1109/TCYB.2018.2868994
    4. Zhao-Xia WANG, Da-Jun DU, Min-Rui FEI, Average Consensus in Directed Networks of Multi-agents with Uncertain Time-varying Delays, 2014, 40, 18741029, 2602, 10.1016/S1874-1029(14)60406-7
    5. Li Xiao, Xiaofeng Liao, Huiwei Wang, Cluster Consensus on Discrete-Time Multi-Agent Networks, 2012, 2012, 1085-3375, 1, 10.1155/2012/274735
    6. Yujuan Han, Wenlian Lu, Tianping Chen, 2013, Cluster consensus of networks of second-order multi-agent systems with inter-cluster non-identical inputs, 978-1-4673-5534-6, 4667, 10.1109/CCDC.2013.6561778
    7. Wenlian Lu, Fatihcan M. Atay, Jürgen Jost, 2014, Chapter 12, 978-3-319-01694-8, 155, 10.1007/978-3-319-01695-5_12
    8. Wenlian Lu, Fatihcan M. Atay, Local Pinning of Networks of Multi-Agent Systems With Transmission and Pinning Delays, 2016, 61, 0018-9286, 2657, 10.1109/TAC.2015.2508883
    9. Bo Liu, Wenlian Lu, Licheng Jiao, Tianping Chen, Consensus in Networks of Multiagents with Stochastically Switching Topologies and Time-Varying Delays, 2018, 56, 0363-0129, 1884, 10.1137/16M1095354
    10. Delphine Bresch-Pietri, Domitilla Del Vecchio, 2014, Design of safety distributed control under bounded time-varying communication delay, 978-1-4799-3274-0, 1781, 10.1109/ACC.2014.6858968
    11. Yao Chen, Daniel W. C. Ho, Jinhu Lu, Zongli Lin, Convergence Rate for Discrete-Time Multiagent Systems With Time-Varying Delays and General Coupling Coefficients, 2016, 27, 2162-237X, 178, 10.1109/TNNLS.2015.2473690
    12. Haitao Han, Zhiming Wang, Qing Zhou, Consensus of complex network systems and ergodicity of Markov chains, 2015, 9, 1751-8652, 184, 10.1049/iet-cta.2014.0060
    13. Hamed Rezaee, Farzaneh Abdollahi, Consensus Problem Over High-Order Multiagent Systems With Uncertain Nonlinearities Under Deterministic and Stochastic Topologies, 2017, 47, 2168-2267, 2079, 10.1109/TCYB.2016.2628811
    14. Yujuan Han, Wenlian Lu, Tianping Chen, 2014, Pinning dynamic complex networks by time-varying controller-vertex set, 978-1-4799-1484-5, 2726, 10.1109/IJCNN.2014.6889628
    15. Bo Liu, Wenlian Lu, Tianping Chen, A new approach to the stability analysis of continuous-time distributed consensus algorithms, 2013, 46, 08936080, 242, 10.1016/j.neunet.2013.06.007
    16. Behrouz Touri, Cedric Langbort, On Endogenous Random Consensus and Averaging Dynamics, 2014, 1, 2325-5870, 241, 10.1109/TCNS.2014.2337973
    17. Yilun Shang, Group pinning consensus under fixed and randomly switching topologies with acyclic partition, 2014, 9, 1556-181X, 553, 10.3934/nhm.2014.9.553
    18. Hamed Rezaee, Farzaneh Abdollahi, Discrete-time consensus strategy for a class of high-order linear multiagent systems under stochastic communication topologies, 2017, 354, 00160032, 3690, 10.1016/j.jfranklin.2016.10.014
    19. Otti D'Huys, Thomas Jüngling, Wolfgang Kinzel, Stochastic switching in delay-coupled oscillators, 2014, 90, 1539-3755, 10.1103/PhysRevE.90.032918
    20. Wenlian Lu, Ren Zheng, Tianping Chen, Centralized and decentralized global outer-synchronization of asymmetric recurrent time-varying neural network by data-sampling, 2016, 75, 08936080, 22, 10.1016/j.neunet.2015.11.006
    21. Otti D’Huys, Thomas Jüngling, Wolfgang Kinzel, 2016, Chapter 7, 978-3-319-28027-1, 127, 10.1007/978-3-319-28028-8_7
    22. Fatihcan M. Atay, The consensus problem in networks with transmission delays, 2013, 371, 1364-503X, 20120460, 10.1098/rsta.2012.0460
    23. Yujuan Han, Wenlian Lu, Tianping Chen, Changkai Sun, Optimizing Pinned Nodes to Maximize the Convergence Rate of Multiagent Systems with Digraph Topologies, 2019, 2019, 1076-2787, 1, 10.1155/2019/4096981
    24. Cluster Consensus in Discrete-Time Networks of Multiagents With Inter-Cluster Nonidentical Inputs, 2013, 24, 2162-237X, 566, 10.1109/TNNLS.2013.2237786
    25. Xingjun Wang, Yujuan Han, 2023, Finding Most Influential Inter-Layer Edges to Enhance Diffusion on Two-Layer Interconnected Networks, 979-8-3503-5996-1, 480, 10.1109/EIECC60864.2023.10456748
  • Reader Comments
  • © 2011 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Networks and Heterogeneous Media
1.3 1.9

Metrics

Article views(4899) PDF downloads(145) Cited by(25)

Preview PDF
Download XML
Export Citation
Article outline
Abstract
References

Other Articles By Authors

Related pages

Tools

Copyright © AIMS Press

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog