Francesco Bullo

Florian Dorfler, Francesco Bullo

Consider a weighted and undirected graph, possibly with self-loops, and its corresponding Laplacian matrix, possibly augmented with additional diagonal elements corresponding to the self-loops. The Kron reduction of this graph is again a graph whose Laplacian matrix is obtained by the Schur complement of the original Laplacian matrix with respect to a subset of nodes. The Kron reduction process is ubiquitous in classic circuit theory and in related disciplines such as electrical impedance tomography, smart grid monitoring, transient stability assessment in power networks, or analysis and simulation of induction motors and power electronics. More general applications of Kron reduction occur in sparse matrix algorithms, multi-grid solvers, finite--element analysis, and Markov chains. The Schur complement of a Laplacian matrix and related concepts have also been studied under different names and as purely theoretic problems in the literature on linear algebra. In this paper we propose a general graph-theoretic framework for Kron reduction that leads to novel and deep insights both on the mathematical and the physical side. We show the applicability of our framework to various practical problem setups arising in engineering applications and computation. Furthermore, we provide a comprehensive and detailed graph-theoretic analysis of the Kron reduction process encompassing topological, algebraic, spectral, resistive, and sensitivity analyses. Throughout our theoretic elaborations we especially emphasize the practical applicability of our results.

John W. Simpson-Porco, Florian Dörfler, Francesco Bullo

Motivated by the recent and growing interest in smart grid technology, we study the operation of DC/AC inverters in an inductive microgrid. We show that a network of loads and DC/AC inverters equipped with power-frequency droop controllers can be cast as a Kuramoto model of phase-coupled oscillators. This novel description, together with results from the theory of coupled oscillators, allows us to characterize the behavior of the network of inverters and loads. Specifically, we provide a necessary and sufficient condition for the existence of a synchronized solution that is unique and locally exponentially stable. We present a selection of controller gains leading to a desirable sharing of power among the inverters, and specify the set of loads which can be serviced without violating given actuation constraints. Moreover, we propose a distributed integral controller based on averaging algorithms which dynamically regulates the system frequency in the presence of a time-varying load. Remarkably, this distributed-averaging integral controller has the additional property that it maintains the power sharing properties of the primary droop controller. Our results hold without assumptions on identical line characteristics or voltage magnitudes.

Fabio Pasqualetti, Antonio Bicchi, Francesco Bullo

This work addresses the problem of ensuring trustworthy computation in a linear consensus network. A solution to this problem is relevant for several tasks in multi-agent systems including motion coordination, clock synchronization, and cooperative estimation. In a linear consensus network, we allow for the presence of misbehaving agents, whose behavior deviate from the nominal consensus evolution. We model misbehaviors as unknown and unmeasurable inputs affecting the network, and we cast the misbehavior detection and identification problem into an unknown-input system theoretic framework. We consider two extreme cases of misbehaving agents, namely faulty (non-colluding) and malicious (Byzantine) agents. First, we characterize the set of inputs that allow misbehaving agents to affect the consensus network while remaining undetected and/or unidentified from certain observing agents. Second, we provide worst-case bounds for the number of concurrent faulty or malicious agents that can be detected and identified. Precisely, the consensus network needs to be 2k+1 (resp. k+1) connected for k malicious (resp. faulty) agents to be generically detectable and identifiable by every well behaving agent. Third, we quantify the effect of undetectable inputs on the final consensus value. Fourth, we design three algorithms to detect and identify misbehaving agents. The first and the second algorithm apply fault detection techniques, and affords complete detection and identification if global knowledge of the network is available to each agent, at a high computational cost. The third algorithm is designed to exploit the presence in the network of weakly interconnected subparts, and provides local detection and identification of misbehaving agents whose behavior deviates more than a threshold, which is quantified in terms of the interconnection structure.

Florian Dorfler, Francesco Bullo

The Kuramoto model captures various synchronization phenomena in biological and man-made systems of coupled oscillators. It is well-known that there exists a critical coupling strength among the oscillators at which a phase transition from incoherency to synchronization occurs. This paper features four contributions. First, we characterize and distinguish the different notions of synchronization used throughout the literature and formally introduce the concept of phase cohesiveness as an analysis tool and performance index for synchronization. Second, we review the vast literature providing necessary, sufficient, implicit, and explicit estimates of the critical coupling strength for finite and infinite-dimensional, and for first and second-order Kuramoto models. Third, we present the first explicit necessary and sufficient condition on the critical coupling to achieve synchronization in the finite-dimensional Kuramoto model for an arbitrary distribution of the natural frequencies. The multiplicative gap in the synchronization condition yields a practical stability result determining the admissible initial and the guaranteed ultimate phase cohesiveness as well as the guaranteed asymptotic magnitude of the order parameter. Fourth and finally, we extend our analysis to multi-rate Kuramoto models consisting of second-order Kuramoto oscillators with inertia and viscous damping together with first-order Kuramoto oscillators with multiple time constants. We prove that the multi-rate Kuramoto model is locally topologically conjugate to a first-order Kuramoto model with scaled natural frequencies, and we present necessary and sufficient conditions for almost global phase synchronization and local frequency synchronization. Interestingly, these conditions do not depend on the inertiae which contradicts prior observations on the role of inertiae in synchronization of second-order Kuramoto models.

Fabio Pasqualetti, Florian Dörfler, Francesco Bullo

Future power networks will be characterized by safe and reliable functionality against physical malfunctions and cyber attacks. This paper proposes a unified framework and advanced monitoring procedures to detect and identify network components malfunction or measurements corruption caused by an omniscient adversary. We model a power system under cyber-physical attack as a linear time-invariant descriptor system with unknown inputs. Our attack model generalizes the prototypical stealth, (dynamic) false-data injection and replay attacks. We characterize the fundamental limitations of both static and dynamic procedures for attack detection and identification. Additionally, we design provably-correct (dynamic) detection and identification procedures based on tools from geometric control theory. Finally, we illustrate the effectiveness of our method through a comparison with existing (static) detection algorithms, and through a numerical study.

Wenjun Mei, Shadi Mohagheghi, Sandro Zampieri et al.

