Information Technology Reference
In-Depth Information
traverses an edge of the graph, this incurs a unit cost and the total cost of the
algorithm is the total number of edge-traversals made by all the agents together,
in the worst case execution of the algorithm.
Other than optimizing on the time or the movement cost, one can consider the
space cost of an algorithm e.g. the memory that needs to be allocated at each node of
the graph, or the memory used by an agent during the algorithm. Thus, we associate
three different cost measures for a rendezvous algorithm: (i) Movement Cost, (ii)
Node Memory, and (iii) Agent Memory.
Problem Definition
Definition 1 (Rendezvous).
Given a distributed mobile environment (
G
,
λ
,
Q
,
p
,
δ
is said to solve
rendezvous
if for any distributed execution of
the algorithm by the agents, there exists a node
v
), an algorithm
A
∈
G
such that all agents in
Q
eventually reach node
v
and do not move thereafter.
In the definition above, we do not require the agents to terminate explicitly (i.e.
an agent may not be aware when rendezvous has been achieved). Note that even
though we consider only deterministic algorithms, the outcome of the algorithm may
depend on the particular sequence of events and actions during the (asynchronous)
execution of the algorithm by the individual agents. We define a
distributed execu-
tion
of an algorithm as one possible sequence of actions and events that is consistent
with the environment and the algorithm.
We say that rendezvous is feasible in
(
,
λ
,Q,
,
δ
)
G
p
, if and only if there exists a
(
,
λ
,Q,
,
δ
)
deterministic algorithm that solves
rendezvous
in
G
p
.
Definition 2 (Rendezvous-with-Detect).
Given a distributed mobile environment
(
, an algorithm is said to solve
Rendezvous-with-Detect
if the follow-
ing holds for any distributed execution of the algorithm. If rendezvous is feasible in
(
G
,
λ
,Q,
p
,
δ
)
must eventually terminate at one unique node
v
of
G
and if not, then each agent must terminate in its homebase and output “Ren-
dezvous is not solvable”.
G
,
λ
,Q,
p
,
δ
)
, then all agents in
Q
When there are more than 2 agents, i.e.
|Q| >
2, we can define the concept of
partial rendezvous
where at least
w
agents are required to gather at a node of
the graph. This will be discussed further in Sect.
12.8
.
< |Q|
Properties of Graphs: Coverings and Universal Exploration Sequences
The notions presented in this section were introduced in [
6
]. Any connected (undi-
rected) graph
G
can be represented by a strongly connected symmetric digraph
D
, where each edge of
G
is represented by a pair of symmetric arcs in
D
, one in each direction. In this section, we present some definitions and results re-
lated to directed graphs and their coverings, which we use to characterize the solv-
able instances for rendezvous. A directed graph (digraph)
D
=
Dir
(
G
)
=(
V
(
D
)
,
A
(
D
)
,
s
D
,
t
D
)
Search WWH ::
Custom Search