Donald Bren School of Information and Computer Sciences
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.