In this work we review a class of deterministic nonlinear models for the propagation of infectious diseases over contact networks with strongly-connected topologies. We consider network models for susceptible-infected (SI), susceptible-infected-susceptible (SIS), and susceptible-infected-recovered (SIR) settings. In each setting, we provide a comprehensive nonlinear analysis of equilibria, stability properties, convergence, monotonicity, positivity, and threshold conditions. For the network SI setting, specific contributions include establishing its equilibria, stability, and positivity properties. For the network SIS setting, we review a well-known deterministic model, provide novel results on the computation and characterization of the endemic state (when the system is above the epidemic threshold), and present alternative proofs for some of its properties. Finally, for the network SIR setting, we propose novel results for transient behavior, threshold conditions, stability properties, and asymptotic convergence. These results are analogous to those well-known for the scalar case. In addition, we provide a novel iterative algorithm to compute the asymptotic state of the network SIR system.

Fabio Pasqualetti, Antonio Franchi, Francesco Bullo

The subject of this work is the patrolling of an environment with the aid of a team of autonomous agents. We consider both the design of open-loop trajectories with optimal properties, and of distributed control laws converging to optimal trajectories. As performance criteria, the refresh time and the latency are considered, i.e., respectively, time gap between any two visits of the same region, and the time necessary to inform every agent about an event occurred in the environment. We associate a graph with the environment, and we study separately the case of a chain, tree, and cyclic graph. For the case of chain graph, we first describe a minimum refresh time and latency team trajectory, and we propose a polynomial time algorithm for its computation. Then, we describe a distributed procedure that steers the robots toward an optimal trajectory. For the case of tree graph, a polynomial time algorithm is developed for the minimum refresh time problem, under the technical assumption of a constant number of robots involved in the patrolling task. Finally, we show that the design of a minimum refresh time trajectory for a cyclic graph is NP-hard, and we develop a constant factor approximation algorithm.

Fabio Pasqualetti, Ruggero Carli, Francesco Bullo

This work presents a distributed method for control centers to monitor the operating condition of a power network, i.e., to estimate the network state, and to ultimately determine the occurrence of threatening situations. State estimation has been recognized to be a fundamental task for network control centers to ensure correct and safe functionalities of power grids. We consider (static) state estimation problems, in which the state vector consists of the voltage magnitude and angle at all network buses. We consider the state to be linearly related to network measurements, which include power flows, current injections, and voltages phasors at some buses. We admit the presence of several cooperating control centers, and we design two distributed methods for them to compute the minimum variance estimate of the state given the network measurements. The two distributed methods rely on different modes of cooperation among control centers: in the first method an incremental mode of cooperation is used, whereas, in the second method, a diffusive interaction is implemented. Our procedures, which require each control center to know only the measurements and structure of a subpart of the whole network, are computationally efficient and scalable with respect to the network dimension, provided that the number of control centers also increases with the network cardinality. Additionally, a finite-memory approximation of our diffusive algorithm is proposed, and its accuracy is characterized. Finally, our estimation methods are exploited to develop a distributed algorithm to detect corrupted data among the network measurements.

Joseph W. Durham, Ruggero Carli, Paolo Frasca et al.

We propose distributed algorithms to automatically deploy a team of mobile robots to partition and provide coverage of a non-convex environment. To handle arbitrary non-convex environments, we represent them as graphs. Our partitioning and coverage algorithm requires only short-range, unreliable pairwise "gossip" communication. The algorithm has two components: (1) a motion protocol to ensure that neighboring robots communicate at least sporadically, and (2) a pairwise partitioning rule to update territory ownership when two robots communicate. By studying an appropriate dynamical system on the space of partitions of the graph vertices, we prove that territory ownership converges to a pairwise-optimal partition in finite time. This new equilibrium set represents improved performance over common Lloyd-type algorithms. Additionally, we detail how our algorithm scales well for large teams in large environments and how the computation can run in anytime with limited resources. Finally, we report on large-scale simulations in complex environments and hardware experiments using the Player/Stage robot control system.

Fabio Pasqualetti, Domenica Borra, Francesco Bullo

This work studies consensus strategies for networks of agents with limited memory, computation, and communication capabilities. We assume that agents can process only values from a finite alphabet, and we adopt the framework of finite fields, where the alphabet consists of the integers {0,...,p-1}, for some prime number p, and operations are performed modulo p. Thus, we define a new class of consensus dynamics, which can be exploited in certain applications such as pose estimation in capacity and memory constrained sensor networks. For consensus networks over finite fields, we provide necessary and sufficient conditions on the network topology and weights to ensure convergence. We show that consensus networks over finite fields converge in finite time, a feature that can be hardly achieved over the field of real numbers. For the design of finite-field consensus networks, we propose a general design method, with high computational complexity, and a network composition rule to generate large consensus networks from smaller components. Finally, we discuss the application of finite-field consensus networks to distributed averaging and pose estimation in sensor networks.

Wenjun Mei, Francesco Bullo

LaSalle invariance principle was originally proposed in the 1950's and has become a fundamental mathematical tool in the area of dynamical systems and control. In both theoretical research and engineering practice, discrete-time dynamical systems have been at least as extensively studied as continuous-time systems. For example, model predictive control is typically studied in discrete-time via Lyapunov methods. However, there is a peculiar absence in the standard literature of standard treatments of Lyapunov functions and LaSalle invariance principle for discrete-time nonlinear systems. Most of the textbooks on nonlinear dynamical systems focus only on continuous-time systems. In Chapter 1 of the book by LaSalle [11], the author establishes the LaSalle invariance principle for difference equation systems. However, all the useful lemmas in [11] are given in the form of exercises with no proof provided. In this document, we provide the proofs of all the lemmas proposed in [11] that are needed to derive the main theorem on the LaSalle invariance principle for discrete-time dynamical systems. We organize all the materials in a self-contained manner. We first introduce some basic concepts and definitions in Section 1, such as dynamical systems, invariant sets, and limit sets. In Section 2 we present and prove some useful lemmas on the properties of invariant sets and limit sets. Finally, we establish the original LaSalle invariance principle for discrete-time dynamical systems and a simple extension in Section~3. In Section 4, we provide some references on extensions of LaSalle invariance principles for further reading. This document is intended for educational and tutorial purposes and contains lemmas that might be useful as a reference for researchers.

Saber Jafarpour, Francesco Bullo

