AF: Medium: Concurrency and Adaptive Self-Organization in Anonymous Dynamic Networks

在计算机科学中，分布式系统由许多计算实体（例如路由器、手机、群体机器人等）组成，每个计算实体独立运行自己的算法以协作执行大规模任务。现代分布式计算应用的一个关键主题是动态的影响，或者系统成员或它们之间的连接的频繁变化。从基于进出范围的智能手机的疾病接触追踪，到理解作为超有机体表现的社会性昆虫的集体智慧，这些“动态网络”的分布式算法实现了计算机科学内外的创新。该项目解决了动态网络当前算法的两个主要限制：假设动态永远不会与个体的行为同时发生，并假设动态网络一次只能执行一项任务。设计能够根据不断变化的环境调整其行为的分布式系统，即使存在并发动态，也会将这一丰富的理论更直接地与计算、生物和社会应用联系起来。此外，该项目还将在以下方面产生影响：(a) 扩大学生和教师对计算机科学的多元化参与；(b) 本科生研究，继续研究人员强大的指导记录；(c) 通过高级课程和研究讲座进行教育和推广。该项目研究动态网络的算法理论，即系统成员或其连接频繁（或对抗性）变化的分布式系统。受个人计算能力有限或没有明确计算能力的领域的推动，该项目特别关注节点匿名（缺乏唯一标识符）、具有次对数内存（不足以计算标识符）并通过消息传递进行通信的设置。该项目的核心问题有两个主要焦点：异步并发和自适应自组织。第一个目标是实现动态网络的并发控制，将异步并发的通用性与简单版本并发中算法设计和分析的便利性结合起来。第二个重点是自适应自组织，启动了由环境信号控制的时变系统任务的研究。这一系列问题抽象了自稳定任务分配，将动态网络核心分布式计算问题的现有研究扩展到匿名和自适应设置，甚至适合没有显式计算能力的建模系统（例如，粒状活性物质）。这些目标将共同推进动态网络理论的基础知识，并为下游在生物和社会系统中编程和表征集体行为的跨学科努力做出贡献。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

In computer science, a distributed system comprises many computational entities (e.g., routers, cell phones, swarm robots, etc.) that each independently run their own algorithms to cooperatively perform large-scale tasks. A key theme across modern applications of distributed computing is the impact of dynamics, or frequent changes in the system's members or the connections among them. From disease contact tracing based on smartphones coming in and out of range to understanding the collective intelligence of social insects behaving as a superorganism, distributed algorithms for these "dynamic networks" enable innovations both within and beyond computer science. This project addresses two major limitations of current algorithms for dynamic networks: assuming that dynamics can never happen at the same time as individuals' actions, and assuming the dynamic network can only perform one task at a time. Designing distributed systems that can adapt their behavior based on their changing environment, even in spite of concurrent dynamics, will tie this rich theory more directly to computational, biological, and social applications. Furthermore, the project will have impact in (a) broadening diverse participation in computer science at both the student and faculty levels, (b) undergraduate research, continuing the researchers' strong mentorship record, and (c) education and outreach through advanced courses and research talks.This project investigates the algorithmic theory of dynamic networks, i.e., distributed systems with frequent (or adversarial) changes in the system's members or their connections. Motivated by domains where individuals have limited or no explicit computational power, this project specifically focuses on a setting where nodes are anonymous (lacking unique identifiers), have sublogarithmic memory (insufficient for computing identifiers), and communicate via message passing. This project's core problems have two main foci: asynchronous concurrency and adaptive self-organization. The first thrust aims to achieve concurrency control for dynamic networks, bridging the generality of asynchronous concurrency with the ease of algorithm design and analysis in simpler versions of concurrency. The second thrust focuses on adaptive self-organization, initiating the study of time-varying system tasks controlled by environmental signals. This family of problems abstracts self-stabilizing task allocation, extending established research on core distributed computing problems for dynamic networks to the anonymous and adaptive setting suitable even for modeling systems without explicit computational capabilities (e.g., granular active matter). Together, these aims will advance fundamental knowledge of dynamic networks theory and contribute downstream to interdisciplinary efforts in programming and characterizing collective behavior in biological and social systems.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.