Interoperability has been broadly conceptualized as the ability of agents to work together. In open systems, the interoperability of agents is an important concern. A common way of achieving interoperability is by requiring agents to follow prescribed protocols in their interactions with others. In existing systems, agents must follow any protocol to the letter; in other words, they should exchange messages exactly as prescribed by the protocol. This is an overly restrictive constraint; it results in rigid, fragile implementations and curbs the autonomy of agents. For example, a customer agent may send a reminder to a merchant agent to deliver the promised goods. However, if reminders are not supported explicitly in the protocol they are enacting, then the reminder would be considered illegal and the transaction may potentially fail. This paper studies the interoperation of agents, dealing with their autonomy and heterogeneity in computational terms.