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

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

基本信息

项目摘要

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
  • 期刊:
  • 影响因子:
    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
简短公告:在持续流失的情况下收集并应用快照和格子协议
Blunting an Adversary Against Randomized Concurrent Programs with Linearizable Implementations
通过可线性化的实现来削弱对手对抗随机并发程序的能力
Brief Announcement: How Fast Reads Affect Multi-Valued Register Simulations
简短公告:读取速度如何影响多值寄存器模拟
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Jennifer Welch其他文献

Perioperative opioid dispensing and persistent use after benign hysterectomy: a systematic review and meta-analysis
良性子宫切除术后围手术期阿片类药物分配和持续使用:系统评价和荟萃分析
  • DOI:
    10.1016/j.ajog.2022.12.015
  • 发表时间:
    2023-07-01
  • 期刊:
  • 影响因子:
    8.400
  • 作者:
    Kamran Hessami;Jennifer Welch;Anja Frost;Abdelrahman AlAshqar;Sara E. Arian;Ethan Gough;Mostafa A. Borahay
  • 通讯作者:
    Mostafa A. Borahay
Young children creating bulletin boards? Yes!
  • DOI:
    10.1007/bf02361325
  • 发表时间:
    1994-12-01
  • 期刊:
  • 影响因子:
    1.800
  • 作者:
    Jennifer Welch;Karen P. Modrzejewski
  • 通讯作者:
    Karen P. Modrzejewski

Jennifer Welch的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Jennifer Welch', 18)}}的其他基金

AF: Small: Complexity of Distributed Storage
AF:小:分布式存储的复杂性
  • 批准号:
    1526725
  • 财政年份:
    2015
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
AF: Medium: A Fair Prescription for Partial Synchrony
AF:中:部分同步的公平处方
  • 批准号:
    0964696
  • 财政年份:
    2010
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Continuing Grant
Collaborative Research: Randomized Distributed Data Structures for Product Design
协作研究:用于产品设计的随机分布式数据结构
  • 批准号:
    0500265
  • 财政年份:
    2005
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
Self-Stabilizing Group Communication for Mobile Environments
移动环境的自稳定群体通信
  • 批准号:
    0098305
  • 财政年份:
    2001
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Continuing Grant
CONACyT: Geocasting in Mobile Ad Hoc Networks Using Location Information
CONACyT:使用位置信息在移动自组织网络中进行地理广播
  • 批准号:
    9976626
  • 财政年份:
    1999
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
Distributed Algorithms for Mobile Ad Hoc Networks
移动自组织网络的分布式算法
  • 批准号:
    9972235
  • 财政年份:
    1999
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
PYI: Realistic Partially Synchronous Models of Distributed Computation
PYI:分布式计算的现实部分同步模型
  • 批准号:
    9396098
  • 财政年份:
    1992
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Continuing Grant
PYI: Realistic Partially Synchronous Models of Distributed Computation
PYI:分布式计算的现实部分同步模型
  • 批准号:
    9158478
  • 财政年份:
    1991
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Continuing Grant
The Impact of Time on Distributed Computing
时间对分布式计算的影响
  • 批准号:
    9010730
  • 财政年份:
    1990
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Powering Small Craft with a Novel Ammonia Engine
用新型氨发动机为小型船只提供动力
  • 批准号:
    10099896
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Collaborative R&D
"Small performances": investigating the typographic punches of John Baskerville (1707-75) through heritage science and practice-based research
“小型表演”:通过遗产科学和基于实践的研究调查约翰·巴斯克维尔(1707-75)的印刷拳头
  • 批准号:
    AH/X011747/1
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Research Grant
Fragment to small molecule hit discovery targeting Mycobacterium tuberculosis FtsZ
针对结核分枝杆菌 FtsZ 的小分子片段发现
  • 批准号:
    MR/Z503757/1
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Research Grant
Bacteriophage control of host cell DNA transactions by small ORF proteins
噬菌体通过小 ORF 蛋白控制宿主细胞 DNA 交易
  • 批准号:
    BB/Y004426/1
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Research Grant
Windows for the Small-Sized Telescope (SST) Cameras of the Cherenkov Telescope Array (CTA)
切伦科夫望远镜阵列 (CTA) 小型望远镜 (SST) 相机的窗口
  • 批准号:
    ST/Z000017/1
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Research Grant
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
  • 批准号:
    2312089
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
CSR: Small: Multi-FPGA System for Real-time Fraud Detection with Large-scale Dynamic Graphs
CSR:小型:利用大规模动态图进行实时欺诈检测的多 FPGA 系统
  • 批准号:
    2317251
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
  • 批准号:
    2332922
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
  • 批准号:
    2331111
  • 财政年份:
    2024
  • 资助金额:
    $ 39.7万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了