Coordination barriers are a major source of inefficiency in distributed query evaluation. Identifying queries that can be evaluated in a distributed, yet coordination-free way, can afford database engines significant performance gains. LogicBlox team members Daniel Zinn, TJ Green, and academic collaborator Professor Bertram Ludaescher of UC Davis, identifies a very expressive form of query that can be evaluated in a coordination-free way. Their paper appears in ICDT 2012, the 15th International Conference on Database Theory. LogicBlox is excited to have supported their work, and looking forward to incorporating this research into our distributed query evaluation engine! 
Abstract In a recent paper by Hellerstein, a tight relationship was conjectured between the number of strata of a Datalog: program and the number of “coordination stages” required for its distributed computation. Indeed, Ameloot et al. showed that a query can be computed by a coordination-free relational transducer network i f it is monotone, thus answering in the armative a variant of Hellerstein’s CALM conjecture, based on a particular de nition of coordination-free computation. In this paper, we present three additional models for declarative networking. In these variants, relational transducers have limited access to the way data is distributed. This variation allows transducer networks to compute more queries in a coordination-free manner: e.g., a transducer can check whether a ground atom A over the input schema is in the “scope” of the local node, and then send either A or not A to other nodes. We show the surprising result that the query given by the well-founded semantics of the unstrati able win-move program is coordination-free in some of the models we consider. We also show that the original transducer network model and our variants form a strict hierarchy of classes of coordination-free queries. Finally, we identify di erent syntactic fragments of Datalog, called semi-monotone programs, which can be used as declarative network programming languages, whose distributed computation is guaranteed to be eventually consistent and coordination-free.