AF : Small : Relaxed Distributed Data Structures: Implementations and Applications
Grant
Overview
Affiliation
Other
View All
Overview
abstract
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.
