Marin Bertier

Marko Obrovac

Cédric Tedeschi

A Protocol for the Atomic Capture of Multiple Molecules on Large Scale Platforms

With the rise of service-oriented computing, applications are more and more based on coordination of autonomous services. Envisioned over largely distributed and highly dynamic platforms, expressing this coordination calls for alternative programming models. The chemical programming paradigm, which models applications as chemical solutions where molecules representing digital entities involved in the computation, react together to produce a result, has been recently shown to provide the needed abstractions for autonomic coordination of services. However, the execution of such programs over large scale platforms raises several problems hindering this paradigm to be actually leveraged. Among them, the atomic capture of molecules participating in concurrent reactions is one of the most significant. In this paper, we propose a protocol for the atomic capture of these molecules distributed and evolving over a large scale platform. As the density of possible reactions is crucial for the liveness and efficiency of such a capture, the protocol proposed is made up of two sub-protocols, each of them aimed at addressing different levels of densities of potential reactions in the solution. While the decision to choose one or the other is local to each node participating in a program's execution, a global coherent behaviour is obtained. Proof of liveness, as well as intensive simulation results showing the efficiency and limited overhead of the protocol are given.

Introduction

With the widespread adoption of the Service-Oriented Architecture (SOA) paradigm, large scale computing platforms have recently undergone a new shift in their shape and usage. Within such platforms, the basic entity is a service, i.e., an encapsulation of some computing, storage, or sensor device, to be used by users or combined with other services. On top of these platforms, applications now commonly compose these services dynamically, under the shape of workflows, i.e., temporal compositions of services. To run over emerging highly distributed and dynamic platforms, without any central authority or orchestrator, services need to be able to coordinate themselves autonomously, in a fully-distributed fashion. In this context, programming models need to be rethought in order to provide the right abstractions for this coordination, while taking into account the distribution and dynamics of the underlying platform.

Artificial chemistries [START_REF] Dittrich | Artificial chemistries -a Review[END_REF], which are chemically-inspired information processing models, have regained momentum in this context, and are now used to model this ecosystem of services [START_REF] Viroli | A Biochemical Approach to Adaptive Service Ecosystems[END_REF]. More concretely, the chemical programming paradigm, initially developed to write highly parallel programs, was identified to provide the right level of abstraction for this context [START_REF] Banâtre | Chemical Programming of Future Service-oriented Architectures[END_REF]. Within the basic version of the chemical programming model [START_REF] Banâtre | A parallel Machine for Multiset Transformation and its Programming Style[END_REF], a program is envisioned as a chemical solution where molecules of data float and react according to some reaction rules specifying the program, to produce new data (products of reactions). At runtime, reactions arise in an implicitly autonomous and parallel mode, and in a non-deterministic order. When no more reactions are possible, the solution contains the result of the computation.

While the chemical paradigm allows the easy design of coordination protocols, running these chemical specifications over distributed platforms is still a widely open issue. Among one of the most significant barriers to be lifted is the atomic capture of multiple molecules satisfying a reaction. At runtime, a molecule can potentially participate in several concurrent reactions. However, it is allowed to participate in only one. Otherwise, the logic of the program would be broken. This problem is exemplified in Section 2.

Let us slightly refine the problem considered in this paper. We consider a chemical program made of a multiset of data, and of a set of rules acting concurrently on them. Both data and rules are distributed amongst a set of nodes on which the program runs. Each node periodically tries to fetch molecules needed for their assigned reactions. As several molecules can satisfy the pattern and conditions of several reactions performed concurrently by different nodes, the same molecule can be requested by several nodes at the same time, inevitably leading to conflicts. Mutual exclusion on the molecules is thus mandatory.

Although our problem resembles the classic resource allocation problem [START_REF] Lamport | Ti clocks, and the ordering of events in a distributed system[END_REF], it differs in several aspects. Firstly, the molecules are exchangeable to some extent. Molecules requested must match a pattern defined in the reaction rule a node wants to perform. In other words, we differentiate two processes which are i) finding molecules matching a pattern (achieved by a discovery protocol ), and ii) obtaining them to perform reactions (achieved by a capture protocol ).

Secondly -and following the previous point -the platform envisioned is at large scale, and the resources dispatched over the nodes are dynamic: molecules are deleted when they react, and new ones are created. Thus, the protocol to discover molecules should be scalable and dynamic. Likewise, the number of resources/molecules (and possible reactions) will fluctuate over time, influencing the design of the capture protocol. Bear in mind that once the holder of a matching molecule is located, the scale of the network is of less importance, since only the requester and holder of the molecule are involved in the capture protocol.

Finally, and to sum up, our objective is to define a protocol for the atomic capture of multiple molecules, that dynamically and efficiently adapts to the density of potential reactions in the system. Contribution. Our contribution is a distributed protocol mixing two subprotocols inspired by previous works on distributed resource allocation, and adapted to the distributed runtime of chemical programs.

The first sub-protocol, referred to as the optimistic one, assumes that the number of molecules satisfying some reaction's pattern and condition is high, so only few conflicts for molecules will arise, nodes being likely to be able to grab distinct sets of molecules. While this protocol is simple, fast, and has a limited communication overhead, it does not ensure liveness when the number of conflicts increases. The second one, called pessimistic, slower, and more costly in terms of communication, ensures liveness in presence of an arbitrary number of conflicts. Switching from one protocol to the other is achieved in a scalable, distributed fashion, based on local success histories in grabbing molecules. A proof of liveness of our protocol is given, and its efficiency is discussed through a set of simulation results. Note that this work, to our knowledge, pioneers research on the distributed execution of chemical programs.

Organisation of the paper. The next section presents the chemical programming paradigm in more details, highlights the need for the atomic capture and describes the system model used throughout the paper. Section 3 details the subprotocols, their coexistence, and the switch from one to the other one. Proofs of liveness and fairness are also given for the complete protocol. Section 4 presents the simulation results and discusses the efficiency and overhead of the protocol. Related works are presented in Section 5. Section 6 concludes.

Preliminaries

Different systems require different algorithms for performing atomic operations varying in complexity. This section describes the programming and system models which compose the required conditions for the protocol proposed.

Chemical Programming Model

The chemical model was initially proposed for a natural expression of parallel processing, by removing artificial structuring and serialisation of programs, focusing only on the problem logic. Following the chemical analogy, data are molecules floating in a solution. They are consumed according to some reaction rules, i.e., the program, producing new molecules, i.e., resulting data. These reactions take place in an implicitly parallel and autonomous way, until no more reactions are possible, a state referred to as inertia. This model was first formalised by GAMMA [START_REF] Banâtre | A parallel Machine for Multiset Transformation and its Programming Style[END_REF], in which the solution is a multiset of molecules, and reactions are rewriting rules on this multiset. A rule replace P by M if V consumes a set of molecules N satisfying the pattern P and the condition V , and produces a set of molecules M . We want to emphasise here that consumption is the only possible change of state a molecule can be subjected to: once it has been consumed, it vanishes from the multiset completely, meaning molecules are only created and deleted, never updated nor recreated. For the sake of illustration, let us consider the following chemical program made up of two rules applied on a multiset of strings, that counts the aggregated number of characters in words with more than two letters: let count = replace s :: string by len(s) if len(s) >= 2 in let aggregate = replace x :: int, y :: int by x + y in "maecenas", "ligula", "massa", "varius", "a", "semper" "congue", "euismod", "non", "mi"

The rule named count consumes a string if it is composed of at least two characters, and introduces an integer representing its length into the solution. The aggregate rule consumes two integers to produce their sum. By its repeated execution, this rule aggregates the sums to produce the final number. At runtime, these rules are executed repeatedly and concurrently, the first one producing inputs for the second one. While the result of the computation is deterministic, the order of its execution is not. Only the mutual exclusion of reactions by the atomic capture of the reactants is implicitly required by the paradigm.

A possible execution is the following. Let us consider, arbitrarily, that the first rule is applied on the first three strings as represented above, and on the last one. The state of the multiset is then the following:

"varius", "a", "semper", "congue", "euismod", "non", 8,

