Win-Move is Coordination-Free (Sometimes)

Daniel Zinn, Todd J. Green, Bertram Ludäscher

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In a recent paper by Hellerstein [15], 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. [9] showed that a query can be computed by a coordination-free relational transducer network iff it is monotone, thus answering in the affirmative a variant of Hellerstein's CALM conjecture, based on a particular definition 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 ¬A to other nodes. We show the surprising result that the query given by the well-founded semantics of the unstratifiable win-move program is coordination-free in some of the models we consider. We also show that the original transducer network model [9] and our variants form a strict hierarchy of classes of coordination-free queries. Finally, we identify different 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.

Original languageEnglish (US)
Title of host publicationDatabase Theory - ICDT 2012
Subtitle of host publication15th International Conference on Database Technology, Proceedings
Number of pages15
StatePublished - 2012
Externally publishedYes
Event15th International Conference on Database Theory, ICDT 2012 - Berlin, Germany
Duration: Mar 26 2012Mar 29 2012

Publication series

NameACM International Conference Proceeding Series


Other15th International Conference on Database Theory, ICDT 2012


  • Datalog
  • Distribution
  • Monotonicity
  • Relational transducer

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'Win-Move is Coordination-Free (Sometimes)'. Together they form a unique fingerprint.

Cite this