AF: Small: Complexity of Distributed Storage

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