Evènement pour le groupe Algorithmique Distribuée

Date 2011-01-10  14:00-15:00
TitreLog-space agents for solving anonymous rendezvous and other graph problems 
RésuméIn this talk we consider deterministic algorithms for some agent-based tasks in graphs. Mobile agents are frequently employed to perform decentralized information management processes, by persistently traversing or crawling the web, collecting, updating and disseminating information, and maintaining network integrity. In the rendezvous problem, two identical (anonymous) mobile agents start from arbitrary nodes in a graph and move from node to node with the goal of meeting. A well-known recent result on exploration, due to Reingold, states that exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with $O(log n)$ bits of memory, where $n$ is the size of the graph. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this minimum size is $Theta(log n)$, where $n$ is the size of the graph, regardless of the delay between the starting times of the agents. We also mention some other problems related to map reconstruction, for which an agent with $Theta(log n)$ bits of memory is sometimes required and always sufficient.  
LieuSalle 178 
OrateurAdrian Kosowski 

Aucun document lié à cet événement.

Retour à l'index