Computer Science Department
School of Computer Science, Carnegie Mellon University


Decentralized Execution of Constraint Handling
Rules for Ensembles

Edmund S. L. Lam*, Iliano Cervesato*

April 2013


Also appears as Qatar Campus Technical Report

Keywords: Distributed Programming, Constraint Logic Programming, Multiset Rewriting

CHR is a declarative, concurrent and committed choice rule-based constraint programming language. In this paper, we adapt CHR to provide a decentralized execution model for parallel and distributed programs. Specifically, we consider an execution model consisting of an ensemble of computing entities, each with its own constraint store and each capable of communicating with its neighbors. We extend CHR into CHRε, in which rewrite rules are executed at one location and are allowed to access the constraint store of its immediate neighbors. We give an operational semantics for CHRε, denoted ωε₀, that defines incremental and asynchronous decentralized rewriting for the class of CHRε rules characterized by purely local matching (0-neighbor restricted rules). We show the soundness of the ωε₀ semantics with respect to the abstract CHR semantics. We then give a safe encoding of the more general 1-neighbor restricted rules as 0-neighbor restricted rules, and discuss how this encoding can be generalized to all CHRε programs.

50 pages

*Carnegie Mellon University, Qatar Campus

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by