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.
|