Then, let us assume, still arbitrarily, that the aggregate rule is triggered three times on the previously introduced integers, producing their sum. Meanwhile, concurrently, the remaining strings are scanned by the count rule. The multiset is then: 6, "a", 6, 6, 7, 3, 2, 21 . With the repeated application of the aggregate rule, the inertia is reached ("a" satisfies neither of the two rules' conditions but could be removed with a different rule): "a", 51 .

It is important to notice that the atomic capture is a fundamental condition. Let us simply assume that the same string is captured by different nodes running the count rule in parallel, then the count for a word may appear more than once in the solution, which would obviously lead to an incorrect result.

In the higher-order version of the chemical programming model [START_REF] Banâtre | Generalised Multisets for Chemical Programming[END_REF] any entity taking part in the computation is represented as a molecule (including rules), which unleashes an uncommonly high expressiveness, able to naturally deal with a wide variety of coordination patterns encountered in large scale platforms [START_REF] Banâtre | Chemical Programming of Future Service-oriented Architectures[END_REF]. However, these works remained mostly conceptual until now.

System Model

We consider a distributed system DS consisting of n machines which communicate by message passing. They are interconnected in such way that a message sent from a machine can be delivered, in a finite amount of time, to any other node in DS. At large scale, this can be achieved by relying on P2P systems, more specifically ones employing distributed hash table (DHT) communication protocols [START_REF] Stoica | Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications[END_REF][START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF]. They allow us to focus on the atomic capture of molecules without having to worry about the underlying communication.

Data and Rules Dissemination. In the following, we assume data and rules have already been dispatched to nodes. Note that any DHT algorithm or network topology may be used for this purpose. Even if the data and rules are initially held by a single external application, it can contact a node in the DHT and transfer it the chemical solution to be executed. The node which received the data scatters the molecules across the overlay according to the DHT's hash function. Molecules are routed concurrently according to DHT's routing scheme. The dissemination of rules can follow a similar pattern, or be broadcast into the network. The only difference is that rules can be replicated on several nodes to satisfy an increased level of parallelism. A more accurate discussion of the rules' distribution falls out of the scope of this paper. In the following, we simply assume every rule of the program is present on at least one node in the system. Discovery Protocol. In order for the reaction to happen, a suitable combination of molecules has to be found. While the details of this aspect are also abstracted out in the following, it deserves to be preliminarily discussed. The basic lookup mechanism offered by DHTs allows the retrieval of an object according to its (unique) identifier. Unlike the exact match functionality provided by DHTs, we require nodes to be able to find some molecule satisfying a pattern (e.g., one integer ) and condition (e.g., greater than 3), as stated in Section 2.1. This can be achieved by the support of range queries on top of the overlay network, i.e., mechanisms to find some (at least one) molecules falling within a range, provided the molecules can be totally ordered on some (possibly complex, multidimensional) criterion [START_REF] Schmidt | Squid: Enabling search in dht-based systems[END_REF]. This mechanism can be easily extended to support patterns and conditions involving several molecules. For instance, when trying to capture two molecules ordered in some specific ways, a rule translator -a unit which constructs the range query -, based on the given rule and the first molecule obtained, constructs the range query to be dispatched to the DHT. If matching molecules are found, the capture protocol will be triggered.

Fault tolerance. DHT systems inherently provide a fault-tolerant communication mechanism. If nodes crash, leave or join, the communication pattern will be preserved. On top of that, in this paper we assume there exists a higher-level resilience mechanism which prevents loss of molecules, such as state machine replication [START_REF] Schneider | Implementing Fault-Tolerant Services Using the State Machine Approach: a Tutorial[END_REF][START_REF] Lynch | Atomic data access in distributed hash tables[END_REF]. Each node replicates its complete state -the molecules and its current actions -across k neighbouring nodes. Thus, in case of its failure, one of its neighbours is able to assume its responsibilities and continue the computation.

Protocol

Here, the protocol in charge of the atomic capture of molecules is discussed. The protocol can run in two modes, based on two different sub-protocols: an optimistic and a pessimistic one. The former is a simplified sub-protocol which is employed while the ratio between actual and possible reactions is kept high. When this rate drops below a certain threshold, the latter, pessimistic sub-protocol is activated. While being the heavier of the two in terms of network traffic, this sub-protocol ensures the liveness of the protocol, even when an elevated number of nodes in the system compete for the same molecules.

Pessimistic Sub-protocol

Based on the three-phase commit protocol [START_REF] Skeen | A Formal Model of Crash Recovery in a Distributed System[END_REF], this sub-protocol ensures that at least one node wanting to execute a reaction will succeed. Molecule fetching is done in three phases -the query, commitment and fetch phases -and involves at least two nodes -the node requesting the molecules, called requester, and the nodes holding the molecules, called holders. Algorithms 3.1 and 3.2 represent the code run on these two entities, respectively, while Figure 1 delivers the time diagram of molecule fetching.

When molecules suitable for a reaction have been found (line 1 in Algorithm 3.1), the query phase begins (line 10). The requester sends QUERY messages asynchronously to all of the holders to inform them it is interested in the molecule. Depending on their local states, each of the holders evaluates separately the received message (lines 1-13 in Algorithm 3.2) and replies with one of the following messages: RESP OK (the requested molecule is available), RESP REMOVED (the requested molecule no longer exists) and RESP TAKEN (the molecule has already been promised to another node). Unless it received only RESP OK messages, the requester aborts the fetch and issues GIVE UP messages to holders, informing them it no longer intends to fetch their molecules (line 14 in Algorithm 3.1).

Following the query phase is the commitment phase, when the requester tries to secure its position by asking the guarantee from the holders it will be able to fetch the molecules (line 19 in Algorithm 3.1). It does so using COMMIT-MENT messages. Upon its receipt, each holder sorts all of the requests received during the query phase (line 14 in Algorithm 3.2) according to the conflict resolution policy (described below). Holders reply, once again, with RESP OK, RESP REMOVED or RESP TAKEN messages. A RESP OK response represents a holder's commitment to deliver its molecule in the last phase. Thus, subsequent QUERY and COMMITMENT requests from other nodes will be resolved with a RESP TAKEN message. Naturally, if a requester does not receive only RESP OK responses to its COMMITMENT requests, it aborts the fetch with GIVE UP messages.

Finally, in the fetch phase, the requester issues FETCH messages, upon which holders transmit it the requested molecules using RESP MOLECULE messages. From this point on, holders issue RESP REMOVED messages to nodes requesting the molecule.

Conflict Resolution. Each of the holders individually decides to which requester a molecule will be given. Since at least one requester needs to be able to complete its combination of molecules, all holders apply the same conflict resolution scheme (lines 20-27 in Algorithm 3.2). We here detail a dynamic and loadbalancing based scheme: each of the messages sent by requesters contains two fields -the requester's id and the number of reactions it has completed thus far. When two or more requesters are competing for the same molecule, holders give priority to the requester with the lowest number of reactions. In case of a dispute, the requester with a lower node identifier gets the molecule.

Optimistic Sub-protocol

When the possibility of multiple, concurrent reactions exists, the atomic fetch procedure can be relaxed and simplified by adopting a more optimistic approach. The optimistic sub-protocol requires only two stages -the fetch and the notification phases. Algorithm 3.3 describes the sub-protocol on the requesters' side, while Algorithm 3.4 describes it on the holders' side. The time diagram of the process of obtaining molecules is depicted in Figure 2.

Once a node has got information about suitable candidates, it immediately starts the fetch phase (line 1 in Algorithm 3.3). It dispatches FETCH messages to the appropriate holders. As with the pessimistic sub-protocol, the holder can respond using the three previously described types of messages (RESP MOLECULE, RESP TAKEN and RESP REMOVED ) as shown in Algorithm 3.4. One holder that replied with a RESP MOLECULE message, starts replying with RESP TAKEN messages to subsequent requests until the requester either returns the molecule or notifies it a reaction took place.

If the requester acquires all of the molecules, the reaction is subsequently performed, and the requester sends out REACTION messages to holders to notify them the molecules are being consumed. This causes holders to reply with RESP REMOVED messages to subsequent requests from other requesters. In case the requester received a RESP REMOVED message, it aborts the reaction by notifying holders with GIVE UP messages, which allows holders to give molecules to others.

Conflict Resolution. Given the fact that a node will most likely execute the optimistic sub-protocol in a highly reactive stage, there is no need for a strict conflict resolution policy. Instead, the node whose request first reaches a holder obtains the desired molecule. However, the optimistic sub-protocol does not ensure that a reaction will be performed in case of conflicts.

Sub-protocol Mixing

During its execution, a program typically can pass through two different stages.

The first one is a highly reactive stage, which is characterised by a high volume of possible concurrent reactions. In such a scenario, the use of the pessimistic sub-protocol would lead to superfluous network traffic, since the probability of a reaction's success is rather high. Thus, the optimistic approach is enough to deal with concurrent accesses to molecules. The second stage is the quiet stage, when there is a relatively small number of possible reactions. Since this entails highly probable conflicts between nodes, the pessimistic sub-protocol needs to be employed in order to ensure the advancement of the system. Thus, the execution environment has to be able to adapt to changes and switch to the desired protocol accordingly. Moreover, these protocols have got to be able to coexist in the same environment, as different nodes may act according to different modalities at the same time.

Ideally, the execution environment should be perceived as a whole in which the switch happens unanimously and simultaneously. Obviously, a global view of the reaction potential cannot be maintained. Instead, each node independently decides which protocol to employ for each reaction. The decision is first based on a node's local success rate denoted σ local , computed based on the success history of the last queries the node issued. In order not to base the decision only on its local observations, a node also keeps track of local success rates of other nodes. Each time a node receives a request or a reply message, the sender supplies it with its own current history-based success rate, stored into another list of tunable size. We denote σ the overall success rate, computed as the weighted arithmetic mean of a node's local success rate and the ones collected from other nodes. Finally, the decision as to which protocol to employ depends on the rule a node wishes to execute. More specifically, it is determined by the number of the rule's arguments, since the more molecules the rule needs, the harder it is to assure they will be grabbed: to grab r molecules, a node employs the optimistic sub-protocol if and only if σ r ≥ s, where r is the number of arguments the chosen rule has and s is a predefined threshold value. If the inequality is not satisfied, the node employs the pessimistic sub-protocol.

Coexistence. Due to the locality of the switch between protocols, not all participants in the system will perform it in the exact same moment, leading to possible inconsistencies in the system, where some nodes try to grab the same molecules using different protocols. In order to distinguish between optimistic and pessimistic requests, each requester incorporates a request type field into the message being sent. Based on this field, the node holding the conflicting molecules gives priority to nodes employing the more conservative, pessimistic algorithm. Although this decision discourages optimistic nodes and sets them back temporarily, it ensures that, in the long run, eventually a node will be able to grab the molecules it needs, since pessimism is favoured over optimism.

Sketch of Proof for Correctness and Liveness

The proposed protocol is a combination of the extensions of two existing protocols presented in [START_REF] Skeen | A Formal Model of Crash Recovery in a Distributed System[END_REF] and [START_REF] Lampson | Crash recovery in a distributed data storage system[END_REF]. These two protocols were initially introduced to guarantee resource transactions with only one holder. In our context, a requester can ask for several molecules owned by different holders.

These protocols must guarantee two properties: i) correctness: a molecule is used in only one reaction (as we consider that every reaction consumes all of the molecules entering it), and ii) liveness: if a node sends a request infinitely often, it will eventually succeed in capturing the molecules, provided the requested molecules are still available.

