Scalable and Resilient Distributed Algorithms for Coordination in Large-Scale Networks
Principal Investigator: Shreyas Sundaram
A key challenge in large-scale networked systems is to allow the individual nodes to cooperatively take actions by repeatedly interacting and exchanging information with the other nodes. This is particularly important when the nodes have access to local information, but must take optimal actions that rely on global data. However, large-scale networks also present multiple entry points for attackers to compromise nodes, causing them to behave in unanticipated ways.
In this project, we formulate scalable and lightweight distributed algorithms to allow nodes in large-scale networks to cooperatively take actions, despite malicious behavior by some of the nodes. Our algorithms provide provable safety and performance guarantees for the non-adversarial nodes in the face of worst-case (and possibly coordinated) adversarial behavior by a potentially massive number of attackers. Our algorithms only require each non-adversarial node to interact with its neighbors, and does not require them to know anything about the global network topology. Our research also leads to new metrics for measuring the resilience of networks to attacks, and designing resilient networks. Our algorithms can be applied to the canonical problems of distributed consensus, distributed optimization, and distributed state estimation, among others.
Through this project, we also formulate techniques to design network topologies to enable coordination. We formulate both stochastic and game-theoretic models for the formation of large-scale complex networks, and identify features of such networks that enable efficient exchange of information and resilience to adversarial behavior.
Students: Aritra Mitra, Kananart Kuwaranancharoen
E. Moradi Shahrivar and S. Sundaram, "The Strategic Formation of Multi-Layer Networks." IEEE Transactions on Network Science and Engineering, vol. 2, no. 4, pp. 164 - 178, Oct - Dec 2015.
M. Pirani and S. Sundaram, "On the Smallest Eigenvalue of Grounded Laplacian Matrices." IEEE Transactions on Automatic Control, vol. 61, no. 2, pp. 509 - 514, Feb. 2016.
E. Moradi Shahrivar and S. Sundaram, "The Game-Theoretic Formation of Interconnections Between Networks." IEEE Journal on Selected Areas in Communications: Special Issue on Game Theory for Networks, vol. 35, no. 2, pp. 341 - 352, Feb. 2017.
E. Moradi Shahrivar, M. Pirani and S. Sundaram, "Spectral and Structural Properties of Random Interdependent Networks." Automatica, vol. 83, pp. 234 – 242, Sept. 2017.
M. Pirani, E. Moradi Shahrivar, B. Fidan and S. Sundaram, "Robustness of Leader-Follower Networked Dynamical Systems" IEEE Transactions on Control of Network Systems (to appear).
S. Sundaram and B. Gharesifard, "Distributed Optimization under Adversarial Nodes." arXiv, 2016.
A. Mitra and S. Sundaram, "Secure Distributed Observers for a Class of Linear Time Invariant Systems in the Presence of Byzantine Adversaries." Proceedings of the 55th IEEE Conference on Decision and Control, Las Vegas, NV, 2016. (invited)
H. Zhang, E. Fata and S. Sundaram, "A Notion of Robustness in Complex Networks." IEEE Transactions on Control of Network Systems, vol. 2, no. 3, pp. 310 - 320, Sept 2015.
H. LeBlanc, H. Zhang, X. Koutsoukos and S. Sundaram, "Resilient Asymptotic Consensus in Robust Networks." IEEE Journal on Selected Areas in Communications: Special Issue on In-Network Computation, vol. 31, no. 4, pp. 766 - 781, Apr 2013.
Keywords: algorithms, distributed algorithms, distributed applications, distributed coordination, large-scale networked systems, network attack, network science, resilience