  We study the problem of how to coordinate the actions of independent agents
in a distributed system where message arrival times are unbounded, but are
determined by an exponential probability distribution. Asynchronous protocols
executed in such a model are guaranteed to succeed with probability 1. We
demonstrate a case in which the best asynchronous protocol can be improved on
significantly. Specifically, we focus on the task of performing actions by
different agents in a linear temporal order -- a problem known in the
literature as Ordered Response. In asynchronous systems, ensuring such an
ordering requires the construction of a message chain that passes through each
acting agent, in order. Solving Ordered Response in this way in our model will
terminate in time that grows linearly in the number of participating agents
$n$, in expectation. We show that relaxing the specification slightly allows
for a significant saving in time. Namely, if Ordered Response should be
guaranteed with high probability (arbitrarily close to 1), it is possible to
significantly shorten the expected execution time of the protocol. We present
two protocols that adhere to the relaxed specification. One of our protocols
executes exponentially faster than a message chain, when the number of
participating agents $n$ is large, while the other is roughly quadratically
faster. For small values of $n$, it is also possible to achieve similar results
by using a hybrid protocol.
