Distributed systems are now everywhere, for example, in wireless communication networks, distributed data-management systems, coordinated robots, transportation systems, and modern multiprocessors. Much of the current theory for distributed systems focuses on highly optimized algorithms for well-behaved platforms such as synchronous graph networks. However, most new distributed algorithms will need to run on much more difficult platforms---platforms that change over time and exhibit noise and uncertainty. In this project, we are studying algorithms that are designed to run in such dynamic and noisy settings, mainly, wireless networks and robot swarms.
Dynamic and noisy systems like these are, in many ways, suggestive of biological systems, such as social insect colonies. Therefore, we are combining our study of wireless and robot systems with a theoretical study of certain kinds of biological systems.
This combined study has two aims: it can provide a new way of understanding and analyzing the behavior of the biological systems, using the viewpoint of distributed algorithms; and it can use this new understanding to help devise better algorithms for engineered systems. ``Better'' here means more flexible (to work in different environments), more robust to failures, and more adaptive to changes.
Studying wireless and biological systems together allows us to look for common principles that cross disciplinary boundaries. Wireless network problems we have studied so far include local and global broadcast communication, data aggregation, and building overlay network structures.
Our work on insect colonies has covered problems of foraging (searching), task allocation, density estimation, and colony relocation (consensus). Our main observation so far has been the strong impact of changes and uncertainty on the algorithmic results. Other observations include the usefulness of probabilistic algorithms in noisy settings; the feasibility of using simple and resource-limited algorithms; the feasibility of making algorithms self-stabilizing in the face of changes; the usefulness of estimating properties of a system or its environment and using the estimates to guide the design of higher-level algorithms; and the possibility of decomposing robust probabilistic algorithms into sub-algorithms.
Thus, we are developing and studying distributed algorithms for dynamic and noisy settings, focusing on wireless networks, robot swarms, and certain biological systems. We are seeking new algorithms to solve fundamental problems of communication, construction, reaching agreement, estimation, data processing, searching, shape formation, task allocation, and more. We also seek corresponding lower bounds, in particular, bounds that highlight the costs of accommodating changes and uncertainty.
Overall, we are trying to discover general principles for distributed computing in dynamic and noisy settings.
