Information Technology Reference
In-Depth Information
consider the effect of limiting the memory of the agent. The task of rendezvous in
tree networks has been studied in synchronous environments for agents with small
memory and it was shown that logarithmic memory is required for rendezvous even
on the line [
13
]. Note that this lower bound does not apply directly in our setting
since the set of solvable instances of rendezvous is strictly larger in a synchronous
environment than in an asynchronous one when the agents cannot mark the vertices.
However, it is well known that
o
(
)
memory is not sufficient for exploration of
an arbitrary graph with termination, if marking is not allowed. Consequently, if the
agents cannot mark the nodes, one can show that
log
n
Ω
(
)
bits of memory are nec-
essary to solve rendezvous of two agents in an arbitrary graph in an asynchronous
environment.
In a synchronous environment without the ability to mark nodes, it is known [
12
]
that
O
log
n
memory is sufficient for rendezvous of two agents starting on asym-
metric positions in an arbitrary graph (even if the agents do not necessarily start at
the same time). The idea of the algorithm in [
12
] is to obtain a unique ordering on
distinct equivalence classes of nodes (without having to construct the views of the
nodes). Each agent can then use the index given to its initial position as its unique
identifier and rendezvous can be achieved using the standard algorithm for agents
having distinct identifiers in synchronous environments.
In the asynchronous setting, when the agent cannot mark nodes, we know that the
starting positions of the agents cannot be used to break symmetry. Thus, rendezvous
is solvable only if
(
log
n
)
is symmetric-covering-minimal. If each agent initially
knows an upper bound on the size of the graph, the agent can execute the first part
of the algorithm of [
12
] to distinguish between equivalence classes of nodes and
to order them. Thereafter, each agent could move to a node that belongs to the
class appearing first in this ordering. If
(
G
,
λ
,
δ
)
is symmetric-covering-minimal,
this node is unique and the agents would have achie
(
G
,
λ
,
δ
)
(
)
Theorem 7.
Agents with O
log
n
memory can solve rendezvous in any environment
(
,
λ
,
δ
)
G
where deterministic rendezvous is feasible without marking.
12.6 Rendezvous with Marking
In this section, we assume that the agents can write on whiteboards present in the
nodes of
G
. If we assume no bounds on the memory available to the agent or at a
node then there is an optimal algorithm to solve rendezvous (or Rendezvous-with-
Detect) for two agents using
Θ
(
m
)
moves. For the general case of
k
≥
2 agents, this
generalizes to an algorithm that requires
O
(
mk
)
moves to solve Rendezvous-with-
(
)
Detect and
O
to solve rendezvous.
The algorithm proceeds in two phases. In the first phase, the agents construct
a spanning forest of the graph using a distributed DFS-type algorithm (described
below as procedure DDFS). At the end of this procedure there is exactly one agent
in each tree in the forest and each agent
a
has a map of the tree that it belongs to (we
call this the agent's territory
T
a
). The second phase of the algorithm is a competition
between neighboring agents, during which each losing agent merges its territory
m
log
k
Search WWH ::
Custom Search