Self-stabilizing distributed constraint satisfaction
Zeev Collin, Rina Dechter, Shmuel M. Katz · eScholarship (California Digital Library) · 1999
Connectionist-type architectures that allow a distributed solution for classes of constraint satisfaction problems are described, and such solutions are presented. The solutions are required to be self-stabilizing, 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. Subprotocols are presented that create a directed spanning tree in a constraint graph, and that assign values traversing such a tree. We show that some restricted topologies such as trees can accommodate the uniform, asynchronous model when neighboring nodes cannot take simultaneous steps. A protocol demonstrating this...