Distributed Constraint Satisfaction Problems (DCSP) is a general framework for multi-agent coordination and conflict resolution. While inter-agent communication in most DCSP algorithms is restricted to only exchanging values of variables, this paper provides a detailed experimental investigation of the impact of inter-agent exchange of additional legal values among agents, within a collaborative setting. We present a new run-time model that takes into account the overhead of the additional communication in various computing/networking environments and show that DCSP strategies with extra communication can lead to significant performance improvement in realistic domains.