Chapter 3
Agent Communication
Agent-to-Agent and Agent-to-World Communication Models
Shared Memory 102
Tuple Space Communication 103
Communication Signals 107
Comparison: Signals and Tuples 108
Process Communication Calculus 111
FIPA ACL 117
AAPL Agents and Capability-based Remote Procedure Calls 118
Further Reading 125
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
102
This chapter introduces some communication and interaction aspects of
MAS and the relationship to the AAPL agent behaviour model. The AAPL tuple-
space agent interaction is presented and its relation to mobile processes and
the -Calculus with channel-based communication.
3.1 Shared Memory
The shared memory model is a commonly used inter-process communica-
tion paradigm for parallel, rather less for distributed systems. It is closely
related to the parallel register and random access machine (PRAM), shown in
the Figure 3.1 below, and discussed in Chapter 5 in conjunction with the Com-
municating Sequential Processes (CS) data processing model.
The PRAM model assumes n identical processing units (PU), which are con-
nected to a shared memory resource with a random access model (SRAM),
with memory cells of equal width that are referenced by a numerical address.
The SRAM model supports read and write operations. Based on the RAM
access model (Exclusive or Concurrent Read and Write), one or more PUs can
access the SRAM. Concurrent read operations are in principle free of conflicts
(neglecting technological and architectural constraints and conflicts), but write
operation can cause access conflicts, e.g., writing of multiple PUs to the same
memory cell storing different values. These conflicts require a conflict resolu-
tion function, commonly solved by mapping concurrent access on a
sequential ordered exclusive access model. The SRAM and PRAM model pro-
vides no explicit synchronization between different PUs and processes they
are executing, and it introduces a strong coupling of the PUs. A shared mem-
ory model is attractive in parallel and distributed programming because it
offers a simplified parallelization paradigm for existing algorithms, which can
be supported by programming language extensions, e.g., multi-threading
extensions for established programming languages, or in distributed pro-
gramming languages like Orca [BAL90]. In distributed systems the reading,
writing, and updating of cached SRAM cells are encapsulated in message
passing. Without additional synchronization primitives the SRAM model is not
useful for inter-process and inter-agent communication. Furthermore, the
SRAM model "violates" the autonomy feature of agents and the loosely cou-
pling of agents with their environment.
This model is used by the SeSAm MAS simulator exclusively for the imple-
mentation of the inter-agent communication. The simulator is used in this
work for all kinds of behavioural MAS and agent platform simulations, dis-
cussed in Section 11.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.2 Tuple Space Communication 103
Fig. 3.1 The Parallel Random Access Machine (PRAM)
3.2 Tuple Space Communication
Tuple spaces represent an associated shared memory model, considering
the shared data as objects with a set of operations supporting the access of
data objects, which are organized in spaces that can be considered as abstract
computation environments. A tuple-space connects different programs,
which can be distributed if the tuple-space is distributed, too, or at least its
operational access. One well-known tuple-space organization and coordina-
tion paradigm is Linda [GEL85]. The tuple-space organization and access
model offers generative communication, i.e., data objects can be stored in a
space by processes with a lifetime beyond the end of the generating process.
3.2.1 The Data Model
The data is organized with tuples. A tuple is a loosely coupled compound of
an arbitrary number of values of any kind. A tuple is a value and once stored
in a tuple space it is persistent. Tuple types are similar to record types, but
they are dynamic and can be constructed at run-time on the fly without any
static type constraints. The field elements of tuples cannot be accessed
directly, commonly requiring pattern matching and pattern-based decompo-
sition, in contrast to record types offering named access to field elements,
though treating of tuples as arrays or lists can solve this limitation. A tuple
with n fields is called n-ary.
Formally, tuples are defined as vectors by the following generation rule with
values v, expressions , and variables x that are considered as actual parame-
ters (i.e., variables x used with value semantics):
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
104
Tuple values require pattern matching based on template pattern, with the
following generation rule, consisting of actual (v,,x) and formal parameters
(x?, variables used with reference semantics):
A search pattern can use a wild-card () instead of formal parameters. Each
tuple e has a type signature Sig(e) = S
e
= T
1
; T
2
; ... ; T
n
, a tuple of the same arity
as e, specifying the type of each tuple field. A tuple can only be addressed by
its association with templates.
Def. 3.1 Matching rule for tuples and templates
Let e =
d
1
; d
2
; ... ; d
n
be a tuple, t =
dt
1
; dt
2
; ... ; dt
m
be a template; than e
matches t (denoted by eßt and match(e,t)=true) if the following conditions hold: (i)
m = n. (ii)
dt
i
= d
i
or dt
i
=
,1 ≤ i ≤ n. Condition (1) checks if e and t have the same
arity, whilst (2) tests if each non-wild-card field of t is equal to the corresponding
field of e.
Commonly the first field of a tuple is handled as a symbolic key identifying a
tuple subclass by using text strings or enumerated symbolic constant values.
3.2.2 The Operational Semantics
There is a set of operations that can be applied by processes, consisting of a
set of pure data-access operations treating tuples as passive data objects, and
operations treating tuples as some kind of active computational objects (more
precisely, data to be computed), offering Remote-Procedure-Call (RPC)
semantics.
out(e)
The execution of the output operation inserts the tuple e in the tuple
space. Multiple copies of the same tuple value can be inserted by
applying the output operation iteratively. The equal tuples cannot be
distinguished after insertion in the tuple space.
Examples:
out("Sensor",1,100);
out("Sensor",2,121);
ed dddd dv x== =
ρρ ρ
, with and :: | ; :: | |ε
tdt dtdtdtdt dtv xx== =⊥
υρυρυρ
, with and :: | ; :: | | | ?|ε
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.2 Tuple Space Communication 105
in(t)
The execution of the input operation removes one tuple e from the
tuple space matching the template t.
Examples:
in("Sensor",1,s1?);
in("Sensor",i?,s?);
rd(t)
The execution of the read operation returns a copy of one tuple e
matching the template t, but does not remove it.
Examples:
rd("Sensor",1,s1?);
rd("Sensor",i?,s?);
inp(t),rdp(t)
Non-blocking versions of the read and input operations, discussed in
the synchronization model of tuple spaces below. They can be used
to test and read/input a tuple.
Example:
res=inp("Sensor",1,s1?);
in?(tmo,t),rdp(tmo,t)
Not permanently blocking versions of the read and input operations,
discussed in the synchronization model of tuple spaces below. They
can be used to test and read/input a tuple.
Example:
res=in?(0,"Sensor",1,s1?);
eval()
This operation allows the injection of tuples that are currently not
fully evaluated using an extended functional tuple (with extended
dt::=v||x|f(x) with a function argument). This operation assumes a
function f(x) that is present in the processes participating in the tuple
space and accessible to the tuple space client implementation, which
cannot be related to the AAPL agent behaviour model.
Therefore, a different approach is applied. A partially (active) tuple,
which was stored in the tuple space by a client process, is consumed
by a service process that executes the function(s) f(x), finally replacing
the partial tuple with a fully evaluated tuple. For this purpose, the
process providing the service uses the listen function to receive evalu-
ation requests and the reply function to pass the evaluated tuple back
to the requesting process.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
106
Example:
P1:eval("square",2,y?)
P2:defsq=funx‐>x*x;
trans:=listen("square",x?,?);
y:=sq(x);
reply(trans,"square",x,y);
The listen function provides a transaction reference that can be used
by the reply function to address the destination of the tuple.
3.2.3 The Synchronization Model
There are producer (generator) and consumer processes. A producer gen-
erates a tuple that can be withdrawn by a consumer process. The tuple output
operation terminates immediately (asynchronous), alternatively after the
tuple was stored in the tuple space (synchronous). A consumer process is
blocked if the request cannot be serviced because there is actually no match-
ing tuple in the tuple space. After a matching tuple was stored in the tuple
space, it will be immediately assigned to one of the waiting consumer pro-
cesses. Therefore, the input operation is always synchronous. The only
exception are the not permanently locking versions, limiting the waiting to an
upper time bound (time-out).
There is no initial temporal ordering of producer and consumer operations.
This should be illustrated in the following example.
Ex. 3.1 Two producer and consumer processes performing multiple tuple space oper-
ations, and different possible tuple ordering outcomes
P1out(ADC1,50);out(ADC1,100);
P2in(ADC1,x?);in(ADC1,y?);
P1||P2P1||(P2{50/x,100/y)|
P2{100/x,50/y})
P1out(ADC,1,50);out(ADC,2,100);out(ADC,3,200)
P2in(ADC,,x?);in(ADC,,y?);
P1||P2P1||(P2{50/x,100/y)|P2{50/x,200/y}|
P2{200/x,100/y)|P2{200/x,50/y}|
P2{100/x,50/y)|P2{100/x,200/y})
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.3 Communication Signals 107
3.2.4 Distributed Tuple Spaces
Distribution of tuple spaces on different nodes implies synchronization
issues, requiring usually reliable group communication that cannot be
expected in technical sensing systems. Distribution of tuple spaces means the
distribution and asynchronous execution of a set of tuple space servers,
rather than one server. A tuple space server provides the necessary coordina-
tion for concurrent or interleaved in/out requests. Distribution of the servers
leads to a distribution of coordination. But this issue can be solved by parti-
tioning the tuple space in sub-spaces, as already introduced, and servicing
each sub-space on a different node by one server. Coordination takes only
place with tuples and templates of the same arity. A distributed search (of the
n-th dimension server) and retrieval is remaining. But this approach lacks of
sufficient "load" balancing because the tuples are usually not equally distrib-
uted with respect to their dimension. There are some work addressing the
distributed search and retrieval (e.g., [ATK08]).
3.2.5 Distribution by Mobile Agents
Keeping the mobile AAPL agent model in mind it is not required to imple-
ment distributed tuple-spaces for inter-agent communication. Distribution of
data is performed by the mobile agents themselves carrying data from one to
another processing node, each providing a tuple space.
3.2.6 Markings and Garbage Collection
Tuples are persistent and exist in a tuple space until a tuple is removed
explicitly. In the context of MAS this can cause to fill up of spaces with orphan
tuples. To avoid this space leak, tuples can be marked with a lifetime tag limit-
ing the existence of a tuple to specific time interval. A garbage collector can be
used to iteratively age these markings until they reach zero lifetime, finally
deleting these tuples. For this reason markings are called temporary tuples. A
marking is defined by the following generation rule.
3.3 Communication Signals
Signals are well-known asynchronous inter-process communication
objects. AAPL signals can be propagated between agents beyond the local
node scope, and can be considered as access paths to agents. Access paths in
the -calculus are mobile channel names, corresponding to the mobile AAPL
signals and agent identifiers, discussed in the next section.
md dddddvx===τετ,::|;::||,:
ρρ ρ
, with and timeout
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
108
3.4 Comparison: Signals and Tuples
Communication is central in large-scale distributed systems with a high
impact on the overall system performance and stability. Two main issues arise
affecting design considerations: 1. Efficiency of the communication with
respect to latency, computational complexity, and storage; 2. Addressing and
delivery of messages to destination entities. Efficiency is a key factor in self-
powered material-integrated low-resource computing networks. Commonly,
end-to-end communication is established between processes using IP proto-
cols and computer nodes having unique addresses, which is not suitable for
large-scale material-integrated networks and mobile agents. The agent model
usually announces autonomy and loosely coupling to the environment, thus
without a strong binding to a specific node. Moreover, there is usually no
global knowledge of the current position of an agent in the network at all.
Basically three approaches are available to exchange information between
agents: Tuple-space access, signal messages, and agent migration.
Tuple-Spaces
Tuple-space communication (see Figure 3.2 a) exchanges data tuples
between entities based on pattern matching, i.e., between processes and
agents. The information exchange is data-driven and bases on the data struc-
ture and content of the data, and do not require any destination addressing
or negotiation between communicating entities. Furthermore, tuple-space
communication is generative, i.e., the lifetime of data can exceeds the lifetime
of the producer. There are producer and consumer agents. A tuple-space can
be localized with a limited access region, commonly limiting data exchange to
entities executed on the same network node. Distributed tuple-spaces require
inter-node synchronization and base on replication and some kind of distrib-
uted memory model. The AAPL agent model originally uses tuple-spaces only
for agent communication executed on the same node.
Agent-to-Agent (A2A) Signals
Signals are lightweight messages that are delivered to specific agents
(Agent-to-Agent A2A, see Figure 3.2 b), in contrast to the anonymous tuple
exchange. One major issue in distributed MAS is remote agent communica-
tion between agents executed on different network nodes. Although an agent
can be addressed by a unique identifier, the path between a source and desti-
nation agent is initially unknown. For the sake of simplicity and efficiency,
routing table management and network exploration in advance is avoided.
Instead, the AAPL platforms (JAM/PAVM) support signal delivery along paths of
mobile agents only. That means, a signal from a source node A can only be
delivered to a destination agent currently on node B iff the destination agent
was executed (or created) on node A some time ago. I.e., two agents must
have been executed on the same node in the past. Agent migration and signal
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.4 Comparison: Signals and Tuples 109
propagation is recorded by the agent platform using look-up table caches
with time limited entries and garbage collection.
Agent-to-Node (A2N) Signals
Previous agent platform implementations only support signal delivery
along migration paths based on the destination agent identifier (private, uni-
cast) or the agent class (public, broadcast). The new JAM platform 2.0 (see
Chapter 8) introduces signal delivery of signals to specific remote platforms
(remote signalling) based on paths specified by the signal sender agent,
shown in Figure 3.2 (c). The destination platform node broadcasts the signal to
all listening agents executed on this particular node. To simulate private A2A
uni-cast (or multi-cast) communication, agents can use a randomly generated
signal name only known by the sender and the receiver. This new approach
enables interaction between agents never executed on the same node. Fur-
thermore, these remote signals are used to implement distributed tuple-
spaces, discussed later.
Mobile Agents
Mobile agents can be used to distribute information in networks. They can
get data/information from the tuple-space of the current node and store
them in remote tuple-spaces by migrating to the respective nodes. The advan-
tage of this approach is the ability to find suitable remote nodes and paths to
nodes autonomously or based on content negotiation, and to filter, map, or
process the collected data, e.g., using data fusion techniques. The disadvan-
tage is a high communication and processing overhead due to the agent
process migration.
Additionally, mobile agents can be used to deliver data in mobile network
environments by using a mobile device for spatial migration (piggyback
approach), not possible with A2A/A2N signals or remote tuples.
Distributed Tuple-Spaces
The new JAM platform 2.0 introduces the support for tuple migration using
the collect, copyto, and store operations performed by agents. This feature
enables the composition of distributed tuple-spaces controlled by agents. The
collect and copyto operations transfer tuples from the local tuple-space to a
remote using pattern matching, similar to the inp and rd operations. The
store operation sends a tuple to a remote tuple-space, similar to the out
operation.
Remote tuple space access is performed via A2N signals, shown in Figure
3.2 (d).
Evaluation
Figure 3.2 shows the analysis of simulation results as part of the use-case
study [[BOS17B] for different agent communication strategies. In this simula-
tion, sensor data derived from an artificial physical system, was distributed
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
110
event-based, leading to varying activity patterns depending on the dynamic
change of the mechanical structure under test within a given time window
(15000 MAS simulation steps with 100 physical simulation iterations).
Fig. 3.2 (Left) Agent communication in AAPL (a) Tuple-space communication between
agents on same node (b) Agent-to-Agent Signals (c) Remote Agent-to-Node Sig-
nals (d) Remote Tuple Operation (Right) Comparison of different approaches
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.5 Process Communication Calculus 111
The Multi-domain simulator SEJAM2P was used to perform the evaluation
and simulation providing real communication tracking (see Sec. 11.7).
Note: A simulation step usually executes one agent activity or signal han-
dler. The first approach uses mobile notification agents to distribute sensor
data to neighbour nodes (created on each event), which causes an up to 40
times higher communication cost compared with the other approaches. In the
second approach distributed notification agents are sent to neighbour nodes
one time, and using A2A signals to update sensor data on neighbour nodes
managed by the notification agents. The third approach uses remote tuple
access based on A2N signals, which causes the lowest communication cost
and do not require previous agent distribution.
3.5 Process Communication Calculus
The -Calculus introduced by Milner (1992) and the extended asynchronous
distributed -Calculus introduced by Hennessy [HEN07] (aD) are common
formal languages for concurrent and distributed systems, suitable for study-
ing the behaviour and reaction of distributed and concurrent systems
including dynamic changes caused by mobility. In the following subsection the
relationship of the AAPL/DATG behaviour and interaction model with the -
Calculus is pointed out, moving the view of point from spatially located agents
in a distributed interconnected system to one unified concurrent system with
dynamic virtual communication channels. The -Calculus used here extends
the -Calculus with the concept of (structural) domains, locations, resources
associated with domains and locations, and migration of processes, close to
the MAS paradigm, introduced in Section 2.8.
3.5.1 The -Calculus and Tuple-Spaces
The reduction of the tuple-space communication to the -Calculus using
communication channels is a non-trivial task. Since in this work communica-
tion is basically channel-based, rather than performed with distributed data
spaces, formal approaches like, for example, tKLAIM [NIC07], modelling tuple-
space interaction on an abstract level with (shared) data-based communica-
tion are not very well suited in a distributed system. The approach presented
in [BRA05] that extends the -Calculus with tuple-space operations and
semantics is better suited as a starting point (LinCa, formal language).
A communication channel in the -Calculus is shared by different agents
(processes), the producer and consumer of tuples, and the tuple-spaces
server, here represented by an agent-process, too. A polyadic channel has a
type signature T
1
,T
2
,.. and is characterized by a fixed arity. Tuples only con-
tain actual parameters, but template patterns contain formal and actual
parameters, which must be handled differently in a channel-based
interaction.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
112
In a distributed system a tuple-space TS is bound to a specific location l and/
or domain d. A first simplification is achieved by the decomposition of each
tuple-space TS in sub-spaces sorting tuples by their arity (number of fields),
i.e., TS
1
, TS
2
, .. , shown in Figure 3.3. This approach is also used for all agent
processing platforms proposed in this work. This can be done due to the fact
that tuples of different arities are always independent.
In the following let TS be a tuple space, e = d
1
; d
2
; ... ; d
n
TS is a tuple of
this space consisting of values d
i
, and t = dt
1
; dt
2
; ... ; dt
m
TP is a template
pattern, which is request specific. Each tuple field element d
i
is always a value
v, which can be calculated by an expression (containing variables). Each tem-
plate field element dt
i
is either a value (actual parameter v) or a variable
reference (formal parameter p). The type signature of a tuple is a type tuple of
the form Sig(e) = S
e
= T
1
; T
2
; ... ; T
n
. The type signature of a template pattern
must be extended with the parameter kind tag pk={t
v
, t
p
}, i.e., Sig(t) = S
t
=
T
1
:pk
1
; T
2
:pk
2
; ... ; T
m
:pk
m
. The type signature of a tuple leads to a further
decomposition of each n-ary subspace TS
n
in a set of subspaces {TS
n,S1
, TS
n,S2
,
..}, differing in the type signature S
i
of the tuples.
Keeping the partitioning of a tuple-space in n-ary sub-spaces ts in mind, all
processes storing tuples with a specific arity using the output operation can
use a shared communication channel. The tagged template type signature
prevents using a shared communication channel for the reading of tuples
based on templates pattern matching. More precisely, two different channels
are required, one forwarding the actual parameters of the template to the TD
i
server process, and one returning the values assigned to the formal parame-
ters of the template. Furthermore, such a channel pair is request specific, and
the channel pair must be created each time when data from the tuple-spaces
is requested. Figure 3.3 illustrates this effect for a tuple-space supporting
three-ary tuples.
In the following the modelling of the tuple-space operations, related to the
AAPL model that was introduced in Section 2.9, using the -calculus algebra is
shown, which was already introduced in Section 2.8.
Assume two agent processes PA
1
and PA
2
that exchange data by communi-
cating with a tuple-space server process PT
n
associated with a tuple-space
containing tuples having the signature Sig(ts
n
)=T
1
; T
2
; ... ; T
n
. Definition 3.2
shows the process notation for the tuple-space server. To satisfy the pro-
ducer-consumer synchronization and data consistency of the tuple-space only
one service request may be serviced at any time. This is ensured by the
sequential functional (recself(..);self). All tuples of a specific tuple-
space (the tuple set) are stored in a data list and modified by common list
operations (nil: () L, cons: E L L, head: L E, tail: L L, concat:L L L).
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.5 Process Communication Calculus 113
Fig. 3.3 The decomposition of tuple-spaces in subspaces (tuple domain TD
i
), each
managing tuples of a specific arity (i) and type signature. There are different
communication channels (CH
1
,CH
2
,..), one common for a specific tuple used
by producer, and multiple private channel pairs for different template signa-
tures used by consumer processes.
The ordering of lists is pointless for tuple-spaces. The server process binds
the data list variable el for storing tuples (in contrast, for example, in the Ker-
nel Language for Agents Interaction and Mobility KLAIM treating tuples as
processes). A server process has a global request channel req
i
bound to a
location l
j
.
A client (producer or consumer of tuples) sends a request over this channel.
The request channel is polyadic with four element fields: the operation type
from the set {IN, OUT, RD,..}, a tuple or template signature (specifying type and
kind of parameters), the data channel communicating the tuple or the actual
parameter of a template of the request, and the acknowledge channel used to
reply to the client process.
An output request receives the tuple from the data channel, stores the
tuple in the subspace list, and finally acknowledges the request, causing the
producer process to proceed (i.e., a process reduction occurs).
¢ ² /
¢ ²
¢ ²
¢ ²
¢ ²
¢ ²
¢ ²
¢ ²
¢ ²
¢ ²
¢ ²
¢ ² ¢ ²
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
114
An input request requires the splitting of the template pattern in the actual
and formal parameters. Therefore, the request must be processed accord-
ingly to the template signature, which is performed by matching the actual
signature type with possible type patterns, e.g., as shown in Figure 3.3. The
data channel only transmits the actual values of a pattern, finally expanded to
a search template pattern by using the expand function and the provided sig-
nature sig, replacing all formal parameters with wild-card symbols. The
acknowledge sent back to the consumer processes contains a collapsed tuple
consisting only of values for the formal parameters of the template pattern,
retrieved by the collapse function using one found tuple and the request
type signature. All tuples matching the search template pattern are filtered by
the filter function. If there was no matching tuple found, the request is sent
back (queued loop-back) to the server request channel (in the -callous the
server process can’t control the consumer process directly, only by preventing
the acknowledge message).
Def. 3.2 Server process at location l
i
servicing the tuple-space TS
i
(in
notation using
channels)
(newreq
i
@l
j
)
Serv
i
(req
i
)@l
j
(newel:T
1
; T
2
; ... ; T
n
list)
recself
(newop,sig,data
,ack)
req
i
?(op,sig,data,ack).
(matchreqwith
OUT:
(newe)data
?(e).elcons(e,el);ack!()
IN,RD:
matchsigwith
sig1:
(newt
1
:T
1
)data?(t
1
).
(news)sfilter(el,expand(t
1
,sig))
ifsnilthen(
(newx)xhead(s)
ifreq=INthen(elremove(el,x))
ack
!<collapse(x,sig)>
)else(req
i
!<op,sig,data,ack>)
sig2:
(newt
2
:T
1
; T
2
)data?(t
2
).
(news)sfilter(el,expand(t
2
,sig))
ifsnilthen(
(newx)xhead(s)
ifreq=INthen(elremove(el,x))
ack
!<collapse(x,sig)>
)else(req
i
!<op,sig,data,ack>)
..
);self
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.5 Process Communication Calculus 115
The client process notation and transformation for the output and input
tuple-space operations and the usage of the three communication channels
involved in each request is shown in Equations 3.1 and 3.2.
(3.1)
(3.2)
A tuple-space is bound to a specific location, here the network node. Two
processes PA
1
and PA
2
can only synchronize and exchange a tuple (assuming
match(e,t)=true) if they access the same tuple-space TS@l at the same location
l, shown by the following reduction rules.
(3.3)
Up to here it is assumed that producer and consumer processes (P
p
, P
c
)
exist during the exchange of tuples. But tuples are persistent and not requir-
ing the existence of the producer process after it has generated a tuple.
The lifetime of the tuple T is independent of the lifetime of the producer
process P
p
. For this reason, the tuple exchange requires the tuple-space
server process P
s
and tuples cannot be exchanged directly by producer and
consumer processes using channels if the producer process does not exist,
though this approach would be natural and a significant simplification. Also, if
tuples are represented by communicating processes themselves (as proposed
in [NIC96] and [NIC98]), producer-tuple and tuple-consumer communication
cannot be performed by using channels without the presence of a coordina-
tion server if the consumer request happened before the producer generates
a matching tuple. The different cases with and without a server are illustrated
in Figure 3.4.
out( , ,..)@
(new , ) ,
vv l
ch ch req l ch ch ch
da i da d
12
( @ !<OUT, > . !<
)
vvv ch
a12
, ,..>) || ?() . P
in t l t v x v x
ch ch
req l
da
i
( )@ ( , ?, , ?,..)
(new , )
(
with
@!<IN
=
11 22
)
,,Sig( ), > . !< >) ||
?( , ..) . P
tchch ch vv
ch x x
da d
a
,,,..
,
12
12
out( )@ || in( )@ out( )@ @ || in( )@elPl tlQl
PQ
elPl t
11 111
.@ .@
||
. llQ l
Pl t lQl
22
1122
.
.
@
@ || in( )@ @
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
116
Fig. 3.4 Different producer-consumer situations with and without a coordinating
tuple-space server [(a) with server, (b) process-to-process, (c) tuples as
processes).
Another issue arise with tuple exchanges without a coordination server if
there are multiple originally independent tuples matches an input request,
which cannot be handled in the cases (b) and (c) in Figure 3.4. At least the cou-
pling of tuple processes is required to coordinate template matching and
scheduling.
3.5.2 The -Calculus and Signals
The AAPL signals can be sent from one agent Ag
n
to another Ag
m
(peer-to-
peer, peer-to-group, or bounded broadcast). A signal can be considered as
being a communication channel connecting two agent processes. A signal
handler of an agent is related to a separate process operating concurrently to
the parent agent process. But there is no direct synchronization between the
parent and signal handler process. Only the shared agent body variables are
used to communicate data, basically not part of the CSP and -Calculus. Usu-
ally an ATG transition is blocked until a Boolean condition expression
containing body variables is true. This transition blocking can be modelled
with a channel communication, too, as well as the signal propagation itself.
The mapping of AAPL signal propagation and handling on the -calculus is
shown in Definition 3.3.
Producer Pp
Server Ps
Consumer Pc
d
d
(a)
Producer Pp
Consumer Pc
d
(b)
Producer Pp
Tuple Ps
Consumer Pc
d
d
(c)
Consumer Pc
d
Time t
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.6 FIPA ACL 117
Def. 3.3 Mapping of AAPL signal propagation and handler on the
-calculus (c: condi-
tional Boolean expression)
AAPL
Agt
a
:
A
i
A
j
:c(v
1
,v
2
,..,v
n
)
handlerS(arg)=..v
i
;..
Agt
b
:
send(Agt
i
,S,va)
‐Calculus
P
a,i,wait
recpifnotc(..)then(event
a
?().p)
P
a,i
P
a,i,comp1
.P
a,i,wait
.P
a,i,trans,j
H
a
rechS
a
?(arg).v
i
;event
a
!();h
P
b
S
a
!<arg>
3.6 FIPA ACL
Agent communication can be achieved basically by three different meth-
ods: 1. Signal propagation (similar to commitment messages in AGENT0,
[SHO91]), 2. Tuple database exchange, and 3. Using agents with a composition
of methods 1 & 2. These basic methods can be used to realize common
higher-level agent communication languages like ACL or KQML (tuple patterns
correspond to message content entries). Signal propagation implements light-
weighted asynchronous peer-to-peer Remote-Procedure calls, executed on
target agents with appropriate signal handlers, which must not necessarily
belong to the same agent class, whereas pattern matching based tuple data-
base access can be performed by any group of agents having a common
understanding of the meaning of data and which are actually processed on
the same platform node.
For example, a simple FIPA ACL based request from agent A (initiator) to B
(participant), which ask for a database tuple on B can be created with the fol-
lowing AAPL code pattern using signals, shown in Example 3.2.
Ex. 3.2 FIPA ACL and AAPL
FIPAACL
(request:senderIDA
:receiverIDB:content(p?):ontologyTS2)
AAPL
:{REQ1,REQ2,INFR,FAIL}
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
118
:{COMERR}
AgentA
:{pv,ps}
INFR:v{
pvv;
pstrue;
wakeup
}
FAIL:{
psfalse;
wakeup
}
request:(AID,p){
REQ1(p)AID;+(100,FAIL);
sleep
ifpsthenpvelseCOMERRend
}
AgentB
REQ1:arg
:{v}
if
?
(p,?)then
‐
(p,?v)
INFR(v)$sender
elseFAIL$sender...
3.7 AAPL Agents and Capability-based Remote Procedure
Calls
One common inter-process communication model is the Remote-Proce-
dure call paradigm, performed by clients and servers, though the roles can be
fully interchanged, i.e., a server can be a client if the server requests a proce-
dure execution on another server.
Considering the well-known capability-based Amoeba RPC interface
[MUL90], shown in Definition 3.4, this procedural RPC programming interface
can be easily mapped on the AAPL agent model, discussed later.
Def. 3.4 Simplified and abstracted Amoeba RPC interface using capabilities [ai: Argu-
ment, xi?: parameter replaced with argument values]
Capability
typecapability=(port:bytes[6],obj:bytes[4],
rights:byte,priv:byte[6])
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.7 AAPL Agents and Capability-based Remote Procedure Calls 119
Client
stat:=trans(cap,a1,a2,..,x1?,x2?,x3?,..)
Server
loop
getreq(port,a1?,a2?,...)
compute
putrep(port,x1,x2,..)
The server resources are specified with capabilities. A capability therefore
holds the server port and additional information about the object. The entries
have the following meaning:
port (P1..P6)
The public server port (6 bytes),
obj (O)
The object number given by the server (4 bytes). It is a unique server inter-
nal identification number of this object,
rights (R)
The rights mask (1 byte) determines the allowed access rights of an object,
like the permission to destroy an object. Each bit in the rights field specifies
one possible access right. The meaning of each bit is dependent of the serv-
er and the kind of the object.
priv (S1..S6)
The security private port (6 bytes). This port protects the rights field against
manipulation.
The rights protection port contains the rights field that is created by a one-
way encoding function fc from a private check port C randomly created by the
server only for this object and the rights field. A restricted capability CAP’ is
build from an original one by restricting the rights field and creating a new
security port using an encode function pc. This function simply calculates the
new security port S’ from the private check port C and the rights field R using a
logical XOR operation and feeds the result to a one-way function Fc, as shown
in Equation 3.4. Each time a server receives a message it checks the security
port using his private check port C and a decode function pd. This function
simply builds the expected security port S’ from the rights field specified in the
received capability and the check port C and compares S’ with the supplied S
port. If they are unequal, the capability was manipulated and will be rejected.
(3.4)
SFcS R’ ( xor )=
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
120
A server uses a getreq function to wait for the arrival of client request
matching the server port. A client transaction using the trans function is syn-
chronous and waits for the reply, send by the server using the putrep
function (see Figure 3.5, left side).
DNS: Capability-Name Mapping. Capabilities are not initially associated with a
name. A hierarchical directory based approach can be used to associate a set
of capability {C
1
(P,O,R
1
,S
1
), C
1
(P,O,R
2
,S
2
), ..} with a set of names N={n
1
,n
2
,..}, ref-
erencing the same object and server. A directory is a (name,capability) table
with its own object capability that is managed by a Directory Name Server
(DNS, see Figure 3.5, right side).
This RPC interface can be implemented with mobile client and server agents
as subclasses that are forked from a root agent class, implementing some
specific agent behaviour, shown in Algorithm 3.1. The RPC extension allows
different forked child agents to execute activities of other child agents (the
servers), which may me mobile, too. If the server and clients belong to the
same root agent (children), the above security handling can be omitted, and
the client-server transaction can always be trusted.
Each time an agent (of the root class ac) wants to execute a RPC on a
remote (or local) agent, it creates (forks) a transaction agent. The transaction
agent inherits the current set of arguments {a
1
, a
2
,..} and the target server
port capability cap. Before the transaction agent can interact with the server
agent, it must locate the server owning the server port cap.port.
Fig. 3.5 Amoeba RPC (left) and Directory Capability Name Service (right)
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.7 AAPL Agents and Capability-based Remote Procedure Calls 121
Fig. 3.6 RPC server search with a distributed MAS [C: Client agent, T: Transaction agent
(red: search agent), S: Server agent]
The search of the server is performed with a divide-and-conquer approach,
similar to the explorer SoS that will be introduced in Section 9.2, shown in Fig-
ure 3.6.
The server search is performed in the lookup activity. If the server is not
existing on the current node, forked transaction search agents will explore the
neighbourhood, and in the case one agent found the server port, it will deliver
the relative distance information back to the waiting transaction agent, per-
formed by the iamhere activity.
The location information (dx0, dy0) will be published in the local tuple data-
base (acting as a cache) and during back propagation on each node along the
back path.
The original transaction agent forks and sent out the child search agents in
all reachable directions in the lookup activity. Each child agent moves to the
specified neighbour node. The created child search agents perform a transi-
tion to the iamhere activity if they found the server. If the server was not
found, it will fork and sent out more agents in all directions excluding its own
forward and backward direction. If a search agent finds the server, it will go
back to its origin and notifies the original transaction agent (iamhere activity).
If the search of the server location was successful, the transaction migrates
to the server place and performs the transaction. To ensure that the server
agent is not migrated in the meantime, the server port is checked again. If the
server is gone, the transaction fails (and the agent dies) After the transaction
is finished, it moves back to the root place and delivers the data to the parent
agent though the tuple-space.
C
S
TTT
T
T
T
T
T
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
122
The previously introduced RPC client-server agent subclasses as part of an
application agent class can alternatively be embedded in their own RPC root
class.
Alg. 3.1 AAPL RPC Implementation with mobile client and non-mobile server agents,
both embedded as subclasses in a root class
1 someagentclass:(dir,radius){
2 Cap:(port:natural,obj:natural)
3 :{cap,req,a1,a2,..,x1,x2,...
4 :{IAMHERE}
5 ..
6 inbound:(nextdir){
7 casenextdirof
8 |NORTHdy>‐radius
9 |SOUTHdy<radius
10 |WESTdx>‐radius
11 |EASTdx<
radius
12 }
13
14 init:{
15 port{1..nmax}mustbepublicintherootclass
16 }
17
18
client:{
19 req<‐{1..nmax}
20 out(TRANS1,cap.port,cap.obj,req,a1,a2,..)superfluous,
21 forkedagentinheritsallarguments
22
ac.trans(ORIGIN,4)
23 stat
‐?
(1sec,TRANS2,cap.port,req,x1?,x2?,..)
24 }
25
26
trans:{
27 a1,a2,..,x1,x2,...
28 :{transid,dx,dy,dx0,dy0,cap:Cap}
29 :{port,req,obj,priv,found}
30
31 init:{
32 foundfalse
33 transid$self
34
‐
(TRAN1,port,obj,req,a1?,a2?,..)superfluous,forkedagent
35 inheritsallarguments
36 }
37
38 lookup:{
39 checkfordesiredserverport
40 if
?
(CAP,cap.port,?,?)then
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.7 AAPL Agents and Capability-based Remote Procedure Calls 123
41
%
(CAP,cap.port,dx0?,dy0?)
42 if(dx,dy)(0,0)then
43 remotelookup,deliverportlocationtowaitingtransagent
44 incr(dx0,dx);
45 incr(dy0,dy)
46 *(lookup,iamhere)
47 else
48 clientandserverhavesamelocation,starttransition..
49 foundtrue
50 else
51 if(dx,dy)=(0,0)then
52 thisistheinitialtranstionagent,fork
searchagents..
53 *(lookup,move)
54 {nextdir|?(nextdir)}do
55
ac.trans(nextdir,radius)
56 *(lookup,move,found=true)
57 *(move,putreq)
58 else
59 thisisalreadyasearchagent,forkmoresearchagents..
60 {nextdir|nextdirdir&
61 nextdir(dir)&
62 ?(nextdir)}do
63
ac.trans(nextdir,radius)
64
65 }
66
67 iamhere:{
68
+
(CAP,cap.port,dx0‐dx,dy0‐dy)
69 |ifdy>0thendecr(dy);(SOUTH)
70 |ifdy<0thenincr(dy);(NORTH)
71 |ifdx>0thendecr(dx);(WEST)
72 |ifdx<0thenincr(dx);(EAST)
73 |if(dx,dy)=(0,0)thenIMAHREtransid
74 }
75
76 putreq:{
77 if
?
(CAP,cap.port,0,0)then
78
+
(CAP,cap.port,req,cap.obj,a1,a2,..)
79 else
($self)destroythisagent,serverisgone
80 }
81
82 getrep:{
83
‐
(REP,cap.port,req,,x1?,x2?,..)
84 }
85
86 move:{
87 ifinbound(dir)then
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
124
88 (dx,dy)(dx,dy)+(dir)
89 (dir)
90 else
($self)destroythisagent,servernotfound
91 }
92
93 deliver:{
94 |ifdy>0thendecr(dy);(SOUTH)
95 |ifdy<0thenincr(dy);(NORTH)
96 |ifdx>0thendecr(dx);(WEST)
97 |ifdx<0thenincr(dx);(EAST)
98 |if
(dx,dy)=(0,0)then
99
+
(TRANS2,cap.port,req,x1,x2,..)
100
($self)
101 }
102
103 IMAHRE:{
104 foundtrue
105 }
106
107 :{
108 initlookup
109 lookupmove|found
110 imahereiamhere|(dx,dy)(0,0)
111 getrepdeliver
112 deliverdeliver|(dx,dy)(0,0)
113 }
114 }
115
116
server:{
117 init:{
118
+
(CAP,port,0,0)
119 }
120 getreq:{
121
‐
(REQ,port,req?,obj?,a1,a2,..)
122 }
123 service:{
124 computef:(a1,a2,..)(x1,x2,..)
125 }
126 putrep:{
127
+
(REP,port,req,x1,x2,..)
128 }
129 :{
130 getreqservice
131 serviceputrep
132 putrepgetreq
133 }
134 }
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
3.8 Further Reading 125
One disadvantage of tuple spaces introduced so far is related to the flat
organisation model of a tuple space, compared, for example, with tree based
directory organisation providing hierarchy and path references of objects
(data or directories). Actually tuples are only matched by their dimension and
template equivalence.
The capability concept can be extended to tuple spaces in such a way that a
tuple space and a tuple server is associated with a capability. An eventually
distributed (replicated) directory service organizes tuple spaces hierarchical
with trees. Nodes offering tuple spaces can publish the capability in a direc-
tory, which can now be referenced by a textual path, easing the selection of
tuple spaces. This extends the tuple space operations in/out/rd (..) with an
extra argument, the server capability.
3.8 Further Reading
1. R. Milner, The space and motion of communicating agents. Cambridge
University Press, 2009.
2. M. Hennessy, A Distributed PI-Calculus. Cambridge University Press,
2007.
3. R. Bordini, J. Hübner, and M. Wooldridge, Programming multi-agent
systems in AgentSpeak using Jason. 2007.
4. M. Schumacher, Objective Coordination in Multi-Agent System Engi-
neering. Springer Berlin, 2001.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 3. Agent Communication
126
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
