Chicago Journal of Theoretical Computer Science

Volume 1999

Article 10

Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe.

Self-stabilizing Distributed Constraint Satisfaction

Zeev Collin (Technion), Rina Dechter (University of California, Davis), and Shmuel Katz (technion)
31 December 1999

Distributed architectures and solutions are described for classes of constraint satisfaction problems, called network consistency problems. An inherent assumption of these architectures is that the communication network mimics the structure of the constraint problem. The solutions are required to be self-stabilizing and to treat arbitrary networks, which makes them suitable for dynamic or error-prone environments. We first show that even for relatively simple constraint networks, such as rings, there is no self-stabilizing solution that guarantees convergence from every initial state of the system using a completely uniform, asynchronous model (where all processors are identical). An almost uniform, asynchronous, network consistency protocol with one specially designated node is shown and proven correct. We also show that some restricted topologies such as trees can accommodate the uniform, asynchronous model when neighboring nodes cannot take simultaneous steps.

DOI: 10.4086/cjtcs.1999.010
[] Article 9 [] Article 11
[back] Volume 1999 [back] Published articles
[CJCTS home]

Last modified: Sat Mar 20 09:32:31 CST 1999