Olivier Baldellon
email: baldellon|roy|fabre@laas.fr

Matthieu Roy

Jean-Charles Fabre

Out-of-order Evaluation of Timed Petri Nets for Distributed Monitoring

Modern embedded systems for safety critical applications, found in planes or cars, are based on real-time distributed networks and require high level of robustness, reliability and adaptability. In order to complement static off-line validation of such systems, this paper introduces a novel approach for online verification of behavioral properties expressed as a sub-family of timed Petri nets. We show that, for the subclass of acyclic safe nets, whose expressivity matches real-time systems constraints, it is possible to define a commutative and associative operation on states that enables out-of-order evaluation of the state of the Petri net, and thus a fully distributed evaluation of the behavior of the system under supervision. Additionally, when provided with a mapping between events and nodes of the distributed system, we show how to efficiently distribute the monitoring system on top of the applicative system, and provide algorithms for local evaluation and merging of information in order to detect as soon as possible when the system deviates from its specification.

I. Introduction

The current and future evolution of embedded systems shifts them from the traditional small sized and centralized machines to widely distributed ones with timing constraints.

In the different means to provide dependability, monitoring systems and applications states seems a suitable and necessary tool to take into account at runtime many factors that could not be fully verified before execution. Indeed, the inherent complexity and unpredictability of distributed systems in interaction with their environment hardens the task of offline verification, due to components composition issues and high complexity.

Monitoring a system is the first step to be taken when programming dependable systems, since it is required to detect that something has failed in the execution, enabling possible reconfiguration of the system.

Alas, on-line monitoring of complex, distributed and real-time systems is a highly complex task that, to our knowledge, has not yet been fully tackled. On-line monitoring of applications (distributed or not) in a centralized way has been an active research domain since few years now (see, e.g., [START_REF] Robert | On-line monitoring of real time applications for early error detection[END_REF], [START_REF] Meredith | Runtime verification with the rv system[END_REF]), but these approaches cannot handle the case of systems that are both distributed and realtime. An interesting paper [START_REF] Jahanian | Runtime monitoring of timing constraints in distributed real-time systems[END_REF] proposed some mechanisms for distributed monitoring of simple properties, but this approach is not easily generalizable for more complex properties, as for example those with logical "or".

This paper introduces a new approach that allows to monitor in an efficient and fault tolerant way properties expressed with arc timed Petri nets. The main idea is to execute the Petri net on the fly, as soon as system events are received, by aggregating partial executions of Petri nets. We will show in the paper that this aggregation provides correct results independently of how (in which order) this aggregation is done. This out-of-order evaluation of Petri nets, which is the main contribution of our work, is an essential feature for enabling distributed run-time evaluation of properties expressed as Petri nets.

This paper is organized as follows. In Section II, we define the model of Petri nets used to express distributed and real time properties, and we express the link between system activity and the properties to be monitored. Then we present the semantics of our model, and define the failure model in Section III. Section IV presents an algebra that enables out-of-order execution of a Petri net, allowing speculative transition firings. Section V describes how to deploy the monitoring mechanisms on a distributed system and how to efficiently verify a property at runtime. Section VI compares our strategy with existing works.

II. System Model

A behavioral property on a system can be expressed with different formalisms, such as logics, (temporal) automata, Petri nets, etc. In this work, we focus on distributed and temporal properties, and we will suppose in the remainder of the paper that we are provided with a behavioral property expressed using a tailored version of arc-timed Petri nets.

First we define in Section II-A the Petri net model used for specifying distributed real-time properties. In Section II-B we refine the hypotheses made on the system and the model. The notion of timed event sequences that will be used to describe the observation done by monitors is explained in Section II-C. An example will be given and explained in Section II-D.

A. Acyclic Safe Nets

We will assume in this paper that the reader is familiar with Petri net formalism. Let us first recall some basic definitions on arc-timed Petri nets. In this paper the set B A will be the set of functions from A to B. Definition 1 -Arc-Timed Petri Net An arc-timed Petri Net is tuple (P, T, • (•), (•) • , M 0 , I), where P is a finite set of places, T is a finite set of transitions, M 0 is the initial marking (a function from the set of places to the set {0, 1}, i.e., M 0 ∈ M + , where M + = {0, 1} P is the set of markings), • (•) and (•) • are the backward and forward incidence marking functions of (M + ) T , and I a function that associates to each arc between a place and a transition a time interval.

We say that there is an arc between a place p and an transition t if p ∈ • t. We will use in this paper the following notations: for every marking m and for every place p, we have

"p ∈ m iff m(p) = 1", • p = {t | p ∈ t • }, p • = {t | p ∈ • t}, and • (•) is the transitive closure of • (•) on P ∪ T .
An arc-timed Petri net is a classical Petri net where arcs between places and transitions are labelled with time intervals. Intuitively, a token can fire a transition if and only if the duration between the token's creation in the place and the firing of the transition belongs to the time interval that labels the arc between the place and the transition. For a more formal definition of the semantics, the reader can refer to [START_REF] Boyer | On the compared expressiveness of arc, place and transition time Petri nets[END_REF] where different formalisms of timed Petri nets -including arc-timed Petri nets -are compared.

Definition 2 -Enabled and Fireable Transitions

Let M be a marking, a transition t is said to be enabled if ∀p ∈ • t, M (p) = 1. A transition t is said to be fireable if 1) t is enabled 2) for any p ∈ • t, the token in place p stayed in p during a time included in I(p, t).

We will now introduce a new subclass of Petri nets, a generalization of occurrence nets that will be called acyclic safe nets. In the next definition, a 1-safe Petri net is a net whose all reachable markings contain at most one token per place; moreover an acyclic Petri net is a net such that • (•) is irreflexive, in other words, for every place or transition e we have e / ∈ • e.

Definition 3 -Acyclic Safe Nets

A arc-timed Petri net N is an acyclic safe net if: -N is a 1-safe acyclic Petri net. -∀p ∈ P, | • p| ≥ 1 ⇒ M 0 (p) = 0 -∀p ∈ P, | • p| = 0 ⇒ M 0 (p) = 1
-∀t ∈ T, there is a reachable marking that enables the transition t (Quasi-liveness).

A direct and important consequence of this definition is that for every correct execution and for every place p, at most one transition of • p and at most one transition of p • can be fired. This will be an interesting point for monitoring by making easy the association of the firing of the transition that created a token and the firing of the transition that consumed it. Indeed, with general Petri net the following scenario, that we want to avoid, is possible. Let p be a place, t 1 be a transition of • p and t 2 be a transition of p • . If the two events "t 1 is fired at time 0" and "t 2 is fired at time 10" are received, we can not be sure that a token stayed in p for a duration of 10 (perhaps two firings was missed: t 2 at time 1 and t 1 at time 9). With acyclic safe nets, such ambiguous situations are not possible.

A drawback of this definition is the impossibility to represent looping processes, such as a periodic task. The special case of periodic tasks can be solved by launching the monitoring of the task periodically. Additionally, a loop with a bounded number of iteration can easily be unfolded. As this formalism is meant for modeling real time systems, unbounded loops that could result in a system hang cannot be represented in this model.

B. System, Model & Events

The principle of our approach is first to describe the system using an acyclic safe net N and then to execute this Petri net with a monitoring mechanism using a mapping that associates to each event a transition.

Transitions associated to events are called event transitions (or e-transition); the monitoring mechanism has to fire them when corresponding events are received. Transitions not associated to events are called logical transitions (or ℓ-transitions); the monitoring mechanism has to fire them as soon as they are fireable.

C. Timed Event Sequences

As explained in the previous subsection, our monitoring approach consists in: first associating to a sequence of observed events (e-transition) a sequence of events (that can correspond to e-transitions or ℓ-transitions), then associating to this sequence of events a Petri net execution. The first association will be described at the end of this paper in Section V. The second association will be described in the next section: Section III. The notion of sequence of event is introduced in this subsection.

Definition 4 -Timed Event

An timed event is a couple (t, τ ) where t is a transition (not necessarily a e-transition) and τ a date (a real number).

A timed event can either be observed (an event associated to an e-transition occurred) or calculated (a ℓtransition that has to be fired). The monitor has to execute a sequence of timed events (e i = (t i , τ i )) 1≤i≤n .

From now on we will assume that for any timed event e i of a sequence E, the two values t i and τ i are defined by the relation (t i , τ i ) = e i .

Definition 5 -Correct Timed Event Sequences Let E = e 1 . . . e n a timed event sequence, we say that E is correct (or valid) if:

t 1 ∆ t 2 ∆ t 3 ∆ t 4 ∆ m t 9 t 5 ∆ m t 10 t 6 [0, 0] [0, 0] t 7 t 8 t 11 ∆ t ∆ s ∆ s
Fig. 1. An example of a distributed property: correctly displaying related information on an airplane control screen

