Technical Report CS0709

TR#:CS0709
Class:CS
Title: SELF-STABILIZING DISTRIBUTED CONSTRAINT SATISFACTION
Authors: Z. Collin, R. Dechter, S. Katz
PDF - RevisedCS0709.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.
CopyrightThe 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.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion
admin