A mechanism for negotiating a relatively transport agnostic communication protocol for use in accomplishing a distributed activity. The potential protocols subject to negotiation may be, for example, extensions to Web Services Coordination. In that case, when the initiator creates a transaction, the initiator also negotiates the desired protocol with its transaction manager. The transaction manager and any other participants in the transaction will then follow that negotiated protocol when communicating with the transaction manager. The protocol may be selected to improve performance and may be tailored to existing needs and capabilities.