{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T08:05:00Z","timestamp":1790928300632,"version":"4.1.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,12,22]],"date-time":"2015-12-22T00:00:00Z","timestamp":1450742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>The CALM-conjecture, first stated by Hellerstein [2010] and proved in its revised form by Ameloot et al. [2013] within the framework of relational transducer networks, asserts that a query has a coordination-free execution strategy if and only if the query is monotone. Zinn et al. [2012] extended the framework of relational transducer networks to allow for specific data distribution strategies and showed that the nonmonotone win-move query is coordination-free for domain-guided data distributions. In this article, we extend the story by equating increasingly larger classes of coordination-free computations with increasingly weaker forms of monotonicity and present explicit Datalog variants that capture each of these classes. One such fragment is based on stratified Datalog where rules are required to be connected with the exception of the last stratum. In addition, we characterize coordination-freeness as those computations that do not require knowledge about all other nodes in the network, and therefore, can not globally coordinate. The results in this article can be interpreted as a more fine-grained answer to the CALM-conjecture.<\/jats:p>","DOI":"10.1145\/2809784","type":"journal-article","created":{"date-parts":[[2015,12,23]],"date-time":"2015-12-23T15:19:49Z","timestamp":1450883989000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Weaker Forms of Monotonicity for Declarative Networking"],"prefix":"10.1145","volume":"40","author":[{"given":"Tom J.","family":"Ameloot","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Zinn","sequence":"additional","affiliation":[{"name":"LogicBlox, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,12,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065214"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0049-y"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989320"},{"key":"e_1_2_1_4_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.   S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275507"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1708"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1060"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951367"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274605"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739056"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247613"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of CIDR. 249--260","author":"Alvaro P.","unstructured":"P. Alvaro , N. Conway , J. Hellerstein , and W. R. Marczak . 2011. Consistency analysis in bloom: A CALM and collected approach . In Proceedings of CIDR. 249--260 . P. Alvaro, N. Conway, J. Hellerstein, and W. R. Marczak. 2011. Consistency analysis in bloom: A CALM and collected approach. In Proceedings of CIDR. 249--260."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). IEEE, 52--63","author":"Alvaro P.","unstructured":"P. Alvaro , N. Conway , J. M. Hellerstein , and D. Maier . 2014. Blazes: Coordination analysis for distributed programs . In Proceedings of the International Conference on Data Engineering (ICDE). IEEE, 52--63 . P. Alvaro, N. Conway, J. M. Hellerstein, and D. Maier. 2014. Blazes: Coordination analysis for distributed programs. In Proceedings of the International Conference on Data Engineering (ICDE). IEEE, 52--63."},{"key":"e_1_2_1_14_1","volume-title":"Dedalus: Datalog in time and space. Tech. Rep. UCB\/EECS-2009-173. EECS Department","author":"Alvaro P.","year":"2009","unstructured":"P. Alvaro , W. Marczak , N. Conway , J. M. Hellerstein , D. Maier , and R. C. Sears . 2009 . Dedalus: Datalog in time and space. Tech. Rep. UCB\/EECS-2009-173. EECS Department , University of California , Berkeley. P. Alvaro, W. Marczak, N. Conway, J. M. Hellerstein, D. Maier, and R. C. Sears. 2009. Dedalus: Datalog in time and space. Tech. Rep. UCB\/EECS-2009-173. EECS Department, University of California, Berkeley."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of ICDT.","author":"Ameloot T. J.","year":"2014","unstructured":"T. J. Ameloot . 2014 . Deciding correctness with fairness for simple transducer networks . In Proceedings of ICDT. T. J. Ameloot. 2014. Deciding correctness with fairness for simple transducer networks. In Proceedings of ICDT."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594541"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 18th International Conference on Database Theory (ICDT). 308--323","author":"Ameloot T. J.","unstructured":"T. J. Ameloot , B. Ketsman , F. Neven , and D. Zinn . 2015. Datalog queries distributing over components . In Proceedings of the 18th International Conference on Database Theory (ICDT). 308--323 . T. J. Ameloot, B. Ketsman, F. Neven, and D. Zinn. 2015. Datalog queries distributing over components. In Proceedings of the 18th International Conference on Database Theory (ICDT). 308--323."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274587"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32925-8_6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/060658709"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2734"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273560"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_14"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.006"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142364"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of LICS. 311--320","author":"Feder T.","unstructured":"T. Feder and M. Y. Vardi . 2003. Homomorphism closed vs. existential positive . In Proceedings of LICS. 311--320 . T. Feder and M. Y. Vardi. 2003. Homomorphism closed vs. existential positive. In Proceedings of LICS. 311--320."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11503-5_9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860704"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90022-O"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of VLDB. 455--468","author":"Hull R.","unstructured":"R. Hull and M. Yoshikawa . 1990. ILOG: Declarative creation and manipulation of object identifiers . In Proceedings of VLDB. 455--468 . R. Hull and M. Yoshikawa. 1990. ILOG: Declarative creation and manipulation of object identifiers. In Proceedings of VLDB. 455--468."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375557"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 18th International Conference on Database Theory (ICDT). 291--307","author":"Ketsman B.","unstructured":"B. Ketsman and F. Neven . 2015. Optimal broadcasting strategies for conjunctive queries over distributed data . In Proceedings of the 18th International Conference on Database Theory (ICDT). 291--307 . B. Ketsman and F. Neven. 2015. Optimal broadcasting strategies for conjunctive queries over distributed data. In Proceedings of the 18th International Conference on Database Theory (ICDT). 291--307."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298542"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142485"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90040-N"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/2964569"},{"key":"e_1_2_1_42_1","unstructured":"D. Zinn. 2012. Weak forms of monotonicity and coordination-freeness. CoRR abs\/1202.0242.  D. Zinn. 2012. Weak forms of monotonicity and coordination-freeness. CoRR abs\/1202.0242."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274588"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2809784","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2809784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:54Z","timestamp":1750225374000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2809784"}},"subtitle":["A More Fine-Grained Answer to the CALM-Conjecture"],"short-title":[],"issued":{"date-parts":[[2015,12,22]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2809784"],"URL":"https:\/\/doi.org\/10.1145\/2809784","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,22]]},"assertion":[{"value":"2015-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}