Systems and methods are provided that enable authentication of transaction coordination messages sent via insecure connections. Also provided are systems and methods for controlling transaction coordination and recovery. In many embodiments, there is an exchange between a coordinator and a sub-coordinator, such that the coordinator provides the sub-coordinator with a coordinator token, and the sub-coordinator provides the coordinator with a sub-coordinator token. The coordinator and sub-coordinator tokens are used to authenticate transaction coordination messages sent over one or more insecure connections between the coordinator and the sub-coordinator.