Information Technology Reference
In-Depth Information
This chapter is organized as follows. The next section defines the model and
the problem and describes some basic properties of graphs which we use in solving
rendezvous. Section
12.3
provides a characterization of those instances where deter-
ministic rendezvous is possible. In the rest of the chapter, we focus on the problem
of Rendezvous-with-Detect where agents solve rendezvous whenever possible and
otherwise detect the fact that rendezvous is not possible. Section
12.4
provides some
minimum conditions required for solving the problem. We present algorithms for
solving Rendezvous-with-Detect both for the model where agents are not allowed
to mark nodes (Sect.
12.5
) and the model where marking is allowed (Sect.
12.6
).
In Sect.
12.7
, we consider the model where each agent is provided with a pebble,
allowing it to mark at most one node of the graph. We also discuss how to tolerate
failures and uncertainties in this model. Finally, in Sect.
12.8
, we study rendezvous
in dangerous environments where some of the agents may disappear (e.g. they are
devoured by some faulty node), and show how to rendezvous the surviving agents.
Section
12.9
concludes this chapter with a discussion of some open directions.
12.2 The Model and Basic Properties
The Environment.
The environment is represented by a simple undirected con-
nected graph
G
of mobile agents that are located
in the nodes of
G
. The initial placement of the agents is denoted by the function
p
:
=(
V
(
G
)
,
E
(
G
))
and a set
Q
Q →
V
(
G
)
. We denote such a distributed mobile environment by
(
G
,Q,
p
)
or
by
(
G
,
χ
p
)
where
χ
p
is a vertex-labeling of
G
such that
χ
p
(
v
)=
1 if there exists an
agent
a
such that
p
0 otherwise. For simplicity, we assume the
agents to be initially located in distinct nodes, but the algorithms can be generalized
to the case when two or more agents start from the same location (e.g. if two agents
happen to be initially co-located, they will move together as a single merged agent).
For the rest of this chapter,
n
(
a
)=
v
,and
χ
p
(
v
)=
=
|
(
)
|
=
|
(
)
|
V
G
and
m
E
G
denotes the numbers of
=
|Q|
vertices and of edges of
G
, while
k
denotes the number of agents. We shall
use the words vertex and node interchangeably.
In order to enable navigation of the agents in the graph, at each node
v
,
the edges incident to
v
are distinguishable to any agent
a
at node
v
.Inotherwords,
there is a bijective function
∈
V
(
G
)
δ
a
,
v
:
{
(
v
,
u
)
∈
E
(
G
)
:
u
∈
V
(
G
)
}→{
1
,
2
,...
d
(
v
)
}
which assigns unique labels to the edges incident at node
v
(where
d
(
v
)
is the degree
of
v
). The function
is called the local orientation or port-
numbering
2
and it is usually assumed that all agents have the same consistent port-
numbering (i.e.
δ
a
=
{
δ
a
,
v
:
v
∈
V
(
G
)
}
). In Sect.
12.7.2
, we shall consider the special case
when this is not true. For the rest of the paper, we assume a common port-numbering
δ
δ
a
=
δ
,
∀
a
∈ Q
(and thus remove the subscript
a
).
2
The labels on the edges may correspond to port numbers on a network
Search WWH ::
Custom Search