AF: Small: Locality and Energy in Distributed Computing

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

Distributed computing is the area of computer science that reasons about the ability of networks of independent computers to solve computational problems. This project focuses on locality sensitive models of distributed computing, which model many types of networks arising in the real world, for example, wired computer networks, wireless sensor networks, and networks of biological agents (cells, ants, etc.). The concept of local interaction is a compelling one that has been studied across the sciences. Theoretical advances in locality-sensitive distributed models will shed new light on similar models studied by biologists, physicists, and neuroscientists, and thereby have a broad impact across scientific disciplines. A key goal of this project is to develop and actively promote practical and theoretically attractive models of energy-efficiency for distributed computing. This project will support the development of a new course in theoretical distributed computing at the University of Michigan. The project will focus mainly on the LOCAL model and derivatives that incorporate congestion, energy, radio communication, and randomization. One goal of this project is to develop a complexity theory for these models, and specifically to develop "time hierarchy" type theorems, characterize the value of random bits, search for complete problems within various complexity classes, and prove unconditional separations between easy and hard problems. Another goal is to understand the exact complexity of critical algorithmic primitives in these distributed models, including symmetry-breaking primitives and information-dissemination primitives like broadcast and gossiping. 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.