Synchronization in coupled oscillators networks is a remarkable phenomenon of relevance in numerous fields. For Kuramoto oscillators the loss of synchronization is determined by a trade-off between coupling strength and oscillator heterogeneity. Despite extensive prior work, the existing sufficient conditions for synchronization are either very conservative or heuristic and approximate. Using a novel cutset projection operator, we propose a new family of sufficient synchronization conditions; these conditions rigorously identify the correct functional form of the trade-off between coupling strength and oscillator heterogeneity. To overcome the need to solve a nonconvex optimization problem, we then provide two explicit bounding methods, thereby obtaining (i) the best-known sufficient condition for unweighted graphs based on the 2-norm, and (ii) the first-known generally-applicable sufficient condition based on the $\infty$-norm. We conclude with a comparative study of our novel $\infty$-norm condition for specific topologies and IEEE test cases; for most IEEE test cases our new sufficient condition is one to two orders of magnitude more accurate than previous rigorous tests.

Fabio Pasqualetti, Florian Dörfler, Francesco Bullo

Cyber-physical systems integrate computation, communication, and physical capabilities to interact with the physical world and humans. Besides failures of components, cyber-physical systems are prone to malignant attacks, and specific analysis tools as well as monitoring mechanisms need to be developed to enforce system security and reliability. This paper proposes a unified framework to analyze the resilience of cyber-physical systems against attacks cast by an omniscient adversary. We model cyber-physical systems as linear descriptor systems, and attacks as exogenous unknown inputs. Despite its simplicity, our model captures various real-world cyber-physical systems, and it includes and generalizes many prototypical attacks, including stealth, (dynamic) false-data injection and replay attacks. First, we characterize fundamental limitations of static, dynamic, and active monitors for attack detection and identification. Second, we provide constructive algebraic conditions to cast undetectable and unidentifiable attacks. Third, by using the system interconnection structure, we describe graph-theoretic conditions for the existence of undetectable and unidentifiable attacks. Finally, we validate our findings through some illustrative examples with different cyber-physical systems, such as a municipal water supply network and two electrical power grids.

Fabio Pasqualetti, Florian Dörfler, Francesco Bullo

Cyber-physical systems integrate computation, communication, and physical capabilities to interact with the physical world and humans. Besides failures of components, cyber-physical systems are prone to malicious attacks so that specific analysis tools and monitoring mechanisms need to be developed to enforce system security and reliability. This paper builds upon the results presented in our companion paper [1] and proposes centralized and distributed monitors for attack detection and identification. First, we design optimal centralized attack detection and identification monitors. Optimality refers to the ability of detecting (respectively identifying) every detectable (respectively identifiable) attack. Second, we design an optimal distributed attack detection filter based upon a waveform relaxation technique. Third, we show that the attack identification problem is computationally hard, and we design a sub-optimal distributed attack identification procedure with performance guarantees. Finally, we illustrate the robustness of our monitors to system noise and unmodeled dynamics through a simulation study.

Francesco Bullo, Fabio Fagnani, Barbara Franci

Recent contributions have studied how an influence system may affect the wisdom of crowd phenomenon. In the so-called naive learning setting, a crowd of individuals holds opinions that are statistically independent estimates of an unknown parameter; the crowd is wise when the average opinion converges to the true parameter in the limit of infinitely many individuals. Unfortunately, even starting from wise initial opinions, a crowd subject to certain influence systems may lose its wisdom. It is of great interest to characterize when an influence system preserves the crowd wisdom effect. In this paper we introduce and characterize numerous wisdom preservation properties of the basic French-DeGroot influence system model. Instead of requiring complete convergence to consensus as in the previous naive learning model by Golub and Jackson, we study finite-time executions of the French-DeGroot influence process and establish in this novel context the notion of prominent families (as a group of individuals with outsize influence). Surprisingly, finite-time wisdom preservation of the influence system is strictly distinct from its infinite-time version. We provide a comprehensive treatment of various finite-time wisdom preservation notions, counterexamples to meaningful conjectures, and a complete characterization of equal-neighbor influence systems.

Wenjun Mei, Noah E. Friedkin, Kyle Lewis et al.

This paper proposes models of learning process in teams of individuals who collectively execute a sequence of tasks and whose actions are determined by individual skill levels and networks of interpersonal appraisals and influence. The closely-related proposed models have increasing complexity, starting with a centralized manager-based assignment and learning model, and finishing with a social model of interpersonal appraisal, assignments, learning, and influences. We show how rational optimal behavior arises along the task sequence for each model, and discuss conditions of suboptimality. Our models are grounded in replicator dynamics from evolutionary games, influence networks from mathematical sociology, and transactive memory systems from organization science.

Alexander Davydov, Saber Jafarpour, Matthew Abate et al.

We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs). INNs are a class of implicit learning models that use implicit equations as layers and have been shown to exhibit several notable benefits over traditional deep neural networks. We first establish that tight inclusion functions of neural networks, which provide the tightest rectangular over-approximation of an input-output map, lead to sharper robustness guarantees than the well-studied robustness measures of local Lipschitz constants. Like Lipschitz constants, tight inclusions functions are computationally challenging to obtain, and we thus propose using mixed monotonicity and contraction theory to obtain computationally efficient estimates of tight inclusion functions for INNs. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs. We design a novel optimization problem for training robust INNs and we provide empirical evidence that suitably-trained INNs can be more robust than comparably-trained feedforward networks.

Saber Jafarpour, Alexander Davydov, Matthew Abate et al.

This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks based upon non-Euclidean contraction theory. The basic idea is to cast the robustness analysis of a neural network as a reachability problem and use (i) the $\ell_{\infty}$-norm input-output Lipschitz constant and (ii) the tight inclusion function of the network to over-approximate its reachable sets. First, for a given implicit neural network, we use $\ell_{\infty}$-matrix measures to propose sufficient conditions for its well-posedness, design an iterative algorithm to compute its fixed points, and provide upper bounds for its $\ell_\infty$-norm input-output Lipschitz constant. Second, we introduce a related embedded network and show that the embedded network can be used to provide an $\ell_\infty$-norm box over-approximation of the reachable sets of the original network. Moreover, we use the embedded network to design an iterative algorithm for computing the upper bounds of the original system's tight inclusion function. Third, we use the upper bounds of the Lipschitz constants and the upper bounds of the tight inclusion functions to design two algorithms for the training and robustness verification of implicit neural networks. Finally, we apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.

Ege Demirci, Francesco Bullo, Ananthram Swami et al.

