The field of multi-agent systems shifts attention from one particular agent to a society of agents; hence the interactions between agents in the society become critical towards the achievement of their goals. We assume that the interactions are managed via a protocol which enables agents to coordinate their actions in order to handle the dependencies that exist between their activities. However, the agents' failures to comply with the constraints imposed by the protocol may cause the agents to have brittle interactions. To address this problem, a constraint relaxation approach derived from the Distributed Partial Constraint Satisfaction Problem (CSP) is proposed. This paper describes the computational aspects of the approach (i.e. specification of a distance metric, searching for a solvable problem and specification of a global distance function). © 2008 Springer Berlin Heidelberg.