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
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 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.
E. Moradi Shahrivar, M. Pirani and S. Sundaram, "Spectral and Structural Properties of Random Interdependent Networks." Automatica, vol. 83, pp. 234 – 242, Sept. 2017.
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.
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.
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.
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.
S. Sundaram and B. Gharesifard, “Distributed Optimization Under Adversarial Nodes.” IEEE Transactions on Automatic Control, 2018 (To appear).
D. Senejohnny, S. Sundaram, C. De Persis and P. Tesi, “Resilience against misbehaving nodes in Selftriggered Coordination Networks.” Proceedings of the IEEE Conference on Decision and Control, Miami Beach, FL, 2018 (to appear).
K. Kuwaranancharoen and S. Sundaram, “On the Location of the Minimizer of the Sum of Strongly Convex Functions.” Proceedings of the IEEE Conference on Decision and Control, Miami Beach, FL, 2018 (to appear).
A. Prasad, H.-L. Choi and S. Sundaram, “Min-Max Tours for Task Allocation to Heterogeneous Agents.” Proceedings of the IEEE Conference on Decision and Control, Miami Beach, FL, 2018 (to appear).
A. Mitra and S. Sundaram, “Secure Distributed State Estimation of an LTI system over Timevarying Networks and Analog Erasure Channels.” Proceedings of the American Control Conference, Milwaukee, WI, 2018 (to appear).
Keywords: algorithms, distributed algorithms, distributed applications, distributed coordination, large-scale networked systems, network attack, network science, resilience