{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T06:58:57Z","timestamp":1648537137596},"reference-count":63,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T00:00:00Z","timestamp":1536105600000},"content-version":"unspecified","delay-in-days":4,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:italic>Cloud computing<\/jats:italic>refers to maximizing efficiency by sharing computational and storage resources, while<jats:italic>data-parallel systems<\/jats:italic>exploit the resources available in the cloud to perform parallel transformations over large amounts of data. In the same line, considerable emphasis has been recently given to two apparently disjoint research topics:<jats:italic>data-parallel<\/jats:italic>, and<jats:italic>eventually consistent, distributed<\/jats:italic>systems.<jats:italic>Declarative networking<\/jats:italic>has been recently proposed to ease the task of programming in the cloud, by allowing the programmer to express only the desired result and leave the implementation details to the responsibility of the run-time system. In this context, we deem it appropriate to propose a study on a<jats:italic>logic-programming-based computational model<\/jats:italic>for eventually consistent, data-parallel systems, the keystone of which is provided by the recent finding that the class of programs that can be computed in an eventually consistent, coordination-free way is that of<jats:italic>monotonic programs<\/jats:italic>. This principle is called Consistency and Logical Monotonicity (CALM) and has been proven by Ameloot<jats:italic>et al.<\/jats:italic>for distributed, asynchronous settings. We advocate that CALM should be employed as a basic theoretical tool also for data-parallel systems, wherein computation usually proceeds synchronously in rounds and where communication is assumed to be reliable. We deem this problem relevant and interesting, especially for what concerns<jats:italic>parallel dataflow optimizations<\/jats:italic>. Nowadays, we are in fact witnessing an increasing concern about understanding which properties distinguish synchronous from asynchronous parallel processing, and when the latter can replace the former. It is general opinion that coordination-freedom can be seen as a major discriminant factor. In this work, we make the case that the current form of CALM does not hold in general for data-parallel systems, and show how, using novel techniques, the satisfiability of the CALM principle can still be obtained although just for the subclass of programs called<jats:italic>connected monotonic queries<\/jats:italic>. We complete the study with considerations on the relationships between our model and the one employed by Ameloot<jats:italic>et al.<\/jats:italic>, showing that our techniques subsume the latter when the synchronization constraints imposed on the system are loosened.<\/jats:p>","DOI":"10.1017\/s147106841800042x","type":"journal-article","created":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T09:16:50Z","timestamp":1536139010000},"page":"874-927","source":"Crossref","is-referenced-by-count":1,"title":["A datalog-based computational model for coordination-free, data-parallel systems"],"prefix":"10.1017","volume":"18","author":[{"given":"MATTEO","family":"INTERLANDI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LETIZIA","family":"TANCA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2018,9,5]]},"reference":[{"key":"S147106841800042X_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294281"},{"key":"S147106841800042X_ref14","unstructured":"Armbrust M. , Xin R. S. , Lian C. , Huai Y. , Liu D. , Bradley J. K. , Meng X. , Kaftan T. , Franklin M. J. , Ghodsi A. and Zaharia M. 2015. Spark sql: Relational data processing in spark. In Proc. of the Special Interest Group on Management of Data SIGMOD, 1383\u20131394."},{"key":"S147106841800042X_ref28","volume-title":"Reasoning About Knowledge","author":"Fagin","year":"2003"},{"key":"S147106841800042X_ref16","doi-asserted-by":"crossref","unstructured":"Beeri C. , Naqvi S. A. , Ramakrishnan R. , Shmueli O. and Tsur S. 1987. Sets and negation in a logic data base language (ldl1). In Proc. of ACM Symposium on Principles of Database Systems. ACM, 21\u201337.","DOI":"10.1145\/28659.28662"},{"key":"S147106841800042X_ref8","doi-asserted-by":"crossref","unstructured":"Alvaro P. , Conway N. , Hellerstein J. M. and Maier D. 2014. Blazes: Coordination analysis for distributed programs. In To appear in Proc. of the IEEE 30th International Conference on Data Engineering, ICDE '14. IEEE Computer Society, Washington, DC, USA.","DOI":"10.1109\/ICDE.2014.6816639"},{"key":"S147106841800042X_ref53","first-page":"1626","article-title":"Hive: A warehousing solution over a map-reduce framework","volume":"2","author":"Thusoo","year":"2009","journal-title":"VLDB"},{"key":"S147106841800042X_ref45","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536403"},{"key":"S147106841800042X_ref31","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174142"},{"key":"S147106841800042X_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/2694413.2694415"},{"key":"S147106841800042X_ref60","unstructured":"Zaniolo C. , Yang M. , Das A. and Interlandi M. 2016. The magic of pushing extrema into recursion: Simple, powerful datalog programs. In Proc. of the 10th Alberto Mendelzon International Workshop on Foundations of Data Management, Panama City, Panama, May 8\u201310, 2016."},{"key":"S147106841800042X_ref58","unstructured":"Xie C. , Chen R. , Guan H. , Zang B. and Chen H. 2015. Sync or async: Time to fuse for distributed graph-parallel computation. In Proc. of the Principles and Practice of Parallel Programming PPoPP, 194\u2013204."},{"key":"S147106841800042X_ref20","doi-asserted-by":"crossref","unstructured":"Borkar V. , Carey M. , Grover R. , Onose N. and Vernica R. 2011. Hyracks: A flexible and extensible foundation for data-intensive computing. In Proc. of the International Conference on Data Engineering, ICDE, 1151\u20131162.","DOI":"10.1109\/ICDE.2011.5767921"},{"key":"S147106841800042X_ref21","doi-asserted-by":"crossref","unstructured":"Brewer E. A. 2000. Towards robust distributed systems. In Proc. of the 19th Annual ACM Symposium on Principles of Distributed Computing, PODC '00. ACM, New York, NY, USA, 7\u2013.","DOI":"10.1145\/343477.343502"},{"key":"S147106841800042X_ref63","unstructured":"Zinn D. , Green T. J. and Lud\u00e4scher B. 2012. Win-move is coordination-free (sometimes). In International Conference on Database Theory, ICDT. ACM, 99\u2013113."},{"key":"S147106841800042X_ref40","doi-asserted-by":"crossref","unstructured":"Koutris P. and Suciu D. 2011. Parallel evaluation of conjunctive queries. In Proc. of ACM Symposium on Principles of Database Systems, PODS '11. ACM, New York, NY, USA, 223\u2013234.","DOI":"10.1145\/1989284.1989310"},{"key":"S147106841800042X_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/214451.214456"},{"key":"S147106841800042X_ref57","doi-asserted-by":"crossref","unstructured":"Wolfson O. and Silberschatz A. 1988. Distributed processing of logic programs. In Proc. of the Special Interest Group on Management of Data SIGMOD, 329\u2013336.","DOI":"10.1145\/50202.50242"},{"key":"S147106841800042X_ref34","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860704"},{"key":"S147106841800042X_ref54","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"S147106841800042X_ref51","doi-asserted-by":"crossref","unstructured":"Seib J. and Lausen G. 1991. Parallelizing datalog programs by generalized pivoting. In Proc. of ACM Symposium on Principles of Database Systems, 241\u2013251.","DOI":"10.1145\/113413.113435"},{"key":"S147106841800042X_ref47","doi-asserted-by":"crossref","unstructured":"Olston C. , Reed B. , Srivastava U. , Kumar R. and Tomkins A. 2008. Pig latin: A not-so-foreign language for data processing. In Proc. of the Special Interest Group on Management of Data, SIGMOD. ACM, 1099\u20131110.","DOI":"10.1145\/1376616.1376726"},{"key":"S147106841800042X_ref24","first-page":"313","volume-title":"NSDI","author":"Condie","year":"2010"},{"key":"S147106841800042X_ref25","unstructured":"Cui H. , Cipar J. , Ho Q. , Kim J. K. , Lee S. , Kumar A. , Wei J. , Dai W. , Ganger G. R. , Gibbons P. B. , Gibson G. A. and Xing E. P. 2014. Exploiting bounded staleness to speed up big data analytics. In Proc. of the USENIX Conference on USENIX Annual Technical Conference, USENIX ATC'14. USENIX Association, Berkeley, CA, USA, 37\u201348."},{"key":"S147106841800042X_ref5","doi-asserted-by":"crossref","unstructured":"Afrati F. N. and Ullman J. D. 2010. Optimizing joins in a map-reduce environment. In Proc. of the 13th International Conference on Extending Database Technology, EDBT '10. ACM, New York, NY, USA, 99\u2013110.","DOI":"10.1145\/1739041.1739056"},{"key":"S147106841800042X_ref11","doi-asserted-by":"crossref","unstructured":"Ameloot T. J. , Ketsman B. , Neven F. and Zinn D. 2014. Weaker forms of monotonicity for declarative networking: A more fine-grained answer to the calm-conjecture. In Proc. of ACM Symposium on Principles of Database Systems. ACM, 64\u201375.","DOI":"10.1145\/2594538.2594541"},{"key":"S147106841800042X_ref32","first-page":"395","volume-title":"International Conference on Database Theory ICDT","author":"Guessarian","year":"1990"},{"key":"S147106841800042X_ref46","unstructured":"Niu F. , Recht B. , Re C. and Wright S. J. 2011. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. In Proc. of the 24th International Conference on Neural Information Processing Systems, NIPS'11. Curran Associates Inc., USA, 693\u2013701."},{"key":"S147106841800042X_ref43","doi-asserted-by":"crossref","unstructured":"Malewicz G. , Austern M. H. , Bik A. J. , Dehnert J. C. , Horn I. , Leiser N. and Czajkowski G. 2010. Pregel: A system for large-scale graph processing. In Proc. of the ACM SIGMOD International Conference on Management of data, SIGMOD '10. ACM, New York, NY, USA, 135\u2013146.","DOI":"10.1145\/1807167.1807184"},{"key":"S147106841800042X_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/2542181"},{"key":"S147106841800042X_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"S147106841800042X_ref44","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0299-1"},{"key":"S147106841800042X_ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1060"},{"key":"S147106841800042X_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1708"},{"key":"S147106841800042X_ref12","unstructured":"Ameloot T. J. , Ketsman B. , Neven F. and Zinn D. 2015. Datalog queries distributing over components. In Proc. of International Conference on Database Theory ICDT, 308\u2013323."},{"key":"S147106841800042X_ref17","first-page":"421","volume-title":"DISC","author":"Ben-Zvi","year":"2010"},{"key":"S147106841800042X_ref18","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.21.323-354"},{"key":"S147106841800042X_ref61","first-page":"1048","article-title":"Fixpoint semantics and optimization of recursive datalog programs with aggregates","volume":"17","author":"Zaniolo","year":"2017","journal-title":"TPLP"},{"key":"S147106841800042X_ref41","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"S147106841800042X_ref35","unstructured":"Hunt P. , Konar M. , Junqueira F. P. and Reed B. 2010. Zookeeper: Wait-free coordination for internet-scale systems. In Proc. of the USENIX Conference on USENIX Annual Technical Conference, USENIXATC'10. USENIX Association, Berkeley, CA, USA, 11\u201311."},{"key":"S147106841800042X_ref55","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"S147106841800042X_ref39","first-page":"268","article-title":"Safety and liveness properties: A survey","volume":"53","author":"Kindler","year":"1994","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"S147106841800042X_ref36","unstructured":"Interlandi M. and Tanca L. 2015. On the CALM principle for BSP computation. In Proc. of the Alberto Mendelzon International Workshop on Foundations of Data Management."},{"key":"S147106841800042X_ref7","unstructured":"Alvaro P. , Conway N. , Hellerstein J. and Marczak W. R. 2011. Consistency analysis in bloom: A calm and collected approach. In Proc. Conference on Innovative Data Systems Research CIDR, 249\u2013260."},{"key":"S147106841800042X_ref49","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)00039-9"},{"key":"S147106841800042X_ref4","doi-asserted-by":"crossref","unstructured":"Afrati F. N. , Borkar V. , Carey M. , Polyzotis N. and Ullman J. D. 2011. Map-reduce extensions and recursive queries. In Proc. of the 14th International Conference on Extending Database Technology, EDBT\/ICDT '11. ACM, New York, NY, USA, 1\u20138.","DOI":"10.1145\/1951365.1951367"},{"key":"S147106841800042X_ref48","doi-asserted-by":"crossref","unstructured":"Ramakrishnan R. , Beeri C. and Krishnamurthy R. 1988. Optimizing existential datalog queries. In Proc. of Symposium on Principles of Database Systems. ACM, 89\u2013102.","DOI":"10.1145\/308386.308420"},{"key":"S147106841800042X_ref52","doi-asserted-by":"crossref","unstructured":"Shkapsky A. , Yang M. , Interlandi M. , Chiu H. , Condie T. and Zaniolo C. 2016. Big data analytics with datalog queries on spark. In Proc. of the International Conference on Management of Data, SIGMOD '16. ACM, New York, NY, USA, 1135\u20131149.","DOI":"10.1145\/2882903.2915229"},{"key":"S147106841800042X_ref50","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1453"},{"key":"S147106841800042X_ref15","first-page":"55","volume-title":"Distributed systems","author":"Babao\u011flu","year":"1993"},{"key":"S147106841800042X_ref1","volume-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"key":"S147106841800042X_ref22","unstructured":"Cal\u00ec A. , Gottlob G. , Lukasiewicz T. and Pieris A. 2011. Datalog+-: A family of languages for ontology querying. In Proc. of Datalog Reloaded \u2013 1st International Workshop, Datalog 2010, Oxford, UK, March 16\u201319, 2010. Revised Selected Papers, 351\u2013368."},{"key":"S147106841800042X_ref30","first-page":"1845","article-title":"DIADEM: Thousands of websites to a single database","volume":"7","author":"Furche","year":"2014","journal-title":"PVLDB"},{"key":"S147106841800042X_ref10","doi-asserted-by":"crossref","unstructured":"Ameloot T. J. , Geck G. , Ketsman B. , Neven F. and Schwentick T. 2015. Parallel-correctness and transferability for conjunctive queries. In Proc. of ACM Symposium on Principles of Database Systems.","DOI":"10.1145\/2745754.2745759"},{"key":"S147106841800042X_ref38","unstructured":"Interlandi M. , Tanca L. and Bergamaschi S. 2013. Datalog in time and space, synchronously. In Proc. of the Alberto Mendelzon International Workshop on Foundations of Data Management."},{"key":"S147106841800042X_ref37","unstructured":"Interlandi M. and Tanca L. 2017. On the CALM principle for bulk synchronous parallel computation. CoRR abs\/1405.7264."},{"key":"S147106841800042X_ref42","doi-asserted-by":"publisher","DOI":"10.1145\/2993.2994"},{"key":"S147106841800042X_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0357-y"},{"key":"S147106841800042X_ref62","unstructured":"Zaniolo C. , Yang M. , Interlandi M. , Das A. , Shkapsky A. and Condie T. 2018. Declarative bigdata algorithms via aggregates and relational database dependencies. In Proc. of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21\u201325, 2018."},{"key":"S147106841800042X_ref56","doi-asserted-by":"crossref","unstructured":"Wolfson O. and Ozeri A. 1990. A new paradigm for parallel and distributed rule-processing. In Proc. of the Special Interest Group on Management of Data SIGMOD, 133\u2013142.","DOI":"10.1145\/93597.98723"},{"key":"S147106841800042X_ref33","first-page":"950","article-title":"Giraph unchained: Barrierless asynchronous parallel execution in pregel-like graph processing systems","volume":"8","author":"Han","year":"2015","journal-title":"VLDB"},{"key":"S147106841800042X_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"S147106841800042X_ref29","volume-title":"Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering","author":"Foster","year":"1995"},{"key":"S147106841800042X_ref59","unstructured":"Zaharia M. , Chowdhury M. , Das T. , Dave A. , Ma J. , McCauley M. , Franklin M. J. , Shenker S. and Stoica I. 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proc. of the NSDI."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S147106841800042X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,23]],"date-time":"2019-10-23T17:26:13Z","timestamp":1571851573000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106841800042X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9]]},"references-count":63,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S147106841800042X"],"URL":"https:\/\/doi.org\/10.1017\/s147106841800042x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9]]}}}