Abstract
This paper investigates the capability of decentralized, connectionist networks to solve Constraint Satisfaction Problems (CSPs). We demonstrate that while purely uniform networks face fundamental limitations due to symmetry, an "almost-uniform" model with a single leader node can reliably solve any CSP through a self-stabilizing, distributed backjumping algorithm. The proposed Network Consistency (NC) protocol provides the first theoretical guarantee of convergence for such distributed systems.
Introduction
Constraint Satisfaction Problems (CSPs), including tasks like graph coloring and scheduling, are fundamental to artificial intelligence. While sequential algorithms are well-established, solving CSPs in a distributed environment—where each variable is a processor with only local knowledge of its neighbors—presents significant challenges.
A primary hurdle in distributed CSPs is symmetry breaking. In a perfectly uniform network where every node runs identical code and starts in the same state, nodes can become trapped in infinite oscillations, never reaching a stable solution. The authors prove that no uniform, self-stabilizing protocol can solve a general CSP, such as the ring ordering problem, without some form of external coordination.
The Network Consistency (NC) Protocol
To overcome the limitations of total uniformity, the paper proposes an "almost-uniform" model. In this architecture, all nodes are identical except for one designated "root" node ($P_0$). This single point of non-uniformity allows the network to organize itself and coordinate a distributed search.
The proposed Network Consistency (NC) Protocol is built upon a distributed version of backjumping, decomposed into three self-stabilizing layers:
- DFS-tree generation: The network first organizes its communication graph into a depth-first search (DFS) tree. This structure is crucial for defining parent-child relationships and ordering the search space.
- Graph-traversal (Privilege Passing): A mechanism passes a "privilege" (or token) between nodes to ensure that only specific nodes change values at any given time, preventing conflicting simultaneous updates.
- Value-assignment: Nodes pick values from their domains to satisfy constraints. If a node reaches a dead-end where no value works, it initiates a "backward phase" (backjumping) to a previous variable in the DFS tree.
Self-Stabilization and Privilege Passing
A key feature of the NC protocol is its self-stabilizing nature. Regardless of the initial state or subsequent transient errors, the network is guaranteed to eventually converge to a valid solution. This makes the system inherently fault-tolerant; if a node's memory is corrupted, the protocol naturally steers the network back toward a consistent configuration.
The privilege passing layer manages the flow of control. By designating a privileged node, the system can serialize parts of the search process where necessary while allowing parallel exploration in independent subtrees.
Key Results and Complexity
The paper provides several critical theoretical insights:
- Convergence Guarantee: The NC protocol is the first connectionist-style distributed CSP model with a formal proof of convergence.
- Complexity: The time complexity is $O(nk^{m+1})$, where $n$ is the number of nodes, $k$ is the domain size, and $m$ is the depth of the DFS tree.
- Parallel Efficiency: While the worst-case complexity remains exponential (consistent with the NP-complete nature of CSPs), the protocol achieves a parallel speedup of approximately $O(n/m)$ by allowing independent subtrees to be processed simultaneously.
Conclusion and Future Work
While the "almost-uniform" model successfully solves general CSPs, some limitations remain. The current uniform solution for tree topologies relies on a "central demon" scheduler, and it remains an open question whether a purely uniform protocol can function under fully asynchronous conditions. Future research may also explore integrating "arc-consistency" subprotocols to improve average-case performance and refining the model for purely message-passing hardware implementations.
Summary updated