On the CALM Principle for Bulk Synchronous Parallel Computation

In the recent years a lot of emphasis has been placed on two apparently disjoined fields: data-parallel and eventually consistent distributed systems. In this paper we propose a theoretical study over an eventually consistent data-parallel computational model. The keystone is provided by the recent finding that a class of programs exists which can be computed in an eventually consistent, coordination-free way: monotonic programs. This principle is called CALM and has been proven for distributed asynchronous settings. We make the case that, using the techniques developed by Ameloot et al., CALM does not hold in general for data-parallel systems, wherein computation usually proceeds synchronously in rounds and where communication is reliable. We then show that using novel techniques subsuming the one of Ameloot et al., the satisfiability of the CALM principle is directly related with the assumptions imposed on the behavior of the system.