C Verhoef
email: c.g.verhoef@cwi.nl.

C Krause

O Kanters

R Van Der Mei

Simulation-Based Performance Analysis of Channel-Based Coordination Models

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Non-functional requirements, such as reliability, security and performance are becoming of increasing importance in many branches of component-based and service-oriented software engineering. Particularly the quantitative aspects inherent in the performance evaluation of composite and distributed systems introduce major challenges. Even if the quality of service (QoS) properties of every individual service and connection is known, it is far from trivial to reason about the end-to-end QoS of the composed system. This is due to the fact that synchronization constraints as well as buffering and routing policies between the different parties in a network can have an impact not only on its qualitative behavioral properties, but also on its overall performance. In the worst case, a 'bad' performance, e.g. if a service takes too long to respond to a request, can even have an influence on the functional properties of the system. However, in this paper we consider rather typical questions of performance evaluation, such as: Where are the bottlenecks in the network? What is the expected delay and the maximum throughput? How much time does it take until a certain event happens? What is the expected utilization of a buffer? Building software compositionally out of a set of primitive components or services is a key task in software engineering in general. The coordination paradigm provides concepts to properly describe the allowed interactions between the active entities in a system. A specific coordination approach is considered in the channel-based coordination language Reo [START_REF] Arbab | Reo: A channel-based coordination model for component composition[END_REF], in which compositionally built components connectors are used as coordination artifacts. Connectors in Reo can be seen as a kind of 'glue code' which coordinate the interactions among a set of components or services from outside. To enable performance evaluation of component connectors, Stochastic Reo [START_REF] Arbab | From coordination to stochastic models of QoS[END_REF] provides an extension that allows to annotate connectors with stochastic performance properties. Specifically, communication channels in Stochastic Reo are annotated with processing delays. Moreover, to reason about the end-to-end QoS of a connector, its boundary nodes are annotated with data arrival rates, modeling the interaction with its environment. In this way, Stochastic Reo provides detailed information about the performance of the primitive buildings blocks on the one hand, and the external world on the other.

The existing techniques for performance evaluation in Stochastic Reo are all based on analytical methods and essentially follow the same recipe. An automata-based model is used to describe the semantics of every primitive channel in a connector. By composing all these automata, a behavioral model for the whole connector is built. Then, using the stochastic annotations of the channels and boundary nodes, a probabilistic performance model, specifically: a continuous-time Markov chain is generated. Finally, the Markov model is fed into a tool for probabilistic analysis, such as PRISM [START_REF] Kwiatkowska | PRISM: Probabilistic Symbolic Model Checker[END_REF] or Matlab. This approach was taken in [START_REF] Arbab | Component connectors with QoS guarantees[END_REF] using Quantitative Constraint Automata (QCA), in [START_REF] Arbab | From coordination to stochastic models of QoS[END_REF] using Quantitative Intentional Automata (QIA) and in [START_REF] Moon | A compositional semantics for stochastic Reo connectors[END_REF] using Stochastic Reo Automata (SRA). An implementation of the QIA-based approach is described in [START_REF] Arbab | Reo2MC: a tool chain for perf. anal. of coordination models[END_REF]. However, all of these approaches to performance evaluation in Reo have two main limitations: (i) they are all restricted to the use of exponential distributions, and (ii) they suffer from the state space explosion problem, because the automaton / continuous-time Markov chain for the whole system has to be computed in advance.

Complementary to the existing analytical methods, we consider a simulation approach for performance analysis in Stochastic Reo, which enables the use of arbitrary (not just exponential) distributions for describing stochastic properties of channels and components. Our approach is based on the coloring semantics [START_REF] Clarke | Connector colouring I: Synchronisation and context dependency[END_REF] of Reo, which enables a step-wise execution scheme (cf. [START_REF] Proença | Deployment of Distributed Component Based Systems[END_REF]). Thus, state spaces can be generated on-the-fly during the simulation without requiring to keep track of the execution history. Therefore, our approach scales much better than the existing automata-based techniques, which require to compute the whole state space before the actual analysis starts. The coloring semantics which we use in our approach, supports context-dependent primitives, such as the LossySync channel (cf. [START_REF] Clarke | Connector colouring I: Synchronisation and context dependency[END_REF]). Moreover, it allows to model the availability of I/O requests at the boundary of a connector, which is a key ingredient to reason about the end-to-end performance of a connector.

We have implemented our simulation approach for Reo in a sophisticated graphical tool, as part of the Eclipse Coordination Tools (ECT) [START_REF]ECT: Eclipse Coordination Tools[END_REF]. Connectors can be specified using a graphical editor in ECT. By annotating these graphical connector models with stochastic information, our simulator generates a large number of performance statistics. Our tool supports both steady-state and transient analysis and can be applied to connectors built using all standard and even user-defined Reo channels. To analyze specific behaviors of the modeled system, a number of tools are available to the user, such as automatic deadlock and livelock detection, visualization of the connector colorings, and charts for the behavior of simulation results during the simulation. Various stopping conditions can be specified for the simulation. Our simulator generates a number of statistical outputs depending on the chosen type of simulation, for an overview we refer to Section 4.1.

Related work.

Model-based methodologies to assess performance of distributed software systems can be categorized [START_REF] Gijsen | An Integrated Performance Modeling Approach for Distributed Applications and ICT Systems[END_REF] in: queuing networks, state/transitionbased analysis, and software performance engineering. A survey of the available results in the theory of queuing networks is given in [START_REF] Boxma | Sojourn times in queueing networks[END_REF]. The Method of Layers in [START_REF] Rolia | The method of layers[END_REF], models the responsiveness of composite services using closed queuing networks using Mean Value Analysis. Stochastic rendezvous networks are introduced in [START_REF] Woodside | The stochastic rendezvous network model for performance of synchronous client-server-like distributed software[END_REF] for performance evaluation of distributed systems with synchronization. Software Performance Engineering is suggested in [START_REF] Smith | Performance Engineering of Software Systems[END_REF] to enable the integration of performance analysis into the software development process. Simulation of stochastic graph transformation systems is described in [START_REF] Torrini | Stochastic simulation of graph transformation systems[END_REF]. In [START_REF] Ledeczi | Modeling methodology for integrated simulation of embedded systems[END_REF] a methodology for simulation of embedded systems is presented. Yacoub et al. [START_REF] Yacoub | A scenario-based reliability anal. approach for component-based software[END_REF] focus on reliability analysis for component-based systems. In [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF] a reasoning technology to simulate and verify pure Web services is defined. In [START_REF] Ajmone Marsan | A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems[END_REF] Generalized Stochastic Petri Nets (GSPN) are proposed for performance analysis of multiprocessor systems. Performance evaluation is done by generating continuous-time Markov chains [START_REF]Performability Modelling: Techniques and Tools[END_REF]. Haas provides an overview of simulation techniques for GSPNs [START_REF] Haas | Stochastic petri nets: Modelling, stability, simulation[END_REF]. GreatSPN is a simulation tool for performance evaluation of distributed systems using GSPNs [START_REF] Chiola | GreatSPN 1.7: graphical editor and analyzer for timed and SPNs[END_REF]. Compared to GSPNs, Reo has a strong notion of synchronization, which, just like the notion of context dependency, propagates through connectors, both not supported by GSPNs. Due to this, traditionally automata based models are used as semantical models for Reo.

