AF: Small: Complexity of Distributed Storage

AF：小：分布式存储的复杂性

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

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.

分布式计算系统无处不在，从手机中的多个核心到互联网本身。 分布式存储或共享数据是分布式系统中计算实体（“处理器”）之间通信的重要机制，有助于开发正确且高效的应用程序。 尽管共享数据是一种理想的抽象，但由于物理限制，在大规模分布式系统中通常不提供共享数据。 相反，处理器保留数据的单独副本，并通过发送消息进行通信以保持副本的一致性。 众所周知，为共享数据提供强有力的数据一致性保证可能成本高昂，特别是对数据的操作可能需要很长时间才能完成。 这一事实激起了人们对更“宽松”版本的数据的兴趣，希望能够更快地实施操作。 作为宽松数据的一个示例，想象一下支持读取和写入操作的数据，其中读取操作可以返回一个不是最近写入的值。为分布式存储系统（实际上是大多数分布式系统）开发正确且可靠的软件由于并发、组件故障和可变的通信延迟引起的复杂性，高效是具有挑战性的。 然而，由于此类软件的普遍存在，能够做到这一点将使社会受益。 该项目采用基于严格数学推理的原则性方法，为分布式存储系统背后的一些基本问题找到分布式算法，特别关注松弛数据，并描述可以利用松弛及其改进性能的应用程序。 项目活动还将包括创建分布式计算本科课程材料，以填补现有空白，并为本科生，特别是代表性严重不足的女性提供研究经验，以鼓励更多人获得计算相关领域的研究生学位。要解决的技术问题包括这些：查找满足“线性化”一致性条件的各种数据结构的最佳实现，其中考虑的性能指标包括最坏情况以及摊销时间；摊余界限通常比孤立的最坏情况结果更有用，但它们并不是很多分析的焦点。 发现放宽对象规范和放宽一致性条件之间的关系。 描述可以利用宽松数据结构或宽松一致性条件的一般应用程序类别。 以通用方式确定数据类型的容错级别。 描述搅动模式（处理器进入和离开系统），这些模式允许在遭受崩溃故障的异步系统中实现线性化对象。 PI 计划将数据类型运算的代数属性分类作为通用工具。