Recovering missing flows on the edges of a network, while exactly respecting local conservation laws, is a fundamental inverse problem that arises in many systems such as transportation, energy, and mobility. We introduce FlowSymm, a novel architecture that combines (i) a group-action on divergence-free flows, (ii) a graph-attention encoder to learn feature-conditioned weights over these symmetry-preserving actions, and (iii) a lightweight Tikhonov refinement solved via implicit bilevel optimization. The method first anchors the given observation on a minimum-norm divergence-free completion. We then compute an orthonormal basis for all admissible group actions that leave the observed flows invariant and parameterize the valid solution subspace, which shows an Abelian group structure under vector addition. A stack of GATv2 layers then encodes the graph and its edge features into per-edge embeddings, which are pooled over the missing edges and produce per-basis attention weights. This attention-guided process selects a set of physics-aware group actions that preserve the observed flows. Finally, a scalar Tikhonov penalty refines the missing entries via a convex least-squares solver, with gradients propagated implicitly through Cholesky factorization. Across three real-world flow benchmarks (traffic, power, bike), FlowSymm outperforms state-of-the-art baselines in RMSE, MAE and correlation metrics.

Arthur N. Montanari, Francesco Bullo, Dmitry Krotov et al.

Recent advances at the intersection of control theory, neuroscience, and machine learning have revealed novel mechanisms by which dynamical systems perform computation. These advances encompass a wide range of conceptual, mathematical, and computational ideas, with applications for model learning and training, memory retrieval, data-driven control, and optimization. This tutorial focuses on neuro-inspired approaches to computation that aim to improve scalability, robustness, and energy efficiency across such tasks, bridging the gap between artificial and biological systems. Particular emphasis is placed on energy-based dynamical models that encode information through gradient flows and energy landscapes. We begin by reviewing classical formulations, such as continuous-time Hopfield networks and Boltzmann machines, and then extend the framework to modern developments. These include dense associative memory models for high-capacity storage, oscillator-based networks for large-scale optimization, and proximal-descent dynamics for composite and constrained reconstruction. The tutorial demonstrates how control-theoretic principles can guide the design of next-generation neurocomputing systems, steering the discussion beyond conventional feedforward and backpropagation-based approaches to artificial intelligence.

Anton V. Proskurnikov, Francesco Bullo

Recent studies on stability and contractivity have highlighted the importance of semi-inner products, which we refer to as pairings, associated with general norms. A pairing is a binary operation that relates the derivative of a curve's norm to the radius-vector of the curve and its tangent. This relationship, known as the curve norm derivative formula, is crucial when using the norm as a Lyapunov function. Another important property of the pairing, used in stability and contraction criteria, is the so-called Lumer inequality, which relates the pairing to the induced logarithmic norm. We prove that the curve norm derivative formula and Lumer's inequality are, in fact, equivalent to each other and to several simpler properties. We then introduce and characterize regular pairings that satisfy all of these properties. Our results unify several independent theories of pairings (semi-inner products) developed in previous work on functional analysis and control theory. Additionally, we introduce the polyhedral max pairing and develop computational tools for polyhedral norms, advancing contraction theory in non-Euclidean spaces.

Veronica Centorrino, Francesca Rossi, Francesco Bullo et al.

This paper studies equality-constrained composite minimization problems. This class of problems, capturing regularization terms and inequality constraints, naturally arises in a wide range of engineering and machine learning applications. To tackle these optimization problems, inspired by recent results, we introduce the \emph{proportional--integral proximal gradient dynamics} (PI--PGD): a closed-loop system where the Lagrange multipliers are control inputs and states are the problem decision variables. First, we establish the equivalence between the stationary points of the minimization problem and the equilibria of the PI--PGD. Then for the case of affine constraints, by leveraging tools from contraction theory we give a comprehensive convergence analysis for the dynamics, showing linear--exponential convergence towards the equilibrium. That is, the distance between each solution and the equilibrium is upper bounded by a function that first decreases linearly and then exponentially. Our findings are illustrated numerically on a set of representative examples, which include an exploratory application to nonlinear equality constraints.

Anand Gokhale, Anton V. Proskurnikov, Yu Kawano et al.

This paper investigates continuous-time and discrete-time firing-rate and Hopfield recurrent neural networks (RNNs), with applications in nonlinear control design and implicit deep learning. First, we introduce a nonlinear separation principle that guarantees global exponential stability for the interconnection of a contracting state-feedback controller and a contracting observer, alongside parametric extensions for robustness and equilibrium tracking. Second, we derive sharp linear matrix inequality (LMI) conditions that guarantee the contractivity of both firing rate and Hopfield neural network architectures. We establish structural relationships among these certificates-demonstrating that continuous-time models with monotone non-decreasing activations maximize the admissible weight space, and extend these stability guarantees to interconnected systems and Graph RNNs. Third, we combine our separation principle and LMI framework to solve the output reference tracking problem for RNN-modeled plants. We provide LMI synthesis methods for feedback controllers and observers, and rigorously design a low-gain integral controller to eliminate steady-state error. Finally, we derive an exact, unconstrained algebraic parameterization of our contraction LMIs to design highly expressive implicit neural networks, achieving competitive accuracy and parameter efficiency on standard image classification benchmarks.

William Retnaraj, Simone Betteti, Alexander Davydov et al.

Linear-threshold networks (LTNs) capture the mesoscale behavior of interacting populations of neurons and are of particular interest to control theorists due to their dynamical richness and relative ease of analysis. The aim of this paper is to advance the study of global asymptotic stability in LTNs with asymmetric neural interactions and heterogeneous dissipation under the structural Lyapunov diagonal stability (LDS) condition. To this end, we introduce a one-parameter family of LTNs that preserves the LDS condition and has a parameter-independent equilibrium set. In the fast limit, this family converges to a projected dynamical system (PDS), while in the slow limit, it converges to a discontinuous hard-selector system (HSS). Under LDS, we prove that the fast PDS limit is globally exponentially stable and that the HSS limit is globally asymptotically stable. This alignment suggests that the limiting systems capture essential mechanisms governing stability across the entire LTN family. Together with numerical evidence, these findings indicate that resolving stability at the fast and slow endpoints provides a promising and structurally grounded path toward establishing global stability for LTNs with biologically plausible recurrence and diagonal dissipation.

Francesca Rossi, Veronica Centorrino, Francesco Bullo et al.

