If a group of people is given local clocks with arbitrarily set times, and there is no global reference (for example GPS), is it possible for the group to synchronize all clocks by only communicating with nearby members? In order for a distributed system to be able to perform high-level tasks that may go beyond the capability of an individual agent, the system must first solve a "clock synchronization" problem to establish a shared notion of time. The study of clock synchronization (or coupled oscillators) has been an important subject of research in mathematics and various areas of science for decades, with fruitful applications in many areas including wildfire monitoring, electric power networks, robotic vehicle networks, large-scale information fusion, and wireless sensor networks. However, there has been a gap between our theoretical understanding of systems of coupled oscillators and practical requirements for clock synchronization algorithms in modern application contexts. This project will develop systematic approaches for bridging this gap based on combinatorial and probabilistic methods. The use of discrete oscillators will be a key thread in developing more robust and efficient clock synchronization algorithms, extending the current proof techniques for convergence guarantee, and providing a foundation for a data-driven approach to the clock synchronization problems. This project will also include interdisciplinary collaboration and research opportunities for students at all levels
One of the key difficulties in analyzing the behavior of coupled oscillators lies in the cyclic hierarchy in the phase space. A widely used observation in the literature is that, if all initial phases are concentrated in an open half-circle, such a cyclic hierarchy disappears and we have robust synchronization results in various settings. Hence deriving global synchronization from arbitrary initial configurations not only warrants self-stabilization of the clock synchronization algorithm under arbitrary perturbation, but also addresses the theoretical limitation of such a half-circle condition. By extending techniques such as local concentration and adaptive pulse-coupling scheme due to the PI, the project aims at deriving global synchronization from an arbitrary initial configuration on undirected finite trees, for non-identical natural frequencies and non-zero propagation delay of signals with optimal bounds on convergence time. The convergence result will be extended to arbitrary graphs by combining with a spanning tree algorithm, and the composite algorithm will be implemented as a fast and resource-minimal clock synchronization algorithm for modern wireless sensor networks. This project will also include interdisciplinary collaboration and research opportunities for students at all levels. In particular, some of the projects involve generating a large database for the collective behavior of some models of discrete coupled oscillators on finite graphs, and applying machine learning techniques to extract key features of the pair of network topology and initial configuration that guarantee synchronization. The project will provide students with research experiences ranging from dynamical systems to computer science and machine learning.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
