We examine how to design convergent and correct message-passing schemes, similar to the min-sum algorithm, for maximum a posteriori (MAP) estimation in the case that the messages passed between two nodes of the network may never be delivered. The proposed solution creates a new, but equivalent, graphical model over which the convergence of a specific message-passing algorithm is guaranteed. We then show that the messages passed on this new model can be reduced to message passing over the original model if we allow some additional state at each node of the network.