---
title: "On the Feasibility of Distributed Constraint Satisfaction"
authors:
  - "Zeev Collin"
  - "Rina Dechter"
  - "Shmuel Katz"
doi: ""
url: "https://ijcai.org/proceedings/1991/48"
pdf: "https://ijcai.org/proceedings/1991/0048.pdf"
venue: "Proceedings of the Twelfth International Joint Conference on Artificial Intelligence"
year: 1991
pages: "318-323"
track: "Automated Reasoning"
keywords:
---

# On the Feasibility of Distributed Constraint Satisfaction

Zeev Collin, Rina Dechter, Shmuel Katz

*Proceedings of the Twelfth International Joint Conference on Artificial Intelligence*, pages 318-323.

## Abstract

This paper characterizes connectionist-type architectures that allow a distribute(! Solution for classes of constraint-satisfaction problems. The main issue addressed is whether there exists a uniform model of computation (where all nodes are indistinguishable) that rg!taJ_antees convergence to a solution from every initial state of the system, whenever such a solution exists. We show that even for relatively simple constraint networks, such as rings, there is no general solution using a completely uniform, asynchronous, model. However, some restricted topologies like trees can accommodate the uniform, asynchronous, model and a protocol demonstrating this fact is presented. An almost-uniform, asynchronous, networkconsistency protocol is also presented. We show that the algorithms are guaranteed to be selfstabilizing, which makes them suitable for dynamic or error-prone environments.