The application of service oriented architecture enables business organizations to collaborate in an agile, just-in-time fashion using loosely coupled services. To ensure interoperability of interacting services, behavioral mismatches between their protocols need to be resolved in a fast and efficient way, which can be accomplished with protocol adaptors. We present an efficient, automated method to synthesize minimal protocol adaptors that resolve behavioral mismatches between asynchronously communicating business protocols. A minimal adaptor only processes those messages that cause the mismatch and has less message overhead at run-time than a non-minimal adaptor. If no adaptor can be synthesized, the method gives feedback on which parts of the protocols need to change to make the protocols adaptable. We show that the proposed method increases the efficiency of state-of-the-art service adaptation both at run-time and design-time. Moreover, the synthesized adaptors are more robust to changes in the input protocols than adaptors constructed with existing protocol adaptation approaches.