Joseph Hellerstein
Electrical Engineering and Computer Science

University of California Berkeley

"CALM Consistency: Disorderly Programming in Bloom"

 

Abstract

The rise of cloud computing and multicore processors is putting enormous pressure on the software community to find solutions to the difficulty of distributed and parallel programming. The main challenges arise from the mismatch between the orderly abstractions of Von Neumann models of computation, and the disorderly realities of distributed and parallel computing platforms. Coordination protocols and transactions are traditional answers to these challenges, but are often rejected by programmers today as an undesirable tradeoff between consistency, latency and availability. However, in the absence of such methods, there are few general principles or tools to help programmers design and verify the correctness of their applications.

I address this situation on two fronts. I begin with the CALM theorem, which formally links Consistency And Logical Monotonicity of distributed programs. This provides a principled foundation for design maxims passed down among experienced distributed systems developers. I then introduce Bloom, a "disorderly" language for distributed computing that encourages order-insensitive, easily-parallelized programming. Using the CALM theorem as a basis, we have developed conservative tests to identify "points of order" in Bloom programs: code locations where coordination logic should be injected to ensure consistency. Once identified, automatic code synthesis can insert coordination logic at points of order; alternatively, it can provide a scaffold for background testing and compensation of potentially inconsistent disorderly code. I illustrate these ideas via Bloom implementations of two canonical case studies in distributed systems: a simple key-value store and a distributed shopping cart service.

Joint work with Peter Alvaro, Peter Bailis, Ras Bodik, Neil Conway, William Marczak and David Maier. http://bloom.cs.berkeley.edu

Time permitting, I will also provide a taste of research in our d^p project, which addresses interactions between people and data during the lifecycle of data analytics. http://www.deepresearch.org

____________________________________________________________________________