Xiang Huang, University of Illinois - Springfield
Xiang Huang
University of Illinois - Springfield
Computing with Population Protocols
This talk focuses on a model of distributed computing known as population protocols. In this talk, we will discuss recent work on computing numbers using interactions between simple devices. Starting with the most basic interactions represented by chemical reactions, A→B, we define what it means for a reaction system (of devices) to compute a number. Systems made up of reactions like A→B can only compute rational numbers. Then, we discuss a more powerful system with two-in-two-out interactions, A+B→ C+D, and learn that this is all we need; adding other types of reactions does not increase the computational power of the interaction model. That is, population protocols (systems consisting only of two-in-two-out reactions), general chemical reaction networks, and the general-purpose analog computer all have the same computational power when it comes to computing real numbers. This discovery inspires intriguing algorithms, potentially improving simulators for these systems, and raises theoretical questions regarding the hierarchy of real numbers and their corresponding computational models. This talk reflects the efforts of several research groups. Additionally, we will introduce our DOE-funded project, discuss its extension of this topic, and offer potential research opportunities to students.
