Adaptive Self-Organization in Anonymous Dynamic Networks

Distributed computing theory has matured well beyond its original inspiration of dedicated computers linked together in static networks for message passing and file sharing. 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. This paradigm shift has enabled distributed computing to innovate both within computer science—e.g., in the construction of self-stabilizing overlay networks—and beyond the realm of engineering in, e.g., economics, biology, neurology, and active matter physics. Motivated by these domains where individuals often have limited to no explicit computational power, we study the algorithmic theory of dynamic networks where nodes are anonymous (lacking unique identifiers), have sublogarithmic memory (insufficient for computing identifiers), and communicate via message passing.

We are specifically interested in asynchronous concurrency and adaptive self-organization. In studying asynchronous concurrency, we challenge the literature’s ubiquitous simplifying assumption that computation and network dynamics remain separated in time, instead designing algorithms that achieve their desired goals in spite of concurrent topological changes. With adaptive self-organization, we initiate the study of an orthogonal type of dynamics, time-varying system tasks, which require algorithms to simultaneously adapt to the environment and achieve self-stabilization.