AF: Small: Collaborative Research: Maintaining order

点击翻译按钮获取中文摘要

This project investigates "order structures," that is, data structures for maintaining total orders on dynamic data sets. Order structures are applicable in surprisingly diverse settings. The PIs aim to answer fundamental theoretical questions relating to order structures. The investigation takes place in the context of two high-impact application areas: (1) tools for debugging parallel programs and (2) data structures used in databases and file systems to organize data on disk or SSDs. As part of the project, the PIs will develop publicly available educational materials and reference implementations on order structures to be incorporated into courses at their institutions and shared openly on the web.The order structures addressed in this project are order-maintenance data structures, sparse tables, and data structures for incremental topological ordering. The investigation comprises (1) new algorithms with good worst-case guarantees, (2) algorithms with strong common-case guarantees, i.e., optimized for common input distributions, (3) provably good concurrent algorithms, (4) algorithms that leverage randomization in surprising ways (e.g., to achieve history independence), and (5) robust lower bounds that also apply to the randomized setting. In the context of the target applications, the PIs will design and use order structures to implement race detectors, which uncover determinacy races in parallel programs. The PIs will also use orders structures to build external-memory key-value stores to make databases and file systems run faster.