AF: Small: Relaxed Distributed Data Structures: Implementations and Applications

AF：小：宽松的分布式数据结构：实现和应用

• 批准号: 1816922
• 负责人: Jennifer Welch
• 金额: $ 39.7万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1816922&HistoricalAwards=false
• 关键词: AF; Small; Relaxed; Distributed; Data

Society has become increasing reliant on distributed computing systems, from search engines to mobile telephony to electronic commerce to social media, and the future is likely to bring autonomous vehicles and more. Yet distributed systems are notoriously hard to design so that they are correct, let alone efficient. One way to construct distributed applications that are easier to verify as correct is to use shared memory for inter-process communication instead of more low-level techniques, as that contributes to better structured code. Although shared memory is a convenient abstraction, it is not generally provided in large-scale distributed systems; instead, the processes keep individual copies of the data and communicate by sending messages to keep the copies consistent. This project will contribute to making shared memory applications more reliable and efficient by developing and analyzing shared data abstractions that have relaxed semantics and thus can exhibit a trade-off between performance and specification. In addition to training graduate students, the project will include a focus on involving domestic undergraduate students, especially women and under-represented minorities, in research through summer as well as academic-year experiences, with the goal of increasing the numbers that attend graduate school in computing related fields. Strongly consistent implementations of shared objects with strict semantics are provably expensive, fueling interest in relaxations. The objectives of the project are: to find optimally efficient algorithms to implement shared objects, focusing on relaxing specifications of both data types and consistency conditions; to understand the relationships between relaxing a type and relaxing a condition; and, to characterize applications that can exploit the relaxations. Current performance analyses of shared object implementations in message-passing systems have numerous gaps: upper and lower bounds are not tight, some classes of operations are not considered, other metrics have not been studied, and mostly only overly-pessimistic worst-case analyses are known. The project will focus on tight amortized analyses of algorithms for relaxed data types and seek a complete characterization. Currently, relaxation of consistency conditions and relaxation of data type specifications have been considered independently; the project will seek to understand the relationships and trade offs between them to ease the task of the programmer. Distributed systems in which processors enter and leave dynamically, such as peer-to-peer networks, data centers, and social networks, are typically asynchronous and crash-prone. Characterizing churn patterns that allow implementations of relaxed shared objects would make it easier to determine if a particular situation can support them. Many opportunities remain for characterizing classes of applications that can exploit relaxed data structures and/or relaxed consistency conditions; this would show which circumstances can benefit from savings obtained from relaxation.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.

从搜索引擎到移动的电话，从电子商务到社交媒体，社会越来越依赖分布式计算系统，未来可能会出现自动驾驶汽车等。 然而，分布式系统是出了名的难以设计，以使它们是正确的，更不用说效率了。 构建更容易验证为正确的分布式应用程序的一种方法是使用共享内存进行进程间通信，而不是使用更低级的技术，因为这有助于更好地结构化代码。 虽然共享内存是一个方便的抽象，但它通常不提供在大规模分布式系统中;相反，进程保持数据的单独副本，并通过发送消息来保持副本的一致性。 这个项目将有助于使共享内存应用程序更可靠和有效的开发和分析共享数据抽象，具有宽松的语义，从而可以表现出性能和规范之间的权衡。 除了培训研究生外，该项目还将重点关注国内本科生，特别是妇女和代表性不足的少数民族，通过夏季和学年的经验参与研究，目标是增加计算机相关领域研究生院的人数。 具有严格语义的共享对象的强一致实现是可证明的昂贵的，从而激发了人们对放松的兴趣。该项目的目标是：找到最有效的算法来实现共享对象，重点是放松数据类型和一致性条件的规范;了解放松类型和放松条件之间的关系;以及，描述可以利用放松的应用程序。 目前的性能分析共享对象实现的消息传递系统有许多差距：上限和下限不紧，一些类的操作没有考虑，其他指标还没有研究，大多数情况下，只有过于悲观的最坏情况下的分析是已知的。 该项目将侧重于对宽松数据类型的算法进行严格的摊销分析，并寻求完整的特征。 目前，放宽一致性条件和放宽数据类型规范已被单独考虑;该项目将设法了解它们之间的关系和权衡，以减轻程序员的任务。 处理器动态进入和离开的分布式系统，例如对等网络、数据中心和社交网络，通常是异步的并且容易崩溃。 描述允许实现宽松共享对象的流失模式，将更容易确定特定情况是否支持它们。 许多机会仍然是表征类的应用程序，可以利用宽松的数据结构和/或宽松的一致性条件，这将表明哪些情况下可以受益于从放松获得的节省。这个奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

项目成果

Store-collect in the presence of continuous churn with application to snapshots and lattice agreement

在存在连续搅动的情况下存储-收集，并应用于快照和网格协议

• DOI: 10.1016/j.ic.2022.104869
• 发表时间: 2022
• 期刊: Information and Computation
• 影响因子: 1
• 作者: Attiya, Hagit;Kumari, Sweta;Somani, Archit;Welch, Jennifer L.
• 通讯作者: Welch, Jennifer L.

Brief Announcement: Collect in the Presence of Continuous Churn with Application to Snapshots and Lattice Agreement

简短公告：在持续流失的情况下收集并应用快照和格子协议

• DOI: 10.1145/3382734.3405709
• 发表时间: 2020
• 期刊: 39th Symposium on Principles of Distributed Computing
• 作者: Attiya, Hagit;Kumari, Sweta;Somani, Archit;Welch, Jennifer L.
• 通讯作者: Welch, Jennifer L.

Blunting an Adversary Against Randomized Concurrent Programs with Linearizable Implementations

通过可线性化的实现来削弱对手对抗随机并发程序的能力

• DOI: 10.1145/3519270.3538446
• 发表时间: 2022
• 期刊: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing
• 作者: Attiya, Hagit;Enea, Constantin;Welch, Jennifer
• 通讯作者: Welch, Jennifer

Brief Announcement: How Fast Reads Affect Multi-Valued Register Simulations

简短公告：读取速度如何影响多值寄存器模拟

• DOI: 10.1145/3293611.3331580
• 发表时间: 2019
• 期刊: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
• 作者: Chaudhuri, Soma;Frank, Reginald;Welch, Jennifer L.
• 通讯作者: Welch, Jennifer L.