Acknowledgments. We are grateful to Farhad Arbab and anonymous reviewers for their insightful comments.

Organization. Section 2 gives a brief overview of (Stochastic) Reo. We define the operational semantics underlying our simulation and introduce our transition system in Section 3. In Section 4 we present our simulation-based stochastic analysis procedure. Our simulation tool is described in Section 5. We present two case studies in Section 6. Section 7 contains conclusions and future work.

Channel-based coordination with Reo

The simulation approach we present here targets the channel-based coordination language Reo [START_REF] Arbab | Reo: A channel-based coordination model for component composition[END_REF]. Channels in Reo are entities that have exactly two ends, which can be either source or sink ends. Source ends accept data into, and sink ends dispense data out of their channel. Reo allows directed channels as well as drain and spout channels, which have respectively two source and two sink ends. Channels may impose constraints on the dataflow at their ends. For instance, the communication through channels can be (a)synchronous and (un)buffered.

For the scope of this paper, we consider a fixed set of channels, summarized in Table 1. The Sync channel consumes data items at its source end and dispenses them at its sink end. The I/O operations are performed synchronously and without any buffering. Thus, the channel blocks if the party at the sink end is not ready to receive data. The LossySync channel behaves in the same way, except that it does not block the party at its source end. Instead, the data item is consumed and destroyed by the channel if the receiver is not ready to accept it. The SyncDrain channel is also synchronous, but it differs in the fact that it has two source ends through which it consumes and destroys data items synchronously. The FIFO channel is a directed, asynchronous channel with a buffer of size one.

Sync

LossySync SyncDrain FIFO Table 1. Some basic Reo channels Channels in Reo can be joined together using nodes, which read data items from sink ends and write data items to source ends of channels that coincide in it. Nodes in Reo behave as non-deterministic mergers on the sink ends and as (synchronous) replicators on the source ends. This means that a node nondeterministically reads a data item from one of the incoming sink ends and replicates it to all outgoing source ends without buffering it.

Building connectors

In Reo, channels and nodes are joined together to build so-called connectors which resemble electronic circuits. These connectors are used as glue code between components or services and essentially enforce a communication protocol between them. This coordination of components or services is performed from outside and without their knowledge, which is also referred to as exogenous coordination.

An important aspect of Reo is the fact that nodes do not buffer data items and therefore allow synchrony to propagate through the connector. For instance, a sequence of n Sync channels joined together using nodes has the same qualitative behavior as a single Sync. Note also that Reo allows an arbitrary mixing of synchrony and asynchrony.

Example 1. We consider a simple instant messenger application, depicted in Fig. 1. Two Client components exchange messages via a connector. Messages are exchanged via FIFO channels and are, thus, buffered. When leaving the buffer again, the messages are synchronously replicated by the node behind the FIFO and sent to both clients. This can succeed only when both clients are ready to accept data, i.e. when there are pending read requests at both in ports. In a nutshell, this connector ensures that the clients get -as an acknowledgment-a copy of their own message when the other client has successfully received it.

Stochastic Reo

Stochastic Reo is an extension of Reo annotated with stochastic properties. In particular, we distinguish between the following two quantitative aspects in Reo:

-Channel delays: Every channel has one or more associated delays represented by a set of random variables. Such a delay models how long it takes for a channel to transfer or process a data item. For instance, a LossySync A→B has two associated delays 'dAB ' and 'dALost', respectively for successful dataflow through the channel, and losing data in the channel if B is not ready to receive data. A FIFO A→B has two associated delays: 'dAF ' and 'dFB '. The former represents the delay for the dataflow from A into the buffer. The latter models the dataflow out of the channel. Sync and SyncDrain channels have only one delay, i.e., for successful dataflow. -Arrivals at nodes: I/O operations are performed at the boundary nodes of a connector through which it interacts with its environment (depicted as empty circles). We assume the time between consecutive arrivals of read and write requests at the boundary nodes depends on their associated stochastic processes. For instance, 'dA' and 'dB ' in the connector in Fig. 1 represent the associated arrival processes of nodes A and B. Furthermore, at most one request at each boundary node can wait for acceptance. If a boundary node is occupied by a pending request, then the node is blocked and consequently all further arrivals at that node are lost.

Note that arrivals at nodes are considered only for boundary nodes, e.g. A, B, C, D, but not X, Y in Fig. 2. Internal nodes are used for synchronous dataflow only and merely pump data in the connector, without interaction with the environment. Therefore, internal nodes have neither an associated arrival rate, nor a delay.

Distributions

In our simulation approach and particularly in the simulation tool which we present in Section 5, we support a number of distribution types, some of them being general stochastic distributions, while others being special constructs for steering the simulation process. The types of supported distributions and their parameters are listed in Table 2. The value after the parameters between the brackets indicates the type of the parameter, where b = Boolean, i = integer, r = real, and s = string.

Distribution Param 1 Param 2 Param 3 Beta α (r) β (r) Binomial n (i) p (r) Chi 2 k (i) Constant (Con) value (r) Exponential (Exp) λ (r) F d1 (r) d2 (r) Gamma k (r) Lognormal µ (r) θ (r) Poisson λ (r) Triangular (Tri) low (r) high (r) avg (r) Uniform low (r) high (r) Weibull k (r) IfNeeded Always Trace path (s) loop (b)
- FIFOD→Y Exp(2) Con(0) Sync Y →B Con(0) - Sync X→B Exp(1) - Sync Y →C Exp(2) - Table 3. Example channel delays Node Arrivals A Exp(1) B Exp(10) C Exp(1/2) D Exp(1/8)
Table 4. Example node arrival rates Example 2. For the instant messenger example, we consider the channel delay and node arrival parameters chosen such that analysis is not trivial, given in Table 3 and 4, respectively. We assume exponential distributions for the request arrivals at all boundary nodes and for most of the channel delays. However, we assume that the dataflow between the buffer of FIFO D→Y to the boundary node B can be performed without any delay (Con(0)). Moreover, the delay of Sync X→C is approximated using a triangular distribution.

Coloring semantics with states

In our simulation approach, we use the so-called coloring semantics [START_REF] Clarke | Connector colouring I: Synchronisation and context dependency[END_REF] of Reo, introduced by Clarke et al. to properly model context-dependent behavior as required for instance for the LossySync channel. The basic idea of the coloring semantics is to associate flow and no-flow colors to channel ends. As shown in [START_REF] Clarke | Connector colouring I: Synchronisation and context dependency[END_REF] one flow and two no-flow colors are sufficient to model context-dependency. Essentially, the two different no-flow colors are used to distinguish between absence and presence of an I/O request. Table 5 depicts the names and graphical notations of the flow and the two no-flow colors, as used in this paper.

(S2) (S3) (S4) (M1) (M2) (M3) (M4)
Table 6. Example colorings

The color flow represents ordinary dataflow at a channel end. The two noflow colors are used to encode a direction of the reason for the fact that no dataflow is possible. Intuitively, no-flow-provide-reason models the fact that the receiving or sending party is not ready to perform an I/O operation. Conversely, no-flow-require-reason says that the party is ready to receive or send data, but is not allowed to perform the operation. At the boundary of a connector, the two no-flow colors can be interpreted as lack of dataflow -either because of a missing, or in spite of a present I/O request.

