AF: Small: Collaborative Research: Maintaining Order

AF：小：协作研究：维持秩序

• 批准号: 1617618
• 负责人: Michael Bender
• 金额: $ 21.03万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617618&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Maintaining

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.

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