AF: Small: Collaborative Research: Maintaining Order

本项目研究“顺序结构”，即用于维护动态数据集上的总顺序的数据结构。订单结构在令人惊讶的不同环境中都适用。PI旨在回答与秩序结构相关的基本理论问题。调查发生在两个高影响的应用领域：(1)用于调试并行程序的工具和(2)数据库和文件系统中用来组织磁盘或SSD上的数据的数据结构。作为该项目的一部分，私人投资机构将开发关于订单结构的公开可用的教育材料和参考实施，以纳入其机构的课程并在网上公开分享。本项目涉及的订单结构是秩序维持数据结构、稀疏表和用于增量拓扑排序的数据结构。研究包括(1)具有良好最坏情况保证的新算法，(2)具有强常见情况保证的算法，即，针对公共输入分布优化的算法，(3)可证明良好的并发算法，(4)以令人惊讶的方式利用随机化的算法(例如，实现历史独立性)，以及(5)也适用于随机化设置的健壮下界。在目标应用程序的上下文中，PI将设计和使用顺序结构来实现竞争检测器，该检测器揭示并行程序中的确定性竞争。PI还将使用订单结构来构建外部内存键值存储，以使数据库和文件系统运行得更快。

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.