Information Technology Reference
In-Depth Information
Theorem 9 ([
7
]).
Two tokens per agent are necessary and sufficient to solve
Rendezvous-with-Detect in the absence of common port-numbering in any envi-
ronment
)
,
λ
)
(
G
,
λ
,Q,
p
)
such that
(
Dir
(
G
is symmetric-covering minimal where
λ
=
λ
×
χ
p
.
12.8 Rendezvous in Dangerous Graphs
We now consider the scenario where some of the nodes of the graph may be dan-
gerous and inaccessible to the agents. This is inspired by communication networks
where some nodes or links between nodes may develop faults. If an agent attempts
to traverse a faulty link or to move to a faulty node it simply disappears (i.e. the agent
is destroyed without leaving a trace). Given a graph with multiple faulty nodes, we
can merge them all into one dangerous node
x
, called the
black hole
. The question
of whether rendezvous can be solved in a graph containing a black hole was first
studied in [
17
] where an algorithm was provided for ring graphs containing a single
black hole. We study the problem for arbitrary graphs with both faulty nodes and
faulty edges, where the agents do not have prior knowledge of the graph topology or
the possible location of faults. Throughout this section we assume the whiteboard
model of communication, i.e. the agents may write any information on the nodes
they visit.
Since the location of a black hole is unknown and cannot be determined unless
an agent falls into it and is destroyed, this means that rendezvous of all agents is
not possible. Thus, the objective is to achieve rendezvous of as many agents as pos-
sible while avoiding the black hole. It can be shown that in an unknown arbitrary
graph with
links that lead to a black hole, it is not possible to solve rendezvous
of more than
k
τ
agents [
9
]. Note that no agent starts from the black hole (i.e. the
homebases are distinct from the black hole node). For agents starting from arbitrary
locations, rendezvous of any two agents is possible only if the graph obtained af-
ter removing the black hole is connected. We now present some other conditions
that must be satisfied for feasibility of deterministic rendezvous in an environment
(
−
τ
G
,
λ
,Q,
p
,
δ
,
η
)
where the function
η
:
E
(
G
)
→{
0
,
1
}
denotes which edges are
safe (
0). Given a graph with multiple faulty
edges and faulty nodes, we can replace each faulty edge
η
(
e
)=
1) and which are faulty (
η
(
e
)=
(
u
,
v
)
with two edges
(
u
,
x
)
and
(
v
,
y
)
leading to two distinct (dangerous) nodes
x
and
y
respectively. We denote
by
, the number of faulty links (each faulty edge accounts for two faulty links).
We define the
extended-map
of the environment
τ
(
G
,
λ
,Q,
p
,
δ
,
η
)
as the labeled
digraph
(
H
,
μ
)
such that,
H
consists of two disjoint vertex sets
V
1
and
V
2
and a set
H
of arcs
A
as defined below:
•
=
(
)
V
1
V
G
;
•
μ
(
)=(
λ
(
)
,
χ
(
))
∀
∈
v
v
v
,
v
V
1
;
H
p
•
For every safe edge
e
=(
u
,
v
)
∈
E
(
G
)
, there are two arcs
a
1
,
a
2
∈ A
such that
s
(
a
1
)=
t
(
a
2
)=
u
,
s
(
a
2
)=
t
(
a
1
)=
v
,and
μ
H
(
a
1
)=(
δ
u
(
e
)
,
δ
v
(
e
))
,
μ
H
(
a
2
)
=(
δ
v
(
e
)
,
δ
u
(
e
))
.
Search WWH ::
Custom Search