The ability to compose acquired skills to plan and execute behaviors is a hallmark of natural intelligence. Yet, despite remarkable cross-disciplinary efforts, a principled account of how task structure shapes gating and how such computations could be delivered in neural circuits, remains elusive. Here we introduce GateMod, an interpretable theoretically grounded computational model linking the emergence of gating to the underlying decision-making task, and to a neural circuit architecture. We first develop GateFrame, a normative framework casting policy gating into the minimization of the free energy. This framework, relating gating rules to task, applies broadly across neuroscience, cognitive and computational sciences. We then derive GateFlow, a continuous-time energy based dynamics that provably converges to GateFrame optimal solution. Convergence, exponential and global, follows from a contractivity property that also yields robustness and other desirable properties. Finally, we derive a neural circuit from GateFlow, GateNet. This is a soft-competitive recurrent circuit whose components perform local and contextual computations consistent with known dendritic and neural processing motifs. We evaluate GateMod across two different settings: collective behaviors in multi-agent systems and human decision-making in multi-armed bandits. In all settings, GateMod provides interpretable mechanistic explanations of gating and quantitatively matches or outperforms established models. GateMod offers a unifying framework for neural policy gating, linking task objectives, dynamical computation, and circuit-level mechanisms. It provides a framework to understand gating in natural agents beyond current explanations and to equip machines with this ability.

Saber Jafarpour, Alexander Davydov, Anton V. Proskurnikov et al.

Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicit-depth learning models where function evaluation is performed by solving a fixed point equation. They generalize classic feedforward models and are equivalent to infinite-depth weight-tied feedforward networks. While implicit models show improved accuracy and significant reduction in memory consumption, they can suffer from ill-posedness and convergence instability. This paper provides a new framework, which we call Non-Euclidean Monotone Operator Network (NEMON), to design well-posed and robust implicit neural networks based upon contraction theory for the non-Euclidean norm $\ell_{\infty}$. Our framework includes (i) a novel condition for well-posedness based on one-sided Lipschitz constants, (ii) an average iteration for computing fixed-points, and (iii) explicit estimates on input-output Lipschitz constants. Additionally, we design a training problem with the well-posedness condition and the average iteration as constraints and, to achieve robust models, with the input-output Lipschitz constant as a regularizer. Our $\ell_{\infty}$ well-posedness condition leads to a larger polytopic training search space than existing conditions and our average iteration enjoys accelerated convergence. Finally, we evaluate our framework in image classification through the MNIST and the CIFAR-10 datasets. Our numerical results demonstrate improved accuracy and robustness of the implicit models with smaller input-output Lipschitz bounds. Code is available at https://github.com/davydovalexander/Non-Euclidean_Mon_Op_Net.

Arie Ogranovich, Taosha Guo, Arvind R. Venkatakrishnan et al.

Associative memory systems enable content-addressable storage and retrieval of patterns, a capability central to biological neural computation and artificial intelligence. Classical implementations such as Hopfield networks face fundamental limitations in memory capacity, scaling at most linearly with network size. We present an associative memory architecture based on Kuramoto oscillator networks with honeycomb topology in which memories are encoded as stable phase-locked configurations. The honeycomb network consists of multiple cycles that share nodes in a chain-like arrangement, creating a one-dimensional lattice of chained+loops. We prove that this architecture achieves exponential memory capacity: a network of $N$ oscillators can store $(2\lceil n_c/4 \rceil - 1)^m$ distinct patterns, where $m$ honeycomb cycles each contain $n_c$ oscillators. Moreover, we fully characterize all stable configurations and prove that each memory's basin of attraction maintains a guaranteed minimum size independent of network scale. Simulations using charge-density-wave (CDW) oscillators validate predicted phase-locking behavior, demonstrating practical realizability in neuromorphic hardware.

Abed K. Musaffar, Ambuj Singh, Francesco Bullo

Large language models (LLMs) are increasingly deployed in human-AI teams as support agents for complex tasks such as information retrieval, programming, and decision-making assistance. While these agents' autonomy and contextual knowledge enables them to be useful, it also exposes them to a broad range of attacks, including data poisoning, prompt injection, and even prompt engineering. Through these attack vectors, malicious actors can manipulate an LLM agent to provide harmful information, potentially manipulating human agents to make harmful decisions. While prior work has focused on LLMs as attack targets or adversarial actors, this paper studies their potential role as defensive supervisors within mixed human-AI teams. Using a dataset consisting of multi-party conversations and decisions for a real human-AI team over a 25 round horizon, we formulate the problem of malicious behavior detection from interaction traces. We find that LLMs are capable of identifying malicious behavior in real-time, and without task-specific information, indicating the potential for task-agnostic defense. Moreover, we find that the malicious behavior of interest is not easily identified using simple heuristics, further suggesting the introduction of LLM defenders could render human teams more robust to certain classes of attack.

Yu Kawano, Francesco Bullo

Many control, optimization, and learning algorithms rely on discretizations of continuous-time contracting systems, where preservation of contractivity under numerical integration is key for stability, robustness, and reliable fixed-point computation. In this paper, we establish conditions under which multi-stage Runge-Kutta methods preserve strong contractivity when discretizing infinitesimally contractive continuous-time systems. For explicit Runge-Kutta methods, preservation conditions are derived by bounding Lipschitz constants of the associated composite stage mappings, leading to coefficient-dependent criteria. For implicit methods, the algebraic structure of the stage equations enables explicit conditions on the Runge-Kutta coefficients that guarantee preservation of strong contractivity. In the implicit case, these results extend classical guarantees, typically limited to weak contractivity in the Euclidean metric, to strong contractivity with respect to the $\ell_1$-, $\ell_2$-, and $\ell_\infty$-norms. In addition, we study well-definedness of implicit methods through an auxiliary continuous-time system associated with the stage equations. We show that strong infinitesimal contractivity of this auxiliary system is sufficient to guarantee unique solvability of the stage equations. This analysis generalizes standard well-definedness conditions and provides a dynamic implementation approach that avoids direct solution of the implicit algebraic equations.

Sean Jaffe, Alexander Davydov, Deniz Lapsekili et al.

