AF: Small: RUI: Towards Asynchronous, Crash-Tolerant Shared Data

About This Grant

The world is full of computing devices and enormous data sets. One approach to solve interesting problems is to distribute computing across many devices, combining their computing power. Unfortunately, data access in such a system is slow due to the physical limitations of communicating over large distances. This project seeks to find techniques to speed up data access in these distributed computing systems. Previous work has done this in well-behaved systems but cannot handle the facts that computers fail and communication delays are unpredictable. In this project, the researchers will design more robust techniques which can handle these real-world difficulties. To do this, a tradeoff is necessary. By allowing data access to be slightly out-of-order, participants in the system can access that data faster and be more resilient to errors in other parts of the distributed system. Efficient access to data is a fundamental building block in modern computing systems, so better techniques for providing that access can speed up and improve a broad range of computing activities. This project explores distributed algorithms for relaxed data types. Specifically, the researchers intend to use relaxation of a First-In, First-Out Queue to provide resiliency to crashes, arbitrary message delays, and concurrent action by remote users in a distributed system. These relaxations weaken the ordering guarantees of a Queue, which allows more-performant algorithms, and hopefully implementations in systems where a traditional Queue is impossible. Algorithms for such relaxed queues exist in well-behaved models where it is easier to define the limitations of what is possible, such as those without crashes and with known bounds on communication delay. In this project, the researchers will move toward more realistic models of computation, designing shared data structure algorithms which tolerate unpredictable timing and crashes of participants in the distributed system. Taking advantage of the relaxed order of data retrieval, an algorithm can achieve better performance and be resilient to faults in the distributed system. The researchers will prove their algorithms correct and begin structuring broader questions of what other data types could benefit from similar techniques. 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.