University of Hertfordshire

Interface Reconciliation in Kahn Process Networks using CSP and SAT

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Documents

View graph of relations
Original languageEnglish
Title of host publicationProceedings of the 5th Int. Workshop on the Cross-Fertilization Between CSP and SAT
PublisherCSPSAT
Publication statusPublished - 2015
Event5th Int. Workshop on the Cross-Fertilization Between CSP and SAT - Cork, Ireland
Duration: 31 Aug 2015 → …

Workshop

Workshop5th Int. Workshop on the Cross-Fertilization Between CSP and SAT
CountryIreland
CityCork
Period31/08/15 → …

Abstract

We present a new CSP- and SAT-based approach for coordinating interfaces of distributed stream-connected components provided as closed-source services. The Kahn Process Network (KPN) is taken as a formal model of computation and a Message Denition Language (MDL) is introduced to describe the format of messages communicated between the processes. MDL links input and output interfaces of a node to support ow inheritance and contextualisation. Since interfaces can also be linked by the existence of a data channel between them, the match is generally not only partial but also substantially nonlocal. The KPN communication graph thus becomes a graph of interlocked constraints to be satised by specic instances of the variables. We present an algorithm that solves the CSP by iterative approximation while generating an adjunct Boolean SAT problem on the way. We developed a solver in OCaml as well as tools that analyse the source code of KPN vertices to derive MDL terms and automatically modify the code by propagating type denitions back to the vertices after the CSP has been solved. Techniques and approaches are illustrated on a KPN implementing an image processing algorithm as a running example.

ID: 9998282