Price of asynchrony in mobile agents computing

The aim of this paper is to fill up this gap. We show for the first time that for some natural task executed by mobile agents in a network, the optimal cost of its deterministic solution in the asynchronous setting has higher order of magnitude than that in the synchronous scenario. The task for which we show this difference is well-studied: that of rendezvous of two agents in an infinite oriented grid. More precisely, we consider two agents with distinct integer labels starting at a distance D in the infinite oriented grid. Each agent knows D and its own label but not the label of the other agent and it does not know the position of the other agent relative to its own. Agents do not have any global system of coordinates. They have to meet in a node or inside an edge of the grid, and the cost of a rendezvous algorithm is the number of edge traversals by both agents until the meeting. We show that in the synchronous scenario rendezvous can be performed at cost O(Dℓ), where ℓ is the length of the (binary representation of the) smaller label, while cost Ω(D2+Dℓ) is needed for asynchronous completion of rendezvous. Hence, for instances with ℓ=o(D), the optimal cost of asynchronous rendezvous is asymptotically larger than that of synchronous rendezvous.