Title: Mixing and clustering in message-passing schemes Abstract: The belief propagation algorithm and its variants have recently been shown to work quite well on hard constraint satisfaction problems. Survey propagation is one such algorithm that has been developed for solving the k-SAT problem. This algorithm is based on two hypotheses deriving from the replica symmetry breaking theory developed for the statistical mechanics of spin glasses. The first is that the solutions of constraint satisfaction problems near threshold organize into disjoint clusters. The second is that within each cluster there is spatial mixing. In this paper we show that both hypotheses hold for a large class of constraint satisfaction problems.