Information Technology Reference
In-Depth Information
12.5 Rendezvous Without Marking
In this section we assume that the agents have no means of marking the nodes of
the graph (i.e. no whiteboards or tokens are available). The knowledge of
n
(or, at
least some upper bound on it) is required to even explore the graph unless the graph
happens to be a tree. In asymmetric trees, rendezvous is possible without marking
and without knowledge of
n
. It is possible to traverse an anonymous tree and find
the central edge or central node in the tree (every tree has either a central node or a
central edge). The usual technique for rendezvous is to gather at the central node or
at one of the endpoints of the central edge. In the latter case, the agent needs to do
a comparison of the subtrees at either end of the central edge
e
, in order to choose
among the two end-points of
e
. This problem has been studied for agents having
small memory (see Sect.
12.5.2
).
12.5.1 Agents Having Unbounded Memory
When an upper bound on
n
is known a priori, and the agents have sufficient memory,
it is possible to solve rendezvous in an arbitrary graph
by constructing
the minimum-base of the labeled graph and then moving to a unique node of the
minimum-base. Note that according to Theorem
1
, rendezvous is solvable in this
case only if
(
G
,
λ
,
δ
)
is covering minimal. If that condition is satisfied then the
constructed minimum-base is isomorphic to
G
and thus all the agents will reach the
same node, hence solving rendezvous.
In case the exact value of
n
is provided, it is possible to use the same algorithm to
check for symmetric-covering-minimality and thus, solve Rendezvous-with-Detect.
We now discuss the algorithm (see [
8
] for more details). The first part of the algo-
rithm is a traversal of the graph visiting every vertex of
G
at least once. The second
part is the classification of the visited vertices into equivalence classes. Initially all
vertices are put in the same class and in subsequent rounds, the algorithm refines
the classes until each class corresponds to one vertex of the minimum-base. For the
traversal we use a UXS
U
(
G
,
λ
,
δ
)
n
is an upper bound on
n
and
d
is some
upper bound on the maximum degree of the graph
G
. We now describe the class
refinement process.
Given a graph
G
and node
u
of
G
and a sequence of edge-labels
(
N
,
d
)
where
N
≥
Y
=((
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,...,
(
p
j
,
q
j
))
,
we say that
Y
is
accepted
from
u
if there exists a path
P
=(
u
=
u
0
,
u
1
,...,
u
j
)
in
G
δ
(
)=
≤
≤
(
,
)=
δ
(
,
)
>
such that
P
Y
, i.e. for each
i
,1
i
j
,
p
i
q
i
u
i
−
1
u
i
.Forany
k
0,
,
two vertices
u
v
that have the same view up to depth
k
are said to be
k
-equivalent; we
∼
k
v
.The
k
-class of
u
is the set of all vertices that are
k
-equivalent to
u
and this set is denoted by
denote it by
u
C
,a
C
)
[
u
]
k
. Given any two
k
-classes
C
,
(
C
,
-
distinguishing
path
is a sequence of edge-labels
Y
C
,
C
=((
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,...,
(
p
j
,
q
j
))
such that
Search WWH ::
Custom Search