Correctness Proof. Correctness is easy to prove because both protocols we rely on have been proved to be correct independently. There are two cases of conflict between the two protocols. When an optimistic request arrives before a pessimistic one, the pessimistic request is aborted because the molecule has already been reserved by the optimistic requester. On the other hand, if a pessimistic request arrives first, the optimistic request is aborted in favour of the pessimistic one.

Liveness Proof. To prove the liveness property, we show that: i) if no successful reaction happens in the system, nodes eventually switch to the pessimistic protocol, ii) if several pessimistic requesters are in conflict, at least one reaction is not aborted, and iii) a node cannot see its reactions infinitely aborted.

Initially, and hopefully most of the time, nodes use the optimistic subprotocol for their requests. In case of a conflict between two optimistic requesters, both requests can easily be aborted. Consider the example where two concurrent requesters try to capture two molecules, A and B. If the first requester succeeds in grabbing A while the second captures B, then the two requests will be aborted.

For the pessimistic protocol, we define a total order based on the number of successfully completed reactions by a node and its id. In case of a conflict, all of the reactions might be aborted except for one -the reaction initiated by the node which comes first as per the total order. Because the total order is based on the number of successful reactions, if a node, in case of an abort, tries again infinitely to request molecules for its reaction, eventually, if the requested molecules are still available, the reaction will take place, given the fact that its position moves up the total ordering when other nodes succeed in executing their reactions.

When a request of a node is aborted, the node decreases its value of σ (see Section 3.3). With each message sent, the node includes the information about its local σ, and collects the values received with each message. If there are many conflicts during a certain period of time, all the more so if there is no successful reaction, the local σ of all of the nodes decreases. This effect leads to a situation where the value of the computed σ r for all new reactions will be lower than the threshold s, which will force the nodes to use the pessimistic protocol when initiating new requests, which insures the system's liveness.

When presenting algorithms for atomic capture, it is common to study their convergence times. However, any discussion about convergence when dealing with the chemical programming model is not feasible, as convergence itself, and thus the convergence time, is an application-specific property. However, the next section presents an evaluation of the proposed algorithm, and sheds some light on the subject.

Evaluation

Our protocol was simulated in order to better capture its performances. We developed a Python-based discrete-time simulator, including a DHT layer performing the random dissemination of a set of molecules over the nodes, on top of which the layer containing the capture protocol itself was built. At this layer, any message issued at step t will be received and processed by the destination node at time t + 1. Moreover, each time a capture attempt either led to a reaction, or an abortion, the node tries to fetch another set of r randomly chosen molecules. Finally, on the top layer, a simple chemical application was simulated.

All presented experiments simulate a system of 250 nodes trying to execute a chemical program containing a solution with 15 000 molecules and a straightforward rule which simply consumes two molecules without producing new ones. Such a simple program allows us to concentrate exclusively on evaluating the capture protocol itself, without having to deal with application-specific logic. In the same vein, reactions' duration are assumed negligible. Each simulation was run 50 times and the figures presented below show the values obtained by averaging result data from these runs. Keep in mind that the final steps of the executions shown in the figures represent, due to the effect of averaging, worstcase scenarios obtained during simulation. Simulations were limited to execute at most 500 steps, as later steps are not relevant. Experiment 1. Firstly we evaluate separately the performance characteristics of both sub-protocols. Figure 3 shows the averaged number of reactions left to execute at each step, until inertia, using only the optimistic mode, only the pessimistic mode, and the complete protocol with switches between protocols (using σ = 0.7), respectively. Note that a logarithmic scale is used. The figure shows that, using only the optimistic protocol, while we can see a strong decline in the number of reactions left at the beginning of the computation, i.e., when a lot of reactions are possible and that thus there are only few conflicts in the requests, it gets harder for nodes to grab molecules when this number declines.

In fact, the system is not even able, for most of the executions, to conclude the execution, as a few reactions left are never executed, always generating conflict at fetch time. When the nodes are all pessimistic, there is a steady, linear decrease in the number of reactions left, and the system is able to reach the inertia in a reasonable amount of time, thanks to the liveness ensured in this mode. For most steps, the mixed curve traces the exact same path as the optimistic one, which means that during this period the nodes employ the optimistic sub-protocol. However, at the end, the system is able to quickly finish the execution as an aftermath of switching to the pessimistic protocol. After the switch, it diverges from the optimistic one to mimic the pessimistic curve, exhibiting a benefit of a 42% performance boost compared to the performance of the pessimistic subprotocol. Finally, the theoretic optimum curve represents the minimal amount of steps needed to complete the execution in a centralised system. Comparing it to our protocol, we notice an increase of 166% in the number of steps needed to reach inertia. This is understandable, because there is usually a coordinator in centralised systems with which conflict situations can be circumvented, but it opens the door to serious defaults, such as single-point-of-failure or bottleneck problems.

