AF: Small: Locality and Energy in Distributed Computing

AF：小：分布式计算中的局部性和能量

基本信息

批准号：
1815316
负责人：
Seth Pettie
金额：
$ 45万
依托单位：
Regents of the University of Michigan - Ann Arbor
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815316&HistoricalAwards=false
关键词：
AF Small Locality Energy Distributed

项目摘要

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.

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