Valid behaviors of channels are described as colorings of their respective ends. Table 6 depicts the colorings of the Sync the Merger primitive. The latter is used for modeling nodes in Reo. For the colorings of other primitives such as the FIFO channel we refer to [START_REF] Clarke | Connector colouring I: Synchronisation and context dependency[END_REF]. Note that the colors are always read from the perspective of the primitive. For instance, in coloring (S2) of the Sync the party at the right end provides a reason for no flow, whereas the source end on the left requires a reason. This models the behavior where data is available at the source end but the receiver at the sink end is not ready to accept data. Similarly, in coloring (S3) there is no flow, because there is no data available at the source end. Finally, coloring (S4) models the situation where no data is available and the receiver is also not ready to accept any data. Similarly, the colorings of the Merger primitive in Table 5 show the valid dataflows through sink nodes and how reasons for no dataflow are being propagated.

Valid colorings of primitives are joined together and give rise to valid colorings of the whole connector (see [START_REF] Clarke | Connector colouring I: Synchronisation and context dependency[END_REF] for details).

Example 3. Fig. 2 depicts an example coloring of the instant messenger application. The coloring is based on the following state of the connector: FIFO A→X is full, FIFO D→Y is empty, there are read requests at the boundary nodes B and C, and no write requests at A and D. This particular coloring models a dataflow action from the full FIFO A→X to both clients, i.e., a synchronized message delivery and acknowledgment.

Fig. 2. A coloring of the instant messenger application

Coloring transition system

Colorings describe only dataflow events, but not the state of primitives or the whole connector. Therefore, we now incorporate a notion of state into the coloring model, which gives rise to a transition structure defined in the following. Let Color be a fixed set of flow colors, as defined in Table 5.

Definition 1 (coloring transition system). A coloring transition system C = (N, B, Q, =⇒) consists of a set of nodes N , a set of boundary nodes B ⊆ N , a set of states Q and a set of coloring transitions =⇒ ⊆ Q × Color N × Q.

We often write q =⇒ c q for a transition where c ∈ Color N is a coloring. Colorings model dataflows, which is why we also refer to transitions as dataflow transitions or just dataflows.

However, this model does not reflect the interaction of the connector with its environment. Specifically, boundary nodes receive requests from their components. Therefore, we model the state of boundary nodes explicitly as:

-States = {empty, waiting, busy} A boundary node is empty when there is no I/O request pending, waiting when the node received an I/O request pending for processing, and busy when it is sending or receiving data. We model the state change of boundary nodes on request arrivals using the map Arrival : States → States defined as follows:

-Arrival = {empty → waiting, waiting → waiting, busy → busy} In the following, we relate the state of the boundary nodes with the coloring semantics. Specifically, we define a transition structure where colorings are being enabled based on the presence/absence of requests. Moreover, we model the start and the end of dataflows as distinct events. This is important to measure, e.g., the duration of dataflows and the waiting time of requests at boundary nodes.

Definition 2 (induced intensional coloring transition system). Given a coloring transition system C = (N, B, Q, =⇒). The induced intensional coloring transition system is a tuple C = (Q, →, start =⇒, end =⇒) where:

-Q = Q × States B × 2 is a set of states where a state q ∈ Q consists of a state q • ∈ Q together with (q n ) n∈B ∈ States B and q ∼ ∈ {true, false} -→ ⊆ Q × B × Q is a set of request arrival transitions - start =⇒, end =⇒ ⊆ Q × Color N × Q are sets

of dataflow start and end transitions

where the transition relations are defined by the following rules:

∃n ∈ B : q n = Arrival (q n ) ∀m = n ∈ B : q m = q m q • = q • q ∼ = q ∼ q → n q (1) q • =⇒ c q • q ∼ = false ∀n ∈ B : q ∼ = true c(n) = ⇒ q n = q n = empty c(n) = ⇒ q n = q n = waiting c(n) = ⇒ q n = waiting ∧ q n = busy q start =⇒ c q
(2)

q ∼ = true p start =⇒ c p → * q q ∼ = false ∀n ∈ B : q n = busy ⇔ q n = empty q n = busy ⇔ q n = q n q end =⇒ c q (3)
In an intensional coloring transition system (ICTS), we distinguish between request/data arrival transitions (1), dataflow start (2), and dataflow end (3) transitions. Moreover, the state space of an ICTS is enriched with the states of the boundary nodes and a global dataflow flag. This operational semantics is the basis of our simulation approach.

Simulation-based stochastic analysis

In this section, we show how to construct a discrete event simulator engine (DES) [START_REF] Fishman | Principles of discrete event simulation[END_REF] for Stochastic Reo, which can be used for performance evaluation of connectors. The core idea of simulation in general is to generate a large number of sample path sequences, which are used as a characterization of the system behavior. Formally, a sample path is a realization of a (stochastic) process X(t) of transitions between states over time. In a DES, states change at discrete points in time, rather than continuously with time. An advantage of simulation over algorithmic approaches, such as QIA [START_REF] Arbab | From coordination to stochastic models of QoS[END_REF], is that all kinds of stochastic distributions can be used for specifying channel delays and request arrivals at nodes, in particular the ones given in Table 2. As underlying stochastic semantic model for our approach we use a generalized semi-Markov process (GSMP), a classical model for discrete event stochastic systems [START_REF] Glynn | On the role of generalized semi-markov processes in simulation output analysis[END_REF].

Definition 3 (generalized semi-Markov process). A generalized semi-Markov process is a stochastic process X(t) with state space S generated by a stochastic timed automaton A defined as A = (S, E, F (x), T (x, e), p 0 , P ), with E a set of events, F (x) the set of feasible events at state x ∈ S, T (x, e) the state transition function with x the current state and event e ∈ E, p 0 the probability mass for the initial state, and P the probability function for all events.

Lemma 1. Let C = (Q, →, start =⇒, end =⇒
) be an ICTS. This induces a minimal GSMP A = (S, E, F (x), T (x, e), p 0 , P ) such that the states are given by S = Q, Note that the probability function P and the initial probability mass p 0 are derived from the channel delays and request arrival distributions specified by the user. Thus, mapping the semantical ICTS model to a GSMP enables the use of discrete event simulation for performance analysis of connectors.

events are E = {request b | b ∈ B} ∪ {start c | c ∈ Color N } ∪ {stop c | c ∈ Color N },
Since we are not limited to use only continuous distributions, to model delays and inter-arrival times, multiple events could take place at the same time. In such a case, the correct DES process order of the event sequence is crucial. Therefore, we enforce that dataflow events take precedence over request arrival events. Furthermore, in this case, multiple possible dataflows, i.e. colorings, can be activated. A scheduler then selects one dataflow based on a given execution policy, such that only one dataflow is active at a time to ensure proper synchronization.

Simulation and analysis

We distinguish between two types of simulation: steady-state analysis, and transient analysis. Moreover, we consider a number of stopping criteria, i.e., maximum simulation time, maximum number of events, deadlocks, livelocks, and observed states. The latter offers the possibility to end the simulation in a specific state, which is particularly important for transient analysis.

