Probable Approximate Coordination

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.