Speaker:
Euripides Markou
University of Thessaly, Lamia, Greece

Title: 
Mobile Agents Rendezvous in spite of a Malicious Agent

Time/Location
Oct 14, Wed 12:30 pm - 1:30 pm, Room: 5345 HP 

Abstract:
We examine the problem of rendezvous, i.e., 
having multiple mobile agents gather in a 
single node of a network. Unlike previous 
studies, we need to achieve rendezvous in 
presence of a malicious agent that moves 
through the network and tries to block 
the honest agents and prevent them from 
gathering. The malicious agent is assumed 
to be arbitrarily fast, has full knowledge 
of the network and it cannot be exterminated 
by the honest agents. On the other hand, 
the honest agents are assumed to be quite 
weak: They are asynchronous and anonymous, 
they have only finite memory, they have no 
prior knowledge of the network and they 
can communicate only when they meet at a node. 
We present necessary conditions for solving 
rendezvous in spite of the malicious agent 
in arbitrary networks. We then focus on ring 
and mesh topologies and provide algorithms 
to solve rendezvous. For ring networks, our 
algorithms solve rendezvous in all feasible 
instances of the problem, while we show that 
rendezvous is impossible for an even number 
of agents in unoriented rings. For the 
oriented mesh networks, we prove that the 
problem can be solved when the honest agents 
initially form a connected configuration 
without holes if and only if they can see 
which are the occupied nodes within a two-hops 
distance. 

http://users.softlab.ntua.gr/~emarkou/publications/