Global stability and robustness guarantees in learned dynamical systems are essential to ensure well-behavedness of the systems in the face of uncertainty. We present Extended Linearized Contracting Dynamics (ELCD), the first neural network-based dynamical system with global contractivity guarantees in arbitrary metrics. The key feature of ELCD is a parametrization of the extended linearization of the nonlinear vector field. In its most basic form, ELCD is guaranteed to be (i) globally exponentially stable, (ii) equilibrium contracting, and (iii) globally contracting with respect to some metric. To allow for contraction with respect to more general metrics in the data space, we train diffeomorphisms between the data space and a latent space and enforce contractivity in the latent space, which ensures global contractivity in the data space. We demonstrate the performance of ELCD on the high dimensional LASA, multi-link pendulum, and Rosenbrock datasets.

Simone Betteti, Giacomo Baggio, Francesco Bullo et al.

The Hopfield model provides a mathematically idealized yet insightful framework for understanding the mechanisms of memory storage and retrieval in the human brain. This model has inspired four decades of extensive research on learning and retrieval dynamics, capacity estimates, and sequential transitions among memories. Notably, the role and impact of external inputs has been largely underexplored, from their effects on neural dynamics to how they facilitate effective memory retrieval. To bridge this gap, we propose a novel dynamical system framework in which the external input directly influences the neural synapses and shapes the energy landscape of the Hopfield model. This plasticity-based mechanism provides a clear energetic interpretation of the memory retrieval process and proves effective at correctly classifying highly mixed inputs. Furthermore, we integrate this model within the framework of modern Hopfield architectures, using this connection to elucidate how current and past information are combined during the retrieval process. Finally, we embed both the classic and the new model in an environment disrupted by noise and compare their robustness during memory retrieval.

Anand Gokhale, Anton V. Proskurnikov, Yu Kawano et al.

This paper studies contractivity of firing-rate and Hopfield recurrent neural networks. We derive sharp LMI conditions on the synaptic matrices that characterize contractivity of both architectures, for activation functions that are either non-expansive or monotone non-expansive, in both continuous and discrete time. We establish structural relationships among these conditions, including connections to Schur diagonal stability and the recovery of optimal contraction rates for symmetric synaptic matrices. We demonstrate the utility of these results through two applications. First, we develop an LMI-based design procedure for low-gain integral controllers enabling reference tracking in contracting firing rate networks. Second, we provide an exact parameterization of weight matrices that guarantee contraction and use it to improve the expressivity of Implicit Neural Networks, achieving competitive performance on image classification benchmarks with fewer parameters.

Anand Gokhale, Vaibhav Srivastava, Francesco Bullo

Large language models (LLMs) have shown promise in zero-shot and single step reasoning and decision making problems, but in long horizon sequential planning tasks, their errors compound, often leading to unreliable or inefficient behavior. We introduce LogicGuard, a modular actor-critic architecture in which an LLM actor is guided by a trajectory level LLM critic that communicates through Linear Temporal Logic (LTL). Our setup combines the reasoning strengths of language models with the guarantees of formal logic. The actor selects high-level actions from natural language observations, while the critic analyzes full trajectories and proposes new LTL constraints that shield the actor from future unsafe or inefficient behavior. LogicGuard supports both fixed safety rules and adaptive, learned constraints, and is model-agnostic: any LLM-based planner can serve as the actor, with LogicGuard acting as a logic-generating wrapper. We formalize planning as graph traversal under symbolic constraints, allowing LogicGuard to analyze failed or suboptimal trajectories and generate new temporal logic rules that improve future behavior. To demonstrate generality, we evaluate LogicGuard across two distinct settings: short-horizon general tasks and long-horizon specialist tasks. On the Behavior benchmark of 100 household tasks, LogicGuard increases task completion rates by 25% over a baseline InnerMonologue planner. On the Minecraft diamond-mining task, which is long-horizon and requires multiple interdependent subgoals, LogicGuard improves both efficiency and safety compared to SayCan and InnerMonologue. These results show that enabling LLMs to supervise each other through temporal logic yields more reliable, efficient and safe decision-making for both embodied agents.

Simone Betteti, Giacomo Baggio, Francesco Bullo et al.

Firing rate models are dynamical systems widely used in applied and theoretical neuroscience to describe local cortical dynamics in neuronal populations. By providing a macroscopic perspective of neuronal activity, these models are essential for investigating oscillatory phenomena, chaotic behavior, and associative memory processes. Despite their widespread use, the application of firing rate models to associative memory networks has received limited mathematical exploration, and most existing studies are focused on specific models. Conversely, well-established associative memory designs, such as Hopfield networks, lack key biologically-relevant features intrinsic to firing rate models, including positivity and interpretable synaptic matrices that reflect excitatory and inhibitory interactions. To address this gap, we propose a general framework that ensures the emergence of re-scaled memory patterns as stable equilibria in the firing rate dynamics. Furthermore, we analyze the conditions under which the memories are locally and globally asymptotically stable, providing insights into constructing biologically-plausible and robust systems for associative memory retrieval.

Sean Jaffe, Ambuj K. Singh, Francesco Bullo

Compressing large neural networks with minimal performance loss is crucial to enabling their deployment on edge devices. (Cho et al., 2022) proposed a weight quantization method that uses an attention-based clustering algorithm called differentiable $k$-means (DKM). Despite achieving state-of-the-art results, DKM's performance is constrained by its heavy memory dependency. We propose an implicit, differentiable $k$-means algorithm (IDKM), which eliminates the major memory restriction of DKM. Let $t$ be the number of $k$-means iterations, $m$ be the number of weight-vectors, and $b$ be the number of bits per cluster address. IDKM reduces the overall memory complexity of a single $k$-means layer from $\mathcal{O}(t \cdot m \cdot 2^b)$ to $\mathcal{O}( m \cdot 2^b)$. We also introduce a variant, IDKM with Jacobian-Free-Backpropagation (IDKM-JFB), for which the time complexity of the gradient calculation is independent of $t$ as well. We provide a proof of concept of our methods by showing that, under the same settings, IDKM achieves comparable performance to DKM with less compute time and less memory. We also use IDKM and IDKM-JFB to quantize a large neural network, Resnet18, on hardware where DKM cannot train at all.

Wei Ye, Francesco Bullo, Noah Friedkin et al.

AI and humans bring complementary skills to group deliberations. Modeling this group decision making is especially challenging when the deliberations include an element of risk and an exploration-exploitation process of appraising the capabilities of the human and AI agents. To investigate this question, we presented a sequence of intellective issues to a set of human groups aided by imperfect AI agents. A group's goal was to appraise the relative expertise of the group's members and its available AI agents, evaluate the risks associated with different actions, and maximize the overall reward by reaching consensus. We propose and empirically validate models of human-AI team decision making under such uncertain circumstances, and show the value of socio-cognitive constructs of prospect theory, influence dynamics, and Bayesian learning in predicting the behavior of human-AI groups.