-if t i ∈ • t j (t j is a causal successor of t i ), then i ≤ j.
for every place p, if there are two timed events e i = (t i , τ i ) and e j = (t j , τ j ) such that p ∈ • t i and p ∈ • t j then e i = e j : a token can only be fired once. for every e i = (t i , τ i ), for all p ∈ • t i ,

-if | • p| = 0, then τ i ∈ I(p, t i ): p is a source. -if | • p| = 0 then there is a unique timed event e k = (t k , τ k ) such that p ∈ t • k and τ i -τ k ∈ I(p, t i ): the timing of the event is correct. Property 1 -Validity of Correct Sequences Let E = e 1 .
. . e n be a correct timed event sequence. For every j ∈ {1, . . . , n}, if the transitions t 1 , . . . , t j-1 are fired at time τ 1 , . . . τ j-1 then the transition t j is fireable at time τ j .

Proof: Let us prove this result by induction. Let E be a correct timed event sequence. Case 1: E has only one timed event e = (t, τ ). Def. 5 implies that for all p in • t, | • p| = 0 (otherwise, there would be an event e k = (t k , τ k ) such that p ∈ t • k and thus we would have t k ∈ • t and e k = e: absurd !). Because no transitions were fired, the marking is the initial marking M 0 , and hence , by Def. 3, ∀p ∈ • t, M 0 (p) = 1. From this result we can know that t is enabled (Def. 2) and, as τ k ∈ I(p, t), then we can conclude (Def. 2) that t is fireable. Case 2: E contains more than one timed event. By induction we know that we were able to fire the transitions t i at respective dates τ i for i ≤ n -1. Let M be the new marking obtained by firing of transitions (t i ) i=1..n-1 . Let p be a place of • t n . By item 1 of Def. 5, no transition in p • was fired. If | • p| = 0 then, due to the original marking M 0 , M (p) = 1. If | • p| = 1, there is an event e k such that the firing of t k added a token in p and then M (p) = 1. Finally, we can conclude that t is enabled and, thanks to the second item of Def. 5, t is fireable.

D. An Example of Distributed Property

Let us consider a critical display in a plane that provides information to the pilot. The screen is split in two parts: the left part (Primary Flight Display) and the right part (Navigation Display).

When the plane is in autopilot mode, the system periodically captures information on plane attitude (t 1 ). Based on this information, a regulation loop is executed, and the end of this processing sends an event t 2 . Then, actuation orders of flight-related parameters are sent before event t 3 , and, finally, the update of display information sends event t 4 . On the left part, the Navigation Display, some navigation information like position information, active route and tracking are displayed by means of the Control and Display System.

Fig. 1 presents the related distributed property on the behavior of the overall display. Event transitions (etransitions associated to system events) are colored in grey and ℓ-transitions (logical events or computations performed by the monitor) in white. There are six events in the system: t 1 . . . t 6 .

Informally, this property can be explained as follows: the upper branch of the net (t 2 , t 3 , t 4 ) corresponds the left part of the screen and is a sequential process, while the lower branch (t 5 , t 6 , t 7 , t 8 ) is the right part of the screen and presents a choice (two disjoint and exclusive possible paths). In the upper branch, sensing, processing, actuating and displaying have to be performed timely. The labels on arcs express the idea that each computation step has worst case execution time (WCET) in a time interval ∆. In parallel, in the lower branch corresponding to the Navigation Display, sensors capture information and, depending on some value ranges, information is delivered to the User Application if it belongs to the correct range, or triggers a recovery action when it is out of range. Notice that all branches are synchronized at the end to provide synchronous display of related events both on Primary Flight and Navigation Displays. This is why the lower branch splits in two, the output of the display process depends on the occurrence pattern "value in range" (whether t 5 or t 6 happens). In practice the choice is described by the property: "t 5 or t 6 have to happen, but not both". As there is only one token in the place preceding t 7 and t 8 , only one of those two transitions can be fired. Suppose that t 5 , t 6 are fired in this order; then t 7 will be fired, and t 8 will not be enabled anymore, resulting in the death of the token between t 6 and t 8 . The two places and the two transitions with the ∆ m time interval forbid a token to stay forever before t 5 or t 6 if one of those two transitions is not fired. Indeed, a token that stays forever in a non final place is considered to be a dead token.

A third property that is expressed in this example is that the two branches must be synchronized (the display of the left and right part must be consistent): let τ 1 the date of t 4 's execution and τ 2 the date of t 5 or t 6 . If we want |τ 1τ 2 | to be less that a given value d s , then, by choosing ∆ s = [0, d s /2], a timing failure will occur whenever the two branches are not synchronized by at most d s .

