Distributed computing systems having mechanisms for efficiently coordinating transactions between nodes in the system are provided. One or more nodes may negotiate maximum time periods in which to communicate with each other or a transaction coordinator. A node is determined to be non-responsive when the time since a last communication exceeds the maximum time period. The maximum time period may include an adjustment for the latency of at least a portion of the distributed computing system.