Skip to main content
Open Access Publications from the University of California

Self-stabilizing distributed constraint satisfaction

  • Author(s): Collin, Zeev
  • Dechter, Rina
  • Katz, Shmuel
  • et al.

This paper characterizes connectionist-type architectures that allow a distributed solution for classes of constraint satisfaction problems, and presents such solutions. We first consider whether there exists a uniform model of computation that guarantees convergence to a solution from every initial state of the system, whenever such a solution exists. Even for relatively simple constraint networks, such as rings, we show that there is no general solution that guarantees convergence from every initial state of the system using a completely different uniform, asynchronous model. However, some restricted protocol demonstrating this fact is presented. An almost-uniform, asynchronous, network consistency protocol is also presented. Subprotocols are given to maike an undirected tree directed and to traverse a graph. We show that the algorithms are guaranteed to be self-stabilizing, which makes them suitable for dynamic or error-prone environments.

Main Content
Current View