The middle branch with one place and one arc with interval ∆ t , expresses the property that the time that elapsed between the beginning (firing of t 1 , or end of measurement) and the end (firing of t 9 , or display of the screen) of the computation must be in ∆ t . Hence, setting ∆ m = [sup(∆ t ), ∞[ frees up any blocked token and avoids dead tokens that do not correspond to any error at the end of the computation.

III. Semantics

In this section we describe how an execution of a Petri net is computed from a sequence of timed events. It is important to notice that we will not only consider correct event based sequences and that failures will be encountered. Instead of considering the execution itself, we will consider the final state of this execution. In this section, the state is computed in a post-mortem and centralized way. In Section IV we remove this assumption by providing a method to compute this state at runtime, in a distributed way.

A. Failures and States

We will assume two types of failures. The first one is timing failures. It corresponds to the case where a token in a place p has to fire a transition t while the age of this token is not included in the time interval I(p, t). The second kind of failures, missing events, happen when a required event does not occur.

As the failure model includes missing events, when the timed event sequences will be executed on the Petri net, some transitions will have to be fired even if they are not enabled, i.e., tokens are missing in places before the transition. To handle this issue, we introduce in this section an extension of the set of marking by allowing one negative token in places where one token should be deleted. The new set of marking will be denoted

M ± = {-1, 0, 1} P . Definition 6 -State A state is a tuple (M, ǫ t , ǫ m , c + , c -)
where M is a marking of M ± , ǫ t is the set of timing failure, ǫ m is the set of missing events, c + is the positive calendar function that returns for every place p the date when a positive token appeared (a transition of • p was fired) and c -the negative calendar function that returns for every place the date when a negative token appeared (a transition of p • was fired). The set of states is denoted

S ± = M ± × E T × E M × C + × C -.
The timing failures set E T is composed of tuples (p, t, δ) defined by "a token stayed in a place p during δ and has to fire transition t while t is not fireable"

The missing events set E M is composed of couples (place, sign). A couple (p, +) is in E M if a transition was not fired when it was supposed to be, letting a positive token that will never disappear in place p. A couple (p, -) is in E M if a not enabled transition t was fired, resulting in a negative token in place p.

The positive calendar function gives, for every place p, the date when the token appears, if any (the date when a transition of • p was fired). The negative calendar function provides for every place a couple (date, transition): the date when the token left the place, and the transition it fired. Notice that these two functions are partial functions, since not every place is used in every execution.

B. Semantics

The semantics is a function that takes as an input a timed event sequence and returns a state (a marking, two sets of failures and a two calendars).

Let E = (e i = (t i , τ i )) 1≤i≤n a timed event sequence. We define the timing-failure function with (p, t, δ) ∈ f ailure(E) if and only if a token in place p fires a transition t after having waited δ while it is not allowed. In a more formal way, (p, t, δ) ∈ f ailure(E) iff ∃i, j such that:

-

t = t j -p ∈ t • i ∩ • t j -δ = τ j -τ i / ∈ I(p, t j )
Definition 7 -Semantics Let M 0 be an initial marking and E = (e i = (t i , τ i )) 1≤i≤n a timed event sequence. The result of the execution E is a state sem(E) = (M, ǫ t , ǫ m , c + , c -) of S ± such that :

-M is the marking obtain from M 0 by firing transitions t 1 , . . . , t n . ǫ t is the set of timing failures: ǫ t = f ailure(E) ǫ m is the set of missing events, defined by:

ǫ m = (p, +) M (p) = 1 ∧ p • = ∅ ∪ (p, -) M (p) = -1
the calendar functions c + and c -are defined as follows:

∀i ∈ 1..n ∀p∈ t • i , c + (p) = τ i ∀p∈ • t i , c -(p) = (τ i , t i )

IV. Algebra and Distributed Execution

We defined in Section III a semantics based on timed events. The computational result of such a semantics is a final marking and failure sets. We will see in this section how we can compute this result, not in a sequential way (as it is usually done) but in a fully distributed way. In other words, even if a transition t 1 has to be fired before t 2 in the Petri net, we provide a semantics that will allow to fire t 2 and t 1 in parallel.

The main idea is the following. Let S 0 be an initial state and e 1 , . . . e n a timed event sequence. To compute the final state and the errors, we have to add e 1 to S 0 and then e 2 to the result and so on. Our approach consists in associating a state [e i ] to each event e i and introducing a new operation ⊗ to obtain a commutative group. Thus, to compute First we define a new set of markings that will allows us to get a commutative group. Then, to take into account time properties and potential errors, we extend this operation on states to obtain a commutative monoid structure.

S 0 ⊗ [e 1 ] ⊗ [e 2 ] ⊗ [e 3 ] ⊗ [e 4 ],

A. Marking

Let N be an acyclic safe net and P the set of places of N . We define the set of markings of N with M = Z P . We introduced before two others definitions of the set of markings: M + = {0, 1} P and M ± = {-1, 0, 1} P . The previous definition was useful because in acyclic safe nets all possible markings are in M ± . Before explaining why the new definition is interesting, let us generalize the classical ⊕ operation on markings in M Z : Definition 8 -Addition of marking We define the operation ⊕ on M as follows: let M and M ′ be two markings. For any place p:

(M ⊕ M ′ )(p) = M (p) + M ′ (p)
Definition 9 -Marking of a transition Let t be a transition. Its associated marking t is defined by, for every place p :

t (p) = t • (p) -• t(p)
Intuitively, the idea behind the previous two formal definitions is the following: if, from a marking M , a fireable transition t is fired, then the new marking is the result of the operation M ⊕ t .

As an example, Fig. 2 shows five markings of the same Petri net: the initial marking, three transitions markings, and the final marking. It is easy to see that adding in any order the first four markings results in the final marking, obtained by the execution of t 1 , t 2 , t 3 from M 0 . The two next properties formalize this idea.

Notice that, in general, adding two unrelated markings may result in meaningless marking (e.g., every marking of M \ M ± is meaningless). Considering such meaningless computation is required only to provide a group structure.

Property 2 -Group structure

The couple (M, ⊕) forms an abelian (i.e. commutative) group.

Proof: The operation ⊕ is an internal operation on M (but was not in M ± ). The commutativity and associativity are direct consequences of the commutativity and associativity of the + operation in Z. The neutral element is the empty marking defined by ∀p ∈ P, 0

⊕ (p) = 0. = ⊕ ⊕ ⊕ M f t 1 t 3 t 2 M 0 t 1 t 2 t 3

Fig. 2. Marking addition

Property 3 -Computation of the final marking Let N be an occurrence net, M 0 a marking of N and t 1 , . . . , t n a valid execution of N starting from M 0 , then we have the following property:

M 0 t1,...,tn -----→ M 0 ⊕ n i=1 t i
Proof: This is a direct consequence of the fact that firing a transition t from a marking M results in the addition of the two markings M and t (by definition of t ).

B. Failure Detector ⋄µ

The next step is to define an operation on states to obtain a commutative monoid. The main issue is that missing events cannot be determined using only algebraic properties: the detection of such failures depends on time. At runtime, to compute the state, the set of received events is not sufficient to compute the set of missing events (the exact set can only be computed post-mortem).

To circumvent this issue, we introduce in this section a failure detector ⋄µ. Intuitively, the main goal of the oracle that compute ⋄µ is to determine the set of missing events ǫ m that cannot be computed during the execution using only algebra on a subset of the timed events e 1 , . . . , e n (in this example, e 1 , . . . , e n are observed events, and the subset corresponds to partial information available at runtime).

Definition 10 -Failure detector ⋄µ Let E be an execution and (M, ǫ t , ǫ m , c + , c -) its semantics. The oracle ⋄µ is defined by:

at any time, ⋄µ is included in ǫ m , after a known bounded delay, ⋄µ is equal to ǫ m .

Notice that this failure detector definition is similar to the eventually perfect failure detector ⋄P [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF] with two differences: firstly, the definition holds for missed events instead of process crashes, and secondly, the delay from which the failure detector provides accurate results is bounded, with a known bound.

C. States

Information from markings does not include timing properties. In this section, we introduce a new notion of state by refining the definition of markings.

A state is a tuple of S = M × E T × E M × C + × C -where M is the set of markings defined in the previous section, E T is the set of timing failures, E M is the set of missing events and C + , C -are the agenda function sets.

Let us define a new operation ∪ f on calendar functions:

(c ∪ f c ′ )(p) = min(c(p), c ′ (p)) (if c(p)
is not defined, we will note c(p) = ⊥ and ∀x, min(x, ⊥) = x). This function is an associative, commutative one.

Definition 11 -Addition of states

The operation ⊗ on S is defined by Algorithm 1.

Algorithm 1 The ⊗ operation

1: function ⊗(S, S ′ )

2:

(M, ǫ t , ǫ m , c + , c -) ← S

3:

(M ′ , ǫ ′ t , ǫ ′ m , c ′ + , c ′ -) ← S ′ 4: M ′′ ← M ⊗ M ′ 5: ǫ ′′ t ← ǫ t ∪ ǫ ′ t 6: ǫ ′′ m ← ǫ m ∪ ǫ ′ m 7: c ′′ + ← c + ∪ f c ′ + 8: c ′′ -← c -∪ f c ′ - 9:
for p ∈ P do 10:

if M (p) ≥ 1 and M ′ (p) ≤ -1 then ⊲ addition of a positive and a negative token 11:

(d ′ , t) ← c ′ - (p
(p) = τ and ∀p ∈ • t, c -(p) = (τ, t).
Definition 13 -Marking of a missing event Let m be a missing event. We associate to this failure a state [m] = (0 ⊗ , ∅, ∅, {m}, ∅).

Theorem 1 -Computation of the final state

Let N be an acyclic safe net, S 0 the initial state of N , e 1 , . . . , e n a timed event sequence, and ǫ m the set of missing events of this sequence. Then:

sem(e 1 , . . . , e n ) = S 0 ⊗ n i=1 [e i ] ⊗ m∈ǫm [m]
The previous Theorem uses ǫ m , which cannot be computed instantaneously at runtime, but rather approximated by the failure detector ⋄µ: after a known bounded delay, ⋄µ equals ǫ m .

Proof: This result is a direct consequence of Definition 7 (semantics), Algorithm 1, and the definitions of [e i ] and [m].

A set E G is said to be generated by the ⊗ operation and the set E if: 1) E ⊂ E G , 2) if e and e ′ are in E G , then e ⊗ e ′ is in E G . In other words, E G is the closure of E with respect to ⊗.

Theorem 2 -Monoid Structure Let E = e 1 , . . . , e n be a timed event sequence and ǫ m its set of missing events. Let S E be the subset of S generated by the ⊗ operation on the set

{S 0 } ∪ {[e i ] | 1 ≤ i ≤ n} ∪ {[m] | m ∈ ǫ m }. (S E , ⊗) is a commutative monoid.
It is important to notice that the associativity property can be achieved only because we restrict ourself to acyclic safe nets: at most one token can appear in a place. Consider the case where two different tokens appear in a same place, one at the date τ 1 with the event e 1 , and another one at the date τ 2 with the event e 2 . Consider a third event e 3 that add a negative token to this place. The computation of ([e 1 ] ⊕ [e 3 ]) ⊕ [e 2 ] or the one of [e 1 ] ⊕ ([e 3 ] ⊕ [e 2 ]) will result in different states (in the first case, p contains one token that appeared in date τ 2 , while in the second case, p contain one token that appeared in date τ 1 ).

Lemma 1 -Calendar function consistency

Let E = e 1 , . . . , e n a timed event sequence and ǫ m its set of missing events. Let S E be the subset of S generated by the ⊗ operation on the set

{S 0 } ∪ {[e i ] | 1 ≤ i ≤ n} ∪ {[m] | m ∈ ǫ m }. Let
(p) = c 2 + (p) (resp. c 1 -(p) = c 2 -(p)).

Proof of Lemma 1:

This result is a direct consequence of the definition of a timed event sequence. As a positive token only appears at most once in a place, then there exists an unique i such that e i created the positive token. By definition of S E , if a state of this set has c + (p) defined, then the corresponding date is given by e i . The reasoning is similar for negative token.

Proof of Theorem 2: To prove this result, we have to prove that (S E , ⊗) is an internal, associative and commutative law with a neutral element. The fact that ⊗ is an internal law of S E is true by definition of S E . The commutativity property is a direct consequence of the symmetry of the code of Algorithm 1 (the two inputs S and S ′ have a symmetric same role). The neutral element is (0 ⊗ , ∅, ∅, ∅, ∅), and this can be easily checked with the algorithm. The only difficulty is to prove the associativity.

First of all, with the notation of Algorithm 1, the value of M ′′ (resp. c ′′ + , c ′′ -and ǫ ′′ m ) depends only of those of M (resp. c + , c -and ǫ m ) and M ′ (resp. c ′ + , c ′ -and ǫ ′ m ). As the operations used to compute these values, ⊗, ∪ and ∪ f are associative operations, we can deduce that for any states S 1 , S 2 and S 3 , the two values S 1 ⊗ (S 2 ⊗ S 3 ) and (S 1 ⊗ S 2 ) ⊗ S 3 have the same marking, calendar functions and missing events set.

To conclude the proof, let m = (p, t, δ) a timing failure present in the timing failures set of S 1 ⊗ (S 2 ⊗ S 3 ). We will demonstrate that m is present in the timing failures set of (S 1 ⊗ S 2 ) ⊗ S 3 . In the following, c i -denotes the negative calendars function of S i .

- -Third case: if m was computed during the operation S 1 ⊗ (S 2 ⊗ S 3 ) then using a similar reasoning, we can also prove that m is a missing event of (S 1 ⊗ S 2 ) ⊗ S 3 We just proved that the timing failures set of S 1 ⊗(S 2 ⊗S 3 ) is included in the one of (S 1 ⊗ S 2 ) ⊗ S 3 . We can prove as well, using the commutativity property, that the timing failures set of S 3 ⊗ (S 2 ⊗ S 1 ) is included in the one of (S 3 ⊗ S 2 ) ⊗ S 1 . We have the equality of the timing failures sets of S 1 ⊗ (S 2 ⊗ S 3 ) and (S 1 ⊗ S 2 ) ⊗ S 3 . Hence we can conclude that S 1 ⊗ (S 2 ⊗ S 3 ) = (S 1 ⊗ S 2 ) ⊗ S 3 .

V. A Distributed Monitoring Protocol

Section III defined the semantics (i.e., the final state) of an observed timed event sequence. Section IV showed how this semantics can be computed in an unordered and distributed way (Theorem 1 and 2).

In this section we will show how we can use these two theorems to implement an efficient distributed monitor. We will describe in a first part the distributed model we consider and in a second part the distributed protocol.

A. System & Network Model

We assume we have a distributed system of monitors M = {m 1 , . . . , m n }. Some of the monitors can catch events, while some others are used for computation and routing only. Typically this system can be based on a preexisting network that runs the distributed application we want to monitor. To simplify routing we will assume that a covering tree has already been computed and will be used for communication.

In our model, each event is caught by only one monitor. The event/monitor association is given by a function location from M T . The next figure gives an example of such an network. In the example, events associated to a monitor appear next to it. This part will describe a protocol where events are caught by monitors that will forward information up to the root of the covering tree.

t 3 m1 t 4 m2 m3 m4 t2 m5 t 5 m6 t 1 , t 6

B. Deploying a Property

We saw in previous section that the computation of the final state can be done in an unordered and distributed way. We will show in this section how the computation can be mapped to the monitor tree. The main difficulty in our approach is not to compute the final state, but to find the timed event sequence. A part of the execution is known thanks to the monitor: events corresponding to etransitions are caught by monitors, but the other part, i.e., events corresponding to ℓ-transitions, must be computed.

To compute such transition, we will assign to each ℓ-transition a monitor that will be in charge of firing this transition. We have already a location function that associates to each e-transition a monitor, we will now extend this function to associate to each ℓ-transition a monitor: this monitor will be then responsible of the firing of this logical transition.

We will present for that a distributed algorithm that starts from a monitor node and deploy from this node the set of transitions between the different nodes of the tree. This algorithm is a recursive algorithm: the root node shares the Petri net between itself and its children. Then the children start over with sharing with their own children the Petri net they received. The recursive algorithm end when leaves are attained. To explain the algorithms, let us first introduce a few new notions.

The notion of dependency is defined to allow us to answer the following question: "what is the minimal set of events d(t) needed to know if a transition t can be fired?". To know if a transition t must be fired, we need to know if there is a token in places just before this transition, i.e. in places p ∈ • t. Similarly, to know if there is a token in a place, we need to know if a token enters this place, i.e. a transition of • p was fired, or if a token leaves this place, i.e. a transition of p • was fired. In the following definition, d(t) is the set defined by

d(t) = {t ′ ∈ • p ∪ p • | p ∈ • t}.
Definition 14 -Events Dependencies Let t be a transition of a Petri net N , we define the set of events dependencies of t in T as:

dep(t, T ) =    {t} if t is an e-transition t ′ ∈d(t) dep(t ′ , T \ {t}) otherwise
From now on, we will denote dep(t) the set dep(t, T ) where T is the complete set of transitions of the Petri net. For example dep(t 8 ) = {t 5 , t 6 }.

The previous definition describes the dependency of ℓtransitions on e-transitions. The next definition shows how to extract a sub Petri net from another Petri net. The main idea is, as a node will only be responsible of the firing of some transitions, it only needs a subpart of the original net.

Definition 15 -Sub-Petri net Let N = (P, T, • (•), • (•), M 0 , I) be an acyclic safe net and T ′ a subset of T . We define the sub-Petri net induce by

T ′ by N |T ′ = (P ′ , T ′ , • (•), • (•), M 0 , I) where P ′ = {p ∈ P | ∃t ∈ T ′ s.t. p ∈ • t ∪ t • }.
Based on dependancy definition (Definition 14) and sub-Petri net (Definition 15), Algorithm 2 computes an efficient partitioning of the Petri net.

The algorithm assumes to be executed on a given covering tree. On the current node, we denote c 1 , . . . , c n the trees whose root are children of the current node. For example, if the current node is m 3 , then we will have

c 1 = {m 1 }, c 2 = {m 2 } and c 3 = {m 4 , m 5 , m 6 }.
The partitioning procedure waits for the reception of an executable net and splits the transitions of this net in n + 1 sets, with n the number of children. For this purpose, two arrays events and logical are computed such that the transitions of events[i] ∪ logical[i] will be fired by monitors of the subtree c i if i = 0, i = 0 corresponding to transitions to be fired by the current node. The net that will be executed by the current node is stored in the variable local_net.

Let us explain this algorithm. It starts when a message start N is received, where N is the Petri net that the current node has to partition between itself and its children.

First (lines 5 to 11), it splits the set of event transitions in n+1 subsets, where n is the number of children. For each event transition, if this transition is caught by a monitor of the subtree c i , then this transition is added to events[i] (line 7). If there is no such child, it means that the events corresponding to the transition must be caught by the end for 23: end procedure current node and thus, the transition is added to events[0] (line 9).

Then (lines 12 to 18) it splits the set of logical transitions in n + 1 sets as above. If an ℓ-transition can be computed in a child c i (if every event transitions that are dependency of the ℓ-transitions are in events[i]), then this transition must be added to logical [i]. If no child can compute this transition, the the current node can and will compute it (line 16).

The last part of the algorithm consists in sending the Petri net that will be monitor by the child c i to the root of c i . The restriction of the Petri net to N |event[i]∪logical [i] allows us to be sure that, in the children's execution of the algorithm, if the line 9 or 16 is reached, then the children root will be responsible to the current transition.

C. The Monitoring Protocol

We describe here the runtime part of the monitoring protocol that performs its computation in a recursive way. The algorithm assumes that the monitoring system has a tree structure, and that logical transitions have been partitioned and assigned to monitors by Algorithm 2.

The main idea of the runtime evaluation is the following: each node computes a partial state s with the transition it is responsible of and the partial state computed by its children in the tree. When this partial state is computed, the current node sends this value to its father if it is not the root. If it is the root, then the computed state is the final state.

The ⋄µ failure detector, described in Definition 10, is an independent thread that sends messages missing(m) as soon as a missing event m is observed. Notice that the implementation of ⋄µ is omitted in this paper, but a simple implementation using timeouts can be used here: if a timeout expires too early, then the corresponding event will be ignored.

To compute its partial state in the monitoring protocol of Algorithm 3, each node initializes a variable s to 0 ⊗ and updates it with the partial state received from its children (line 6 of Algorithm 3), the events and missing events it received (line 7 and 8), and updates the corresponding partial state. When all messages have been received (this property is indicated by the reception of a a stop message, line 5), it sends its state to its father (lines 15 and 16) if the current node is not the root.

Every time the current state s is changed, the protocol searches if some logical transitions can be fired. The firable ℓ function gives for every node the subset of logical transitions it is responsible of and that are fireable. As a token in a place p ∈ • t cannot be fired before c + (p)+min(I(p, t)) (with min the function that returns the lower bound of an interval), the date when this transition is fired is the maximum of the different c + (p)+min(I(p, t)) values. In other words, a logical transition is fired as soon as it is fireable. Notice that this date is not computed using a local clock, but only using events dates.

We will assume that there is a timeout mechanism that can be triggered as soon as the first message, be it an event, a missing event or a state, is received. The main goal is to avoid waiting infinitely because of a failure on the network that will make impossible for a monitor node to receive a message that it is supposed to received. This timeout mechanism is hidden behind an oracle that sends a message stop when all timeouts have been reached. In this case, the monitor will simply stop waiting for new messages.

D. Efficiency, Fault Tolerance & Robustness

A classical drawback of Petri nets is that events are defined in a sequential way: a transition can only be fired when all preceding transitions have been fired; if a single event is missing, it is not possible to execute the net. As our approach allows to fire a transition even if this transition is not enabled, then (1) every event transition will be fired, and (2) every ℓ-transition that can be fired will be fired, as soon as the e-transitions it depends on have been fired.

The protocol presented above is optimal in two ways. First, it is easy to see that the number of sent messages is equal to the number of edges in the monitor tree; if this tree is directly mapped to the communication infrastructure, then this solution is clearly optimal. Second, the final state is not computed at the root of the monitor tree, but the computation is distributed on the monitor network: a failure will be detected as soon as a node has enough else send state(s) to father 17: end procedure information to compute it. This property is ensured by Algorithm 2, that assigns logical transitions to the first monitor that that receives the necessary information to fire such transitions (as defined by the events dependencies function of Definition 14).

Interestingly, this last property can be used to implement an efficient recovery process: as soon as a failure is detected, the treatment to manage this failure, e.g. a degraded mode of operation, can be done locally. In other words, the treatment will only imply monitors in the subtree whose root detected the failure.

With regards to quality of the detection mechanism, notice that the quality of the result is a growing function of the quality of both observation of the execution and monitor network. If all events that can be detected are detected and if the monitor network satisfies real time properties, then the final state computed will be the real final state of the system and will be computed in real time. On the other hand, if many events are not detected and if timeouts are chosen in a very pessimistic way, then the result will be computed more slowly and will be less accurate (i.e., detection of failures includes too many false positive ones).

Finally, one can notice that the underlying structure of our detection mechanism, a tree, is in no way a faulttolerant data structure. To circumvent this issue, which is independent from the problem we are solving, traditional fault-tolerance mechanisms should be used to increase robustness of the tree. Two main strategies can be used: (1) a replication strategy applied to monitoring nodes of the tree (e.g., leader-follower replication or active replication), and (2) a classical node failure detection mechanism to monitor nodes healthiness and trigger a reconfiguration of the underlying tree in case of a failure.

VI. Related Works

As it was explained in this paper, our approach consists in transforming a Petri net execution in an algebraic computation that allows, thanks to the commutativity and associativity properties, to compute the execution in a distributed way, and thus, to implement a distributed monitor of real-time properties. Some research works propose centralized monitoring of real-time properties [START_REF] Meredith | Runtime verification with the rv system[END_REF] expressed using ltl formulae. Unfortunately, logics formulae are inherently centralized and cannot be easily adapted for distributed monitoring.

Some other works are compatible with the distribution of the monitoring as [START_REF] Zhou | DMaC: Distributed Monitoring and Checking[END_REF] or [START_REF] Jahanian | Runtime monitoring of timing constraints in distributed real-time systems[END_REF]; however, the way the distribution is done is different from ours. In our approach, a distributed property can be monitored in a distributed way while their strategy associates to each property a node of the network that will be in charge of this property: in other words, each property has a centralized monitor assigned. These approaches have a major drawback: the expressivity of the specification language used in [START_REF] Jahanian | Runtime monitoring of timing constraints in distributed real-time systems[END_REF] only allows conjunction of simple properties, while our model of Petri nets can express general logics formulae.

Interesting works on centralized monitoring of asynchronous [START_REF] Fabre | Distributed monitoring of concurrent and asynchronous systems[END_REF] or real-time [START_REF] Chatain | Time supervision of concurrent systems using symbolic unfoldings of time petri nets[END_REF] distributed systems, are those of C. Jard et al.. There are three main differences with our work. First of all, the monitoring consists in finding from an events sequence a corresponding Petri net execution to "explain" the observation. In our formalism, executable nets, at most one transition is associated to each event and this problem is trivial, but those works consider Petri net where a simple event can correspond to many transitions. The second difference is that there are no ℓ-transitions: every transition is associated to an event.

The algebraic view of execution can be seen as a specialization and generalization for the case of acyclic safe nets of the algebraic view of Petri Nets defined in [START_REF] Meseguer | Petri nets are monoids[END_REF]. We first added the notion of negative tokens that enables commutativity and associativity of operations. We also generalized this algebraic structure for arc-timed Petri net by reasoning on states and not only on markings.

A work that must not be mistook with ours is the one on distributable nets [START_REF] Hopkins | Distributable nets[END_REF]. This approach executes the Petri net in a distributed network and the execution should follow a location function: a transition can only be fired on a specific node. The resulting execution is still a sequential execution -if an event happens before an other, then the corresponding transitions must be fired in the same order -while our approach is by nature a concurrent evaluation, and hence easily distributable.

VII. Conclusion

This paper presented a new algebraic approach for outof-order evaluation of timed Petri nets: the verification of the correctness of an execution is reduced to a simple computation in an associative and commutative set. This approach allows to implement distributed monitoring protocols in a simple way; thanks to the algebra, local computations are sufficient to compute the global state and to detect potential deviations from the specification.

Results presented in this paper represent a first important step towards the development of an efficient and realistic distributed and real-time monitoring tool. A major next step consists in generalizing our model to more expressive versions of arc timed Petri nets. There is also room for improvement in the definition of the state algebra. Currently, the final state contains in the two calendar functions the dates of all transitions firings. A future version of this algebra will simplify the two calendar functions: if two states are added and if the addition results in the firing of a transition, then the date of this firing could be removed from the resulting state, thus reducing states complexity.

Another important point is to precisely evaluate efficiency of the distributed verification algorithm. The one presented here is very efficient in terms of the number of exchanged messages, but can be slow with regards to the latency of detection. We are currently working on providing a true real-time and distributed protocol.

Last, the aim of our monitoring protocol is to detect failures; another line of research for future works is to make this protocol compatible with classical recovery mechanisms [START_REF] Randell | The evolution of the recovery block concept[END_REF]. The main idea is to detect and recover failure locally, i.e. in the smallest possible subtree.

  a first node can compute [e 2 ] ⊗ [e 3 ] another one [e 1 ] ⊗ [e 4 ], the two of them can send the result to a last one that will compute S 0 ⊗([e 2 ]⊗[e 3 ])⊗([e 1 ]⊗[e 4 ]).

Fig. 3 .

 3 Fig. 3. The Monitor Network

  ∅, ∅, c + , c -) with c + and c - defined by ∀p ∈ t • , c +

	13:	if d ′ -d / ∈ I(p, t) then	⊲ timing failure
	14:	ǫ ′′ t ← ǫ ′′ t ∪ {(p, t, d ′ -d)}
	15:	end if
	16:	end if
	17:
	19: 20:	d ′ ← c ′ + (p) if d -d ′ / ∈ I(p, t) then	⊲ timing failure
	21:	ǫ ′′ t ← ǫ ′′
	22:	end if
	23:	end if
	24:	end for
	25:	return (M ′′ , ǫ ′′ t , ǫ ′′ m , c ′′ + , c ′′ -)
	26: end function
	Definition 12 -Marking of a state
	Let e = (t, τ ) be an event. We associate to this event a
	state [e] defined by [e] = ( t ,

)