Experiment 2. Next, we want to assess the impact of the switch threshold s on the overall performance of the system. from 0.1 to 0.9. As suspected, the curves overlap during most steps, most nodes employing the optimistic sub-protocol. The first curve to diverge is the one where the switch threshold is set very high, to s = 0.9. Because the system depicted by that curve did not fully exploit the optimistic sub-protocol, it is the last to finish the execution. Although slightly, the other curves start diverging at different moments, and, thus, complete the execution at different steps. Looking at Figure 4 brings us to the conclusion that, out of the five values tested for the switch threshold, s = 0.7 yields the best performance results in this particular scenario. Finding an overall optimal value for s falls out of the scope of this paper.

Experiment 3. Here we examine the properties of the process of switching from one protocol to the other. Figure 5 shows that, at the beginning of the execution, all of the nodes start off grabbing molecules by using the optimistic sub-protocol. The switch happens about half way through the execution. Around that time, optimistic nodes can no longer efficiently capture molecules, so they switch to the pessimistic sub-protocol. We observe that, due to exchange of local σ values, nodes in the system reach a global consensus rather quickly -for a system with 250 nodes, at most 15 steps are needed for all of the nodes to switch to the pessimistic protocol.

Experiment 4. Finally, we investigate the communication costs involved in the process. Figure 6 depicts the number of messages sent per cycle (where one cycle comprises 12 simulation steps), classified into two categories: useful messages (ones which led to a reaction, in black) and useless messages (ones which did not induce a reaction, in grey). We note that the protocol takes over the best properties of both of its sub-protocols. Firstly, it takes over the elevated percentage of useful messages of the optimistic sub-protocol. After the switch, the pessimistic protocol kicks in, bringing with it a decrease in the total number of messages. When compared to the communication costs of each of the sub-protocols separately (both depicted on the right-hand side of Figure 6), we see that switching from one protocol to the other reduces network traffic and improves scalability.

Related Works

The chemical paradigm was originally conceived for programs which need to be executed on parallel machines. The pioneering work of Banâtre et al. [START_REF] Banâtre | A parallel Machine for Multiset Transformation and its Programming Style[END_REF] provides two conceptual approaches to the implementation problem, in both of which each processor of a parallel machine holds a molecule and compares it with the molecules of all the other processors. A slightly different approach was proposed in the work of Linpeng et al. [START_REF] Huang | Implementation of gamma on a massively parallel computer[END_REF], where a program is executed by placing molecules on a strip, and then folding them over after each vertical comparison. Recently, Lin et al. developed a parser of GAMMA programs for their execution on a cluster exploiting GPU computing power [START_REF] Lin | Computing Gamma Calculus on Computer Cluster[END_REF]. All works mentioned exhibit significant speed-up properties, but the platforms experimented are rather restricted.

Mutual exclusion and resource allocation algorithms have been studied extensively. Nevertheless, most research focuses on sharing one specific resource, or critical section, amongst many processes [START_REF] Sanders | The information structure of distributed mutual exclusion algorithms[END_REF][START_REF] Chandy | The drinking philosophers problem[END_REF]. A basic solution for the k-out of-M problem was given by Raynal [START_REF]A Distributed Solution to the k-out of-M Resources Allocation Problem[END_REF]. This early work is a static permissionbased algorithm in which only the number of a predefined set of resources varies from node to node. In addition, the solution supposes a global knowledge of the system. On the other hand, an execution environment for chemical programs is a dynamic system in which nodes need to obtain different molecules, which can be thought of as resources, at different times.

The three-phase commit protocol was originally proposed as a crash recovery protocol for distributed database systems [START_REF] Skeen | A Formal Model of Crash Recovery in a Distributed System[END_REF]. Although, in its essence similar to the three-phase commit protocol, the goal of the optimistic sub-protocol proposed in this paper is to secure the liveness of the system by ensuring that at least one node will be able to complete its reaction.

Conclusion

While chemical metaphors are gaining attention in the modelling of autonomous service coordination, the actual deployment of programs following the chemical programming model over distributed platforms is a widely open problem. In this paper, we have described a new protocol to capture several molecules atomically in an evolving multiset of objects distributed on top of a large-scale platform. By dynamically switching from one sub-protocol to the other, our protocol fully exploits their good properties (the low communication overhead and speed of the optimistic protocol, when the density of reactants is high, and the liveness guarantee of the pessimistic protocol, when this density drops), without suffering from their drawbacks. These features are illustrated by simulation.

This protocol is part of an ambitious work which aims at building a distributed autonomic platform providing all the features required to execute chemical programs. This work is quite interesting in that it revisits classical problems in distributed systems, but with the large scale requirements, as well as the specificities of the chemical model, in mind. In this way, this paper tackles the mutual exclusion: in our context the liveness property is a system property while, more traditionally, liveness is a process' property. Among the directions planned for this work, we will refine the execution model, to, for instance, balance the load of reactions among the nodes of the platform. On the practical side, we plan to use these algorithms to actually leverage the expressiveness of the chemical paradigm for a workflow management system such as defined in [START_REF] Fernandez | Decentralized approach for execution of composite web services using the chemical paradigm[END_REF].

Algorithm 3 . 1 : 11 phase ⇐ query; 12 foreach molecule in combination do 13 dispatch

 31111213 Pessimistic Protocol -Requester. 1 on event combination found 2 QueryPhase(combination); 3 on event response received 4 if phase = query then 5 QueryPhaseResp(resp mol); 6 else if phase = commitment then 7 CommitmentPhaseResp(resp mol); 8 else if phase = f etch then 9 FetchPhaseResp(resp mol); 10 begin QueryPhase(combination) QUERY(molecule); 14 begin QueryPhaseResp(resp mol) 15 if resp mol = RESP OK then 16 Abandon(combination); 17 else if all responses have arrived then 18 CommitmentPhase(combination); 19 begin CommitmentPhase(combination) 20 phase ⇐ commitment; 21 foreach molecule in combination do 22 dispatch COMMITMENT(molecule); 23 begin CommitmentPhaseResp(resp mol) 24 if resp mol = RESP OK then 25 Abandon(combination); 26 else if all responses have arrived then 27 FetchPhase(combination); 28 begin FetchPhase(combination) 29 phase ⇐ f etch; 30 foreach molecule in combination do 31 dispatch FETCH(molecule); 32 begin FetchPhaseResp(resp mol) 33 add resp mol to reaction args; 34 if all responses have arrived then 35 Reaction(reaction args); 36 begin Abandon(combination) 37 phase ⇐ none; 38 foreach molecule in combination do 39 dispatch GIVE UP(molecule); Algorithm 3.2: Pessimistic Protocol -Holder.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Pessimistic exchanges. Fig. 2. Optimistic exchanges.

Fig. 3 .

 3 Fig. 3. Performance comparison of the protocol's variants.

9 Fig. 4 .

 94 Fig. 4. Execution time for different switch thresholds.

Figure 4 Fig. 5 .

 45 Fig. 5. Number of nodes employing optimistic and pessimistic protocols per step.

Fig. 6 .

 6 Fig. 6. Number of messages sent per cycle.


Melissa De Neve

Isabelle Sioen
email: isabelle.sioen@ugent.be

Polly E Boon

Claudia Arganini

Joanna Moschandreas

Jiri Ruprich

Lafay Lionel

Pilar Amiano

Davide Arcella

M Azpiri

Ellen ; Dtu

Van Klaveren

Rivm Verger

Afssa Walkiewicz

De Henauw

L Lafay

L Busk

T Christensen

L D'addezio

S Fabiansson

T Hirvonen

M Kersting

S Koulouridaki

K-H Liukkonen

M Oltarzewski

Papoutsou

I Rehurkova

L Ribas-Barba

L Serra-Majem

M Tornaritis

E Trolle

E Verger

A Westerlund

S De Henauw

Huybrechts

Harmonization of food categorization systems for dietary exposure assessments among European children

Keywords: Exposure, Exposure assessment, Total diet, Survey Additives/Contaminants: Lead, Metals -selenium, Colours Food Types: Beverages, Cereals and grain, Cooked foods, Ingredients exposure assessment, children, Europe, food categorisation, EXPOCHI, food 46 colours, lead, selenium, chromium 47 48

