NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence

NSF-BSF：协作研究：AF：小型：通过历史独立性实现算法性能

• 批准号: 2247577
• 负责人: Michael Bender
• 金额: $ 30万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-05-01 至 2026-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2247577&HistoricalAwards=false
• 关键词: NSF; BSF; Collaborative; Research; AF

A data structure is said to be history independent (HI) if the way that the data is stored reveals nothing about the history of operations that lead to the current state. History independence was introduced to protect data structures from malicious attacks. For example, voting machines that store votes in the order they were cast can reveal surprising information about voters, whereas a history-independent data organization on a voting machine does not.This project considers a new use for history independence. The project will demonstrate that history independence can be a powerful analytical tool for designing randomized data structures and algorithms---especially in the case of oblivious adversaries. The project investigates problems in: (1) online algorithms, (2) resource allocation, (3) random-acess memory (RAM) and external-memory dictionary data structures, (4) load balancing, and (5) scalable concurrent data structures. The researchers have already shown how to use HI to crack a four-decades-old open problem in list labeling and to make substantial progress on a well-known load balancing problem. This work promises to broaden the scope of HI to both sequential and concurrent settings. The team will continue community-building efforts to introduce randomized algorithms to the undergraduate curriculum, as well as running workshops that can expose junior researchers to these techniques. The team will also continue its efforts to engage members of underrepresented groups in research earlier in their careers.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.

如果数据存储的方式没有揭示导致当前状态的操作史，则据说数据结构是独立的（HI）。引入了历史独立性，以保护数据结构免受恶意攻击。例如，按照他们被施放的命令存储投票的投票机可以揭示有关选民的惊人信息，而在投票机上独立于历史的数据组织则没有。该项目将表明，历史独立性可以成为设计随机数据结构和算法的强大分析工具 - 尤其是在遗忘对手的情况下。该项目研究以下问题：（1）在线算法，（2）资源分配，（3）随机访问记忆（RAM）和外部内存词典数据结构，（4）负载平衡以及（5）可扩展的并发数据结构。研究人员已经展示了如何使用HI在列表标签​​中解决一个四年一的旧问题，并在众所周知的负载平衡问题上取得了重大进展。这项工作有望将HI范围扩大到顺序和并发设置的范围。该团队将继续进行社区建设的努力，以将随机算法引入本科课程，以及可以将初级研究人员暴露于这些技术的讲习班。该团队还将继续努力，使代表性不足的团体的成员在其职业生涯的早期研究中参与研究。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响审查标准通过评估来支持的。

项目成果

IcebergHT: High Performance Hash Tables Through Stability and Low Associativity

• DOI: 10.1145/3588727
• 发表时间: 2023-05
• 期刊: Proceedings of the ACM on Management of Data
• 作者: P. Pandey;M. A. Bender;Alex Conway;Martín Farach-Colton;William Kuszmaul;Guido Tagliavini;Robert C. Johnson

Modern Hashing Made Simple

现代哈希变得简单

• 发表时间: 2024
• 期刊: Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA
• 作者: Michael A. Bender;Martin Farach-Colton;John Kuszmaul;William Kuszmaul
• 通讯作者: William Kuszmaul

An Associativity Threshold Phenomenon in Set-Associative Caches

• DOI: 10.1145/3558481.3591084
• 发表时间: 2023-04
• 期刊: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: M. A. Bender;Rathish Das;Martín Farach-Colton;Guido Tagliavini

The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems

在安全关键系统中安全有效地使用低保证率预测

• 发表时间: 2023
• 期刊: Proceedings of the EuroMicro Conference on Real-Time Systems (ECRTS 2023
• 作者: Kunal Agrawal;Sanjoy Baruah;Michael Bender;Alberto Marchetti-Spaccamela
• 通讯作者: Alberto Marchetti-Spaccamela