Distributed Programming

There is a rising demand to write distributed programs that can scale to many machines in data-centers. Examples include large-scale machine learning, graph algorithms, data mining etc. It is difficult to write efficient and robust parallel programs in the data-center setting---users must take care to reduce communication overhead while also handling machine failures.

Inspired by the success of data-flow programming models like MapReduce, the Piccolo and Spartan projects investigate new data-centric distributed programming models to simplify the construction of in-memory data-center applications such as PageRank, neural network training etc.

Russell Power, Chien-Chin Huang, Qi Chen, Yisheng Liao, Jinyang Li

Geo-storage systems

Many large-scale web applications today run across multiple data centers to improve fault tolerance and reduce network delays to users. These web applications need a geo-distributed storage backend to store and share data. Unfortunately, unlike storage systems operating within a single data center, a geo-distributed storage system faces the unpleasant tradeoff of consistency vs. performance because of large inter-data-center communication delay.

We study this fundmental consistency vs. performance tradeoff in terms of new consistency and programming models for geo-replicated storage. Walter (SOSP'11) is a geo-replicated key-value store with a novel consistency model called parallel snapshot isolation. Lynx provides serializability at low latency while offering the familiar relational table interface.

Yang Zhang, Russell Power, Yair Sovran, Jinyang Li

Proof-based verifiable computation

How can a machine specify a computation to another one and then, without executing the computation, check that the other machine carried it out correctly? This question is motivated by the cloud and other third-party computing models.

The Pepper project is tackling this question by reducing to practice powerful tools from complexity theory and cryptography: probabilistically checkable proofs (PCPs), efficient arguments, and related notions. Recently, this research area has seen a number of exciting results (ours and others); together, they suggest that in the future, PCP-related machinery could be a real tool for building actual systems.

Srinath Setty, Riad Wahby, Michael Walfish

Simplified GPU Programming

Despite GPUs alluring performance potential, it is notoriously difficult to write efficient programs for them. Parakeet is a runtime compiler for an array-oriented subset of Python. It selectively augments the standard Python interpreter by compiling and executing functions explicitly marked for acceleration by the programmer. Parakeet has been released and used by real users. Specifically, it is currently being used by as part of Spartan's GPU backend to distribute computation among a cluster of GPU machines.

Alex Rubinsteyn, Dennis Shasha

Data Structures and Algorithms for Databases

Niv Dayan, Philippe Bonnet, and Dennis Shasha are working on fast data structures for solid state drives. These data structures are the fastest available for any workloads having for which at least 10% of the operations are not reads.

Rosalba Giugno, Alfredo Ferro, their students and Dennis Shasha are working on fast algorithms for finding subpatterns in graphs and doing data mining in graphs. The systems GraphGrep and its followers have been widely downloaded.

Dennis Shasha

Other ongoing projects

Juliana Freire, Fernando Chirigati, and Dennis work on systems to support computational reproducibility using provenance and operating system support.

Dennis Shasha works on applied projects such as a database and tools to support cross-linguistic analysis, algorithms for making magnetic resonance imagery faster, and a database to support research in millimeter wave wireless, and a tool for automatic database tuning.