Two mobile deterministic agents (robots), starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents are subject to delay faults. If it planned to move and the fault happened, then the agent does not move and is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability 0<p<1), unbounded adversarial (the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial (the adversary can delay an agent for at most c consecutive rounds, where c is unknown to the agents). The main quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals.

For random faults, we show an algorithm with cost polynomial in the size n of the network and polylogarithmic in the larger label L, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous cannot be solved in arbitrary graphs but is solvable in trees. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in n, and logarithmic in the bound c and in the larger label L.

Joint work with Jérémie Chalopin, Yoann Dieudonné and Andrzej Pelc