Concurrent Constraint Programming

Concurrent Constraint Programming (CCP) is a model for computing that describes multiple 'agents' (processes) reading and writing 'constraints' to shared variables. Communication is based on ask and tell:

ask: an agent queries the constraint store to see whether a condition holds. Doing so is generally blocking; for example, if you ask (X < Y), you will block until this is condition is known to be true or false. Usefully, you can often know whether the condition is true or false without actually knowing the values of X or Y.
tell: an agent modifies the 'constraint store' to include a new constraint. I.e. given variables X and Y, one might add something like (X+Y)<7 or (X > Y). If adding this constraint would result in an inconsistency, this 'failure' must somehow be handled.

One might see a close relationship to TupleSpace and BlackboardMetaphor: a centralized constraint store keeps all relevant data, and agents each seeking locations they may contribute by adding more new constraints. A significant difference, though, is that ConcurrentConstraintProgramming is logically monotonic: nothing is ever removed from the constraint store. (Though GarbageCollection can still occur when a constraint is no longer relevant to any agent, or when an agent is no longer relevant to the constraint store.)

There are 'timed' variations based on TemporalLogic that will associate a discrete time with each constraint and allowing propagation rules (for defining T+1 in terms of T), and those allow the constraints themselves to be non-monotonic over monotonic time. Other extensions include soft constraints (constraints have priorities, representing preference), stochastic constraints (introduces probability, for simulation), non-deterministic constraints, 'universal' constraints (which apply 'forall' style rules across a domain, rather than applying to specific variables), and so on.

A few CCP papers distinguish 'indeterminism' (committed choice, subject to RaceCondition) vs. 'non-determinism' (which relates to 'backtracking' or logically following all branches simultaneously and killing off inconsistent paths; NonDeterministicTuringMachine). Outside CCP, I have not seen literature to corroborate that this is a widely accepted distinction. Backtracking in CCP is easy to represent, though: you only need disjunctive constraints ((X < 5) || (X > 10)).

As with ConstraintProgramming, most implementations of CCP will be limited in expressiveness to a limited set of primitive 'domains', such as natural numbers, real numbers, propositional logic, etc. for which efficient evaluation strategies are known. Other domains may be modeled atop these primitive domains.

Unlike ConstraintProgramming, which has a clear 'goal' condition (an assignment to variables), there is no 'goal' driving CCP.

The stylistic relationship to ConstraintProgramming (CP) is weak, mostly related to the 'constraint store'. CP is clearly driven by a goal (GoalBasedProgramming) to satisfy a given set of constraints by assignment to a set of variables. CCP, by comparison, is focused upon how the agents themselves progress; while agents may be implemented with an in-the-large 'goal' in mind, they make local decisions. If CCP is used to accomplish a goal, the given set of agents will represent only one solution 'strategy' among many.

See: TupleSpace, BlackboardMetaphor, ConstraintProgramming, ReactiveDemandProgramming

CategoryConcurrency