Distinguished Lecture Series

 

"CALM Consistency: Disorderly Programming in Bloom"

Joseph M. Hellerstein, UC Berkeley

Thursday, May 5, 2011 at 4:00 P.M.

Room 368 (CIT 3rd floor)

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, Neil Conway, and William Marczak. http://bloom.cs.berkeley.edu

Joseph M. Hellerstein is a Professor of Computer Science at the University of California, Berkeley, whose work focuses on data-centric systems and the way they drive computing. He is an ACM Fellow, an Alfred P. Sloan Research Fellow and the recipient of two ACM-SIGMOD "Test of Time" awards for his research. In 2010, Fortune Magazine included him in their list of 50 smartest people in technology , and MIT's Technology Review magazine included his work on Distributed Programming on their 2010 TR10 list of the 10 technologies "most likely to change our world". Key ideas from his research have been incorporated into commercial and open-source software from IBM, Oracle, and PostgreSQL. He is a past director of Intel Research Berkeley, and currently serves on the technical advisory boards of a number of computing and Internet companies.

Host: Ugur Cetintemel