Saber Jafarpour, Matthew Abate, Alexander Davydov et al.

Implicit neural networks are a general class of learning models that replace the layers in traditional feedforward models with implicit algebraic equations. Compared to traditional learning models, implicit networks offer competitive performance and reduced memory consumption. However, they can remain brittle with respect to input adversarial perturbations. This paper proposes a theoretical and computational framework for robustness verification of implicit neural networks; our framework blends together mixed monotone systems theory and contraction theory. First, given an implicit neural network, we introduce a related embedded network and show that, given an $\ell_\infty$-norm box constraint on the input, the embedded network provides an $\ell_\infty$-norm box overapproximation for the output of the given network. Second, using $\ell_{\infty}$-matrix measures, we propose sufficient conditions for well-posedness of both the original and embedded system and design an iterative algorithm to compute the $\ell_{\infty}$-norm box robustness margins for reachability and classification problems. Third, of independent value, we propose a novel relative classifier variable that leads to tighter bounds on the certified adversarial robustness in classification problems. Finally, we perform numerical simulations on a Non-Euclidean Monotone Operator Network (NEMON) trained on the MNIST dataset. In these simulations, we compare the accuracy and run time of our mixed monotone contractive approach with the existing robustness verification approaches in the literature for estimating the certified adversarial robustness.

Pedro Cisneros-Velarde, Francesco Bullo

Much recent interest has focused on the design of optimization algorithms from the discretization of an associated optimization flow, i.e., a system of differential equations (ODEs) whose trajectories solve an associated optimization problem. Such a design approach poses an important problem: how to find a principled methodology to design and discretize appropriate ODEs. This paper aims to provide a solution to this problem through the use of contraction theory. We first introduce general mathematical results that explain how contraction theory guarantees the stability of the implicit and explicit Euler integration methods. Then, we propose a novel system of ODEs, namely the Accelerated-Contracting-Nesterov flow, and use contraction theory to establish it is an optimization flow with exponential convergence rate, from which the linear convergence rate of its associated optimization algorithm is immediately established. Remarkably, a simple explicit Euler discretization of this flow corresponds to the Nesterov acceleration method. Finally, we present how our approach leads to performance guarantees in the design of optimization algorithms for time-varying optimization problems.

Omid Askarisichani, Elizabeth Y. Huang, Abed K. Musaffar et al.

Discovering the antecedents of individuals' influence in collaborative environments is an important, practical, and challenging problem. In this paper, we study interpersonal influence in small groups of individuals who collectively execute a sequence of intellective tasks. We observe that along an issue sequence with feedback, individuals with higher expertise and social confidence are accorded higher interpersonal influence. We also observe that low-performing individuals tend to underestimate their high-performing teammate's expertise. Based on these observations, we introduce three hypotheses and present empirical and theoretical support for their validity. We report empirical evidence on longstanding theories of transactive memory systems, social comparison, and confidence heuristics on the origins of social influence. We propose a cognitive dynamical model inspired by these theories to describe the process by which individuals adjust interpersonal influences over time. We demonstrate the model's accuracy in predicting individuals' influence and provide analytical results on its asymptotic behavior for the case with identically performing individuals. Lastly, we propose a novel approach using deep neural networks on a pre-trained text embedding model for predicting the influence of individuals. Using message contents, message times, and individual correctness collected during tasks, we are able to accurately predict individuals' self-reported influence over time. Extensive experiments verify the accuracy of the proposed models compared to baselines such as structural balance and reflected appraisal model. While the neural networks model is the most accurate, the dynamical model is the most interpretable for influence prediction.

Xiaoming Duan, Francesco Bullo

This article surveys recent advancements of strategy designs for persistent robotic surveillance tasks with the focus on stochastic approaches. The problem describes how mobile robots stochastically patrol a graph in an efficient way where the efficiency is defined with respect to relevant underlying performance metrics. We first start by reviewing the basics of Markov chains, which is the primary motion model for stochastic robotic surveillance. Then two main criteria regarding the speed and unpredictability of surveillance strategies are discussed. The central objects that appear throughout the treatment is the hitting times of Markov chains, their distributions and expectations. We formulate various optimization problems based on the concerned metrics in different scenarios and establish their respective properties.

Rui Yan, Xiaoming Duan, Zongying Shi et al.

This paper introduces two metrics (cycle-based and memory-based metrics), grounded on a dynamical game-theoretic solution concept called sink equilibrium, for the evaluation, ranking, and computation of policies in multi-agent learning. We adopt strict best response dynamics (SBRD) to model selfish behaviors at a meta-level for multi-agent reinforcement learning. Our approach can deal with dynamical cyclical behaviors (unlike approaches based on Nash equilibria and Elo ratings), and is more compatible with single-agent reinforcement learning than alpha-rank which relies on weakly better responses. We first consider settings where the difference between largest and second largest underlying metric has a known lower bound. With this knowledge we propose a class of perturbed SBRD with the following property: only policies with maximum metric are observed with nonzero probability for a broad class of stochastic games with finite memory. We then consider settings where the lower bound for the difference is unknown. For this setting, we propose a class of perturbed SBRD such that the metrics of the policies observed with nonzero probability differ from the optimal by any given tolerance. The proposed perturbed SBRD addresses the opponent-induced non-stationarity by fixing the strategies of others for the learning agent, and uses empirical game-theoretic analysis to estimate payoffs for each strategy profile obtained due to the perturbation.

Xiaoming Duan, Mishel George, Rushabh Patel et al.

This paper analyzes the meeting time between a pair of pursuer and evader performing random walks on digraphs. The existing bounds on the meeting time usually work only for certain classes of walks and cannot be used to formulate optimization problems and design robotic strategies. First, by analyzing multiple random walks on a common graph as a single random walk on the Kronecker product graph, we provide the first closed-form expression for the expected meeting time in terms of the transition matrices of the moving agents. This novel expression leads to necessary and sufficient conditions for the meeting time to be finite and to insightful graph-theoretic interpretations. Second, based on the closed-form expression, we setup and study the minimization problem for the expected capture time for a pursuer/evader pair. We report theoretical and numerical results on basic case studies to show the effectiveness of the design.

