{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:16:41Z","timestamp":1750306601357,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"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":[[2015,6,30]]},"abstract":"<jats:p>A distributed database system often operates in an asynchronous communication model where messages can be arbitrarily delayed. This communication model causes nondeterministic effects like unpredictable arrival orders of messages. Nonetheless, in general we want the distributed system to be deterministic; the system should produce the same output despite the nondeterministic effects on messages.<\/jats:p>\n          <jats:p>Previously, two interpretations of determinism have been proposed. The first says that all infinite fair computation traces produce the same output. The second interpretation is a confluence notion, saying that all finite computation traces can still be extended to produce the same output. A decidability result for the confluence notion was previously obtained for so-called simple transducer networks, a model from the field of declarative networking. In the current article, we also present a decidability result for simple transducer networks, but this time for the first interpretation of determinism, with infinite fair computation traces. We also compare the expressivity of simple transducer networks under both interpretations.<\/jats:p>","DOI":"10.1145\/2757215","type":"journal-article","created":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T15:45:37Z","timestamp":1435679137000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deciding Determinism with Fairness for Simple Transducer Networks"],"prefix":"10.1145","volume":"40","author":[{"given":"Tom J.","family":"Ameloot","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989320"},{"key":"e_1_2_2_2_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_2_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1708"},{"volume-title":"Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR'11)","author":"Alvaro P.","key":"e_1_2_2_4_1","unstructured":"P. Alvaro , N. Conway , J. Hellerstein , and W. R. Marczak . 2011. Consistency analysis in Bloom: A CALM and collected approach . In Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR'11) . 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 the 5th Biennial Conference on Innovative Data Systems Research (CIDR'11). 249--260."},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT'14)","author":"Ameloot T. J.","year":"2014","unstructured":"T. J. Ameloot . 2014 . Deciding correctness with fairness for simple transducer networks . In Proceedings of the 17th International Conference on Database Theory (ICDT'14) . 84--95. T. J. Ameloot. 2014. Deciding correctness with fairness for simple transducer networks. In Proceedings of the 17th International Conference on Database Theory (ICDT'14). 84--95."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594541"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274587"},{"key":"e_1_2_2_9_1","volume-title":"Deciding eventual consistency for a simple class of relational transducer networks","author":"Ameloot T. J.","year":"1942","unstructured":"T. J. Ameloot and J. Van den Bussche . 2013. Deciding eventual consistency for a simple class of relational transducer networks . Hasselt University , Tech . rep. http:\/\/hdl.handle.net\/ 1942 \/14571. T. J. Ameloot and J. Van den Bussche. 2013. Deciding eventual consistency for a simple class of relational transducer networks. Hasselt University, Tech. rep. http:\/\/hdl.handle.net\/1942\/14571."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01872848"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2460276.2462076"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2466486.2482856"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514924"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.006"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142364"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"N. Francez. 1986. Fairness. Springer New York.   N. Francez. 1986. Fairness. Springer New York.","DOI":"10.1007\/978-1-4612-4886-6"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11503-5_9"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860704"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989456"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008921"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142485"},{"volume-title":"Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04)","author":"Nash A.","key":"e_1_2_2_27_1","unstructured":"A. Nash and B. Ludascher . 2004. Processing unions of conjunctive queries with negation under limited access patterns . In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04) . Springer, 422--440. A. Nash and B. Ludascher. 2004. Processing unions of conjunctive queries with negation under limited access patterns. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04). Springer, 422--440."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cl.2012.02.001"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"M. Shapiro N. M. Preguica C. Baquero and M. Zawirski. 2011a. A comprehensive study of convergent and commutative replicated data types. Tech. report RR-7506. INRIA.  M. Shapiro N. M. Preguica C. Baquero and M. Zawirski. 2011a. A comprehensive study of convergent and commutative replicated data types. Tech. report RR-7506. INRIA.","DOI":"10.1007\/978-3-642-24550-3_29"},{"key":"e_1_2_2_31_1","first-page":"67","article-title":"Convergent and commutative replicated data types","volume":"104","author":"Shapiro M.","year":"2011","unstructured":"M. Shapiro , N. M. Preguica , C. Baquero , and M. Zawirski . 2011 b. Convergent and commutative replicated data types . Bull. EATCS 104 , 67 -- 88 . M. Shapiro, N. M. Preguica, C. Baquero, and M. Zawirski. 2011b. Convergent and commutative replicated data types. Bull. EATCS 104, 67--88.","journal-title":"Bull. EATCS"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00029-6"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT'14)","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen . 2014 . Triejoin: A simple, worst-case optimal join algorithm . In Proceedings of the 17th International Conference on Database Theory (ICDT'14) . 96--106. T. L. Veldhuizen. 2014. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of the 17th International Conference on Database Theory (ICDT'14). 96--106."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_2_2_35_1","volume-title":"An Introduction to MultiAgent Systems","author":"Wooldridge M.","unstructured":"M. Wooldridge . 2009. An Introduction to MultiAgent Systems , 2 nd ed. Wiley . M. Wooldridge. 2009. An Introduction to MultiAgent Systems, 2nd ed. Wiley.","edition":"2"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13174-010-0007-6"},{"key":"e_1_2_2_37_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\/2757215","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2757215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:49Z","timestamp":1750227409000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2757215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2757215"],"URL":"https:\/\/doi.org\/10.1145\/2757215","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}