AF: Small: Complexity of Distributed Storage
AF: Small: Complexity of Distributed Storage
批准号:
1526725
负责人:
Jennifer Welch
金额:
$41.6万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2015
资助国家:
美国
项目状态:
已结题
起止时间:
2015-09-01 至 2018-08-31
中文摘要
分布式计算系统无处不在,从手机中的多核到互联网本身。 分布式存储或共享数据是分布式系统中计算实体(“处理器”)之间通信的重要机制,并有助于开发正确和有效的应用程序。 虽然共享数据是一种理想的抽象,但由于物理限制,它通常不会在大规模分布式系统中提供。 相反,处理器保留数据的各个副本,并通过发送消息来保持副本的一致性。 众所周知,为共享数据提供关于数据一致性的强有力保证可能是昂贵的-特别是,对数据的操作可能需要很长时间才能完成。 这一事实激发了人们对更“轻松”的数据版本的兴趣,希望可以更快地实现操作。 作为松弛数据的一个例子,想象一下支持读和写操作的数据,其中读操作可以返回不是最近写入的值。由于并发、组件故障和可变通信延迟导致的复杂性,为分布式存储系统(实际上是大多数分布式系统)开发正确且高效的软件是具有挑战性的。 然而,能够这样做将有利于社会,因为这样的软件无处不在。 该项目采用基于严格数学推理的原则性方法,为分布式存储系统的一些基本问题找到分布式算法,特别关注松弛数据,项目活动还将包括创建有关分布式计算的本科课程材料,以填补现有的空白,并提供研究经验对于本科生,特别是女性谁是可悲的代表性不足,鼓励更多的获得研究生学位,在计算相关领域。要解决的技术问题包括:找到各种数据结构的最佳实现,满足“线性化”的一致性条件,其中考虑的性能指标包括最坏情况以及摊销时间;摊销界限通常比孤立的最坏情况结果更有用,但它们并没有成为许多分析的焦点。 发现放松对象的规范和放松一致性条件之间的关系。 描述可以利用宽松的数据结构或宽松的一致性条件的一般应用程序类别。 以通用的方式确定数据类型的容错级别。 描述允许线性化对象在异步系统中实现的扰动模式(处理器进入和离开系统),该异步系统会发生崩溃故障。 PI计划作为一种通用工具,通过代数属性对数据类型操作进行分类。
英文摘要
Distributed computing systems are all around us, ranging from multiple cores in a cell phone to the Internet itself. Distributed storage, or shared data, is a vital mechanism for communication among computing entities ("processors") in distributed systems and facilitates the development of correct and efficient applications. Although shared data is a desirable abstraction, it is not generally provided in large-scale distributed systems due to physical limitations. Instead, processors keep individual copies of the data, and communicate by sending messages to keep the copies consistent. It is known that providing shared data with strong guarantees on how consistent the data is can be expensive -- in particular, the operations on the data can take a long time to complete. This fact has fueled interest in more "relaxed" versions of the data, in the hope that operations can be implemented faster. As an example of relaxed data, imagine data that supports read and write operations where a read operation can return a value that is not the one most recently written.Developing software for distributed storage systems (and indeed for most distributed systems) that is correct and efficient is challenging due to complications caused by concurrency, component failures, and variable communication delays. Yet being able to do so will benefit society because of the ubiquity of such software. This project takes a principled approach, based on rigorous mathematical reasoning, to find distributed algorithms for some fundamental problems that underlie distributed storage systems, with especial focus on relaxed data, and to characterize applications that can exploit the relaxations and their improved performance.Project activities will also include creating undergraduate curricular materials on distributed computing to fill existing gaps and providing research experiences for undergraduates, especially women who are woefully under-represented, to encourage more to obtain graduate degrees in computing-related field.The technical problems to be solved include these: Find optimal implementations of various data structures that satisfy the "linearizability" consistency condition, where the performance metrics considered include worst-case as well as amortized time; amortized bounds are often of more use than isolated worst-case results, yet they have not been the focus of much analysis. Discover the relationship between relaxing the specification of an object and relaxing the consistency condition. Characterize general classes of applications that can exploit relaxed data structures or relaxed consistency conditions. Determine the level of fault-tolerance of data types in a generic way. Characterize patterns of churn (processors entering and leaving the system) that allow linearizable objects to be implemented in an asynchronous system subject to crash failures. The PIs plan to apply, as a general tool, classifications of data type operations by their algebraic properties.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: Relaxed Distributed Data Structures: Implementations and Applications
-
批准号:1816922
-
项目类别:Standard Grant
-
资助金额:$39.7万
-
财政年份:2018
-
负责人:Jennifer Welch
-
依托单位:
AF: Medium: A Fair Prescription for Partial Synchrony
-
批准号:0964696
-
项目类别:Continuing Grant
-
资助金额:$73.77万
-
财政年份:2010
-
负责人:Jennifer Welch
-
依托单位:
Collaborative Research: Randomized Distributed Data Structures for Product Design
-
批准号:0500265
-
项目类别:Standard Grant
-
资助金额:$20.0万
-
财政年份:2005
-
负责人:Jennifer Welch
-
依托单位:
Self-Stabilizing Group Communication for Mobile Environments
-
批准号:0098305
-
项目类别:Continuing Grant
-
资助金额:$28.0万
-
财政年份:2001
-
负责人:Jennifer Welch
-
依托单位:
CONACyT: Geocasting in Mobile Ad Hoc Networks Using Location Information
-
批准号:9976626
-
项目类别:Standard Grant
-
资助金额:$5.2万
-
财政年份:1999
-
负责人:Jennifer Welch
-
依托单位:
Distributed Algorithms for Mobile Ad Hoc Networks
-
批准号:9972235
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:1999
-
负责人:Jennifer Welch
-
依托单位:
PYI: Realistic Partially Synchronous Models of Distributed Computation
-
批准号:9396098
-
项目类别:Continuing Grant
-
资助金额:$21.57万
-
财政年份:1992
-
负责人:Jennifer Welch
-
依托单位:
PYI: Realistic Partially Synchronous Models of Distributed Computation
-
批准号:9158478
-
项目类别:Continuing Grant
-
资助金额:$3.53万
-
财政年份:1991
-
负责人:Jennifer Welch
-
依托单位:
The Impact of Time on Distributed Computing
-
批准号:9010730
-
项目类别:Standard Grant
-
资助金额:$6.0万
-
财政年份:1990
-
负责人:Jennifer Welch
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: