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

点击翻译按钮获取中文摘要

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.