Method, system and computer program product embodiments for, in an input/output (I/O) link handling complex instruction chains, a messaging scheme incorporating a method of error recovery between an initiator processor and a receiver processor, are provided. An operation initiation message is been sent from the initiator processor to the receiver processor for the receiver processor to begin work on an operation. If determined to be necessary, a terminate operation message is sent from the initiator processor to the receiver processor. The initiator processor withholds sending additional messages for the operation until a terminate operation response message is received. Once the terminate operation message is received, outstanding messages in process are flushed from the receiver processor. The receiver processor withholds sending additional messages to the initiator processor as the outstanding messages are completed. The terminate operation response message is sent from the receiver processor to the initiator processor.