On the Feasibility of Distributed Constraint Satisfaction

Collin, Zeev; Dechter, Rina; Katz, Shmuel

On the Feasibility of Distributed Constraint Satisfaction

Download BibTeX Cite

Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Automated Reasoning. 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.

Zeev Collin, Rina Dechter, and Shmuel Katz. 1991. On the Feasibility of Distributed Constraint Satisfaction. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91. IJCAI, 318–323. https://ijcai.org/proceedings/1991/48

@inproceedings{ijcai1991p48,
  title     = {On the Feasibility of Distributed Constraint Satisfaction},
  author    = {Collin, Zeev and Dechter, Rina and Katz, Shmuel},
  booktitle = {Proceedings of the Twelfth International Joint Conference on
               Artificial Intelligence, {IJCAI-91}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {John Mylopoulos and Ray Reiter},
  pages     = {318--323},
  year      = {1991},
  month     = {8},
  note      = {Automated Reasoning},
  url       = {https://ijcai.org/proceedings/1991/48},
}

TY  - CPAPER
TI  - On the Feasibility of Distributed Constraint Satisfaction
AU  - Collin, Zeev
AU  - Dechter, Rina
AU  - Katz, Shmuel
T2  - Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1991
SP  - 318
EP  - 323
UR  - https://ijcai.org/proceedings/1991/48
ER  -