assessments for lead, chromium, selenium and food colours. For this, two food 30 categorisation systems were developed to classify the food consumption data in such a way 31 that these could be linked to occurrence data of the considered compounds. One system 32 served for the exposure calculations of lead, chromium and selenium. The second system 33 was developed for the exposure assessment of food colours. The food categories defined for 34 the lead, chromium and selenium exposure calculations were used as a basis for the food 35 colour categorisation, with adaptations to optimize the linkage with the food colour 36 occurrence data. With this work, an initial impetus was given to make user-friendly food 37 categorisation systems for contaminants and food colours applicable on a pan-European 38 level. However, a set of difficulties were encountered in creating a common food 39 categorisation system for 14 individual food consumption databases that differ in type and 40 number of foods coded and in level of detail provided about the consumed foods. The work 41 done and the problems encountered in this project can be of interest for future projects in 42 which food consumption data will be collected on a pan-European level and used for 43 common exposure assessments. 44 In the area of chemical food safety, food categorisation systems are used to link food 53 consumption data with occurrence data of adverse chemicals present in foods, such as 54 additives and contaminants. Such food categorisation systems are needed since occurrence 55 data and food consumption data are often not available at the same level of detail. 56 Food consumption data are mostly collected for different purposes (e.g. monitoring 57 population intakes of a range of macro-and micronutrients). Broad food categorizations that 58 are not at a very detailed level of food description may suffice for these purposes. However, 59

in the field of food safety, occurrence data of e.g. additives and contaminants can be 60 collected at a different level of detail (e.g. at food or ingredient level). Use of broad food 61 categories may then hamper the linkage with food consumption data. For example, additives 62 are often analysed or set in specific foods (sometimes at brand level) as described in 63 regulations, whereas trace metals are often analysed in raw foods, such as milk, meat, etc. 64

Linkage of these occurrence data to food consumption data requires a conversion of 65 consumption levels at food level to that at the level of raw ingredient [START_REF] Boon | 432 Harmonisation of food consumption data format for dietary exposure 433 assessments of chemicals analysed in raw agricultural commodities[END_REF]. In 66 addition are contamination or concentration data (e.g. for food colours) in general over-67 estimated when they are aggregated at broad food groups because trace elements for 68 instance are in general measured in foods that are supposed to contain the element or to 69 have a high content of this substance. Furthermore, the level of detail present in food 70 consumption surveys may be limited since subjects cannot always provide all the required 71 information of what they have consumed (definitely when retrospective dietary intake 72 assessment methods were used). Obtaining detailed information among children is even 73 harder as they have only a limited capacity to recall their own food intake and parents are 74 often unable to know what their child consumed at school or in the kindergarten. Therefore 75 food consumption data are often available without all the detailed information needed to 76 perform exposure assessments, what will result in an increase of the uncertainty in the 77 resulting exposure outcome. 78

To link food consumption and occurrence data to assess the exposure to chemicals 79 present in food, often foods consumed and those analysed are categorised in such a way 80 that the most optimal link between both databases is established. Different categorisation 81 systems are available for this, such as the categorisation system described in the SCOOP 82 Tasks Report 3.2.11 (European Commission 2004) Food categorisation is a crucial activity to allow for processing of food consumption data, 88 because it is not possible to interpret dietary data without aggregating individual food items 89 into food groups, either before (close-ended survey forms, e.g. food frequency questionnaire) 90

or after (open-ended forms, e.g. diary) the collection of food consumption data. 91

Categorisation of food items implies the identification of foods and their characteristics in 92 order to put the most similar items in the same category of the developed food categorisation 93 system [START_REF] Turrini | Food coding in nutritional surveys[END_REF][START_REF] Møller | LanguaL 2008 -The LanguaL Thesaurus[END_REF]. The experience in the food data processing 94 field has shown the necessity of developing different food categorisation systems related to 95 the objectives of the study [START_REF] Møller | LanguaL 2008 -The LanguaL Thesaurus[END_REF]. 96

From November, 1 st , 2008 until November, 30 th , 2009, EFSA funded a research project 97 aiming to create a relational network of different individual European food consumption 98 databases of children (aged 1 to 14 years) and to perform dietary exposure assessment 99 studies. Within this project, called EXPOCHI (Individual food consumption data and exposure 100 assessment studies for children), fourteen individual food consumption databases 101 representative for diverse regions/countries within Europe were harmonized in order to use 102 the consumption data for four specific exposure assessment studies, i.e. for lead, chromium, 103 selenium and a set of food colours. In total, 14 partners covering 13 European countries 104 participated in the project. Food consumption data was derived from 24-h dietary recalls and 105 dietary records. More information about the consortium, rationale, methods and design of this 106 project can be found in a separate paper [START_REF] Huybrechts | 475 Dietary Exposure Assessments for Children in Europe (the EXPOCHI project): 476 rationale, methods and design[END_REF]. 107

Within the project, the different scientific partners provided the food consumption 108 databases, whereas EFSA was responsible for the occurrence databases of the substances 109 under study. To be able to conduct the requested exposure assessment studies in a 110 standardized way, the 14 different consumption databases were harmonised by categorising 111 all food items in common food groups. To optimize and harmonize the food linking in the 112 EXPOCHI project, a food categorization manual was made. With the use of the manual, a 113 standardised procedure of linking different European consumption databases with one 114

European occurrence database per compound was established. Two food categorisation 115 systems were developed within the project: one for the exposure assessments to lead, 116 chromium and selenium and a second one for the food colours. In this paper, both 117 categorisation systems as well as the difficulties encountered are described and discussed. 118 119

Materials and methods 120

Two different food categorisation systems and manuals developed so that all partners categorised their food items in a standardized way. Two food 124 categorisation systems were developed, both described in detail in two extensive manuals: 125 an EXPOCHI-manual on Food Categorisation for (1) Lead, Chromium and Selenium and (2) 126

Food Colours (freely available on request). 127

To apply the two food categorisation systems, first a list of unique food items as coded in 128 the food consumption databases needed to be generated, containing -if available -details 129 such as preparation, fat content (e.g. for milk), etc. Each food item in this food list was 130 defined by a unique name (preferably in the local language as well as an English translation) 131 and a unique food code. Starting from this food list, food items needed to be categorised in 132 food groups, as defined in the food categorisation system by means of a data entry method 133 described in the manuals. For this it is important that the characteristics of the foods as 134 enclosed in the name of each food item are known in order to be able to categorise the foods 135 correctly. During the categorisation, no difference was made between foods eaten at home 136 or out-of-home, since those details were missing in most food consumption databases. 137

To develop the categorisation procedure and set up the manuals, preliminary samples of 138 the 14 food lists obtained from the national food consumption databases and received from 139 each partner in the EXPOCHI-project were explored to foresee problems and difficulties that 140 partners would encounter during the categorisation work. These possible problems and 141 difficulties were listed in the manuals and solutions were provided. Moreover, due to these 142 food list samples, examples of food items from all geographical regions under study (e.g. 143 specific local food items) could be included in the manuals. The manuals were continuously 144 updated during the project to address all difficulties experienced during the categorisation 145 work in the participating countries. 146

To illustrate the results of the food categorisation work, data from four different individual 147 food consumption databases are presented covering a North-European country (Sweden), a 148

West-European country (Belgium), a South-European country (Italy) and an East-European 149 country (Czech Republic). For Sweden, the data were collected in 2003 by a nationwide food 150 consumption survey conducted among children aged 3 to 4 and 7 to 13 years (Enghardt-151 Barbieri et al. 2006). The Swedish consumption databases consisted in total of 1548 different 152 food items. The Belgian food consumption data used in this project were collected in 2002-153 2003 from a representative sample of Flemish children aged 2.5 to 6.5 years (Huybrechts et 154 al. 2008) 2004 with children aged 4 to 14 years [START_REF] Ruprich | Individual food 489 consumption -the national study SISP04[END_REF]. This database counted 515 159 different food items, primarily aggregated for the national total diet study focused mainly on 160 contaminants. For more details on the databases see [START_REF] Huybrechts | 475 Dietary Exposure Assessments for Children in Europe (the EXPOCHI project): 476 rationale, methods and design[END_REF]. 161 162 1. Lead, chromium and selenium 163 The food categorisation system for lead, chromium and selenium was based on the food 164 categorisation system described in the SCOOP Tasks report 3.2.11 (European Commission 165 2004). The groups mentioned in this SCOOP report are based on definitions from the Codex 166 General Standard for Food Additives (GSFA) developed by the Codex Alimentarius 167

