Probable Approximate Coordination
We study the problem of how to coordinate the actions of independent agents in an asynchronous distributed system where message arrival times are unbounded, but are determined by an exponential probability distribution. Specifically, we focus on the task of ordering of actions performed by different nodes in a linear temporal order – a problem known in the literature as Ordered Response. Ensuring such an ordering, even with probability 1, requires the construction of a message chain that passes through each acting site, in order. As a result, any protocol that solves Ordered Response with such guarantees must require linear time in expectation. We show, however, that relaxing the specification slightly allows for a significant saving in time. Namely, if Ordered Response should be guaranteed with high probability (smaller than 1), it is often possible to significantly shorten the expected execution time of the protocol.
*M.Sc. student under the supervision of Prof. Yoram Moses.