DATA OPTIMIZATIONS FOR CONSTRAINT AUTOMATA

Sung-Shik T. Q. Jongmans*, Farhad Arbab

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Constraint automata (CA) constitute a coordination model based on finite automata on infinite words. Originally introduced for modeling of coordinators, an interesting new application of CAs is implementing coordinators (i.e., compiling CAs into executable code). Such an approach guarantees correctness-by-construction and can even yield code that outperforms hand-crafted code. The extent to which these two potential advantages materialize depends on the smartness of CA-compilers and the existence of proofs of their correctness.

Every transition in a CA is labeled by a "data constraint" that specifies an atomic data-flow between coordinated processes as a first-order formula. At run-time, compiler-generated code must handle data constraints as efficiently as possible. In this paper, we present, and prove the correctness of two optimization techniques for CA-compilers related to handling of data constraints: a reduction to eliminate redundant variables and a translation from (declarative) data constraints to (imperative) data commands expressed in a small sequential language. Through experiments, we show that these optimization techniques can have a positive impact on performance of generated executable code.

Original languageEnglish
Article number11
Number of pages38
JournalLogical Methods in Computer Science
Volume12
Issue number3
DOIs
Publication statusPublished - 27 Apr 2017

Keywords

  • protocols
  • constraint automata
  • Reo
  • compilation
  • optimization
  • performance
  • PARTIALLY-DISTRIBUTED COORDINATION
  • CHANNEL-BASED COORDINATION
  • REO
  • SATISFACTION
  • HYPERGRAPHS
  • MODEL

Cite this

@article{4dc9b03b51504f9b9050fa1e5c7f148c,
title = "DATA OPTIMIZATIONS FOR CONSTRAINT AUTOMATA",
abstract = "Constraint automata (CA) constitute a coordination model based on finite automata on infinite words. Originally introduced for modeling of coordinators, an interesting new application of CAs is implementing coordinators (i.e., compiling CAs into executable code). Such an approach guarantees correctness-by-construction and can even yield code that outperforms hand-crafted code. The extent to which these two potential advantages materialize depends on the smartness of CA-compilers and the existence of proofs of their correctness.Every transition in a CA is labeled by a {"}data constraint{"} that specifies an atomic data-flow between coordinated processes as a first-order formula. At run-time, compiler-generated code must handle data constraints as efficiently as possible. In this paper, we present, and prove the correctness of two optimization techniques for CA-compilers related to handling of data constraints: a reduction to eliminate redundant variables and a translation from (declarative) data constraints to (imperative) data commands expressed in a small sequential language. Through experiments, we show that these optimization techniques can have a positive impact on performance of generated executable code.",
keywords = "protocols, constraint automata, Reo, compilation, optimization, performance, PARTIALLY-DISTRIBUTED COORDINATION, CHANNEL-BASED COORDINATION, REO, SATISFACTION, HYPERGRAPHS, MODEL",
author = "Jongmans, {Sung-Shik T. Q.} and Farhad Arbab",
year = "2017",
month = "4",
day = "27",
doi = "10.2168/LMCS-12(3:11)2016",
language = "English",
volume = "12",
journal = "Logical Methods in Computer Science",
issn = "1860-5974",
publisher = "Technical University of Braunschweig",
number = "3",

}

DATA OPTIMIZATIONS FOR CONSTRAINT AUTOMATA. / Jongmans, Sung-Shik T. Q.; Arbab, Farhad.

In: Logical Methods in Computer Science, Vol. 12, No. 3, 11, 27.04.2017.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - DATA OPTIMIZATIONS FOR CONSTRAINT AUTOMATA

AU - Jongmans, Sung-Shik T. Q.

AU - Arbab, Farhad

PY - 2017/4/27

Y1 - 2017/4/27

N2 - Constraint automata (CA) constitute a coordination model based on finite automata on infinite words. Originally introduced for modeling of coordinators, an interesting new application of CAs is implementing coordinators (i.e., compiling CAs into executable code). Such an approach guarantees correctness-by-construction and can even yield code that outperforms hand-crafted code. The extent to which these two potential advantages materialize depends on the smartness of CA-compilers and the existence of proofs of their correctness.Every transition in a CA is labeled by a "data constraint" that specifies an atomic data-flow between coordinated processes as a first-order formula. At run-time, compiler-generated code must handle data constraints as efficiently as possible. In this paper, we present, and prove the correctness of two optimization techniques for CA-compilers related to handling of data constraints: a reduction to eliminate redundant variables and a translation from (declarative) data constraints to (imperative) data commands expressed in a small sequential language. Through experiments, we show that these optimization techniques can have a positive impact on performance of generated executable code.

AB - Constraint automata (CA) constitute a coordination model based on finite automata on infinite words. Originally introduced for modeling of coordinators, an interesting new application of CAs is implementing coordinators (i.e., compiling CAs into executable code). Such an approach guarantees correctness-by-construction and can even yield code that outperforms hand-crafted code. The extent to which these two potential advantages materialize depends on the smartness of CA-compilers and the existence of proofs of their correctness.Every transition in a CA is labeled by a "data constraint" that specifies an atomic data-flow between coordinated processes as a first-order formula. At run-time, compiler-generated code must handle data constraints as efficiently as possible. In this paper, we present, and prove the correctness of two optimization techniques for CA-compilers related to handling of data constraints: a reduction to eliminate redundant variables and a translation from (declarative) data constraints to (imperative) data commands expressed in a small sequential language. Through experiments, we show that these optimization techniques can have a positive impact on performance of generated executable code.

KW - protocols

KW - constraint automata

KW - Reo

KW - compilation

KW - optimization

KW - performance

KW - PARTIALLY-DISTRIBUTED COORDINATION

KW - CHANNEL-BASED COORDINATION

KW - REO

KW - SATISFACTION

KW - HYPERGRAPHS

KW - MODEL

U2 - 10.2168/LMCS-12(3:11)2016

DO - 10.2168/LMCS-12(3:11)2016

M3 - Article

VL - 12

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

SN - 1860-5974

IS - 3

M1 - 11

ER -