12: d ← c + (p) if M ′ (p) ≥ 1 and M (p) ≤ -1 then

⊲ addition of a negative and a positive token 18:

(d, t) ← c -(p) t {(p, t, dd ′ )}

  S 1 and S 2 be two states of S E with

	S i = (M i , ǫ i t , ǫ i m , c i + , c i -); for any place p we have: if c 1 + (p) (resp. c 1 -(p)) and c 2 + (p) (resp. c 2 -(p)) are both defined then c 1 +

  First case: if m is in the failure set of S 1 , S 2 or S 3 , then m is trivially in (S 1 ⊗ S 2 ) ⊗ S 3 .-Second case: if m was computed during the operation S 2 ⊗ S 3 , it means that either M

	S 3 . -Second sub-cases: M 1 (p) ≤ -1, then c 1 -(p) is
	defined and thanks to Lemma 1 we know that
	c 1 -(p) = c 3

2 (p) ≥ 1 and M 3 (p) ≤ -1 or M 2 (p) ≤ 1 and M 3 (p) ≥ -1 (lignes 10 and 17 of the algorithm). Without loss of generality we will only consider the first case: at least one positive token in p for the marking of S 2 and at least a negative one in p for the marking of S 3 . There are still two subcases.

-First sub-cases: M 1 (p) ≥ 0, then the marking of S 1 ⊗ S 2 will associated more than one token in p and then m will be compute during (S 1 ⊗ S 2 ) ⊗ -(p): thus, m will be compute during S 1 ⊗ S 2 .

