权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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模型及其衍生产品，包括拥堵、能源、无线电通信和随机化。该项目的一个目标是为这些模型开发一个复杂性理论，特别是开发“时间层次”类型定理，表征随机比特的值，在各种复杂性类中搜索完整问题，并证明简单和困难问题之间的无条件分离。另一个目标是了解这些分布式模型中关键算法原语的确切复杂性，包括对称破坏原语和信息传播原语，如广播和八卦。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（31）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The Communication Complexity of Set Intersection and Multiple Equality Testing

集合交集的通信复杂性和多重相等性检验

DOI：
10.1137/20m1326040
发表时间：
2021
期刊：
SIAM Journal on Computing
影响因子：
1.6
作者：
Huang, Dawei;Pettie, Seth;Zhang, Yixiang;Zhang, Zhijun
通讯作者：
Zhang, Zhijun

Contention resolution without collision detection

无需冲突检测的争用解决方案

DOI：
10.1145/3357713.3384305
发表时间：
2020
期刊：
Proceedings 52 ACM Symposium on Theory of Computing (STOC
影响因子：
0
作者：
Bender, Michael A.;Kopelowitz, Tsvi;Kuszmaul, William;Pettie, Seth
通讯作者：
Pettie, Seth

The Distributed Complexity of Locally Checkable Problems on Paths is Decidable

路径上局部可检查问题的分布式复杂度是可判定的

DOI：
10.1145/3293611.3331606
发表时间：
2019
期刊：
Proceedings 38th Symposium on Principles of Distributed Computing
影响因子：
0
作者：
Balliu, Alkida;Brandt, Sebastian;Chang, Yi-Jun;Olivetti, Dennis;Rabie, Mikaël;Suomela, Jukka
通讯作者：
Suomela, Jukka

Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts

稀疏扳手、仿真器和缩径快捷方式的下限