Recently a new class of algorithms for constraint satisfaction problems
has emerged. These are known as message-passing algorithms. When applied to random instances of 3-SAT with density below the satisfiability threshold these algorithms have very high success probability even without doing any backtracking. The survey propagation algorithm - introduced by Mezard, Parisi and Zecchina in 2002 - is one such message-passing algorithm which is successful for very high density of clauses, i.e. very close to the conjectured satisfiability threshold. It is originally based on sophisticated statistical physics approximation methods. We show that it can also be interpreted as a belief propagation algorithm applied to a novel distribution on partial assignments. These partial assignments encode clusters of solutions of the formula.