< Back to previous page

Publication

Deciding Confluence for a Simple Class of Relational Transducer Networks

Journal Contribution - Journal Article

Networks of relational transducers can serve as a formal model for declarative networking, focusing on distributed database querying applications. In declarative networking, a crucial property is eventual consistency, meaning that the final output does not depend on the message delays and reorderings caused by the network. Here, we formalize eventual consistency as a confluence notion, meaning that finite executions of the system can always be extended to yield the desired output. We show that confluence is decidable when the transducers satisfy some syntactic restrictions, some of which have also been considered in earlier work on automated verification of relational transducers. This simple class of transducer networks computes exactly all distributed queries expressible by unions of conjunctive queries with negation.
Journal: THEORY OF COMPUTING SYSTEMS
ISSN: 1432-4350
Issue: 4
Volume: 57
Pages: 1038 - 1111
Publication year:2015
Keywords:Relational transducer, Eventual consistency, Confluence, Decidability, Conjunctive query, relational transducer, eventual consistency, confluence, decidability, conjunctive query
BOF-keylabel:yes
IOF-keylabel:yes
BOF-publication weight:0.5
CSS-citation score:1
Authors from:Higher Education
Accessibility:Open