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

AF：中：匿名动态网络中的并发性和自适应自组织

• 批准号: 2312537
• 负责人: Joshua Daymude
• 金额: $ 81.33万
• 依托单位: Arizona State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2312537&HistoricalAwards=false
• 关键词: AF; Medium; Concurrency; Adaptive; Self

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.

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

项目成果

Energy-Constrained Programmable Matter Under Unfair Adversaries

不公平对手下的能量受限可编程物质

• DOI: 10.4230/lipics.opodis.2023.7
• 发表时间: 2024
• 期刊: 27th International Conference on Principles of Distributed Systems (OPODIS 2023
• 作者: Weber, Jamison W.;Chhabra, Tishya;Richa, Andréa W.;Daymude, Joshua J.
• 通讯作者: Daymude, Joshua J.