Openness in Asynchronous Constraint Satisfaction Algorithms

Constraint satisfaction occurs in many practical applications. Recently, there has been increasing interest in distributed constraint satisfaction (DisCSP), where variables and constraints are distributed among several agents, and algorithms for finding solutions through asynchronous exchange of messages among agents. An important reason for distributed problem solving is openness: allowing the problem to define itself dynamically through the combination of agents that participate in it. We investigate openness in complete asynchronous search algorithms for DisCSP, in particular the problem of agents joining and leaving a search process in progress without destroying consistency for the other agents, and give complete search algorithms that satisfy this property.