Commission (Codex Alimentarius Commission 2009). The document describes the 168 conditions under which permitted food additives may be used in all foods, whether or not 169 they have previously been standardised by Codex. However, for the EXPOCHI-project, those 170 definitions needed to be adjusted since foods in consumption databases are generally 171 mentioned 'as eaten', whereas the definitions found in GSFA are mentioned 'as product in 172 the food manufactory'. 173 174 1.1.

Main group and subgroups 175

The lead, chromium and selenium categorisation system consisted of four hierarchical 176 grouping levels: main group (MG), subgroup 1 (SG1), subgroup 2 (SG2) and subgroup 3 177 (SG3) and one descriptor: special code (SC). This structure is in accordance with Turrini 178 [START_REF] Turrini | Food coding in nutritional surveys[END_REF], distinguishing two types of food coding variables: hierarchical codes and 179 crosswise codes. Hierarchical codes aim at identifying the type of products (food group, 180 subgroup), while crosswise codes are dedicated to the description of the characteristics 181 (packaged or not, fresh or preserved, etc.). 182

The hierarchical categorisation process applied in this project was divided into two 183 consecutive steps. Firstly, a main group was defined per food item in the food list. These 184 main food groups and their definitions originated from the GSFA, describing 16 main groups 185 (Codex Alimentarius Commission 2009). Two extra main groups 'Vegetarian meat and fish 186 substitutes (MG17)' and 'Miscellaneous: foods that cannot be placed in categories (MG18)' 187 were added to make it possible to categorise all food items occurring in the national food 188 consumption databases. Table 1 lists all main groups defined in the food categorisation 189 system for the lead, chromium and selenium exposure calculations. In the EXPOCHI manual, 190 the GSFA definitions were reported, including extensions of the definitions to clarify the main 191 groups more clearly. A short list of food items to be included in a certain food group and of 192 some to be categorised elsewhere illustrated these definitions. The first step was complete 193 when all food items had been assigned to one of the 18 main groups. 194

The second step consisted of categorization at subgroup level, which included a refining 195 of the main group categorisation by means of maximum three subgroup levels: SG1, SG2 196 and SG3. Figure 1 shows an example of subdividing MG 10 (Eggs and egg products) into 197 four different groups on the level of SG1 (10.1,10.2,10.3 and 10.4) and two different groups 198 on the level of SG2 when considering SG1 = 10.1 (i.e. fresh eggs): 10.1.1 and 10. 1.2. 199 As is shown in Figure 1, the explanation per main group began with a brief summary 200 based on which it was decided to which subgroup a food item belonged. This was followed 201 by a diagram demonstrating the structure of all subgroups within one main group. Every 202 decision taken during the categorisation work was checked by the given definitions. 203

It was not always possible to categorise each food item at all three subgroup levels (SG1, 204 2 and 3), due to two reasons: (1) not all main groups were subdivided into a second and third 205 subgroup level, and ( 2) not all national food consumption database provided enough detail 206 for each food item to be able to categorise it at a next (or lower), more detailed, subgroup 207

level. An illustration of this can be found in the example given in Figure 1, for SG2 of the 208 group 'fresh eggs' (10.1). Most food consumption databases did not include details on 209 whether eggs originated from indoor or outdoor reared eggs. Therefore, in those cases, the 210 categorisation stopped at the level of SG1. 211 212

Special code 213

An extra variable 'special code' (SC) was added as a descriptor for five main groups to 214 add relevant information that was not included in the categorisation system based on MG, 215 SG1, SG2 and SG3. This special code indicated the presence of a specific component (e.g. 216 chocolate filling) or a physical state (e.g. powdered form), and was applied within the 217 following five main groups: MG4 (fruits, vegetables, seaweed, nuts and seeds), MG7 (bakery 218 wares), MG9 (fish, fish products, molluscs, cephalopods, crustacean and echinoderms), 219 MG13 (foodstuff intended for particular nutritional use) and MG14 (beverages). If food items 220 contained more than one component/filling a combination of numbers was used by placing 221 the numbers in ascending order. A special code indicating the presence of soy in a food was 222 used for all main groups. Database. Efforts were made to keep the anticipated major food contributors for lead, 236 chromium and selenium in different food categories and, at the same time, to minimise the 237 need for the reclassification of food descriptors. This resulted in a list of 42 communal food 238 groups (Table 3) making it possible to link the food consumption data to the occurrence data. 239

The main group and subgroup together with the special code were subsequently re-240 organized, as well as certain food items in such a way that the concentration data per 241 communal food group were representative for the food items in those food groups. 242 243

Food colours 244

The food categorisation system as specified in the Council Directive 94/36/EC (European 245

Commission 1994) was used to develop a system to classify all food items present in the 246 different national food lists in order to perform dietary exposure assessments for food colours. 247

This food colour classification system was tuned to the Flavourings, Additives and food 248 Contact materials Exposure Task (FACET) project (http://www.ucd.ie/facet/). Occurrence 249 data were provided by EFSA according to this categorization system. 250

Within the EXPOCHI-project, 41 different food colours were considered for exposure 251 assessment. All, except lycopene, could be approached by one categorisation system based 252 on 84 different food groups (Table 4), partly based on the Council Directive 94/36/EC and 253 partly developed particularly for this project using the information of the FACET project (i.e. 254 to further divide the category 'all other foodstuff' in more detailed categories) (European 255

Commission 1994; [START_REF] Oldring | Exposure to Substances from Food Contact Materials 486 and an Introduction to the FACET Project[END_REF]). Of the 84 food groups, 16 were not taken into 256 account within the EXPOCHI-project because the age group addressed in the exposure 257 assessment to food colours was limited to children aged 1 up to 10 years (e.g. food groups 258 like 'spirituous beverages', 'whisky', 'liqueurs' were irrelevant for this age group). The 68 food 259 groups that were considered in the EXPOCHI-project are marked in Table 4. 260 As stated, a separate food classification system was developed to classify foods for the 261 lycopene exposure assessments. Since naturally occurring lycopene was not considered in 262 the exposure analyses, the system included only food groups in which lycopene could be 263 added as an additive. The food groups differed from those used for the other food colours on 264 the level of aggregation. For example, lycopene is permitted in all types of bread, whereas 265 for the other food colours, only malt bread was considered (see Table 4 and5). Compared to 266 the general food colour categorisation system, fewer food groups were needed to classify the 267 food items for lycopene, since addition of lycopene is only permitted in a limited number of 268 food groups (in total 33 food groups; see Table 5). 269

The food list including the main groups and subgroups of the food classification 270 system for lead, chromium and selenium formed the starting point for the food colour 271 classification system. Around half of the food items occurring in the food lists from the 272 different EXPOCHI-partners belonged to a MG-SG combination that could be re-273 coded as a whole in one single food colour group. For example, all food items in the 274 food group 10.1 'Fresh eggs' (see Figure 1) belonged to the food colour group 0 'No 275 food colours'. For the food items belonging to such a MG-SG-combination, the re-276 coding into the food colour categorisation system could be performed automatically.

277

In contrast, for the other part of the food items, the categorisation into the food colour 278 groups was less straightforward, because food items within a similar MG-SG- 3 shows the percentage per country of food items classified in each communal 295 food group for the lead, chromium and selenium exposure assessment. These results show 296 first of all that not all 42 communal food groups were needed to classify all food items. For 297 example, the communal groups 9 'Food supplements' and 34 'Other food for special dietary 298 uses' were used by two of the four countries, whereas group 26 'Other seafood' was only 299 used by Italy. Another difference was the percentage of food items in communal food group 2 300 'Vegetables'. This percentage was low for the Italian database compared to the other 301 countries, whereas the percentage of food items in group 3 'Waters' was high in Italy. 302

Results are also shown for the lycopene categorisation based on these four national 303 consumption databases (Table 5). In this paper, we described the food categorisation systems that were developed and 312 applied to categorise 14 different food European consumption databases of children in the 313 ages of 1 up to 14 years in order to prepare them for an exposure assessment study of three 314 contaminants (lead, chromium and selenium) and a set of food colours. Although different 315 food categorisation systems already exist [START_REF] Møller | LanguaL 2008 -The LanguaL Thesaurus[END_REF], none could be applied 316 without any modification. The work described in this paper illustrates that food categorisation 317 systems can differ substantially depending on the compound under study, as described 318 earlier [START_REF] Turrini | Food coding in nutritional surveys[END_REF]): the food classification system developed for the contaminants differed 319 on many aspects from the one developed for food colours (e.g. number of food groups, 320 composition of food groups, number of food items per food groups). 321

