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

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.