Acknowledgements

The authors want to thank Jean Fanchon for his insightful comments during the writing of this paper.


Valérie ; Vromman
email: valerie.vromman@afsca.be

Nadia Waegeneers

Christa Cornelis

Isabel De Boosere

Mirja Van Holderbeke

Christine Vinkx

Erik Smolders

André Huyghebaert

Luc Pussemier

DG Fasfc

Dietary cadmium intake by the Belgian adult population

Keywords: Potatoes, Bread, Cereals, Vegetables cadmium, dietary intake, risk assessment, cereal products

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cadmium is a non essential trace element. It is mainly an environmental contaminant, which on the one hand, is naturally present in the environment and on the other hand, may originate from industrial and agricultural sources. Food, including drinks, is the main source of Cd exposure for the non-smoking and nonoccupationally exposed part of the population (WHO 1992). [START_REF] Fouassin | Evolutie van het gemiddelde lood-en cadmiumgehalte in de dagelijkse voeding in België[END_REF] evaluated the average Cd concentration in food from the daily diet and estimated Cd dietary intake of the Belgian population at 48 µg per day. More than 2,500 food samples in big and small market were taken and analyzed by atomic absorption spectrometry or [START_REF] Fouassin | Evolutie van het gemiddelde lood-en cadmiumgehalte in de dagelijkse voeding in België[END_REF] with analysis result from 1989.