The unique aspect of the food categorisation work performed in this project is that food 322 items present in 14 different consumption databases for European children were categorised 323 in a uniform way, making it possible to estimate the exposure to the chemicals under study in 324 a uniform way. The food consumption databases used in this study were derived from 325 different studies performed at the national / regional level. These databases differed on many 326 aspects, including dietary assessment methods used and age ranges addressed. Another 327 important difference, which affected the food categorisation (and consequently the resulting 328 exposure calculations), was the way in which the primary dietary information was recorded 329 and aggregated into food items and (sub) food groups. Due to this, the level of detail available of the foods present in the national / regional consumption databases differed 331 greatly. The examples used in this paper to illustrate the approach show that the different 332 food consumption databases differed much in the number of food items entered. For 333 example, the Italian and Swedish databases contained up to three times more food items 334 than the Czech database. The number of food items gives an indication of the level of detail 335 present in the database. For example, in some databases 'milk' can be the only entry, 336 whereas in other databases milk can be entered as 'milk, skimmed', 'milk, semi-skimmed' 337 and 'milk, whole'. Moreover, some food consumption databases contained details as brand 338 names (e.g. of confectionary), additives (e.g. yoghurt with or without sugar), etc. whereas 339 others did not. In fact, the attention paid either to specific food categories (e.g. supplements) 340 or to specific food components could affect the level of food description for the corresponding 341

groups. An additional remark concerns whether the transformation from composite food to 342 ingredients was performed or not. This operation could lead to vary the number of food 343 items. Overall, the more details available, the better and more detailed the categorisation 344 work could be performed. 345

To address the heterogeneous databases, two detailed manuals were developed, which 346 contain explanations and examples aiming to minimize the chance of misclassifications. 347

Difficulties during the project were discussed, resulting in updated version of the manuals. 348

These manuals address many differences in food items entered in national / regional 349 databases and can be very valuable when developing food categorisation systems to be 350 used in pan-European food consumption surveys. The development of such a food 351 consumption survey is one of EFSA's long-term objectives (EFSA, 2009). 352

To be able to link the categorised food consumption data with the lead, chromium and 353 selenium occurrence data received from EFSA, foods categorised according to the 354 hierarchical food categorisation system were generalised to 42 communal groups. During 355 this process, certain details on the foods entered in the different regional/national food 356 consumption databases were inevitably lost. Due to this, the link between the foods 357 consumed and those analysed will not be optimal, affecting negatively the representativity of 358 the ensuing exposure results. It is therefore important, for an optimal exposure result, that 359 both the food consumption and occurrence data are categorised at the highest level of detail 360 possible. In practice however, often either the consumption data or occurrence data are 361 categorised at a level that makes an optimal link not feasible. During the interpretation of the 362 exposure results obtained with such data, this should be taken into account. If for instance 363 the level of coding is too low there is a danger of assuming that all foods within that category 364 contain the highest level. Alternatively it could be assumed that all foods contain average 365 levels and so missing the true high-level individual. 366 Also the food categorisation system developed for the exposure assessments to food 367 colours, started from the detailed, hierarchical system developed based on the food 368 categorisation system described in the SCOOP Tasks report 3.2.11 (European Commission 369 2004). However, the food groups needed to be recoded to the groups specified in the 370 Council Directive 94/36/EC (European Commission 1994). In the first step, scripts could be 371 used to reclassify automatically about half of the food items in the food lists from the 372 hierarchical system to the groups of the food colour system. This was a time-saving 373 procedure and it reduced the chance of mistakes (like typing errors). 374

Next, it should be noted that the precision of matching occurrence and consumption 375 categories can have a major impact on the uncertainties introduced into the model. For the 376 food colour exposure assessment, the most important source of uncertainty was the use of 377

'maximum permitted level' data in the worst case scenario, resulting in an overestimation of 378 the exposure, also due to the use of very broad food groups. Also for the other components 379 (lead, chromium and selenium), it is very likely that the exposure was overestimated due to 380 the use of broad food groups. How large this overestimation is, is difficult to predict, since no 381 information on the specific foods that were analysed was available. However, the approach 382 used in this project is the best approach presently possible and is a major step forward 383 compared to national risk assessments performed in the past. 384

This issue needs to be taken into consideration when making national comparisons since 385 the level of detail in food description will vary between surveys. Therefore, compromises are 386 needed to be made between loss of precision caused by including as many countries as 387 possible or improved accuracy but only within those countries that have highly detailed food 388 descriptions. Additionally, future exposure assessment studies should focus on the 389 development of a total diet study based on the core foods method which allows to get 390 contamination data more in line with food really consumed. 391

Overall, the authors believe that they have a positive bias in the calculation method, that is a 392 conservative bias. The reason for this is that the occurrence values are often based on 393 targeted sampling of problem products that will influence the overall mean upwards. As 394 described in the manuscript, the authors also did some considerable adjustment to exclude 395 typical adult products rarely consumed by children. 396

Although the limitations mentioned above should always be considered when interpreting 397 results derived from the EXPOCHI project, this project delivered important data for analyses 398 in the field of exposure assessments in children in Europe, and was a first and valuable step 399 that needed to be done to proceed from a country specific view to a European view. 400

Acknowledging the shortcomings of the current system, EFSA has three main activities 401 under way to address this: (1) the development of a harmonised food description and 402

categorisation system that at least should be able to translate different approaches into a 403 (3) and finally the development of a guideline for a total diet 405 study approach to get baseline occurrence data. However, these steps are part of a long-406 term strategy that will not happen overnight. 407

Conclusion 408

In this paper we describe two food categorisation methodologies, one for contaminants 409 and one for food colours. The difficulties associated with the creation of a single food 410 categorisation system for several heterogeneous food consumption databases, and possible 411 solutions, were highlighted. The work performed illustrates that food categorisation systems 412 differ depending on the compound under study and that the categorisation work is influenced 413 by the level of detail present in the food consumption databases. Without good planning of 414 objectives for food consumption studies and effort devoted to concerted food categorisation 415 activities in places where occurrence data are produced or collected, the considerable lose of 416 information and higher uncertainty of exposure assessment have to be expected. 417

Nevertheless, the developed systems are an important step forward to reach the goal of a 418 pan-European food categorisation system to perform harmonised exposure assessments at 419 a European level. The best way forward will be by means of a common categorization 420 system based on hierarchical systems for both, food consumption and also concentration 421 → Fresh in-shell eggs are not expected to contain additives. However, colours may be used for decorating, dyeing or stamping the exterior surfaces of shell eggs.

Variable MG = 10 Variable SG1 = 1

Eggs from indoor reared hens

→ Hens reared in battery cages

Variable MG = 10 Variable SG1 = 1 Variable SG2 = 1 Eggs and egg products If more details are available for food items that meet the definition of "10.1", they should be checked for the following characteristics:

• If known from indoor reared hens • If known from outdoor reared hens:

If more details are available for food items with a "MG" = 10, they should be checked for the following characteristics:

• Fresh eggs • Egg products produced from fresh eggs: liquid, frozen or dried , go further with this chapter. shell eggs are not expected to contain additives. However, colours may be used for decorating, dyeing or ms that meet the definition of "10.1", they should be checked for the following If more details are available for food items with a "MG" = 10, they should be checked for the following characteristics:

•
F

  children were used to conduct harmonised dietary exposure 29

5

  Within the EXPOCHI-project, it was the aim to conduct harmonised dietary exposure 122 assessment in children living in different European countries. Therefore, procedures were 123

