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
Abstract
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.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 9
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 11
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 1999
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}