Information Technology Reference
In-Depth Information
case, we can assume that the starting locations of the agents are distinctly labeled
by the function
λ
=
λ
×
χ
p
.
χ
p
and thus consider the node-labeling
Theorem 2.
Rendezvous is solvable in the environment
(
G
,
λ
,Q,
p
,
δ
)
if and only if
,
λ
,
δ
)
(
is symmetric-covering-minimal with respect to any label-preserving cov-
ering projection, where
G
λ
=
λ
×
χ
p
.
We can assume that the edge-labeling and node labeling of the graph is given
by an adversary. Thus, it makes sense to characterize the family of graphs where
rendezvous is possible for any labeling (assuming that the labeling provides a local
orientation at each node).
Theorem 3.
Given any connected graph G, the following statements are equivalent:
1. For any port-numbering
δ
, and any placement
χ
p
of agents in G, rendezvous
;
2. For any port-numbering function
can be solved in
(
G
,
χ
p
,
δ
)
δ
, each vertex of
(
G
,
δ
)
has a distinct view;
,
,...
(
)
∈
[
,|
(
)
|−
]
3. There is no partition V
1
V
2
V
k
of V
G
with k
1
V
G
1
such that for
,
∈
[
,
]
any distinct i
j
1
k
, the following conditions hold:
(i) G
[
V
i
]
is d-regular for some d, and if d is odd, it contains a perfect matching,
(ii) G
[
V
i
,
V
j
]
is regular.
4. Dir
(
G
)
is symmetric-covering-minimal.
12.4 Impossibility Results
From the results of the previous section, we know rendezvous can be solved only
in an environment
,
λ
,
δ
)
is symmetric-covering minimal. Given such an instance, it is possible to construct
another instance
(
G
,
λ
,Q,
p
,
δ
)
where the corresponding labelled graph
(
G
,
λ
H
,
δ
H
)
,
λ
H
,
δ
H
)
(
H
such that
|
V
(
H
)
|
=
2
|
V
(
G
)
|
and
(
H
covers
,
λ
,
δ
)
,
λ
H
,
δ
H
)
(
. Any algorithm that
solves
Rendezvous-with-Detect
must be able to distinguish between these two in-
stances. It is not possible to distinguish between these two instances unless the
agents are provided with some prior knowledge which allows them to deduce the
size of the graph with some accuracy. In fact, if the agents know an upper bound
B
such that
B
G
, and thus, rendezvous is not possible in
(
H
2
n
this is already sufficient to solve
Rendezvous-with-Detect
. (Recall
that for any graph
H
that covers
G
and is not isomorphic to
G
, the size of
H
must be
strictly a multiple of the size of
G
and thus
<
.)
Theorem 4.
The knowledge of only an arbitrary upper bound on n is not sufficient
for solving Rendezvous-with-Detect in an environment
|
V
(
H
)
|
is at least twice of
|
V
(
G
)
|
.
We now consider the move complexity of Rendezvous-with-Detect. It is easy
to see that each edge of the graph must be traversed by at least one agent. More-
over, in a symmetric environment (e.g. a ring with agents placed equidistant apart)
each agent may need to make
O
(
G
,
λ
,Q,
p
,
δ
)
moves before it can detect the impossibility of
rendezvous. This gives us the following lower bound.
Theorem 5.
Solving Rendezvous-with-Detect with k agents in an arbitrary graph of
n nodes and m edges requires
(
n
)
Ω
(
m
+
nk
)
moves in the worst case.
Search WWH ::
Custom Search