Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/19145

Title: Deciding Determinism with Fairness for Simple Transducer Networks
Authors: Ameloot, Tom
Issue Date: 2015
Abstract: 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. 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.
Notes: [Ameloot, Tom J.] Hasselt Univ, Hasselt, Belgium. [Ameloot, Tom J.] Transnat Univ Limburg, Limburg, Belgium.
URI: http://hdl.handle.net/1942/19145
DOI: 10.1145/2757215
ISI #: 000357269900003
ISSN: 0362-5915
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A293.36 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.