Jeffrey R. Peters, Amit Surana, Grant S. Taylor et al.

A framework is introduced for planning unmanned aerial vehicle flight paths for visual surveillance of ground targets, each having particular viewing requirements. Specifically, each target is associated with a set of imaging parameters, including a desired (i) tilt angle, (ii) azimuth, with the option of a 360-degree view, and (iii) dwell-time. Tours are sought to image the targets, while minimizing both the total mission time and the time required to reach the initial target. An epsilon-constraint scalarization is used to pose the multi-objective problem as a constrained optimization, which, through careful discretization, can be approximated as a discrete graph-search. It is shown that, in many cases, this approximation is equivalent to a generalized traveling salesperson problem. A heuristic procedure for solving the discrete approximation and recovering solutions to the full routing problem is presented, and is shown to have resolution completeness properties. Algorithms are illustrated through numerical studies.

Saber Jafarpour, Elizabeth Y. Huang, Francesco Bullo

Synchronization in networks of coupled oscillators is a widely studied topic with extensive scientific and engineering applications. In this paper, we study the frequency synchronization problem for networks of Kuramoto oscillators with arbitrary topology and heterogeneous edge weights. We propose a novel equivalent transcription for the equilibrium synchronization equation. Using this transcription, we develop a power series expansion to compute the synchronized solution of the Kuramoto model as well as a sufficient condition for the strong convergence of this series expansion. Truncating the power series provides (i) an efficient approximation scheme for computing the synchronized solution, and (ii) a simple-to-check, statistically-correct hierarchy of increasingly accurate synchronization tests. This hierarchy of tests provides a theoretical foundation for and generalizes the best-known approximate synchronization test in the literature. Our numerical experiments illustrate the accuracy and the computational efficiency of the truncated series approximation compared to existing iterative methods and existing synchronization tests.

Elizabeth Y. Huang, Saber Jafarpour, Francesco Bullo

Synchronization in the networks of coupled oscillators is a widely studied topic in different areas. It is well-known that synchronization occurs if the connectivity of the network dominates heterogeneity of the oscillators. Despite extensive study on this topic, the quest for sharp closed-form synchronization tests is still in vain. In this paper, we present an algorithm for finding the Taylor expansion of the inverse Kuramoto map. We show that this Taylor series can be used to obtain a hierarchy of increasingly accurate approximate tests with low computational complexity. These approximate tests are then used to estimate the threshold of synchronization as well as the position of the synchronization manifold of the network.

Jeffrey R. Peters, Sean J. Wang, Amit Surana et al.

A decomposition-based coverage control scheme is proposed for multi-agent, persistent surveillance missions operating in a communication-constrained, dynamic environment. The proposed approach decouples high-level task assignment from low-level motion planning in a modular framework. Coverage assignments and surveillance parameters are managed by a central base station, and transmitted to mobile agents via unplanned and asynchronous exchanges. Coverage updates promote load balancing, while maintaining geometric and temporal characteristics that allow effective pairing with generic path planners. Namely, the proposed scheme guarantees that (i) coverage regions are connected and collectively cover the environment, (ii) subregions may only go uncovered for bounded periods of time, (iii) collisions (or sensing overlaps) are inherently avoided, and (iv) under static event likelihoods, the collective coverage regions converge to a Pareto-optimal configuration. This management scheme is then paired with a generic path planner satisfying loose assumptions. The scheme is illustrated through simulated surveillance missions.

Vaibhav Srivastava, Amit Surana, Miguel P. Eckstein et al.

We study the mixed human-robot team design in a system theoretic setting using the context of a surveillance mission. The three key coupled components of a mixed team design are (i) policies for the human operator, (ii) policies to account for erroneous human decisions, and (iii) policies to control the automaton. In this paper, we survey elements of human decision-making, including evidence aggregation, situational awareness, fatigue, and memory effects. We bring together the models for these elements in human decision-making to develop a single coherent model for human decision-making in a two-alternative choice task. We utilize the developed model to design efficient attention allocation policies for the human operator. We propose an anomaly detection algorithm that utilizes potentially erroneous decision by the operator to ascertain an anomalous region among the set of regions surveilled. Finally, we propose a stochastic vehicle routing policy that surveils an anomalous region with high probability. Our mixed team design relies on the certainty-equivalent receding-horizon control framework.

Vaibhav Srivastava, Fabio Pasqualetti, Francesco Bullo

We design persistent surveillance strategies for the quickest detection of anomalies taking place in an environment of interest. From a set of predefined regions in the environment, a team of autonomous vehicles collects noisy observations, which a control center processes. The overall objective is to minimize detection delay while maintaining the false alarm rate below a desired threshold. We present joint (i) anomaly detection algorithms for the control center and (ii) vehicle routing policies. For the control center, we propose parallel cumulative sum (CUSUM) algorithms (one for each region) to detect anomalies from noisy observations. For the vehicles, we propose a stochastic routing policy, in which the regions to be visited are chosen according to a probability vector. We study stationary routing policy (the probability vector is constant) as well as adaptive routing policies (the probability vector varies in time as a function of the likelihood of regional anomalies). In the context of stationary policies, we design a performance metric and minimize it to design an efficient stationary routing policy. Our adaptive policy improves upon the stationary counterpart by adaptively increasing the selection probability of regions with high likelihood of anomaly. Finally, we show the effectiveness of the proposed algorithms through numerical simulations and a persistent surveillance experiment.

Florian Dorfler, Francesco Bullo

Motivated by recent interest for multi-agent systems and smart power grid architectures, we discuss the synchronization problem for the network-reduced model of a power system with non-trivial transfer conductances. Our key insight is to exploit the relationship between the power network model and a first-order model of coupled oscillators. Assuming overdamped generators (possibly due to local excitation controllers), a singular perturbation analysis shows the equivalence between the classic swing equations and a non-uniform Kuramoto model. Here, non-uniform Kuramoto oscillators are characterized by multiple time constants, non-homogeneous coupling, and non-uniform phase shifts. Extending methods from transient stability, synchronization theory, and consensus protocols, we establish sufficient conditions for synchronization of non-uniform Kuramoto oscillators. These conditions reduce to and improve upon previously-available tests for the standard Kuramoto model. Combining our singular perturbation and Kuramoto analyses, we derive concise and purely algebraic conditions that relate synchronization and transient stability of a power network to the underlying system parameters and initial conditions.