Technical Report CS0709

 TR#: CS0709 Class: CS Title: SELF-STABILIZING DISTRIBUTED CONSTRAINT SATISFACTION Authors: Z. Collin, R. Dechter, S. Katz PDF - Revised CS0709.revised.pdf Abstract: 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 {\bf 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 uniform, asynchronous model. However, some restricted topologies such as trees can accommodate the uniform, asynchronous model and a protocol demonstrating this fact is presented. An {\bf almost-uniform}, asynchronous, network consistency protocol is also presented. Subprotocols are given to make 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. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0709), rather than to the URL of the PDF files directly. The latter URLs may change without notice.