R15  
SelfStabilizing Distributed Constraint Satisfaction
Zeev Collin (zeev@cs.technion.ac.il),
Rina Dechter (dechter@ics.uci.edu) &
Shmuel Katz (katz@cs.technion.ac.il)

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 selfstabilizing and to treat arbitrary networks, which makes them suitable for dynamic or errorprone environments. We first show that even for relatively simple constraint networks, such as rings, there is no selfstabilizing solution that guarantees convergence from every initial state of the system using a completely uniform, asynchronous model (where all processors are identical). An almostuniform , 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. [ps] [pdf] 