A Constraint Satisfaction Problem (CSP) is to find an assignment to a set of variables that is consistent wrt. a set of constraints over these variables. CSPs frequentlyarise in applications of distributed artificial intelligence [3] and may often not be solved bya centralized constraint solver for privacyor security reasons. In this distributed case (DCSP) constraints and variables are distributed among multiple automated agents.