279

  combination did not belong to a similar food colour group. For example, the food 280 items classified in 9.4.1 'Fish canned in oil' could belong to different food colour 281 groups (FCG): fish roe belongs to FCG=16; surimi belongs to FCG=15 and fish past 282 belongs to FCG=12. This second step of the classification was performed according 283 to guidelines included in the second categorisation manual. results of the food categorisation, data are shown for four of the 14 288 different countries: Belgium, Italy, Sweden and Czech Republic; and for two categorisation 289 systems: the one for lead, chromium and selenium and the one for lycopene. A first important 290 remark is the huge difference in the total number of food items entered in the different food 291 consumption databases. The Czech databases contained the least number of food items 292 (n=515), followed by Belgium with 1056 different food items, Italy with 1530 and Sweden with 293 1548 food items. 294

  the dissemination of guidelines developed on how to harmonise food 404 consumption data collection;

Figure 1 .

 1 Figure Caption: 500

  Preserved eggs e.g. salt-cured, alkaline treated • Egg-based dessert If no more details are available: the final code is MG = 10 ! If not known fresh eggs or egg product = If more details are available for the food items in MG = 10: eggs and egg products, go further with this chapter. shell eggs are not expected to contain additives. However, colours may be used for decorating, dyeing or stamping the exterior surfaces of shell eggs. the definition of "10.1", they should be checked for the following If known from indoor reared hens: → 10.1.1 If known from outdoor reared hens: → 10.1.2 If more details are available for food items with a "MG" = 10, they should be checked for the following characteristics: If no more details are available: the final code is MG = 10 ! If not known fresh eggs or egg product = MG = 10 and SG1 = 1 (fresh) see page 108

  used to assess the exposure to different 83 mycotoxins and the Concise European Food Consumption Database developed by the 84 European Food Safety Authority (EFSA) (EFSA 2008), which has been used to assess the 85 exposure to numerous chemicals, such as ochratoxin A (EFSA, 2006), arsenic (EFSA,

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

  and consisted of 1056 different food items. The Italian food consumption data were 155

	157	2009). The Italian food consumption databases consisted of 1530 different food items. In
	158	Czech Republic, a food consumption survey was conducted between November 2003 and
		F o r
		P
		e
		e r
		R
		e
		v i e
		w
		O n l
		y
	156	collected during the period of 2005-2006 for children aged 1 to 10 years (Leclercq et al.
		6

  Table 2 lists all special codes that were applied in the framework of 223 During the project, it emerged that EFSA was not able to provide the occurrence data for the 227 contaminants lead, chromium and selenium categorised according to the food categorisation 228 system described in the SCOOP Tasks report 3.2.11 (European Commission 2004) but only 229 according to the categorisation used in EFSA's Concise Food Consumption Database (EFSA 230 2008). Due to the huge number of occurrence data resulting from food testing in the different 231 Member States (94,126 for lead, 23,750 for chromium and 47,858 for selenium), EFSA 232 considered it inconvenient to reclassify all food descriptors in the occurrence database 233 according to the SCOOP system. A link was therefore needed between the newly developed 234 food categorisation system and that of EFSA's Concise European Food Consumption 235

	226	1.3.	Link with occurrence data of lead, chromium and selenium
			F o r
			P
			e
			e r
			R
			e
			v i e
			w
			O n l
			y
	224	this project.
			8

  Table 5 indicates that some food groups were not needed 304 by any of the four countries, such as groups 31 'Salmon substitutes' and 37 'Edible cheese 305 and edible casings'. The table also indicates that the percentage of food items to which 306 lycopene could be added differed considerably between the different databases, being 307 around 40% in Belgium, 31% in Italy and Sweden, and 22% in Czech Republic.

	308
	309
	310	Discussion
	311

Table 1 .

 1 Food groups used for the classification of food items to assess the exposure to lead, chromium

	1
	and selenium
	MG Main group
	1	Dairy products and analogues (incl. dairy based ices), excluding products of food category "2. Fats and oils, and fat emulsions" e.g. butter
	2	Fats, oils and fat emulsions (incl. imitation milks)
	3	Edible ices (excl. dairy based ices)
	4	o r Fruits and vegetables (including mushrooms and fungi, roots and tubers, pulses and legumes, and aloe vera), seaweeds, and nuts and seeds
	5	Confectionary	P
	6	e r e Cereals and cereal products (cereal grains, tubers, roots, pulses and legumes) (no bakery wares)
	7 8 9 10 Eggs and egg products Bakery wares Meat, meat products, poultry and game R e v Fish, fish products, molluscs, cephalopods, crustaceans and echinoderms (MCCE) i e w 11 Sweeteners (incl. honey)
	12 Salt, spices, soups, sauces, salads and protein products 13 Foodstuff intended for particular nutritional uses 14 Beverages (excl. dairy products, imitation milks)	O n l y
	15 Ready-to-eat savouries
	16 Composite foods
	17 Vegetarian meat and fish substitutes
	18 Miscellaneous -foods that cannot be placed in categories
	2
				1

Table 2 .

 2 The special codes used for the classification of food items to assess the exposure to lead,

		Food Additives and Contaminants	Page 20 of 28
	chromium and selenium
	4
	Special code	Component or physical state
	1	Fruit (filling)
	2	Nuts/seeds (filling) (incl. coconut)
	3	Vegetables (incl. olives)
	4	Pulses/legumes
	5	Chocolate (filling)
	6	Dairy (filling)
	71	Powdered form
	72	Concentrated form
	73	Dissolved from powder or concentrate / Original form
	8	No filling / no pieces
	91	Fish
	92	Molluscs
	93	Crustaceans
	94	Cephalopods
	95	Echinoderm
	96	Reptiles: e.g. crocodile, snake
	97	Amphibian: e.g. frog
	900	Soy
	999	Not known
	5

http://mc.manuscriptcentral.com/tfac Email: fac@tandf.co.uk

Table 3 .

 3 The communal food groups used in the food categorisation system for lead, chromium and selenium to link food consumption data to occurrence 6 data of these chemicals combined with the percentage of food items per food group for four different countries

	7
	Communal food
	group	Name

http://mc.manuscriptcentral.com/tfac Email: fac@tandf.co.uk http://mc.manuscriptcentral.com/tfac Email: fac@tandf.co.uk

Table 4 .

 4 Food groups used for the classification of food items to assess the exposure to food colours

	9
	10	(exc. lycopene)
		Code	Food group name

Table 5 .

 5 Food groups used for the classification of food items to assess the exposure to

	lycopene
	Code Food group name	Belgium	Italy (%);	Sweden	Czech
			(%);	n=1530	(%);	Republic
			n=1056		n=1548	(%); n=515
	0	No lycopene	60.61	69.54	68.73	77.48
	19 Non-alcoholic flavoured drinks	3.60	1.70	2.33	1.17
	20 Candied fruits and vegetables, Fruit Mustard	0.19	0.20	1.23	0.58
	21 Confectionery	0.95	5.88	1.29	1.36
	22 Decorations and coatings	0.00	0.00	0.06	0.00
		Fine bakery wares (e.g. viennoiserie, biscuits,
	23	cakes and wafers)	9.19	5.95	6.40	4.47
	24 Edible ices	0.19	0.07	0.58	0.00
	25 Flavoured processed cheese	0.57	0.52	0.39	0.78
	26 Desserts including flavoured milk products	6.34	3.59	5.94	2.33
		Sauces, seasonings (for example, curry
		powder, tandoori), pickles, relishes, chutney
	27	and picalilli	2.37	0.52	3.75	3.30
		Jams jellies and marmalades as mentioned in
	28	directive 79/693/EC and similar fruit preps	1.42	0.65	1.16	0.78
	29 Fish paste and crustacean paste	0.00	0.00	0.06	0.39
	30 Pre-cooked crustaceans	0.09	0.07	0.13	0.00
	31 Salmon substitutes	0.00	0.00	0.00	0.00
	32 Surimi	0.00	0.00	0.00	0.00
	33 Fish roe	0.00	0.00	0.13	0.19
	34 Smoked fish	0.38	0.07	0.39	0.39
		Snacks: extruded or expanded savoury snack
	35	products	1.33	0.13	0.90	0.97
		Snacks: other savoury snack products and
	36	savoury coated nuts	0.38	0.65	0.26	0.39
	37 Edible cheese and edible casings	0.00	0.00	0.00	0.00
	38 Complete formulae for weight control	0.00	0.00	0.00	0.00
		intended to replace total daily intake or an

http://mc.manuscriptcentral.com/tfac Email: fac@tandf.co.ukFood Additives and Contaminants

Code

Food group name EXPOCHI*