Channel delays and node inter-arrival times. As described in Section 2.2, we associate a number of stochastic delays to every channel, and request inter-arrival times to boundary nodes. The derived GSMP allows the distributions to be general stochastic distributions, as in Table 2. Besides the standard distributions there are some special constructs. IfNeeded and Always can be used to model inter-arrival times without specifying a particular distribution, but depending on the current state of the connector. IfNeeded ensures that a boundary node always is in the empty or busy, but never waiting. Thus, request are spawned on demand. Always ensures that a node is never in the empty state. Whenever the node is finished with a dataflow, it immediately switches to waiting. Moreover, predefined inter-arrival times and channel delays can be specified as a Trace.

QoS measures. Among others, the following QoS measures can be computed during the simulation. The channel utilization, channel locked utilization, and dataflow utilization represent the percentage of time a channel is busy handling requests, locked for further processing, and the time a certain dataflow is activated, respectively. Request arrival statistics for boundary nodes include the expected node state and request observation state. The latter is the probability for the node being in a certain state during a request arrival. The expected waiting time measure is the expected waiting time at each boundary node. The conditional waiting time is the waiting time after a request arrived at a node. For FIFO channels, the expected buffer utilization can be calculated. For LossySync channels, the expected loss ratio of requests is an interesting measure. For nodes, the expected merger direction gives further insight about the internal routing of data in the connector. Global QoS measures of interest include the steady state probabilities of the connector and the dataflow probabilities. The latter is the probability of a specific coloring being active.

End-to-end delay A special role plays the expected end-to-end delay between a given start to another end boundary node of a connector. We compute the end-to-end delay of dataflows using a recursive depth-first traversal through all channels and nodes with active dataflow. Based on the active dataflow, we calculate the longest dataflow path through the connector, from the given start to the given end point. This uniquely determines the duration of the dataflow and, thus, the point in time where the dataflow is finished. A detailed algorithm for computing the end-to-end delay is given in [START_REF] Kanters | QoS analysis by simulation in Reo[END_REF].

Tool support

We have implemented the presented simulation approach for Reo in discrete event simulation tool as part of the Eclipse Coordination Tools [START_REF]ECT: Eclipse Coordination Tools[END_REF]. All distribution types given in Table 2 and all QoS measures described in Section 4.1, including end-to-end delays, are supported by this tool. The current scheduler implementation selects a dataflow randomly, with even distribution, thus does not prioritize. For all statistics, the expectation, standard deviation, the coefficient of variation, and confidence interval are calculated. ECT includes a graphical editor for specifying connector models. These graphical connector models are annotated with stochastic information which is sufficient for performing the stochastic simulation with our tool. The simulator is integrated with the graphical environment of ECT, as shown in the screenshot in Fig. 3, and generates a number of charts and diagrams.

Our simulation tool supports both steady-state and transient analysis. Steadystate analysis is only possible if the system actually reaches steady-state, which is not guaranteed in simulation-based analysis. Therefore, we have implemented a number of tools to facilitate convergence checking. Specifically, the tool generates charts that show how the different QoS measure develop over time during the simulation runs. Furthermore, the tool computes the number of observations, result histograms, and supports automatic deadlock and livelock detection.

All analysis results are available in the user interface, and can can be additionally exported for subsequent analysis with other tools. Dataflows, i.e., colorings, are visualized graphically which provides an intuitive way to investigate the dataflow statistics.

Depending on the size of the modeled system, state spaces can grow very fast. However, the implementation of the coloring semantics in ECT supports step-wise execution. Our simulation tool uses this functionality for an on-the-fly generation of the state space, thus, enabling simulation without prior computation of the whole state space.

Case studies

In the following, we present two case studies for our simulation approach. We perform steady-state simulations with the ending condition of 10,000,000 events, Fig. 3. Simulation-based stochastic analysis in the Eclipse Coordintation Tools and a warm-up period of 10,000 events. A comprehensive case study of an industrial software system is described in [START_REF] Moon | Stochastic Reo: A case Study[END_REF].

Case 1: Instant Messenger

In this example we investigate the instant messenger example, introduced in Section 2.1. As distinct from existing performance evaluation techniques for Reo our approach allows us to analyze in detail the impact of the configuration, as specified in Table 3, on the behavior of the instant messenger.

Using our simulator, we found an asymmetry between the two dataflow regions of the message delivery parts, caused by the configuration. For Client 1, this is the dataflow represented by the coloring in Fig. 2. For Client 2 it is the symmetric dataflow. Using the dataflow utilization statistic, we found out that in 54.0% of the time, dataflow for the message delivery of Client 1 is active, versus only 3.6% of the time for the message delivery of Client 2. We can also look to the dataflows from another perspective, i.e., whether the clients are both sending, both receiving, one is sending and one is receiving, or both are idle. The results are shown in Table 7.

When we look to the merging directions of node B, 64.1% of the data arrives from the Sync X→B (acknowledgment message from Client 1) and only 35.9% arrives from the direction of node Y . Due to the symmetrical structure of the 8. End-to-end delays connector, the merging directions for node C are the same. From the buffer utilization statistics, we derive that the buffer between A and X is full 92.8% of the time, compared to 59.5% for the buffer between D and Y . Using the expected node states, blocking probabilities of all boundary nodes can be inspected (the percentage time the boundary node is waiting or busy). The probabilities are, for node A: 87.1%, B: 98.0%, C: 59.7%, and D: 41.9%. The very high blocking probability of node B can be explained by the very high arrival rate of requests at B and the high delay of the dataflow of the message delivery part of Client 1.

In Table 8, the effect on the end-to-end delay from A to C and from D to B is shown, varying the delay µ D,f if o between D and the buffer of FIFO D→Y . When we decrease the delay from 0.5 to 0.02 (rate 2.0 and 50.0), the decrease in delay between A and C is very small (7.677 vs. 7.642). If we increase the delay from 0.5 to 8.0 there is, as one would expect, a major increase in the end to end delay from D to B. Interestingly, the delay from A to C increases as well. This is due to the fact that if the dataflow between D and the FIFO buffer is active, no other dataflow can happen at the same time and the waiting time of requests at node A increases and therefore also the end-to-end delay between A and C.

Case 2: Production line decision making

In this example, we model a production line in Reo, as shown in Fig. 4. It uses 1 permanent server on the right-hand side, and whenever there are 3 jobs in the queue, modeled by a sequence of FIFO channels, one additional server is started. Whenever a job is assigned to the queue, it will wait until it has been serviced by server 1, so it will never go to server 2. We vary the service rate of the base server and keep all other parameters constant to investigate the impact on the queue length.

For the arrival rate we have chosen a Weibull distribution with k = 1.5. Both servers have a log-normal distribution with µ = 0 and σ = 1. We vary the µ of the first server. The average queue length of the queue before the permanent server is shown in Figure 5. The average inter-arrival times at boundary node A is around 0.9, so when the average server duration of the base server exceeds this time, the server is not capable of handling all request. Because of this, the queue will fill up and the second server will be used to help the first server. When the average service duration is around 0.9, the average queue length increases rapidly, until it converges to the maximum queue size. When the service time becomes large enough, almost all of the requests will be redirected to server 2 or blocked if server 2 is also not available. We introduced a performance evaluation approach for Reo based on a new transition system and discrete event simulation. Our approach is more powerful then the existing techniques for performance analysis in Reo in two respects: (i) it allows the use of arbitrary distributions, and (ii) scales much better due to an on-the-fly state-space generation. We implemented our approach in a tool that supports both steady-state and transient analysis.

