1932

Abstract

We review selected results related to the robustness of networked systems in finite and asymptotically large size regimes in static and dynamical settings. In the static setting, within the framework of flow over finite networks, we discuss the effect of physical constraints on robustness to loss in link capacities. In the dynamical setting, we review several settings in which small-gain-type analysis provides tight robustness guarantees for linear dynamics over finite networks toward worst-case and stochastic disturbances. We discuss network flow dynamic settings where nonlinear techniques facilitate understanding the effect, on robustness, of constraints on capacity and information, substituting information with control action, and cascading failure. We also contrast cascading failure with a representative contagion model. For asymptotically large networks, we discuss the role of network properties in connecting microscopic shocks to emergent macroscopic fluctuations under linear dynamics as well as for economic networks at equilibrium. Through this review, we aim to achieve two objectives: to highlight selected settings in which the role of the interconnectivity structure of a network in its robustness is well understood, and to highlight a few additional settings in which existing system-theoretic tools give tight robustness guarantees and that are also appropriate avenues for future network-theoretic investigations.

Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-091219-012549
2020-05-03
2024-06-23
Loading full text...

Full text loading...

/deliver/fulltext/control/3/1/annurev-control-091219-012549.html?itemId=/content/journals/10.1146/annurev-control-091219-012549&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Korte B, Vygen J. 2002. Combinatorial Optimization: Theory and Algorithms Berlin: Springer
    [Google Scholar]
  2. 2. 
    Christiano P, Kelner JA, Madry A, Spielman DA, Teng SH 2011. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing273–82 New York: ACM
    [Google Scholar]
  3. 3. 
    Zhou K, Doyle J, Glover K 1996. Robust and Optimal Control Upper Saddle River, NJ: Prentice Hall
    [Google Scholar]
  4. 4. 
    Ba Q, Savla K. 2018. Robustness of DC networks under controllable link weights. IEEE Trans. Control Netw. Syst. 5:1479–91
    [Google Scholar]
  5. 5. 
    Zimmerman RD, Murillo-Sánchez CE, Thomas RJ 2011. MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education. IEEE Trans. Power Syst. 26:12–19
    [Google Scholar]
  6. 6. 
    Ba Q. 2018. Elements of robustness and optimal control for infrastructure networks PhD Thesis, Univ. South. Calif Los Angeles: http://digitallibrary.usc.edu/cdm/compoundobject/collection/p15799coll40/id/475855/rec/1
    [Google Scholar]
  7. 7. 
    Willems J. 1970. The Analysis of Feedback Systems Cambridge, MA: MIT Press
    [Google Scholar]
  8. 8. 
    Desoer C, Vidyasagar M. 1975. Feedback Systems: Input–Output Properties New York: Academic
    [Google Scholar]
  9. 9. 
    Jiang ZP, Liu T. 2018. Small-gain theory for stability and control of dynamical networks: a survey. Annu. Rev. Control 46:58–79
    [Google Scholar]
  10. 10. 
    Shamma JS. 1991. The necessity of the small-gain theorem for time-varying and nonlinear systems. IEEE Trans. Autom. Control 36:1138–47
    [Google Scholar]
  11. 11. 
    Freeman RA. 2001. On the necessity of the small-gain theorem in the performance analysis of nonlinear systems. Proceedings of the 40th IEEE Conference on Decision and Control 1:51–56 Piscataway, NJ: IEEE
    [Google Scholar]
  12. 12. 
    Doyle J. 1982. Analysis of feedback systems with structured uncertainties. IEE Proc. D 129:242–50
    [Google Scholar]
  13. 13. 
    Safonov M. 1982. Stability margins of diagonally perturbed multivariable feedback systems. IEE Proc. D 129:251–56
    [Google Scholar]
  14. 14. 
    Packard A, Doyle J. 1993. The complex structured singular value. Automatica 29:71–109
    [Google Scholar]
  15. 15. 
    Poola K, Tikku A. 1995. Robust performance against time-varying structured perturbations. IEEE Trans. Autom. Control 40:1589–602
    [Google Scholar]
  16. 16. 
    Megretski A. 1993. Necessary and sufficient conditions of stability: a multiloop generalization of the circle criterion. IEEE Trans. Autom. Control 38:753–56
    [Google Scholar]
  17. 17. 
    Shamma JS. 1994. Robust stability with time-varying structured uncertainty. IEEE Trans. Autom. Control 39:714–24
    [Google Scholar]
  18. 18. 
    Khammash M, Pearson JB. 1991. Performance robustness of discrete-time systems with structured uncertainty. IEEE Trans. Autom. Control 36:398–412
    [Google Scholar]
  19. 19. 
    Willems JC. 2007. Dissipative dynamical systems. Eur. J. Control 13:134–51
    [Google Scholar]
  20. 20. 
    Arcak M, Meissen C, Packard A 2016. Networks of Dissipative Systems: Compositional Certification of Stability, Performance, and Safety Cham, Switz: Springer
    [Google Scholar]
  21. 21. 
    Megretski A, Rantzer A. 1997. System analysis via integral quadratic constraints. IEEE Trans. Autom. Control 42:819–30
    [Google Scholar]
  22. 22. 
    Nesterov Y, Nemirovskii A. 1994. Interior-Point Polynomial Algorithms in Convex Programming Philadelphia: Soc. Ind. Appl. Math.
    [Google Scholar]
  23. 23. 
    Boyd S, El Ghaoui L, Feron E, Balakrishnan V 1994. Linear Matrix Inequalities in System and Control Theory Philadelphia: Soc. Ind. Appl. Math.
    [Google Scholar]
  24. 24. 
    Bamieh B, Filo M. 2018. An input-output approach to structured stochastic uncertainty. arXiv:1806.07473 [cs.SY]
  25. 25. 
    Fisher J, Bhattacharya R. 2009. Linear quadratic regulation of systems with stochastic parameter uncertainties. Automatica 45:2831–41
    [Google Scholar]
  26. 26. 
    Kim KKK, Shen DE, Nagy ZK, Braatz RD 2013. Wiener's polynomial chaos for the analysis and control of nonlinear dynamical systems with probabilistic uncertainties. IEEE Control Syst. Mag. 33:558–67
    [Google Scholar]
  27. 27. 
    Wang J, Elia N. 2012. Distributed averaging under constraints on information exchange: emergence of Lévy flights. IEEE Trans. Autom. Control 57:2435–49
    [Google Scholar]
  28. 28. 
    Gonçalves JM, Megretski A, Dahleh MA 2003. Global analysis of piecewise linear systems using impact maps and surface Lyapunov functions. IEEE Trans. Autom. Control 48:2089–106
    [Google Scholar]
  29. 29. 
    Sontag ED. 2010. Contractive systems with inputs. Perspectives in Mathematical System Theory, Control, and Signal Processing JC Willems, S Hara, Y Ohta, H Fujioka 217–28 Berlin: Springer
    [Google Scholar]
  30. 30. 
    Como G, Savla K, Acemoglu D, Dahleh MA, Frazzoli E 2013. Stability analysis of transportation networks with multiscale driver decisions. SIAM J. Control Optim. 51:230–52
    [Google Scholar]
  31. 31. 
    Sandholm WH. 2010. Population Games and Evolutionary Dynamics Cambridge, MA: MIT Press
    [Google Scholar]
  32. 32. 
    Como G, Savla K, Acemoglu D, Dahleh MA, Frazzoli E 2013. Robust distributed routing in dynamical networks—part I: locally responsive policies and weak resilience. IEEE Trans. Autom. Control 58:317–32
    [Google Scholar]
  33. 33. 
    Como G, Savla K, Acemoglu D, Dahleh MA, Frazzoli E 2013. Robust distributed routing in dynamical networks—part II: strong resilience, equilibrium selection and cascaded failures. IEEE Trans. Autom. Control 58:333–48
    [Google Scholar]
  34. 34. 
    Savla K, Lovisari E, Como G 2013. On maximally stabilizing adaptive traffic signal control. 2013 51st Annual Allerton Conference on Communication, Control, and Computing464–71 Piscataway, NJ: IEEE
    [Google Scholar]
  35. 35. 
    Massoulié L. 2007. Structural properties of proportional fairness: stability and insensitivity. Ann. Appl. Probab. 17:809–39
    [Google Scholar]
  36. 36. 
    Tassiulas L, Ephremides A. 1992. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control 37:1936–48
    [Google Scholar]
  37. 37. 
    Como G, Lovisari E, Savla K 2015. Throughput optimality and overload behavior of dynamical flow networks under monotone distributed routing. IEEE Trans. Control Netw. Syst. 2:57–67
    [Google Scholar]
  38. 38. 
    Ba Q, Savla K. 2020. Computing optimal control of cascading failure in DC networks. IEEE Trans. Autom. Control. In press. https://doi.org/10.1109/TAC.2019.2930232
    [Crossref] [Google Scholar]
  39. 39. 
    Savla K, Como G, Dahleh MA 2014. Robust network routing under cascading failures. IEEE Trans. Netw. Sci. Eng. 1:53–66
    [Google Scholar]
  40. 40. 
    Blume L, Easley D, Kleinberg J, Kleinberg R, Tardos É 2011. Which networks are least susceptible to cascading failures?. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science393–402 Piscataway, NJ: IEEE
    [Google Scholar]
  41. 41. 
    Acemoglu D, Carvalho VM, Ozdaglar A, Tahbaz-Salehi A 2012. The network origins of aggregate fluctuations. Econometrica 80:1977–2016
    [Google Scholar]
  42. 42. 
    Acemoglu D, Ozdaglar A, Tahbaz-Salehi A 2017. Microeconomic origins of macroeconomic tail risks. Am. Econ. Rev. 107:54–108
    [Google Scholar]
  43. 43. 
    Sarkar T, Roozbehani M, Dahleh MA 2019. Asymptotic network robustness. IEEE Trans. Control Netw. Syst. 6:812–21
    [Google Scholar]
  44. 44. 
    Herman I, Martinec D, Hurák Z, Šebek M 2014. Nonzero bound on Fiedler eigenvalue causes exponential growth of H-infinity norm of vehicular platoon. IEEE Trans. Autom. Control 60:2248–53
    [Google Scholar]
/content/journals/10.1146/annurev-control-091219-012549
Loading
/content/journals/10.1146/annurev-control-091219-012549
Loading

Data & Media loading...

  • Article Type: Review Article
This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error