They observed a decline of Cd concentration in food which may presumed be due to the decrease in direct atmospheric deposition of Cd onto crops and soils.

Cadmium might constitute a serious health hazard for large groups of the population because it can bioaccumulate [START_REF] Marzec | Exposure to cadmium, lead and mercury in the adult population from Eastern Poland, 1990-2002[END_REF]. The half-life of Cd in the human body is 10 to 30 years [START_REF] Nawrot | Environmental exposure to cadmium and risk of cancer: a prospective population-based study[END_REF]. The most severe form of foodborne chronic Cd intoxication is the Itai Itai disease [START_REF] Kobayashi | Influence of consumption of cadmium-polluted rice or Jinzu river water on occurrence of renal tubular dysfunction and/or Itai Itai disease[END_REF]), which combines bone disorders and renal effects and is characterized by extreme pain. The disease was mainly diagnosed in a limited area in Japan that had been polluted. Cadmium concentrations found in locally grown rice were ten times higher than in other areas (Moritsugi andKobayashi 1964 cited in EC 2007). The most critical organ, i.e. the organ that exhibits the first adverse effects in long-term low-level Cd exposure, is the kidney. The critical effect is renal tubular dysfunction, which is often manifested as the presence of low molecular weight proteins (e.g. β-2-microglobulin) in urine (FAO/WHO 2000). In the general population, i.e. at low (dietary) Cd exposure, the urinary excretion of Cd reflects the amount stored in the kidney, as long as the amount of absorbed Cd has not yet saturated all Cd-binding sites, and increases progressively with age [START_REF] Lauwerys | Cadmium: exposure markers as predictors of nephrotoxic effects[END_REF]. Once the binding sites become saturated (i.e. after excessive exposure), further absorbed Cd is rapidly excreted in urine. When Cd-induced renal tubular damage develops, a considerable increase in the urinary excretion of Cd occurs because of its loss from the renal depot [START_REF] Lauwerys | Cadmium: exposure markers as predictors of nephrotoxic effects[END_REF]. Several markers of renal tubular function, such as β-2-microglobulin, are significantly and positively associated with urinary Cd [START_REF] Lauwerys | Does environmental exposure to cadmium represent a health risk? Conclusions from the Cadmibel study[END_REF].

A provisional tolerable weekly intake (PTWI) for Cd of 7 µg kg -1 body weight was established by the Joint FAO/WHO Expert Committee on Food Additives (JECFA; FAO/WHO 2004) and endorsed in 1995 by the Scientific Committee for Food of the European Commission (SCF 1995). The PTWI was based on the prevalence of renal tubular dysfunction, a biomarker of toxicity, and set at such a level that the Cd concentration in the renal cortex would not exceed 50 µg g -1 after 50 years of exposure. The health risk related to Cd exposure has recently been re-evaluated by the Scientific Panel on Contaminants in the Food Chain (CONTAM) of the European Food Safety Authority (EFSA), which established a tolerable weekly intake (TWI) of 2.5 µg kg -1 body weight [START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF]. The establishment of the TWI was based on a meta-analysis to evaluate the dose-response relationship between urinary Cd and urinary β-2microglobulin and set at a level to remain below 1µg Cd g -1 creatinine in urine in 95% of the population by age 50 [START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF].

The objective of this study was to estimate the dietary Cd intake of the general adult population in Belgium, to compare this dietary Cd exposure to the new TWI established by EFSA and to determine which food groups are the major contributors to the dietary Cd exposure. Dietary Cd intake was also calculated for individuals who follow the nutritional recommendations for the consumption of vegetables or fish and compared to the TWI established by EFSA.

Materials and methods

Cadmium data

Food items were sampled in the framework of the control program of the Belgian Federal Agency for the Safety of the Food Chain (FASFC) in the period 2006-2008. The goal of this program is to control the conformity with regulations and to guarantee food safety [START_REF] Maudoux | Food safety surveillance through a risk based control programme: Approach employed by the Belgian Federal Agency for the Safety of the Food Chain[END_REF]). The samples were analyzed in different accredited laboratories and by using different analytical methods (inter alia atomic absorption spectrometry, inductively coupled plasma-mass spectrometry). The methods used are among others subject to interlaboratory trials to check the quality of the results. Only the edible portion of the samples were analyzed. The limit of detection (LOD) or quantification (LOQ) for the analyses varied with the food matrix, the analytical technique used and per laboratory. The sensitivity of an analytical method is, for cost and time reasons, often set by the laboratory to fulfill legislative requirements and not fine-tuned to optimal sensitivity. This is perfectly satisfactory for routine monitoring purposes, but does cause slight problems when results are used to calculate human exposure [START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF]. The calculation of the descriptive statistics for the below the LOD. Such samples do not necessarily indicate that Cd is not present in the sample, but only that the analytical method could not detect the possible amount of Cd present. These samples were assigned a value of half the limit of detection (middle bound principle). In some cases, the samples were reported as a concentration value below the limit of quantification (LOQ). In these cases the numeric concentration was estimated as half of the limit of quantification.

The results of the middle bound scenario were compared with a lower bound scenario in which samples with Cd levels below the LOD or LOQ were set to zero, and an upper bound (worst-case) scenario in which samples with Cd levels below the LOD or LOQ were set to the LOD or LOQ respectively. According to WHO (1995), two estimates using zero and LOD for all results less than LOD must be done if the proportion of samples below the LOD is between 60 and 80%.

Food consumption data

A Belgian national food consumption survey was performed in 2004 by the Belgian Institute for Public Health. Aims, design and methods of this survey are described elsewhere [START_REF] Vriese | The Belgian food consumption survey: aims, design and methods[END_REF]. This survey describes the food consumption schema of 3,083 participants over 15 years of age. Information on food intake was collected using two non-consecutive 24h recalls in combination with a self-administered food frequency questionnaire. The selection of interviewed people and the moment of the interview were chosen in order to obtain a representative consumption profile of the Belgian population spread over one year. The dietary Cd exposure of the Belgian adult population (> 15 years of age) was estimated based on the mean consumption of the food items over the two non-consecutive days.

Estimation of cadmium intake

Cadmium was analyzed in 55 categories (food items) of foods. Liver of horse, game and bovine like kidneys of horse, game and bovine were grouped for the determination of the Cd intake. The Cd intake was calculated by a deterministic approach multiplying for each food item the median Cd concentration by its mean consumption.

The use of the median Cd concentration in food was preferred over the use of the mean concentration because the latter is more sensitive to extreme values. The obtained results were summed up for all food items to estimate an overall exposure. The dietary Cd intake was compared to the TWI of 2.5 µg kg -1 body weight set by [START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF]

⋅ ⋅ ⋅ (1)
The values of the body weight were set per individual.

The Cd intake was also determined by multiplying, for each individual, the consumption of each food (average over the two 24h recalls) by the median Cd concentration in that food item and by summing the results for all food items.

The dietary Cd intake for individuals who follow the nutritional recommendations for the consumption of vegetables or fish was similarly determined. For each individual who eats 250 g or more vegetables or 30 g or more fish per day, the consumption of a food item was multiplied with the median Cd concentration in the food items. The obtained results were then summed up for all food items to estimate an overall exposure.

Results

