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 的法定使命，并且通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

DOI：
10.1016/j.ic.2022.104869
发表时间：
2022-05
期刊：
Information and Computation
影响因子：
1
作者：
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-07
期刊：
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing
影响因子：
0
作者：
Attiya, Hagit;Enea, Constantin;Welch, Jennifer
通讯作者：
Welch, Jennifer

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

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

DOI：
10.1145/3293611.3331580
发表时间：
2019-01
期刊：
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
影响因子：
0
作者：
Chaudhuri, Soma;Frank, Reginald;Welch, Jennifer L.
通讯作者：
Welch, Jennifer L.

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

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