4 DISTRIBUTED COMPUTING ENVIRONMENTS
their difference will depend solely on the initial value of their input registers. An
analogy is the legal system in democratic countries: the law (the set of rules) is the
same for every citizen (entity); still, if you are in the police force, while on duty, you
are allowed to perform actions that are unlawful for most of the other citizens.
An important consequence of the homogeneous behavior property is that we can
concentrate solely on environments where all the entities have the same behavior.
From now on, when we mention behavior we will always mean homogeneous col-
lective behavior.
1.2 COMMUNICATION
In a distributed computing environment, entities communicate by transmitting and
receiving messages. The message is the unit of communication of a distributed envi-
ronment. In its more general definition, a message is just a finite sequence of bits.
An entity communicates by transmitting messages to and receiving messages from
other entities. The set of entities with which an entity can communicate directly is not
necessarily E; in other words, it is possible that an entity can communicate directly
only with a subset of the other entities. We denote by N
out
(x) ⊆ E the set of entities
to which x can transmit a message directly; we shall call them the out-neighbors of
x . Similarly, we denote by N
in
(x) ⊆ E the set of entities from which x can receive a
message directly; we shall call them the in-neighbors of x.
The neighborhood relationship defines a directed graph
G = (V,
E), where V
is the set of vertices and
E ⊆ V ×V is the set of edges; the vertices correspond to
entities, and (x,y) ∈
E if and only if the entity (corresponding to) y is an out-neighbor
of the entity (corresponding to) x.
The directed graph
G = (V,
E) describes the communication topology of the envi-
ronment. We shall denote by n(
G), m(
G), and d(
G) the number of vertices, edges, and
the diameter of
G, respectively. When no ambiguity arises, we will omit the reference
to
G and use simply n, m, and d.
In the following and unless ambiguity should arise, the terms vertex, node, site,
and entity will be used as having the same meaning; analogously, the terms edge, arc,
and link will be used interchangeably.
In summary, an entity can only receive messages from its in-neighbors and send
messages to its out-neighbors. Messages received at an entity are processed there in
the order they arrive; if more than one message arrive at the same time, they will
be processed in arbitrary order (see Section 1.9). Entities and communication may
fail.
1.3 AXIOMS AND RESTRICTIONS
The definition of distributed computing environment with point-to-point communi-
cation has two basic axioms, one on communication delay, and the other on the local
orientation of the entities in the system.