As future work, we plan to support the use of convergence of statistics as stopping criteria and to add automatic sensitivity analysis. To gain more insight in the precise distribution of the results of statistics, keeping all information of every single observation, and a detailed distribution plot, will be helpful. Another promising extension is to link current automata-based models directly to the simulator state-space. Thereby, it will be possible to define statistics and stopping criteria for different semantical models.

Fig. 1 .

 1 Fig. 1. Instant messenger application modeled in Reo

  -provide-reason no-flow-require-reason

  and the transitions T are given by the union of →, start =⇒ and end =⇒.Proof. The semi-Markov property holds, because for a transition s e → s the next state s is depending only on the current state s ∈ S and event e ∈ E.

Fig. 4 .

 4 Fig. 4. Reo connector for a production line

Fig. 5 .

 5 Fig. 5. Average queue length for production line

Table 2 .

 2 Supported distributions

	Channel	Delay 1 Delay 2
	FIFOA→X	Exp(2)	Exp(1)
	Sync X→C Tri(5, 10, 7)

Table 5 .

 5 Colors

	Sync	Merger
	(S1)

Table 7 .

 7 Dataflow probabilities

	µ D,f if o	A → C	D → B
	Delay	σ	Delay	σ
	0.125 10.867 0.110 14.734 0.200
	2.000 7.677 0.039 8.343 0.139
	50.000 7.642 0.029 8.361 0.117
	Table

Supported by NWO project Cooper. Supported by the research school in 'Service-Oriented Systems Engineering' at HPI.


Paul Tarau
email: tarau@cs.unt.edu

Coordination and Concurrency in Multi-Engine Prolog

Keywords: multi-engine Prolog, agent coordination, high-level multithreading, coroutining Linda blackboards, publish/subscribe, Java-based Prolog system

We discuss the impact of the separation of logic engines (independent logic processing units) and multi-threading on the design of coordination mechanisms for a Prolog based agent infrastructure. We advocate a combination of coroutining constructs with focus on expressiveness and a simplified, multi-threading API that ensures optimal use available parallelism. In this context, native multi-threading is made available to the application programmer as a set of high-level primitives with a declarative flavor while cooperative constructs provide efficient and predictable coordination mechanisms. As illustrations of our techniques, a parallel fold operation as well as cooperative implementations of Linda blackboards and publish/subscribe are described.

Introduction

Multi-threading has been adopted in today's Prolog implementations as it became widely available in implementation languages like C or Java.

An advantage of multi-threading over more declarative concurrency models like various AND-parallel and OR-parallel execution schemes, is that it maps to the underlying hardware directly: on typical multi-core machines threads and processes are mapped to distinct CPUs1 . Another advantage is that a procedural multi-threading API can tightly control thread creation and thread reuse.

On the other hand, the explicit use of a procedural multi-threading API breaks the declarative simplicity of the execution model of logic based languages. At the same time it opens a Pandora's box of timing and execution order dependencies, resulting in performance overheads for various runtime structures that need to be synchronized. It also elevates risks of software failure due to programmer errors given the mismatch between assumptions about behavior expected to follow the declarative semantics of the core language and the requirements of a procedural multi-threading API.

In this paper we will describe how efficient and flexible agent coordination is facilitated by a design emphasizing the decoupling of the multi-threading API and the logic engine operations and encapsulation of multi-threading in a set of high-level primitives with a declarative flavor.

In this process, we use threads encapsulated as high level programming language constructs with focus on performance benefits, and we are resorting to determinacy, through lightweight, cooperative sequential constructs, to express coordination patterns.

We have implemented the API in the context of an experimental, Java-based Prolog system, Lean-Prolog 2 .

LeanProlog is based on a reimplementation of BinProlog's virtual machine, the BinWAM. It succeeds our Jinni Prolog implementation that has been used in various applications [START_REF] Tarau | Towards Inference and Computation Mobility: The Jinni Experiment[END_REF][START_REF] Tarau | Intelligent Mobile Agent Programming at the Intersection of Java and Prolog[END_REF][START_REF] Tarau | Inference and Computation Mobility with Jinni[END_REF][START_REF] Tarau | Agent Oriented Logic Programming Constructs in Jinni[END_REF] as an intelligent agent infrastructure, by taking advantage of Prolog's knowledge processing capabilities in combination with a simple and easily extensible runtime kernel supporting a flexible reflexion mechanism. Naturally, this has suggested to investigate whether some basic agent-oriented language design ideas can be used for a refactoring of Prolog's interoperation with the external world, including interaction with other instances of the Prolog processor itself.

Agent programming constructs have influenced design patterns at "macro level", ranging from interactive Web services to mixed initiative computer human interaction. From the very beginning, Performatives in Agent communication languages [START_REF] Mayfield | Evaluation of KQML as an Agent Communication Language[END_REF]6] have made these constructs reflect explicitly the intentionality, as well as the negotiation process involved in agent interactions. At the same time, it has been a long tradition of logic programming languages [START_REF] Hermenegildo | An abstract machine for restricted and-parallel execution of logic programs[END_REF] to use multiple logic engines for supporting concurrent execution.

In this context we have centered our implementation around logic engine constructs providing an API that supports reentrant instances of the language processor. This has naturally led to a view of logic engines as instances of a generalized family of iterators called Fluents [START_REF] Tarau | Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects[END_REF], that have allowed the separation of the first-class language interpreters from the multi-threading mechanism, while providing a very concise source-level reconstruction of Prolog's built-ins. Later we have extended the original Fluents with a few new operations [START_REF] Tarau | Interoperating Logic Engines[END_REF] supporting bi-directional, mixed-initiative exchanges between engines, bringing them closer to an agent-oriented view as autonomous logic processors.

The resulting language constructs, that we have called Interactors, express control, metaprogramming and interoperation with stateful objects and external services.

On the other hand, our multi-threading layer has been designed to be independent of the interactor API. This allows assumptions of determinacy when working with multiple engines (and other sequential interactors) within a thread.

The multi-threading API integrates thread-construction with interactors called Hubs that provide synchronization between multiple consumers and producers. It supports high-level performance-centered concurrency patterns while removing the possibility of programming errors involving explicit synchronization.

The guiding architectural principle we based our design on, can be stated concisely as follows: separate concurrency for performance from concurrency for expressiveness. Arguably, it is a good fit with the general idea behind declarative programming languages -delegate as much low level detail to underlying implementation as possible rather than burdening the programmer with complex control constructs.

The paper is organized as follows. Section 2 overviews logic engines and describes their basic operations and the interactor API that extends the same view to various other built-in predicates. Section 3 introduces Hubs -flexible synchronization devices that allow interoperation and coordination between threads. Section 4 describes a set of high-level multi-threading operations that ensure concurrent execution seen as a means to accelerate computations while keeping the semantics as close as possible to a declarative interpretation.

Sections 5 and 6 show that fundamental coordination patterns like Linda blackboards and publish/subscribe can be implemented cooperatively in terms of sequential operations on logic engines.

Finally, section 7 discusses related work and section 8 concludes the paper.

Logic engines as answer generators

