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

从搜索引擎到移动电话，从电子商务到社交媒体，社会越来越依赖分布式计算系统，未来可能会出现自动驾驶汽车等。然而分布式系统的设计是出了名的难以保证其正确性，更不用说高效了。构建更容易被验证为正确的分布式应用程序的一种方法是使用共享内存进行进程间通信，而不是使用更低级的技术，因为这有助于更好地构建结构化代码。虽然共享内存是一种方便的抽象，但在大规模分布式系统中通常不提供；相反，进程保留数据的各个副本，并通过发送消息来保持副本的一致性进行通信。该项目将通过开发和分析具有宽松语义的共享数据抽象，从而在性能和规范之间进行权衡，从而使共享内存应用程序更加可靠和高效。除了培训研究生外，该项目还将重点关注国内本科生，特别是女性和代表性不足的少数民族，在暑期和学年的研究中参与研究，目标是增加在计算机相关领域就读研究生院的人数。具有严格语义的共享对象的强一致实现显然是昂贵的，这激发了人们对松弛的兴趣。该项目的目标是：找到最有效的算法来实现共享对象，重点是放松数据类型和一致性条件的规范；了解放松类型与放松条件之间的关系；并且，描述可以利用弛豫的应用程序。当前对消息传递系统中共享对象实现的性能分析存在许多差距：上界和下界不严格，没有考虑某些操作类别，没有研究其他指标，而且大多数情况下只知道过于悲观的最坏情况分析。该项目将侧重于松弛数据类型算法的严格平摊分析，并寻求完整的表征。目前，一致性条件的松弛和数据类型规范的松弛被分别考虑；项目将试图理解它们之间的关系和权衡，以减轻程序员的任务。处理器动态进入和离开的分布式系统（例如点对点网络、数据中心和社交网络）通常是异步的，并且容易崩溃。描述允许实现宽松共享对象的流失模式，可以更容易地确定特定情况是否支持它们。仍然有许多机会来描述可以利用宽松数据结构和/或宽松一致性条件的应用程序类；这将表明在哪些情况下可以从放松所获得的节省中获益。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.