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

如果存储数据的方式不揭示导致当前状态的操作的历史，则数据结构称为历史独立(HI)。引入历史独立性以保护数据结构免受恶意攻击。例如，按照投票顺序存储选票的投票机可以揭示关于选民的令人惊讶的信息，而投票机上独立于历史的数据组织则不会。这个项目考虑了历史独立性的新用途。该项目将证明历史独立性可以成为设计随机化数据结构和算法的强大分析工具-特别是在不经意间的对手的情况下。该项目研究了以下方面的问题：(1)在线算法，(2)资源分配，(3)随机存取内存(RAM)和外部内存字典数据结构，(4)负载平衡，和(5)可伸缩并发数据结构。研究人员已经展示了如何使用HI来破解列表标记中已有40年历史的开放问题，并在众所周知的负载平衡问题上取得实质性进展。这项工作有望将HI的范围扩大到顺序设置和并发设置。该团队将继续社区建设工作，将随机化算法引入本科课程，并举办研讨会，让初级研究人员接触这些技术。该团队还将继续努力让未被充分代表的群体的成员在他们职业生涯的早期参与研究。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.