AF: Small: Locality and Energy in Distributed Computing

分布式计算是计算机科学的一个领域，它研究了独立计算机网络解决计算问题的能力。 该项目的重点是分布式计算的局部敏感模型，它模拟了真实的世界中出现的许多类型的网络，例如，有线计算机网络，无线传感器网络和生物代理（细胞，蚂蚁等）的网络。 局部相互作用的概念是一个令人信服的概念，已经在各个科学领域进行了研究。局部敏感分布式模型的理论进展将为生物学家、物理学家和神经科学家研究的类似模型提供新的思路，从而对各个科学学科产生广泛的影响。该项目的一个主要目标是开发和积极推广分布式计算的实用和理论上有吸引力的能源效率模型。该项目将支持密歇根大学开发一门新的理论分布式计算课程。该项目将主要集中在分布式计算模型和包含拥塞、能量、无线电通信和随机化的衍生物上。这个项目的一个目标是为这些模型开发一个复杂性理论，特别是开发“时间层次”类型的定理，描述随机位的值，在各种复杂性类中搜索完整的问题，并证明简单和困难问题之间的无条件分离。 另一个目标是了解这些分布式模型中关键算法原语的精确复杂性，包括破坏性原语和信息传播原语，如广播和八卦。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.