Information Technology Reference
In-Depth Information
L
which is
the labeling function. However, note that this labeling is not necessarily injective, i.e.
two vertices may have the same label. This means that we must design algorithms
that work for any such labeling, and in particular for the constant labeling which
labels all nodes with the same label
c
The vertices of
G
are labeled over the set of symbols
L
by
λ
:
V
(
G
)
→
∈
L
(in this case, the nodes of the graph are
said to be
anonymous
).
The environment is thus represented by the tuple
(
,
λ
,Q,
,
δ
)
G
p
or equivalently
(
,
λ
,
χ
,
δ
)
by
G
. In case the nodes of the graph are anonymous, we shall omit
λ
.
p
The Agents.
Each agent
a
starts from the node
p
, called the
homebase
of
a
,and
executes a sequence of steps. The agents start from the same initial state but may
not necessarily start at the same time, and every action they perform (computing,
moving, etc.) takes a finite but otherwise unpredictable amount of time (i.e. the
actions of the agents are not synchronized). The actions that an agent
a
located at
a node
v
can perform depend on the state of the agent and the state of the node
v
(including the degree of
v
, the label of
v
, and the presence of other agents or marks
left by other agents). An agent can see another agent only when they are both located
at the same node. However, an agent may not even detect the presence of another
agent if both are traversing the same edge. Two agents may traverse the same edge
at different speeds; thus if agents
a
and
b
start traversing the same edge
(
a
)
one
after the other, it is possible that agent
b
arrives at the other end-point earlier than
agent
a
.
(
u
,
v
)
Communication model: Whiteboards and Tokens.
As mentioned before, two
agents may communicate (i.e. exchange information) directly only when they are
at the same node. To facilitate the task of rendezvous, sometimes the agents may
be allowed to leave marks on a node as a signal for other agents. In the
white-
board
model, the agents communicate by reading and writing information on public
whiteboards locally available at the nodes of the network. Each node
v
∈
G
has a
whiteboard (which is a shared region of its memory) and any agent visiting node
v
can read or write to the whiteboard. Access to the whiteboard is restricted by fair
mutual exclusion, so that at most one agent can access the whiteboard of a node at
the same time, and any requesting agent will be granted access within finite time.
A more restrictive model is the
token
model, where no whiteboards are available
but each agent has one or more identical
tokens
(sometimes called pebbles) to mark
nodes. An agent that contains a token can place it on a node
v
before leaving the
node; this token will be visible to any agent visiting node
v
, i.e. the visiting agent
can determine whether or not there is a token at that node. Similar to the whiteboard
model, we assume mutually exclusive access to node; Thus two agents may not
place their tokens at the same node simultaneously, they must do so sequentially.
The tokens are moveable, i.e. an agent can pick up a token, carry the token and
place it on a different node that the agent visits.
Cost Measures.
The cost of an algorithm can be the time taken until rendezvous
is achieved. Since we consider the actions of the agents to be asynchronous, a more
useful measure for the efficiency of the algorithm is the amount of movement made
by the agents, called the move complexity. In other words, whenever an agent
Search WWH ::
Custom Search