About 4,000 results of Cd analyses in food items were collected (Table 1). Cadmium was detected in 23% of the samples with a higher detection rate in matrices such as cereals, potatoes, root vegetables and offal. The highest concentrations were measured in offal (liver and kidney) of game and horse (Table 1). concentrations in buckwheat (0.046 mg kg -1 fresh weight) were higher than in wheat flour (0.025 mg kg -1 fresh weight) and than in rye flour (0.017 mg kg -1 fresh weight) [START_REF] Jorhem | Levels of lead, cadmium, zinc, copper, nickel, chromium, manganese, and cobalt in foods on the Swedish market, 1983-1990[END_REF]. This is reflected in the different types of bread, as measured by [START_REF] Tahvonen | Lead and cadmium in Finnish breads[END_REF] in Finnish breads: the respective Cd concentrations in rye bread, coffee bread (which is based on white wheat flour) and wholewheat bread were 0.014, 0.023 and 0.030 mg Cd kg -1 dry weight. The types of bread that were analyzed in the current study (e.g. white, wholemeal wheat or rye bread), were not specified. Biscuits, pastries and breakfast cereals were not analyzed, neither was rice. The Cd concentrations in pastries and biscuits are generally slightly lower than in white bread [START_REF] Bordajandi | Survey of persistent organochlorine contaminants (PCBs, PCDD/Fs, and PAHs), heavy metals (Cu, Cd, Zn, Pb, and Hg), and arsenic in food samples from Huelva (Spain): levels and health implications[END_REF][START_REF] Karavoltsos | Cadmium content in foodstuffs from the Greek market[END_REF]. Cadmium concentrations in different types of rice on the Swedish market ranged from <0.001 to 0.088 mg kg -1 fresh weight, with a mean of 0.024 mg kg -1 fresh weight [START_REF] Jorhem | Elements in rice from the Swedish market: 1. Cadmium, lead and arsenic (total and inorganic)[END_REF]).

