CNS Core: Small: Modernizing Consistency Models

Princeton University, Princeton NJ

Investigators

Abstract

This project promotes the progress of science by exploring new methods for making large-scale computer applications easier to program correctly and run faster. Such applications are built out of several pieces with one key piece being a distributed data store that mediates access to the application's data. This project explores new ways to specify the interface between applications and the data store so that applications can complete all their accesses to the data store more quickly. It also explores how applications can use this new, faster interface without making programming more complicated. Together, this should advance the field of distributed systems by introducing new interfaces (consistency models), showing these new interfaces do not add programming complexity, developing new data stores that support the new interfaces, and demonstrating how the new interfaces and systems result in faster applications. These improvements have the potential to improve the speed and correctness of the large-scale computer applications that are an integral part of our lives. Further, this project will advance discovery and broaden participation in science by involving undergraduate and graduate researchers. Consistency models define the contract between a distributed system and the applications built on it. The dominant consistency models were defined decades ago and assume restrictive models of application execution that preclude the use of multi-dispatch---multiple concurrent operations between an application execution and the system---and distributed execution---application processing happening in multiple places simultaneously. Multi-dispatch and distributed execution, however, are common in modern applications because they greatly reduce latency compared to the single-dispatch and centralized execution assumed by classic models. This proposal seeks to modernize consistency models by including multi-dispatch communication and distributed execution. This will allow programmers to rigorously reason about the correctness of their applications while also gaining the latency benefit of multi-dispatch and/or distributed execution. Further, it seeks to define modern consistency models to be equivalent to classic models: if an application is correct when running on a classic model while respecting its assumptions, it will be correct when run on the modernized model. This avoids the typical subtle trade-offs between guarantees and performance of new consistency models and fully hides the concurrent access to the system from programmers. Instead, it allows programmers to stick to reasoning about the classic consistency models they already know. For each of multi-dispatch and then distributed execution, we propose defining new consistency models, designing systems that provide the new consistency models, and then demonstrating end-to-end latency improvement for applications built on the new systems through evaluation. 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.