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 reports@cs.cmu.edu