Our Interactor API has evolved progressively into a practical Prolog implementation framework starting with [START_REF] Tarau | Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects[END_REF] and continued with [START_REF] Tarau | Logic Engines as Interactors[END_REF] and [START_REF] Tarau | Interoperating Logic Engines[END_REF]. We summarize it here and refer to [START_REF] Tarau | Interoperating Logic Engines[END_REF] for the details of a semantic description in terms of Horn Clause Logic of various engine operations. A logic engine is simply a language processor reflected through an API that allows its computations to be controlled interactively from another engine very much the same way a programmer controls Prolog's interactive toplevel loop: launch a new goal, ask for a new answer, interpret it, react to it.

A logic engine can be seen as an instance of the Prolog runtime system implementing LD-resolution [START_REF] Tarau | Nonstandard Answers of Elementary Logic Programs[END_REF] on a given clause database, together with a set of built-in operations. The command new_engine(AnswerPattern, Goal, Interactor)

creates a new logic engine, uniquely identified by Interactor, which shares code with the currently running program and is initialized with Goal as its starting point. AnswerPattern is a term, usually a list of variables occurring in Goal, of which answers returned by the engine will be instances. Note however that new engine/3 acts like a typical constructor, no computations are performed at this point, except for initial allocation of data areas.

Iterating over computed answers

Note that our logic engines are seen, in an object oriented-style, as implementing the interface Interactor. This supports a uniform interaction mechanism with a variety of objects ranging from logic engines to file/socket streams and iterators over external data structures.

The ask interactor/2 operation is used to retrieve successive answers generated by an Interactor, on demand. It is also responsible for actually triggering computations in the engine. The query ask_interactor(Interactor, AnswerInstance) tries to harvest the answer computed from Goal, as an instance of AnswerPattern. If an answer is found, it is returned as the(AnswerInstance), otherwise the atom no is returned. Note that bindings are not propagated to the original Goal or AnswerPattern when ask interactor/2 retrieves an answer, i.e. AnswerInstance is obtained by first standardizing apart (renaming) the variables in Goal and AnswerPattern, and then backtracking over its alternative answers in a separate Prolog interpreter. Therefore, backtracking in the caller interpreter does not interfere with Interactor's iteration over answers. Backtracking over Interactor's creation point, as such, makes it unreachable and therefore subject to garbage collection. An interactor is stopped with the stop_interactor(Interactor) operation, that, in the case of logic engines, allows reclaiming resources held by the engine.

So far, these operations provide a minimal API, powerful enough to switch tasks cooperatively between an engine and its client and emulate key Prolog built-ins like if-then-else and findall [START_REF] Tarau | Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects[END_REF], as well as typical higher order operations like fold and best of [START_REF] Tarau | Interoperating Logic Engines[END_REF].

A yield/return operation

The following operations provide a "mixed-initiative" interaction mechanism, allowing more general data exchanges between an engine and its client.

First, like the yield return construct of C# and the yield operation of Ruby and Python, our return/1 operation return(Term) will save the state of the engine and transfer control and a result Term to its client. The client will receive a copy of Term simply by using its ask interactor/2 operation.

Note that an interactor returns control to its client either by calling return/1 or when a computed answer becomes available. By using a sequence of return and ask interactor operations, an engine can provide a stream of intermediate/final results to its client, without having to backtrack. This mechanism is powerful enough to implement a complete exception handling mechanism simply by defining throw(E) :-return(exception(E)).

When combined with a catch(Goal, Exception, OnException), on the client side, the client can decide, upon reading the exception with ask interactor/2, if it wants to handle it or to throw it to the next level.

Coroutining logic engines

Coroutining has been in use in Prolog systems mostly to implement constraint programming extensions. The typical mechanism involves attributed variables holding suspended goals that may be triggered by changes in the instantiation state of the variables. We discuss here a different form of coroutining, induced by the ability to switch back and forth between engines.

The operations described so far allow an engine to return answers from any point in its computation sequence. The next step is to enable an engine's client3 to inject new goals (executable data) to an arbitrary inner context of an engine. Two new primitives are needed:

to_engine(Engine, Data)
that is called by the client 4 to send data to an Engine, and from_engine(Data) that is called by the engine to receive a client's Data.

A typical use case for the Interactor API looks as follows:

1. the client creates and initializes a new engine 2. the client triggers a new computation in the engine, parameterized as follows:

(a) the client passes some data and a new goal to the engine and issues an ask interactor/2 operation that passes control to it (b) the engine starts a computation from its initial goal or the point where it has been suspended and runs (a copy of) the new goal received from its client (c) the engine returns (a copy of) the answer, then suspends and returns control to its client 3. the client interprets the answer and proceeds with its next computation step 4. the process is fully reentrant and the client may repeat it from an arbitrary point in its computation

As a key difference with typical multi-threaded Prolog implementations like Ciao-Prolog [START_REF] Carro | Concurrency in Prolog Using Threads and a Shared Database[END_REF] and SWI-Prolog [START_REF] Wielemaker | Native Preemptive Threads in SWI-Prolog[END_REF], our Interactor API is designed up front with a clear separation between engines and threads as we prefer to see them as orthogonal language constructs. To ensure that communication between logic engines running concurrently is safe and synchronized, we hide the engine handle and provide a producer/consumer data exchanger object, called a Hub, when multi-threading.

A Hub can be seen as an interactor used to synchronize threads. On the Prolog side it is introduced with a constructor hub/1 and works with the standard interactor API: ask_interactor(Hub, Term) tell_interactor(Hub, Term) stop_interactor(Hub)

On the Java side, each instance of the Hub class provides a synchronizer between M producers and N consumers. A Hub supports data exchanges through a private object port and it implements the Interactor interface. Consumers issue ask interactor/2 operations that correspond to tell interactor/2 operations issued by producers.

A group of related threads are created around a Hub that provides both basic synchronization and data exchange services. The built-in new_logic_thread(Hub, X, G, Clone, Source)

creates a new thread by either "cloning" the current Prolog code and symbol spaces or by loading new Prolog code in a separate name space from a Source (typically a precompiled file or a stream). Usually a default constructor new_logic_thread(Hub, X, G) is used. It shares the code but it duplicates the symbol table to allow independent symbol creation and symbol garbage collection to occur safely in multiple threads without the need to synchronize or suspend thread execution.

4 High-level concurrency with higher-order constructs Encapsulating concurrent execution patterns in high-level abstractions, when performance gains are the main reason for using multiple threads, avoids forcing a programmer to suddenly deal with complex procedural issues when working with (mostly) declarative constructs in a language like Prolog. It is also our experience that in an exclusively dynamically-typed language like Prolog this reduces software risks significantly.

One of the deficiencies of sequential or multi-threaded findall-like operations is that they might build large lists of answers unnecessarily. With inspiration drawn from combinators in functional languages, one can implement a more flexible multi-threaded fold operation instead.

The predicate multi fold(F, XGs, Xs) runs a list of goals XGs of the form Xs :-G and combines, with F, their answers, to accumulate them into a single final result, without building intermediate lists. The predicate multi fold relies on the predicate launch logic threads to run threads initiated by the goal list XGs. When launching the threads, we ensure that they share the same Hub for communication and synchronization. Once all threads are launched, we use the predicate fold thread results to collect results computed by various threads from Hub, and to combine them into a single result, while keeping track of the number of threads that have finished their work.

