Progressive negotiation is a strategy for resolving conflicts among distributed heterogeneous cooperating agents. This strategy aims at minimizing backtracking to previous solutions and provably ensures consistency of agents’ distributed solutions and convergence on a globally-satisfiable solution. The progressive negotiation strategy is enforced by a task-independent agent called Facilitator, which coordinates and controls the interaction of cooperating agents. The interaction of cooperating agents includes the communication of messages, the identification of conflicts, and the negotiation of conflicts as a way to resolve them. In this paper, we formally present our conceptualization of cooperating agents and their interaction via the facilitator. We next discuss the conflict types identified by agents and then present the progressive negotiation strategy for resolving conflicts. We then present two theorems that discuss the consistency and convergence of distributed solutions ensured by the strategy. Finally, we conclude with a summary of this paper and remarks about the strategy.