I will present some recent work with Victor Dalmau on the complexity of the Distributed Constraint Satisfaction Problem (DCSP). We study the DCSP on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed template computational problems depends on the template’s polymorphisms. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time.
I will discuss the proof of this dichotomy while establishing a tight connection between the basic LP relaxation of a CSP and the well-known concept of iterated degree from graph theory, which we extend to CSPs.