  Two identical anonymous mobile agents have to meet at a node of the infinite
oriented grid whose nodes are unlabeled. This problem is known as rendezvous.
The agents execute the same deterministic algorithm. Time is divided into
rounds, and in each round each agent can either stay idle at the current node
or move to an adjacent node. An adversary places the agents at two nodes of the
grid at a distance at most $D$, and wakes them up in possibly different rounds.
Each agent starts executing the algorithm in its wakeup round.
  If agents cannot leave any marks on visited nodes then they can never meet,
even if they start simultaneously at adjacent nodes and know it. Hence, we
assume that each agent marks any unmarked node it visits, and that an agent can
distinguish if a node it visits has been previously marked or not. The time of
a rendezvous algorithm is the number of rounds between the wakeup of the later
agent and rendezvous. We ask the question whether the capability of marking
nodes enables the agents to meet, and if so, what is the fastest rendezvous
algorithm.
  We consider this problem under three scenarios. First, agents know $D$ but
may start with arbitrary delay. Second, they start simultaneously but do not
have any {\em a priori} knowledge. Third, most difficult scenario, we do not
make any of the above facilitating assumptions. Agents start with arbitrary
delay and they do not have any a priori knowledge. We prove that in the first
two scenarios rendezvous can be accomplished in time $O(D)$. This is clearly
optimal. For the third scenario, we prove that there does not exist any
rendezvous algorithm working in time $o(D^{\sqrt{2}})$, and we show an
algorithm working in time $O(D^2)$. The above negative result shows a
separation between the optimal complexity in the two easier scenarios and the
optimal complexity in the most difficult scenario.
