With increasing deployment of multi-agent and distributed systems, there is an increasing need for coordination failure diagnosis systems. While successfully addressing key challenges, model-based diagnosis had difficulty in being applied to diagnosing coordination failures. However, it is possible to diagnose such failures using a model of the coordination between agents, by defining coordination primitives (concurrence and mutual exclusion). Earlier work showed that a centralized model-based diagnoser can diagnose coordination failures, however, it is not always applicable due to communication and computational overhead, and the problem it has a single point of failure. In this paper we propose a distributed approach to diagnose the coordination between the agents by exchanging information between the agents. We exploit a constraint-satisfaction model, and adapt algorithms from the distributed CSP area, to use as the basis for the diagnosis algorithms. We evaluate these algorithms in extensive experiments with simulated and real mobile robots and show a tradeoff between the effectiveness of the algorithms in terms of communication and computation and the correctness of the diagnosis that the algorithms produce.