Combinatorial and Probabilistic Approaches to Oscillator and Clock Synchronization

如果给一组人提供带有任意设定时间的本地时钟，并且没有全局参考（例如GPS），那么该组是否可能仅通过与附近成员通信来同步所有时钟？为了使分布式系统能够执行可能超出单个代理能力的高级任务，系统必须首先解决“时钟同步”问题，以建立共享的时间概念。几十年来，时钟同步（或耦合振荡器）的研究一直是数学和各个科学领域的重要研究课题，在野火监测、电力网络、机器人车辆网络、大规模信息融合和无线传感器网络等许多领域都有丰硕的应用。然而，我们对耦合振荡器系统的理论理解与现代应用环境中时钟同步算法的实际要求之间存在差距。该项目将开发基于组合和概率方法的系统方法来弥合这一差距。离散振荡器的使用将是开发更健壮和有效的时钟同步算法的关键线索，扩展当前的收敛保证证明技术，并为数据驱动的时钟同步问题方法提供基础。该项目还将为各级学生提供跨学科合作和研究机会，分析耦合振荡器行为的关键困难之一在于相空间中的循环层次。在文献中广泛使用的观察是，如果所有的初始阶段集中在一个开放的半圆，这样的循环层次消失，我们有鲁棒的同步结果在各种设置。因此，从任意初始配置导出全局同步不仅保证了时钟同步算法在任意扰动下的自稳定性，而且解决了这种半圆条件的理论局限性。通过扩展局部集中和自适应脉冲耦合方案等技术，该项目旨在从无向有限树上的任意初始配置中导出具有收敛时间最优界的非相同固有频率和非零传播延迟的信号的全局同步。结合生成树算法，将收敛结果扩展到任意图，并将复合算法作为一种快速、资源最小的现代无线传感器网络时钟同步算法实现。该项目还将为各级学生提供跨学科合作和研究机会。特别是，一些项目涉及在有限图上为离散耦合振荡器的一些模型的集体行为生成一个大型数据库，并应用机器学习技术提取保证同步的网络拓扑和初始配置对的关键特征。该项目将为学生提供从动力系统到计算机科学和机器学习的研究经验。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.