fold_thread_results(0, _Hub, _F, Best, Best). fold_thread_results(ThreadCount, Hub, F, SoFar, Best) :-ThreadCount > 0, ask_interactor(Hub, Answer), count_thread_answer(Answer, ThreadCount, ThreadsLeft, F, SoFar, Better), fold_thread_results(ThreadsLeft, Hub, F, Better, Best).

count_thread_answer(no, ThreadCount, ThreadsLeft, _F, SoFar, SoFar) :-ThreadsLeft is ThreadCount-1. count_thread_answer(the(X), ThreadCount, ThreadCount, F, SoFar, Better) :call(F, X, SoFar, Better).

A typical application is the predicate multi best(F, XGs, M), which runs a list of goals XGs of the form N :-G where N is instantiated to a numeric value. By using max/3 to combine the current best answers with a candidate one it extracts at the the maximum M of all answers computed (in an arbitrary order) by all threads. multi_best(XGs,R) :-multi_fold(max,XGs,R).

Note that, as in the case of its fold cousins in functional languages, multi fold can be used to emulate various other higher order predicates. For instance a findall-like predicate is emulated as the predicate multi all(XGs,Xs) which runs a list of goals XGs of the form Xs :-G and combines all answers to a list using list cons. A different pattern arises from combinatorial search algorithms where one wants to stop multiple threads as soon as a first solution is found. Things like restarts in SAT solvers and various Monte Carlo algorithms fit in this category.

For instance, the predicate multi first(K, XGs, Xs) runs each goal of the form Xs :-G on the list XGs, until the first K answers Xs are found (or fewer, if less then K answers exist).

It uses a very simple mechanism built into Lean Prolog's multi-threading API: when a Hub interactor is stopped, all threads associated to it are notified to terminate. In particular, searching for at most one solution is possible:

multi_first(XGs,X) :-multi_first(1,XGs,[X]).
The multi first/3 and multi first/2 predicates provide an alternative to using CUT in Prolog as a means to limit search, while supporting a scalable mechanism for concurrent execution. Note also that multi first/3 it is more flexible than CUT as it can be used to limit the search to a window of K solutions. However, in contrast with CUT, the order in which these first solutions are found is arbitrary.

Agent coordination with cooperative Linda blackboards

The message passing style interaction shown in the previous sections between engines and their clients, can be easily generalized to associative communication through a unification based blackboard interface [START_REF] De Bosschere | Blackboard-based Extensions in Prolog[END_REF]. Exploring this concept in depth promises more flexible interaction patterns, as out of order operations become possible, matched by association patterns. An interesting question arises at this point. Can blackboard-based coordination be expressed directly in terms of engines, and as such, can it be seen as independent of a multi-threading API?

We have shown so far that when focusing on performance on multi-core architectures, multi-threading can be encapsulated in high-level constructs that provide its benefits without the need of a complex procedural API.

To support our claim that "concurrency for expressiveness" works quite naturally with coroutining logic engines we will describe here a cooperative implementation of Linda blackboards. In contrast to multi-threaded or multi-process implementations, it ensures atomicity "by design" for various operations. It is an example of concurrency for expressiveness that can be used orthogonally from concurrency for performance to coordinate cooperatively multiple logic engines within a single thread.

The predicate new coordinator(Db) uses a database parameter Db (a synthetic name, if given as a free variable, provided by db ensure bound) to store the state of the Linda blackboard 5 . The state of the blackboard is described by the dynamic predicates available/1, that keeps track of terms posted by out operations, waiting/2, that collects pending in operations waiting for matching terms, and running/1, that helps passing control from one engine to the next. The predicate new task initializes a new coroutining engine, driven by goal G.

We shall call such an engine "an agent" in the next paragraphs.

new_task(Db, G) :-

Three cooperative Linda operations are available to an agent. They are all expressed by returning a specific pattern to the Coordinator.

coop_in(T) :-return(in(T)), from_engine(X), T=X. coop_out(T) :-return(out(T)).

coop_all(T, Ts) :-return(all(T, Ts)), from_engine(Ts).

The Coordinator implements a handler for the patterns returned by the agents as follows:

handle_in(Db, T, E) :-db_retract1(Db, available(T)),!, to_engine(E, T), db_assertz(Db, running(E)). handle_in(Db, T, E) :-db_assertz(Db, waiting(T, E)). handle_out(Db, T) :-db_retract(Db, waiting(T, InE)),!, to_engine(InE, T), db_assertz(Db, running(InE)). handle_out(Db,T) :-db_assertz(Db, available(T)). handle_all(Db, T, Ts, E) :findall(T, db_clause(Db, available(T), true), Ts), to_engine(E, Ts), db_assertz(Db, running(E)).

The Coordinator's dispatch loop coordinate/1 (failure driven here to run without requiring garbage collection) works as follows:

coordinate(Db) :repeat, ( db_retract1(Db, running(E)) → ask_interactor(E, the(A)), dispatch(A, Db, E), fail ; ! ).

Its dispatch/3 predicate calls the handlers as appropriate.

dispatch(in(X), Db, E) :-handle_in(Db, X, E). dispatch(out(X), Db, E) :-handle_out(Db, X), db_assertz(Db, running(E)). dispatch(all(T, Ts), Db, E) :-handle_all(Db, T, Ts, E). dispatch(exception(Ex), _, _) :-throw(Ex).

Note also that the predicate dispatch/3 propagates exceptions -in accordance with a "fail fast" design principle. When the coordinator is stopped using stop coordinator, the database is cleaned of possible records of unfinished tasks in either running or waiting state. This predicate uses a Lean Prolog extension, foreach which makes failure-driven loops more readable -it is defined as follows:

foreach(When,Then) :-When,once(Then),fail. foreach(_,_).

The following test predicate shows that out-of-order in and out operations are exchanged as expected between engines providing a simple transactional implementation of Linda coordination. When running the code, one can observe that explicit coroutining control exchanges between engines have been replaced by operations of the higher level Linda coordination protocol.

?-test_coordinator. coop_out = f(3),coop_out = f(2),coop_out = f(0),coop_in = f(0), coop_out = f(1),coop_in = f(2),coop_in = f(1),coop_in = f(3).
This shows that "concurrency for expressiveness" in terms of the logic-enginesas-interactors API provides flexible building blocks for the encapsulation of nontrivial high-level concurrency patterns.

Coordinating publishers and subscribers

We will now describe a cooperative publish/subscribe mechanism that uses multiple dynamic databases and provides, as an interesting feature, associative search through the set of subscribed events.

The predicate publish(Channel,Content) initializes a Channel, implemented as a dynamic database together with a time stamping mechanism. Content is a fact to be added to the database, for which the user can (and should) provide indexing declarations to support scalable large volume associative search. The predicate consume new(Subscriber,Channel,Content) reads the next message on Channel. It ensures, by checking and updating channel and subscriberspecific time stamps, that on each call it gets one new event, if available. consume_new(Subscriber,Channel,Content) :-var(Content), get_time_of(Channel,Subscriber,T1), db_clause(Channel,Content,published_at(TP)), T1=<TP, T2 is T1+1, set_time_of(Channel,Subscriber,T2).

