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.