Multi-agent systems are autonomous decentralized platform software on whih application programs such as business transactions, network provisioning and manufacturing control are deployed. In order for the applications to be truly autonomous and decentralized, however, heterogeneous multi-agent systems themselves must communicate and interoperate with each other. To solve the problem, we take a two-step approach. Firstly, message-level interoperability is achieved by a gateway agent that interconnects eterogeneous multi-agent systems. Secondly, higher-level interoperation of conversations, which consist of bi-(or multi-) directional streams of messages, is governed by interaction protocols. We demonstrate the concept and technique of dynamic negotiation of interaction protocols and show how the method improves the assurance of real-world applications in autonomous decentralized systems.