The predicate peek at published(ContentPattern, Matches) supports associative search for published content, independently of the fact that it has already been read. It provides to an agent the set of subscribed events matching ContentPattern.

peek_at_published(Channel,ContentPattern, Matches) :findall(ContentPattern, db_clause(Channel,ContentPattern,_),Matches).

The predicate init publishing(ContentIndexings) sets up indexing using list of ContentIndexings of the form pred(I1,I2,...In) where I1,I2...In can be 1 (indicating that an argument should be indexed) or 0.

?-pubtest. publish(sports, wins(rangers)) publish(politics, loses(meg)) publish(sports, loses(bills)) publish(sports, wins(cowboys)) publish(politics, wins(rand)) consume_new(joe, sports, wins(rangers)) consume_new(mary, sports, wins(rangers)) consume_new(joe, sports, loses(bills)) consume_new(joe, politics, loses(meg)) consume_new(joe, politics, wins(rand)) consume_new(mary, sports, loses(bills))

The final state of various databases can be queried (and cleaned up) with:

?-listings,clean_up_publishing.

% global_time: time_of / 3. time_of($publishing, sports, 2). time_of($publishing, politics, 1). time_of(sports, joe, 2). time_of(politics, joe, 2). time_of(sports, mary, 2). % sports: wins / 1. wins(rangers) :-published_at(0). wins(cowboys) :-published_at(2). % politics: wins / 1. wins(rand) :-published_at(1). % politics: loses / 1. loses(meg) :-published_at(0). % sports: loses / 1. loses(bills) :-published_at(1).

This shows the presence of sequencing information provided by the dynamic predicate published at/1. Note also that these (indexed) databases can be searched associatively by various subscribers for "past" content.

Related work

Multiple logic engines have been present in one form or another in various parallel implementation of logic programming languages, [START_REF] Gupta | Parallel execution of prolog programs: a survey[END_REF][START_REF] Shapiro | The family of concurrent logic programming languages[END_REF] Among the earliest examples of parallel execution mechanisms for Prolog, AND-parallel [START_REF] Hermenegildo | An abstract machine for restricted and-parallel execution of logic programs[END_REF] and ORparallel [START_REF] Lusk | Applications of the aurora parallel prolog system to computational molecular biology[END_REF] execution models are worth mentioning.

However, with the exception of the author's papers on this topic [START_REF] Tarau | Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects[END_REF][START_REF] Tarau | High-Level Networking with Mobile Code and First Order AND-Continuations[END_REF][START_REF] Tarau | Logic Engines as Interactors[END_REF][START_REF] Tarau | Interoperating Logic Engines[END_REF] there are relatively few examples of using first-class logic engines as a mechanism to enhance language expressiveness, independently of their use for parallel programming. A notable exception is [START_REF] Casas | Towards a high-level implementation of flexible parallelism primitives for symbolic languages[END_REF] where such an API is discussed for parallel symbolic languages in general.

In combination with multithreading, our own engine-based API bears similarities with various other Prolog systems, notably [START_REF] Carro | Concurrency in Prolog Using Threads and a Shared Database[END_REF][START_REF] Wielemaker | Native Preemptive Threads in SWI-Prolog[END_REF]. Coroutining has also been present in logic languages to support constraint programming extensions requiring suspending and resuming execution based on changes of the binding state of variables. In contrast to these mechanisms that focus on transparent, fine-grained coroutining, our engine-based mechanisms are coarse-grained and programmer controlled. Our coroutining constructs can be seen, in this context, as focussed on expressing cooperative design patterns that typically involve the use of a procedural multi-threading API.

Finally, our multi findall and multi fold predicates have similarities with design patterns like ForkJoin [START_REF] Lea | A Java fork/join framework[END_REF] or MapReduce [START_REF] Lämmel | Google's MapReduce programming model revisited[END_REF] coming from sharing a common inspiration source: higher-order constructs like map and fold in functional programming.

Conclusion

We have shown that by decoupling logic engines and threads, programming language constructs for coordination can be kept simple when their purpose is clear -multi-threading for performance is separated from concurrency for expressiveness. This is achieved via communication between independent language interpreters independent of the multi-threading API.

Our language constructs are particularly well-suited to take advantage of today's multi-core architectures where keeping busy a relatively small number of parallel execution units is all it takes to get predictable performance gains, while reducing the software risks coming from more complex concurrent execution mechanisms designed with massively parallel execution in mind.

The current version of LeanProlog containing the implementation of the constructs discussed in this paper, and related papers describing other aspects of the system are available at http://logic.cse.unt.edu/tarau/research/LeanProlog .

  multi_fold(F, XGs, Final) :-hub(Hub), length(XGs,ThreadCount), launch_logic_threads(XGs, Hub), ask_interactor(Hub, Answer), (Answer = the(Init) → fold_thread_results(ThreadCount, Hub, F, Init, Final) ; true ), stop_interactor(Hub),Answer=the(_).

  launch_logic_threads([], _Hub). launch_logic_threads([(X :-G)| Gs], Hub) :-new_logic_thread(Hub, X, G), launch_logic_threads(Gs, Hub).

  multi_all(XGs, Rs) :-multi_fold(list_cons,[([] :-true) | XGs],Rs). list_cons(X, Xs, [X | Xs]).

  multi_first(K, XGs, Xs) :-hub(Hub), length(XGs, ThreadCount), launch_logic_threads(XGs, Hub), collect_first_results(K, ThreadCount, Hub, Xs), stop_interactor(Hub).collect_first_results(_, 0, _Hub, []). collect_first_results(0, _, Hub, []) :-stop_interactor(Hub). collect_first_results(K, ThreadCount, Hub, MoreXs) :-K>0, ThreadCount>0, ask_interactor(Hub, Answer), count_thread_answer(Answer, ThreadCount, ThreadsLeft, Xs, MoreXs), ( ThreadCount =:= ThreadsLeft → K1 is K-1 ; K1 is K ), collect_first_results(K1, ThreadsLeft, Hub, Xs).

  new_coordinator(Db) :-db_ensure_bound(Db), maplist(db_dynamic(Db), [available/1,waiting/2,running/1]).

  stop_coordinator(C) :foreach(db_clause(C, running(E), true), stop(E)), foreach(db_clause(C, waiting(_, E), true), stop(E)).

  publish(Channel,Content) :-increment_time_of('$publishing',Channel,T), db_assert(Channel,(Content :-published_at(T))).

We use the word CPU in accordance of what the underlying runtime system and operating system sees as independent processing units in a multi-core/multi-processor machine. For instance, on a two Xeon processor Quad-Core MacPro with hyperthreading, the Java VM sees 16 independent processing units.

It is called Lean-Prolog as we have consistently tried to keep implementation complexity under control and follow minimalist choices in the design of built-ins, external language interfaces and a layered, modular extension mechanism.

Another engine, that uses an engine's services.

Equivalently the tell interactor/2 generic interactor predicate can be also used here.

Note, that, as an extension to standard Prolog, Lean Prolog provides multiple dynamic databases, which, in turn, can be emulated, as shown in[START_REF] Tarau | Interoperating Logic Engines[END_REF], in terms of logic engines. Their operations (like db assert/2 similar to assert/1) have an extra first argument that names the database on which they act).

Acknowledgment

We thank NSF (research grant 1018172) for support.