The Free Termination Property of Queries Over Time

Conor Power, Paraschos Koutris, Joseph M. Hellerstein · 2025

Read The Free Termination Property of Queries Over Time by Conor Power, Paraschos Koutris, Joseph M. Hellerstein (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-00222.txt.

Introduction

Conor Power, Paraschos Koutris, and Joseph M. Hellerstein write a database theory paper from 2025 on when a query can safely end. In a system spread across many machines, a node may hold a full answer yet expect more data later. The question is which queries let a node stop on its own, with no central coordination, and still be right.

They call this trait free termination and frame it as the match to past work on when answers stay correct without coordination. A new model based on simple state machines links older database models to tools software engineers use, such as conflict-free data types. The links aim to guide work on live views of changing data.

Catalog record

CREATORConor Power, Paraschos Koutris, Joseph M. Hellerstein
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-00222

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Free Termination Property of Queries Over Time Conor Power, Paraschos Koutris, Joseph M. Hellerstein Abstract 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. University of California Berkeley, United [email protected]://orcid.org/0000-0002-0660-5110 University of Wisconsin Madison, United [email protected]://orcid.org/0000-0001-6309-1702 University of California Berkeley, United [email protected]://orcid.org/0000-0002-7712-4306 ccs Theory of computation Distributed computing models ccs Information systems Parallel and distributed DBMSs ccs Information systems Stream management ccs Theory of computation Database theory keywords distributed systems, algebraic data models, coordination-free systems † † runningauthor: C. Power, P. Koutris, and J. Hellerstein 1 Introduction Distributed data systems have become a central topic in computing over the last decade due to a confluence of factors including cloud computing, increasing data growth and massively popular global-scale services. A central technical challenge in distributed computing and databases is the use—and avoidance—of coordination mechanisms [ 9 , 18 ] . Coordination in distributed systems is both slow and susceptible to unavailability via the CAP Theorem. In response, theoreticians have studied the question of what programs are computable in a distributed fashion without the use of coordination, most notably in the CALM Theorem [ 6 , 5 , 32 , 8 ] for coordination-free queries. Meanwhile, language designers and systems researchers have begun building systems that encourage coordination-free programming, exemplified by Conflict-free Replicated Data Types (CRDTs) [ 28 , 29 ] , which are popular data structure libraries based on semi-lattices. In this work we push beyond CALM in two directions. The first is to consider a different proof goal. The work on CALM is fundamentally about a soundness property called coordination-free eventual consistency : in the absence of coordination, what properties of a program ensure that each node in a distributed system will emit only correct program outputs over time? Here we pose a complementary completeness question, free termination : in the absence of coordination, what properties of a program ensure that each node in a distributed system can unilaterally terminate after producing all its (correct) results, even if updates may arrive from other nodes in the future? From a practical perspective, free termination is critical to any user or client that requires a complete answer before proceeding. The second ambition of this paper is to generalize the theory in this domain from its roots in relational transducers as explored in the CALM papers, and extend it to the context of the algebraic frameworks that are native to CRDTs, and of increasing interest in database research [ 2 , 20 , 10 , 21 , 22 ] . To that end, we introduce a general model that can capture what guarantees can be offered without coordination in both settings. Our model is based on queries over semiautomata and the guarantees to users are captured as properties of those semiautomata. The main contributions of the paper are as follows: 1. Using semiautomata, we introduce the notion of free termination (Section 3 ) in a state transition system, and show how it can be used to model different types of applications, including incremental view maintenance [ 10 ] and the pre-semiring data model used to extend Datalog [ 2 ] . 2. We then explore how the algebraic properties of the system and the query affect free termination (Section 4.1 ). Among our results, we show that under acyclic state modifications (commonly found in CRDTs), the only queries with free termination are a particular class of threshold queries over the natural partial order of states. We also show that if updates form a group or ring (e.g., in incremental view maintenance models), free termination cannot be achieved. 3. We study how to model coordination-free query computation in a distributed setting via the lens of free termination (Section 5 ). Interestingly, we show that by using the notion of free termination we can achieve a stronger and more fine-grained notion of coordination-freeness that applies to a pair of a query and an input. We show how coordination-freeness for network transducers as defined in [ 6 ] is a specific case of our more general notion of coordination-freeness. This allows us to characterize other queries as coordination-free, for example, antitone queries. 4. Finally, we look into free termination when the state space is finite (Section 6 ). We give a linear-time algorithm for deciding all free termination states in a transition system and also study how to perform state minimization. 1.1 Motivating Examples Before we proceed, we provide some motivating examples from the literature. We start with the domain of CRDTs, which have become quite popular with software engineers and shed light on both of our goals. Grow-Only Set CRDT: A common CRDT is the “grow-only set” CRDT: this is a replicated distributed set where each machine propagates its local set to other machines in the system. Upon receiving a message containing the local set at another machine, the local machine will apply its “merge” operation, modifying its local state to be the union of its current state and the incoming set. This process of propagation over an asynchronous network introduces non-determinism as messages might be delivered in a different order than they are sent and messages may arrive multiple times. The fact that set union forms a semi-lattice ensures that, regardless of these sources of network nondeterminism, the state at each machine will eventually converge to the same value. That eventual value is the union of all of the initial states at each machine and the time at which it is reached is called the quiescence point . Grow-only sets illustrate the point that CRDTs provide coordination-free consistency, but do not support free termination. In the absence of coordination, we do not have a mechanism for determining locally whether we have received all the elements in the network—i.e. whether we have reached a quiescence point. Without a guarantee of quiescence, what should we do to answer a query from a user? CRDTs allow arbitrary queries at any time and make no guarantee on the relationship between the query result at time t and the query result at the quiescence point. For example, consider the query Q(x)=R(x)-T(x) . A value (a) may be returned at time t , but eventually be excluded from the final output via subsequent “merges” into T(a) . This is not a particularly satisfactory contract between the system and the user: what good is distributed state if you do not know when you can query it reliably? Threshold Queries: Threshold queries characterize a class of queries over CRDTs in which a machine is able to unilaterally detect that the output will never change regardless

Read the complete text