Despite the spectacular success of belief propagation algorithms in many application areas, theoretical results concerning both the correctness and convergence of these algorithms are known in very few cases, most of which concern graphs with at most one cycle, or graphs whose cycles b