Among vegetables, Cd was mainly found in spinach, celery, salsify and to a lesser extent in potatoes, leek, parsley and carrots (

Dietary Cd intake

The dietary Cd intake of the Belgian adult population, calculated by a deterministic approach as the sum of the mean consumption multiplied by the median Cd concentration for each food item, was estimated at 0.98 µg kg -1 body weight per week (39,3% of the TWI) (Table 2). The Cd intake was estimated at 0.77 µg kg vegetable intake by Belgian adults is only 138 g per day, while 350 g is recommended (De [START_REF] Vriese | Enquête de consommation alimentaire Belge 1 -2004 Service d'Epidémiologie[END_REF]. This amount of vegetable intake is only reached by 10% of the adult population. Therefore, dietary Cd intake was determined for consumers who daily consume 250 g or more of vegetables (28% of the Belgian population). Mean and 95 th percentile Cd intake for these consumers was estimated at 1.22 µg kg -1 body weight per week (48.7% of the TWI) and 2.25 µg kg -1 body weight per week (90% of the TWI),

respectively. The Belgian Superior Health Council recommends a mean daily fish consumption of 20-40 g by adults [START_REF] Hgr (hoge | Vis en Gezondheid bij Volwassenen FOD Volksgezondheid, Veiligheid van de Voedselketen en Leefmilieu[END_REF], which corresponds to one to two portions per week. However, the average intake by the general population is only 17.9 g and three quarters of the populations does not meet the recommendations (De [START_REF] Vriese | Enquête de consommation alimentaire Belge 1 -2004 Service d'Epidémiologie[END_REF]. Mean and 95 th percentile Cd intake for consumers who eat on average 30 g or more fish per day (21% of the Belgian population), was estimated at 1.10 µg kg -1 body weight per week (43.8% of the TWI) and 2.21 µg kg -1 body weight per week (88.3% of the TWI), respectively.

The deterministic estimation of dietary Cd exposure shows that cereal products have the highest contribution to dietary Cd intake, followed by potatoes, pasta and vegetables (Table 3). The large contribution of cereal products and potatoes results from a high consumption of both food products combined with moderate Cd concentrations. Carrots and spinach have the highest contribution in the vegetable category.

[Insert table 3: Contribution of the food category to Cd intake of the Belgian adult population]

Discussion

The mean dietary Cd intake of the general adult population in Belgium, estimated at 0.98 µg kg 2008). The Cd concentration was not measured in all food groups within the framework of that study, but partially collected from literature. Belgian dietary Cd intake was also estimated by SCOOP in 2004 at 1.9 µg kg -1 body weight per week and in 1996 at 2.74 µg kg -1 body weight per week. This latter study included a high number of food groups.

The mean exposure was calculated in a deterministic way by combination of the mean consumption with the mean concentration in different food categories [START_REF] Scoop | [END_REF].

The dietary exposure estimate in this study is close to recent estimations from most other European countries (Table 4) but is 3 times larger than the dietary exposure estimate in France, 0.319 µg kg -1 body weight per week [START_REF] Leblanc | Dietary exposure estimates of 18 elements from the 1 st French total diet study[END_REF]. Cadmium concentrations measured in food by [START_REF] Leblanc | Dietary exposure estimates of 18 elements from the 1 st French total diet study[END_REF] 11 can be used to make an estimation of the contribution of rice to the total dietary Cd intake. If this value is combined with the mean rice consumption of the Belgian adult population, a weekly Cd intake due to the consumption of rice of 0.022 µg kg -1 body weight can be calculated, which represents 2% of the deterministically derived intake of 1.004 µg kg -1 body weight per week and which is less than 1% of the TWI.

The robustness of the high percentiles of Cd exposure, may be questioned because these percentiles are more sensitive to uncertainties linked to different sources (sampling size, misreporting of consumption, variability in concentrations, analytical uncertainty, …).

These percentiles are, however, important. Therefore, this methodology may be valuable for mean exposure estimations, but due to the large uncertainty for estimations realized for the highest percentiles, these percentiles should be considered with caution.

Cereal products contribute largely to the total dietary Cd intake, both in the current study (> 40%) as in other studies (RIVM 2003;FSA 2009;[START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF]) and former

Belgian estimates (SCOOP). This is mainly due to the large consumption of this food group. The consumption of wholemeal cereal products is promoted as they may provide protection against e.g. various cancers [START_REF] Goodman | Association of soy and fiber consumption with the risk of endometrial cancer[END_REF][START_REF] Chan | Whole grains and risk of pancreatic cancer in a large population-based case-control study in the San Francisco Bay area, California[END_REF][START_REF] Suzuki | Dietary fiber intake and risk of postmenopausal breast cancer defined by estrogen and progesterone receptor status-A prospective cohort study among Swedish women[END_REF]. The mean Cd concentration found by FASFC in bread (0.019 mg kg -1 ) is comparable to those found in white bread in other studies (range 0.015-0.023 mg kg -1 ; [START_REF] Bordajandi | Survey of persistent organochlorine contaminants (PCBs, PCDD/Fs, and PAHs), heavy metals (Cu, Cd, Zn, Pb, and Hg), and arsenic in food samples from Huelva (Spain): levels and health implications[END_REF][START_REF] Karavoltsos | Cadmium content in foodstuffs from the Greek market[END_REF]Marti-Cid et al 2008;[START_REF] Tahvonen | Lead and cadmium in Finnish breads[END_REF]. As wholemeal flour contains about 30% more Cd than white flour [START_REF] Chaudri | The Cadmium Content of British Wheat Grain[END_REF], consumption of wholemeal bread might increase the Cd intake up to 6.6% (from 0.98 to 1.05 µg kg -1 body weight per week). This increase will, on the other hand, be compensated to a large extent by the lower fractional absorption of Cd in the gastrointestinal tract, due to the presence of phytates, nutrients and fibers in the whole grain and bran fractions [START_REF] Moberg | The effect of wheat bran on the absorption and accumulation of cadmium in rats[END_REF][START_REF] Berglund | Intestinal absorption of dietary cadmium in women depends on body iron stores and fiber intake[END_REF][START_REF] Lind | Accumulation of cadmium from wheat bran, sugar-beet fibre, carrots and cadmium chloride in the liver and kidneys of mice[END_REF][START_REF] Reeves | Nutritional status affects the absorption and whole-body and organ retention of cadmium in rats fed rice-based diets[END_REF][START_REF] Andersen | Nutritional interactions in intestinal cadmium uptake -Possibilities for risk reduction[END_REF]). Therefore, the higher Cd content does not seem to be a reason to decrease the consumption of wholemeal wheat.

Conclusion

The mean, median and 95 th percentile dietary exposure to Cd of the Belgian adult population were estimated at 0.98, 0.85 and 2.02 µg kg -1 body weight per week.

Cadmium intake was estimated to be lower than the TWI of 2.5 µg kg -1 body weight for 98% of the Belgian adult population. Dietary exposure to Cd for specific consumer groups such as consumers who follow the nutritional recommendations for the consumption of vegetables and fish, is higher than for the general adult population.

  absorption spectrometry. In 1993, Van Assche and Ciarletta compared the data from

  was performed by also taking into account the samples with results

Figure

  Figure I presents the distribution of the Cd intake of the Belgian adult population determined with the middle bound scenario. The mean, median and 95 th percentile Cd intake were estimated at 0.98, 0.85 and 2.02 µg kg -1 body weight per week, respectively. Two percent of the Belgian adult population has a Cd intake above the TWI of 2.5 µg kg -1 body weight.

Figure 1 :

 1 Figure 1: Distribution of dietary Cd Intake for the Belgian adult population. The TWI value established by EFSA is shown as the vertical line.

  et al. 2009). Therefore, by Royal Decree 1 , bovine offal of animals over 18 months slaughtered in Belgium can not be placed on the market. The Cd concentrations measured by[START_REF] Waegeneers | The European maximum level for cadmium in bovine kidneys is in Belgium only realistic for cattle up to 2 years of age[END_REF] in cattle liver and kidneys of animals of ≤18 months (median: 0.06 mg kg -1 and 0.23 mg kg -1 , respectively;Waegeneers et al. personal communication) were lower than those measured in game and horse liver and kidneys. Cadmium is frequently found in cereal products. It was detected in all pasta samples analyzed by FASFC (Table1). Cadmium concentrations measured by FASFC in cereals were higher than those reported by[START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF]. Cereals like wheat and rice can concentrate cadmium during the growth in the core of the kernel(RIVM 2003).

	F o r Chaudri et al. (1995) analyzed 77 samples of wheat grain. On average, the concentration
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Although Cd has not been analyzed in cattle offal during the selected time period, it is known that the contamination level is quite high (Advice 01-2005; Vromman et al. 2008; Waegeneers of Cd in bran was twice that in wholemeal flour. White flour contained about 31% less

Cd than wholemeal flour. This corresponds to data of

[START_REF] Cubadda | Effects of processing on five selected metals in the durum wheat food chain[END_REF]

, who found that milling of durum wheat, which is used for pasta-making, reduced the Cd content with 32%. Different types of flour contain different amounts of Cd. Cadmium

Table 1

 1 He found that leafy vegetables, and more specifically spinach, contained the highest Cd concentrations. The Cd concentrations in spinach reported by[START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF] are comparable to those measured by the FASFC. Cadmium concentrations in fruit, dairy products, eggs, honey and meat were low (Table1).[Insert Table1: Overview of Cd result in food analyzed by FASFC]

	der Schee (cited in RIVM 2003) analyzed 500 samples of fruits, vegetables and
	potatoes.
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	8

). According to

[START_REF] Versluijs | Accumulatie van metalen in planten[END_REF]

, carrot, spinach, tomato, lettuce and celery have a high Cd uptake from soil. Van 1 Royal Decree of 10 August 2005 modifying Royal Decree of 9 March 1953 concerning trade of meat slaughter and regulating the expertise of animals slaughtered in the country

  dietary Cd intake estimates. Further, intake values may differ from one study to another according to the number and the nature of the food groups which are considered, the calculation methodology and the type of food consumption survey.

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	In the current intake calculations, Cd intake may be underestimated due to the absence
	of some food products in the dietary exposure assessment, e.g. rice, breakfast cereals,
	biscuits and wild mushrooms. Ingredients in mixed dishes (e.g. vegetables in soup) were

were one order of magnitude lower than those measured by FASFC or reported by other authors. The median dietary Cd exposure calculated by

[START_REF] Efsa | Scientific Opinion of the Panel on Contaminants in the Food Chain on a request from the European Commission on cadmium in food[END_REF]

for European countries, 2.3 µg kg -1 body weight per week, was slightly lower than that reported by JECFA (2005) (2.8-4.2 µg kg - 1 body weight per week) but higher than those reported by other authors (Table

4

).

Dietary Cd exposure assessment published by EFSA (

2009

) is based on the mean Cd concentration for each food group (with non-detected values set at half the limit of detection) and on aggregated consumption data reported in the EFSA Concise European Food Consumption database. According to EFSA (2009), the differences might indicate that a refined evaluation based on more disaggregated and representative samples, can result into lower not taken into account either. Rice is mainly imported from outside Europe, and therefore the mean Cd concentration derived by

[START_REF] Jorhem | Elements in rice from the Swedish market: 1. Cadmium, lead and arsenic (total and inorganic)[END_REF]

, i.e. 0.024 mg kg -1 ,

Table 1 :

 1 Dietary Cd exposure of the Belgian adult population was comparable to that in several other European countries. Cereal products and potatoes are the main food groups that contribute to Cd exposure in Belgium. Overview of various food items in which Cd was measured byFASFC in 2006FASFC in , 2007FASFC in and 2008 (Number of samples analyzed, number of samples < quantification limit (LOQ), percent of samples < LOQ, minimum, maximum, mean and median (P50) Cd concentration. The concentrations are expressed on a fresh weight basis.

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

*Vromman Valérie. Email : valerie.vromman@afsca.be

Table 2 :

 2 Estimation of Cd dietary exposure by the Belgian adult population (>15 year)

		Mean consumption (kg kg -1 body	Exposure* (µg kg -1 body	%TWI (= 2,5 µg kg body weight per -1
	Food	weight per day)	weight per week)	week)
	Bread	1.75E-03	0.233	9.31
	Pasta, noodle	4.66E-04	0.176	7.05
	Cereals (wheat)	3.70E-06	0.001	0.05
	Potatoes	1.57E-03	0.226	9.03
	Garlic	2.58E-06	0.0002	0.01
	Courgette	2.52E-05	0.001	0.04
	Tomato	4.55E-04	0.016	0.64
	Pea	3.37E-05	0.012	0.47
	Onion	9.24E-05	0.003	0.13
	Carrot	1.66E-04	0.024	0.97
	Radish	2.46E-06	0.0001	0.00
	Salsify	5.95E-06	0.002	0.07
	Leek	5.28E-05	0.007	0.27
	Celery	1.33E-05	0.003	0.10
	Celeriac	1.08E-05	0.004	0,18
	Lettuce (lettuce, lamb's lettuce, rocket,…)	9.76E-05	0.008	0.30
	Spinach	4.89E-05	0.022	0.90
	Fennel	3.96E-06	0,0001	0.01
	Parsley	6.81E-07	0.0001	0,00
	Endive	1.48E-05	0.001	0.02
	Cabbage (white cabbage, cauliflower,…)	2.07E-04	0.007	0.29
	Cultivated mushroom	4.23E-05	0.001	0.06
	Gooseberry	3.89E-06	0.0001	0.01
	Strawberry	7.64E-05	0.003	0.11
	Grape	8.05E-05	0.003	0.11
	Dried fruit -pine nuts	3.33E-07	0.0003	0.01
	Melon	6.11E-05	0.002	0.09
	Honey	1.61E-05	0.0003	0.01
	Milk	1.40E-03	0.005	0.20
	Cheese	1.48E-04	0.001	0.04
	Yoghurt	5.15E-04	0.004	0.14
	Eggs	1.44E-04	0.001	0.02
	Fish	2.51E-04	0.044	1.76
	Molluscs	2.56E-05	0.032	1.29
	Crustaceans	4.05E-05	0.007	0.28
	Duck meat	4.89E-06	0.0002	0.01
	Rabbit meat	1.85E-05	0.001	0.03
	Chicken meat	2.48E-04	0.009	0.35
	Turkey meat	5.48E-05	0.002	0.08
	Snail	9.18E-07	0.001	0.02
	Sheep & lamb meat	3.35E-04	0,012	0.47
	Pork meat	1.99E-04	0.007	0.28
	Bovine meat	2.54E-04	0.009	0.36

Table 3 :

 3 Contribution of food categories to the dietary exposure of the Belgian adult population

	Food Additives and Contaminants	Page 22 of 24
	Contribution
	to exposure
	Categories of food	(%)
	Cereals (wheat), bread	23.83
	Potatoes	22.99
	Pasta, noodle	17.94
	Vegetables	11.34
	Beverages (water, juice)	4.80
	Meat (poultry, bovine, pork, horse, game)	4.57
	Fish	4.47
	Crustaceans, bivalves	4.01
	Chocolate	3.58
	Dairy products	0.97
	Fruit	0.82
	Offal (horse, game, bovine)	0.57
	Eggs	0.05
	Honey	0.03

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

Table 4 .

 4 Comparison of dietary Cd intake in different European countries.

	Country	(µg kg	Cd intake -1 body weight per	Reference
			week)
	Belgium		0.98	This study
	The Netherlands	1.26 (short-term intake)	RIVM 2003
		0.98 (long-term intake)
	United Kingdom		0.98-1.19	FSA 2009
	Germany		1.45	BfR 2009
	Denmark		1.87	Larsen et al. 2002
	Sweden		1.75	Åkesson et al. 2008
	Spain (Tarragona)		1.67	Bocio et al. 2005
	Spain (Catalonia)	1.4/1.83 (females/males)	Llobet et al. 2003
	Spain (Huelva)		0.77	Bordajandi et al. 2004
	Spain (Canary Islands)		1.1	Rubio et al. 2006
	France		0.319	Leblanc et al. 2005
	Europe		1.9-3.0	EFSA 2009
	Belgium		2.33

*Vromman Valérie. Email : valerie.vromman@afsca.be

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

Acknowledgement

The authors wish to thank the Belgian Federal Agency for the Safety of the Food Chain for providing the data used in this study.