2026-08-16T02:50:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22973 2025-10-02T12:19:59Z ddc:004 open_access

The Free Termination Property of Queries over Time Power, Conor Koutris, Paraschos Hellerstein, Joseph M. distributed systems algebraic data models coordination-free systems Building on prior work on distributed databases and the CALM Theorem, we define and study the question of free termination: in the absence of distributed coordination, what query properties allow nodes in a distributed (database) system to unilaterally terminate execution even though they may receive additional data or messages in the future? This completeness question is complementary to the soundness questions studied in the CALM literature. We also develop a new model based on semiautomata that allows us to bridge from the relational transducer model of the CALM papers to algebraic models that are popular among software engineers (e.g. CRDTs) and of increasing interest to database theory for datalog extensions and incremental view maintenance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Conor Power and Paraschos Koutris and Joseph M. Hellerstein 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.32 urn:nbn:de:0030-drops-229736 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.32 eng https://creativecommons.org/licenses/by/4.0/legalcode