Vincent Danos
email: vincent.danos@pps.jussieu.fr

Jean Krivine

Reversible Communicating Systems

One obtains in this paper a process algebra RCCS, in the style of CCS, where processes can backtrack. Backtrack, just as plain forward computation, is seen as a synchronization and incurs no additional cost on the communication structure. It is shown that, given a past, a computation step can be taken back if and only if it leads to a causally equivalent past.

Introduction

Backtracking means rewinding one's computation trace. In a distributed setting, actions are taken by different threads of computation, and no currently running thread will retain a complete description of the others past. Therefore, there is no guarantee that when a given thread goes back in its own local computation history, this will correspond to going back a step in the global computation trace. Of course, one could ask a thread willing to go back a step, to first verify that it was the last to take an action. But then all concurrent behaviour would be lost, not speaking about the additional communication machinery this choice would incur. On the other hand, letting any thread freely backtrack would result in losing the initial computation structure and reaching computation states which were formerly inaccessible. So, one has to strike a compromise here.

This is what we propose in this paper. A notion of distributed backtracking built on top of Milner's CCS [START_REF] Milner | Communication and Concurrency[END_REF] is provided. At any time, a thread may either fork or synchronize with another thread, and in both cases, the action taken is recorded in a memory. When the thread wants to rewind a computation step, it has to synchronize with either its sibling, in the case the last action was a fork, or with its synchronization partner in the case the last action was a synchronization. Thus backtrack is considered also as a synchronization mechanism.

This mechanism can be construed as a distributed monitoring system and it meshes well with the specifics of the host calculus CCS. Backtrack doesn't involve any additional communication structure and we could obtain a syntax, termed RCCS, for reversible CCS, that stays really close to ordinary CCS.

There is another aspect in which the syntax seems to do well. The compromise it corresponds to, has a clear-cut theoretical characterization. Given a process and a past, one can show that the calculus allows backtrack along any causally equivalent past. Computation traces originating from a process are said to be causally equivalent when one can transform one in the other by commuting successive concurrent actions, or cancelling successive inverse actions.

A similar notion of computation trace equivalence exists in λ-calculus which Lévy could characterize by a suitable labelling system [START_REF] Lévy | Réductions optimales en λ-calcul[END_REF][START_REF] Berry | Minimal and optimal computation of recursive programs[END_REF]. Thus, a pretty good summary of the theoretical status of this backtracking mechanism, is to say that RCCS is a Lévy labelling for CCS. Two reduction paths will be equivalent if and only if they lead to the same process in RCCS. This is what we prove and it seems to be the best one can expect on the theoretical side. 3To summarize the contribution, the present study proposes a syntax for reversible communicating systems, together with a characterization, in terms of causally equivalent traces, of the exact amount of flexibility one allows in backtracking. One also explains how irreversible, or unbacktrackable actions, can be included in the picture and a procedure of memory cleansing is introduced and proved to be sound.

Following Regev [START_REF] Regev | Representation and simulation of biochemical processes using the π-calculus process algebra[END_REF][START_REF] Priami | Application of a stochastic name-passing calculus to representation and simulation of molecular processes[END_REF], process algebras have been investigated recently for modeling biological systems. Since reversibility is the rule in biological interaction, the second author was naturally prompted to look for a theoretical setup for distributed and reversible computations. Biological modeling in a former version of RCCS was explored [START_REF] Danos | Formal molecular biology done in CCS[END_REF]. By that time soundness (here, corollary 1) was proved directly, and the key connection to causal equivalence went unnoticed. Future work, and in particular, applications to the synthesis of sound transactional mechanisms is discussed in the conclusions.

Related Work

Process algebras with backtracking were seen early to be valuable computational objects and independently studied by Prasad [START_REF] Prasad | Combinators and bisimulation proofs for restartable systems[END_REF] and later by Bergstra et al. [START_REF] Bergstra | Process algebra with backtracking[END_REF]. However, both had an exception model in mind, which while providing interesting programming constructs would not have any specific theoretical structure. Another well developed line of research, partly inspired by Lévy's work on causal equivalence in λ-calculus, and partly by the need for refined non-interleaving semantics, is that of the causal analysis of distributed systems [START_REF] Boudol | Permutation of transitions: An event structure semantics for CCS and SCCS[END_REF][START_REF] Degano | A partial ordering semantics for CCS[END_REF][START_REF] Boudol | Observing localities[END_REF][START_REF] Degano | Proved trees[END_REF][START_REF] Boudol | A theory of processes with localities[END_REF][START_REF] Castellani | Observing distribution in processes: Static and dynamic localities[END_REF][START_REF] Degano | Non interleaving semantics for mobile processes[END_REF][START_REF] Boreale | A fully abstract semantics for causality in the π-calculus[END_REF]. However, the only concern here is forward computation. Causal analysis is thought of as a static analysis method, or a theoretical measure of how concurrent a system is, and not as inducing some policy that threads should obey in order to backtrack soundly. In some sense, we present here a synthesis of these two lines of research which, to the best of our knowledge, were never brought together to interact.

Acknowledgements

The authors wish to thank the referees for their suggestions and specifically for correcting a wrong formulation of corollary 1.

The plan to implement backtrack is to assign to each currently running thread an individual memory stack keeping track of past communications. This memory will also serve as a naming scheme and yield a unique identifier for the thread. Upon doing a forward transition, the information needed for a potential roll-back will be pushed on the memory stack.

As said briefly in the introduction, two constraints are shaping the actual syntactic solution explained below. First the notion of past built in the memories has to have some degree of flexibility. Even if one could somehow record the complete succession of events during a distributed computation and only allow backward moves in whatever precise order was taken, this would induce fake causal dependencies on backward sequences of actions. Actions which could have been taken in any order would have to be undone in the precise incidental order in which they happened. So one should not be too rigid on the exact order in which things done have to be undone.

On the other hand the notion of past should not be too flexible. Because if it is, then one might be in danger of losing soundness, in that some backtracking computations could give access to formerly unreachable states. Clearly, if actions are undone before whatever action they caused is, the result is not going to be consistent.

It turns out that the solution proposed here is at the same time consistent and maximally flexible. The final take on this will be a theorem proving that any two computation traces starting in a same state and reaching a same end state are causally equivalent, or in other words that one can be rearranged so as to obtain the other by commuting concurrent actions. Consistency will follow.

But, first of all we need a syntax to describe our processes and this is the matter to which we turn in the next subsection. Let us briefly remind that interaction consists only of binary synchronized communication. In a CCS system something happens when two processes are performing complementary actions at the same time, very much as a handshake.

Recursive definitions can be dealt with, but they are not central to the point being made in this paper and we will do without them.

As the notation for choice suggests, the order in which choices add up is irrelevant. Simple processes will therefore be considered only up to additive structural congruence, that is to say the equivalence relation generated by the following usual identities: P + 0 ≡ P P 1 + P 2 ≡ P 2 + P 1 (P 1 + P 2 ) + P 3 ≡ P 1 + (P 2 + P 3 ), where P 1 , P 2 , and P 3 represent processes of the guarded choice type. 4Monitored processes. In RCCS, simple processes are not runnable as such, only monitored processes are. This second kind of process is defined as follows:

Memories:

m ::= Empty memory | 1 • m Left-Fork | 2 • m Right-Fork | * , α, P • m Semi-Synch | m, α, P • m Synch Monitored Processes: R ::= m P Threads | (R | R) Product | (a)R Restriction
To sort visually our two kinds of processes, the simple ones will be ranged over by P , Q, . . . while the monitored ones will be ranged over by R, S, . . . Sometimes, when it is clear from the context which kind of process is being talked about, we will say simply process in place of monitored process.

As one may readily see from the syntax definition, a monitored process can be uniquely constructed from a set of terms of the form m P , which we will call its threads. In a thread m P , m represents a memory carrying the information that this process will need in case it wants to backtrack. That memory is organized as a stack with the last action taken by the thread sitting on the top together with additional information that we will comment on later. There is an evident prefix ordering between memories which will be written ≤.

As an example we can consider the following monitored process:

R = 1 * , a, 0 b.c.0 | 2 * , a, 0 c.0
It consists of two threads, namely S 1 = 1 * , a, 0 b.c.0 and S 2 = 2 * , a, 0 c.0. Taking a closer look at S 1 , we see a fork action 1 sitting on top of its memory stack, indicating that the last interaction the thread took part in was a fork. Below one finds * , a, 0 indicating that the penultimate action was an a action exchanged with an unidentified partner * . That part of the past of S 1 is shared by S 2 as well. Actually, they both can be obtained from a same process a.(b.c.0 | c.0) as will become evident when we have a precise notion of computation.

Coherent processes. Not all monitored processes are going to be of interest. Since memories are also serving as a naming scheme for threads, they should better be unique. Actually we can ask for a little more than memory uniqueness and this is what we call coherence and proceed now to define.

Definition 1 Coherence, written , is the smallest symmetric relation such that:

-∀i, j : i = j ⇒ i • m j • m; -∀m 1 , m 2 : m m ⇒ m 1 • m m 2 • m .
Memories are coherent if they branch on a fork.

Definition 2 A monitored process is said to be coherent if its memories are pairwise coherent.

Coherence implies in particular that memories are unique in a coherent term, since coherence is irreflexive. But, as said, it is a bit stronger than that. For instance * , b,

0 1 P | * , a, 0 1 Q is not coherent, even if its two memories are distinct.
Define inductively the fork structure λ(m) of a memory m:

λ( ) = λ( * , a, Q • m) = λ( m , a, Q • m) = λ(m) λ( i • m) = i λ(m)
An additional coherence requirement could be that for any memory m occurring in a process R, λ(m) is exactly the forking address of m in R, where by the forking address of m in R we mean the binary string over {1, 2} locating the thread with memory m in R. For an example of a process violating this extra condition, consider: * , a, 0 1 1 0 | 2 0.

From RCCS to CCS and back

Our calculus is clearly only a "decoration" of CCS, a decoration which can be erased by way of the forgetful map ϕ : RCCS → CCS:

ϕ(m P ) = P ϕ(R | S) = ϕ(R) | ϕ(S) ϕ((a)R) = (a)ϕ(R)
Conversely one can lift any CCS process to RCCS with the map (P ) = P . One has that ϕ • is the identity but not the converse ! If we go back to our first example, we see that (ϕ(R)) = (b.c.0 | c.0). The transformation • ϕ is blanking all memories in a monitored process.

RCCS structural congruence

We now want to extend the additive structural congruence defined earlier on simple processes, to monitored processes. The most important additional rule is the following:

m (P | Q) ≡ ( 1 • m P | 2 • m Q) (1)
It explains how memory is distributed when a process divides in two sub-threads.

We see that each sub-thread inherits the father memory together with a fork number indicating which of the two sons the thread is.

Another rule we need is:

m (a)P ≡ (a)m P (2)
Both rules have a natural left to right orientation corresponding to forward computation. Take note also that both these memory rearrangements are invisible in CCS, e.g., ϕ(m

(P | Q)) is actually equal to ϕ( 1 • m P | 2 • m Q).
Structural congruence on monitored processes is then obtained by combining these two identities together with additive congruence. In other words, two processes are structurally equivalent if related by the smallest equivalence relation generated by the identities (1), (2) above, by additive congruence identities, and closed under all syntactical constructs. Lemma 3 Coherence is preserved by structural congruence.

The only case where memories are modified is in using identity [START_REF] Milner | Communication and Concurrency[END_REF] where a given

m is split in 1 • m and 2 • m. By definition 1 • m 2 • m and an m is coherent with m iff it is coherent with both 1 • m and 2 • m. 2
Usual identities associated with the product, such as P | Q ≡ Q | P are not considered here because memories are using the actual product structure of the term to memorize the fork actions. A quotient would force the manipulation of terms up to tree isomorphisms on memories. That is possible and perhaps even interesting if one wants a more mathematical view on the calculus, but certainly results in a less convenient syntax.

Transition Rules

It remains to define a proper notion of computation. To this effect, we use a labelled transition system, LTS for short, that is to say a family of binary relations over monitored processes. Specifically, transitions are of the form:

R µ:ζ -→ S,
where R, S are monitored processes, ζ is a directed action, that is either a forward action or a backward action, while µ is an identifier, that is either a memory or a pair of memories:

ζ ::= α | α * Directed Actions µ ::= m | m, m Identifiers
Basic Rules. First we have the basic transitions concerning threads:

act m α.P + Q m:α -→ * , α, Q • m P act * * , α, Q • m P m:α * -→ m a.P + Q
The first transition is a forward transition whereby the thread does an action α.

A memory triplet * , α, Q containing this action, as well as the leftover part Q is pushed on top of the memory, and the thread proceeds further down its code. The first element in the memory triplet ' * ' stands for an unidentified partner.

The transition itself is indexed by the action α so that it can be synchronized with a transition bearing a complementary action, and the memory m, which will be used to identify oneself in the synchronization.

The second transition goes backward. The process is now undoing an action which is on the top of its memory and is therefore the last action it took. As we discussed already, many actions may have happened in the meantime in the global computation, but none originated from that particular thread, or they were undone before. Backward actions are treated on a par with forward actions and in particular, backtracking also involves communicating.

Contextual Rules. We have seen what transitions a thread may trigger. These transitions can also be done in a context:

R µ:ζ -→ R par-l R | S µ:ζ -→ R | S R µ:ζ -→ R par-r S | R µ:ζ -→ S | R R µ:ζ -→ R ζ a res (a)R µ:ζ -→ (a)R R 1 ≡ R µ:ζ -→ R ≡ R 1 ≡ R 1 µ:ζ -→ R 1
where in the (res) rule, ζ a means that ζ is none of a, ā, a * or ā * . The last rule says that one can freely choose a representative in the structural congruence class before triggering a transition. It is used to push memories down threads using identities (1), [START_REF] Lévy | Réductions optimales en λ-calcul[END_REF] with their natural orientation.

Synchronization Rules. We end the description of transitions with the forward and backward synchronization rules.

Both kinds of synchronizations use a notion of address instanciation in monitored processes. Given a monitored process R and memories m 1 , m 2 , a new process R m2@m1 is obtained by replacing in R all memories of the form * , α, Q • m 1 with m2, α, Q • m 1 . This is used in forward synchronization to let the thread know the name of the other thread it synchronized with.

The complete definition is as follows:

((a)R) m2@m1 := (a)(R m2@m1 ) (R | S) m2@m1 := (R m2@m1 | S m2@m1 ) ( P ) m2@m1 := P ( i • m P ) m2@m1 := i • m P ( m , α, Q • m P ) m2@m1 := m , α, Q • m P ( * , α, Q • m P ) m2@m1 := * , α, Q • m P if m = m 1 ( * , α, Q • m P ) m2@m1 := m2, α, Q • m 1 P if m = m 1
When R is a coherent process, there can be at most one memory of the appropriate form, and therefore R m2@m1 and R differ at most at that particular location. With this definition in place, we can formulate neatly the synchronization rules:

R m1:α -→ R S m2: ᾱ -→ S syn R | S m1,m2:τ -→ R m2@m1 | S m1@m2 R m1:α * -→ R S m2: ᾱ * -→ S syn * R m2@m1 | S m1@m2 m1,m2:τ * -→ R | S
Backward synchronization discussed. As one can see in the definition, backward synchronization is also a communication. Once a thread T in R has used (syn), its memory is instanciated, and the resulting T m1@m2 cannot backtrack if not with rule (syn * ). One doesn't roll back a synchronization all alone. This "locking effect" can be illustrated with the following example:

(a.0 | ā.0) ≡ 1 a.0 | 2 ā.0 1 , 2 :τ -→ 2 , a, 0 • 1 0 | 1 , ā, 0 • 2 0
Both threads are locked together, and the only way backward for them is to synchronize again:

act * * , a, 0 • 1 0 1 :a * -→ 1 a.0 act * * , ā, 0 • 2 0 2 :ā * -→ 1 a.0 syn * 2 , a, 0 • 1 0 | 1 , ā, 0 • 2 0 1 , 2 :τ * -→ 1 a.0 | 2 ā.0
Relation to CCS. Write R → S if there exists a computation leading from R to S in RCCS, and likewise P → Q if there exists a computation from P to Q in CCS.

Lemma 4 If P → Q and ϕ(R) = P , then R → S for some S such that Q = ϕ(S).

To see this, it is enough to forget about backward actions in the LTS above. Then it becomes the ordinary LTS for CCS with memories being useless additional notations. 2 Thus any RCCS term R, such that ϕ(R) = P , can simulate P 's behaviour in a purely forward manner. Of course, what one would like some form of converse guaranteeing the consistency of the backtracking mechanism. We will provide such a converse later in the paper (corollary 1).

Coherence. The transition system which we presented gives means of defining computation traces. Especially convenient is the fact that one doesn't have to work up to associativity and commutativity of the product and therefore gets a simple naming scheme for threads, where a thread can be uniquely identified by its memory. We have to verify that transitions don't disturb this naming scheme and preserve coherence.

Lemma 5 If R µ:ζ -→ S and R is coherent, then so is S.
Basic transitions are only adding to, or chopping off the stack, a triplet of the form m, α, Q , and therefore clearly preserve coherence. Among the other rules, with the exception only the structural congruence rule (≡) and the synchronization rules (syn) and (syn * ) modify memories. The case of structural congruence was already dealt with in a previous lemma. Synchronizations only instantiate or de-instantiate one memory top at a time (because the process undergoing the transition is itself coherent), and this is again a transformation clearly preserving coherence. 2

As a consequence, any process obtained from some (P ), where P is a CCS process, is coherent. Thereafter, we will assume all processes to be coherent.

Interlude

Let us have a short example before going to the causality section. Three convenient bits of notation will ease the reading. First, and although only the canonical notation gives a robust naming scheme, we use fork structures λ(m) instead of full memories m as identifiers. Second, we use n-ary forks though this is not official notation. Last, when the choice left over in a choice action is 0, we just don't write it. That said we can run our example:

(x.a.P | ȳ.x | y.Q) ≡ 1 x.a.P | 2 ȳ.x | 3 y.Q 2 , 3 :τ -→ 1 x.a.P | 3 , ȳ 2 x | 2 , y 3 Q 1 , 2 :τ -→ 2 , x 1 a.P | 1 , x 3 , ȳ 2 0 | 2 , y 3 Q 1 :ā -→ * , a 2 , x 1 P | 1 , x 3 , ȳ 2 0 | 2 , y 3 Q
One sees how the repeated synchronizations create a causal bottleneck: the synch on y caused the synch on x, which in turn caused the a action. Therefore, this sequence of three events is completely sequential and cannot be rearranged in any other order. Nothing is concurrent in this computation. That much is obvious. Less obvious is the fact that one doesn't need to go through the whole computation to realize this. It can be read off the stacks directly in the final process. The rightmost thread wants to backtrack on y with 2 (identifying the middle thread), the middle thread wants to backtrack on x with 1 (identifying the leftmost thread), while the leftmost thread wants to backtrack on a all alone.

The point of the next section is to prove that this property holds in general. Backtracking an event is possible when and only when a causally equivalent trace would have brought this event as the last one. In our example there is no other equivalent trace, and indeed no other action than a can be backtracked.

This example illustrates another point made later. Suppose a is declared to be unbacktrackable, or irreversible, then the process now behaves as P | Q. The last section will extend RCCS and integrate such irreversible actions.

Causality

Transitions and Traces

We need first to go through a few standard definitions.

Recall that a transition t is given by a triplet R µ:ζ -→ S with R, S monitored processes, µ an identifier (that is either a memory or a pair of memories) and ζ a directed action. One says then that R is the source and S the target of t and that S and R are its ends. Transitions will be ranged over in this section with t, t , . . . and similar symbols. Two transitions are said to be coinitial if they have the same source, cofinal if they have the same target, composable if the source of the second is the target of the first. A transition is said to be forward or backward depending on whether its associated action µ is forward or backward.

Sequences of pairwise composable transitions will be called computation traces or simply traces, and will be ranged over by r, s, etc. All notions just defined for transitions extend readily to traces. In particular a trace will be said forward if all transitions it is composed of are forward. The empty trace with source R is denoted by R and when r and s are composable, their composition is written r; s. A derivable transition is one that can be derived using the LTS of the second section. We have had examples of these already. From now on we will assume all transitions and traces to be derivable and with coherent ends (equivalently coherent sources) since these are the ones of interest.

If t is such a transition with identifier µ = m 1 , m 2 , then it must have been obtained by a synchronization, and hence m 1 and m 2 have to be distinct, since one is assuming all processes to be coherent. So identifiers can be considered as sets (with either one or two elements) and be handled with set-theoretic operations. Transitions involving a one element memory will be termed unary, others will be termed binary.

Another noteworthy point is that a derivable transition is essentially derivable in a unique way. The only freedom is in the application of the ≡ rule and apart from the additive congruence, it only involves pushing memories past restrictions and products. Definition 9 Keeping with the notation of the square and loop lemmas above, one defines the causal equivalence, written ∼, as the least equivalence relation between traces closed under composition and such that:

t 1 ; t 2 /t 1 ∼ t 2 ; t 1 /t 2 (3) t; t * ∼ R (4) t * ; t ∼ R (5)
As said earlier, this is the analogue in CCS of the Berry-Lévy notion of equivalence of computation traces "by permutation" [START_REF] Lévy | Réductions optimales en λ-calcul[END_REF]. The "square" part of the definition was already considered by Boudol and Castellani [START_REF] Boudol | Permutation of transitions: An event structure semantics for CCS and SCCS[END_REF] and they were well aware of the connection to Lévy's theory.

RCCS as a Lévy labelling

Theorem 1 Let s 1 and s 2 be coinitial, then s 1 ∼ s 2 iff s 1 and s 2 are cofinal.

By construction if s 1 ∼ s 2 , then s 1 and s 2 must be coinitial and cofinal, so the only if part is trivial. The if part is not. We first need a lemma.

Lemma 10

Let s be a trace, there exists r, r both forward such that s ∼ r * ; r .

We prove this by lexicographic induction on the length of s, and the distance to the beginning of s of the earliest pair of transitions in s contradicting the property. If there is no such contradicting pair, then we are done. If there is one, say t ; t * , and µ(t ) ∩ µ(t * ) = ∅, then t and t * can be swapped by virtue of the square lemma, resulting in a later earliest contradicting pair, and by induction the result follows since swapping keeps the length constant. Suppose now µ(t )∩µ(t * ) = ∅, and suppose further that t is unary and write m for µ(t ). By definition of a unary transition t is pushing some triplet * , α, Q on top of the stack at m, a triplet which t * is then popping. This forces t * to be unary as well, since there is no partner it may synch backwards with. But then t = t and one can apply the loop lemma, hence the total length decreases and again by induction the result follows.

Suppose finally t is binary, then t * has to be as well, because of the locking effect discussed above, and again t = t and the loop lemma applies and so does the inductive hypothesis.2

Intuitively, the lemma says that, up to causal equivalence, one can always reach for the maximum freedom of choice, going backward, and only then go forward. Even more intuitively, one could picture such traces as parabolas, the process first draws potential energy from its memories and only then moves onward. So let us call such traces parabolic. 5Our lemma already has an interesting corollary, namely that backtracking is consistent with respect to CCS, in the weaker sense that RCCS will not generate traces reaching processes the projections of which are unreachable in CCS.

Corollary 1. P → Q if and only if for some R, (P ) → R and ϕ(R) = Q.

The only if part is easy, basically saying that forward CCS computations can be simulated by RCCS ones, a fact that was recorded as an earlier lemma. The if part follows from the lemma above. Indeed, suppose s is an RCCS trace with source (P ) and target R, then the lemma says s ∼ r * ; r for some well chosen forward traces r and r , but then surely r must be empty since its source is (P ) a process that has an empty memory and therefore is incapable of backtrack. So that there is forward trace r equivalent to s. Since forward computations coincide in both systems, P reduces to ϕ(R). 26 Lemma 11 Let s 1 , s 2 be coinitial and cofinal traces and s 2 be forward, then there exists a forward trace s 1 , shorter than s 1 and such that s 1 ∼ s 1 .

We prove this last lemma by induction on the length of s 1 . If s 1 is forward we are done. Else by lemma 10 we may suppose s 1 is parabolic. Let t * ; t be the only two successive transitions in s 1 with opposite directions and call µ the identifiers of t * . Whatever t * takes off the memories in µ has to be put back later down s 1 by some forward transition. Else, because s 2 is forward the difference will stay visible. Call t the earliest such transition in s 1 . For the same reason, that transition t has to be the exact inverse of t * . One can then bubble up t to meet with t * . Indeed, if a transition is conflicting with t on its way to t * , by construction it must be some forward transition t the application of which results in a memory in µ, which is impossible since no backward transitions happened since t * . So by applying repeatedly the square lemma, and then applying [START_REF] Priami | Application of a stochastic name-passing calculus to representation and simulation of molecular processes[END_REF], one obtains a shorter equivalent s 1 and conclude by induction. 2 Proof of theorem. With our lemmas 10 and 11 in place, we can handle the theorem.

Let then s 1 , s 2 be two traces with same source and target. We prove these are causally equivalent, using a lexicographic induction on a pair consisting of the sum of the lengths of s 1 and s 2 , and the depth of the earliest disagreement between them. By lemma 10, we may suppose these are parabolic. Call t 1 and t 2 the earliest transitions were they disagree. There are three main cases in the argument depending on whether these are forward or backward.

1. If t 1 is forward and t 2 is backward, one has s 2 = r * ; t 2 ; u and s 1 = r * ; t 1 ; v for some r, u, v. Lemma 11 applies to t 1 ; v which is forward, and t 2 ; u which is parabolic, so t 2 ; u has a shorter forward equivalent, and so s 2 has a shorter equivalent and the result follows by induction.

2. If t 1 , t 2 are both forward, they can't possibly be conflicting. Suppose they take different additive choices in a same thread, say m α.P + α .P + Q, respectively pushing on the memory * , α, α .P + Q and * , α , α.P + Q . Since by assumption t 1 and t 2 are not the same transition, P and Q have to be different (not even additively congruent that is), and this difference would stay visible onward contradicting s 1 and s 2 being cofinal.

So whenever they work on a same thread they have to make the same additive choices. In particular, this rules out the case where they are both unary, and also the case where they are both binary and working on the same two threads. Let us check the other cases. If one of the transitions is unary and the other is binary, their actions can't coincide on their common memory, since one will push a triplet of the form * , a, Q and the other will push one of the form m, a, Q for some m = * . If both are binary and only intersect on one memory, then again the triplets are distinct since the other partner identifiers, say m 1 and m 2 are different, because these identifiers come from different threads and all processes are assumed coherent. In any case, there would be a visible and permanent difference.

So we know they are indeed concurrent. Call µ 2 the identifier of t 2 . Since t 2 is forward and s 2 is parabolic, whatever t 2 pushes to µ 2 is staying there onward in s 2 . Hence, there must be a transition at µ 2 in s 1 as well, call it t 2 , so that s 1 = s; t 1 ; u; t 2 ; v. That transition has to be of the same arity as t 2 , and with µ(t 2 ) = µ 2 , else again the difference stays visible onward. Since s 1 is parabolic as well, all transitions in u, standing in between t 1 and t 2 are forward and one can apply repeatedly the square lemma and bubble up t 2 , to get s 1 a trace equivalent to s 1 and of the form s 1 = s; t 1 ; t 2 ; u; v. A last application of the same square lemma yields an equivalent s 1 with a later earliest divergence with s 2 and same length so that one can call on the induction hypothesis.

3. Suppose finally both t 1 and t 2 are backward. They can't possibly be conflicting either, because of the locking effect, so they must be concurrent. Either actions undone by t 2 are redone later in s 2 , in which case one argues as in lemma 11 and shortens s 2 into an equivalent s 2 , or they are not redone and therefore these same actions must be undone also in s 1 , else there would be a visible difference between their visible targets, and one argues as in 2 above. 2

Irreversible Actions

Having finally reached for the theoretical property we wanted, we now turn to a more practical issue, namely that of integrating unbacktrackable or irreversible actions in RCCS.

These will be written a, ā, etc. The transition system is adapted by adding rules for the new actions:

commit m κ.P + Q m:κ -→ • • m P R m1:κ -→ R S m2:κ -→ S syn• R | S m1,m2:τ• -→ R | S
with κ ranging over irreversible actions. Since an irreversible action will never be backtracked, there is no need to remember anything, and we use instead of the usual triplet, a placeholder • . For the same reason, there is no rule inverse to (commit), and no longer a need to instanciate R and S in the synchronization rule. One sees that the syntax hardly changes, and that when all actions are taken to be irreversible, it essentially becomes CCS. What was proved in the last section remains valid.

We have seen in Section 3 that all actions that caused the action a became de facto unbacktrackable, even if they were themselves reversible. It seems therefore interesting to understand how irreversible actions can "domino-effect" in a process and this is what we do now.

Propagating irreversible actions

Let M R stand for the set of occurrences of memories in R. Say a memory is locked in R if no trace starting from R can modify it, that is to say, whenever R → S, there is an m ∈ M S such that m ≤ m for the prefix ordering. Let L R be the subset of M R formed of these locked memories.

Lemma 12 L R satisfies:

1. • • m ∈ M R ⇒ • • m ∈ L R 2. m ∈ L R , m ≤ m ⇒ m ∈ L R 3. m, α, P • m ∈ L R ⇒ m , ᾱ, Q • m ∈ L R 4. i • m ∈ L R ⇒ j • m ∈ L R
Points 1 and 2 are obvious, point 3 is saying that in order to backtrack a synch, one needs to do a synch, a fact which we called the locking effect, and point 4 is saying that to undo some action in i • m, one has first to fuse back with one's former sibling in the fork. 2

Coherence alone is not strong enough for these closure properties to capture all locked memories. For instance, m is locked in 1 • m P simply because the fork sibling is missing. However it does for CCS reachable processes.

An example

To illustrate how the lemma works in practice to simplify processes, let us consider the usual encoding of internal sum in CCS: so that in the end all memories are locked in R a and R b , and R has been turned into a weak external sum !7

Conclusion

We have proposed an enrichment of CCS with memories which processes can use to backtrack. Memories are themselves distributed and the syntax stays close to the original concept of CCS. On the theoretical side, we have proved that backtracking is done in exact accordance with the true concurrency concept of causal equivalence. We also have shown how to integrate irreversible actions, and have given a procedure collecting obsolete memories. There are many directions in which this study can be extended. First, one should rephrase this construction in terms of Winskel's event structures for CCS [START_REF] Winskel | Event structure semantics for CCS and related languages[END_REF]. RCCS seems to provide an internal language for reversible event structure and this should be made a precise statement. Second, one should seriously study the notion of bisimulation that is generated by the LTS and study process composition in RCCS, perhaps using notions of history-preserving bisimulations [START_REF] Marek | Hereditary history preserving bisimulations or what is the power of the future perfect in program logics[END_REF]. Third, preliminary investigations show that the whole strategy developed here can be imported in π-calculus. There are more things to be remembered and the amount of symbol-pushing needed for a comparable theory gets daunting. So, beginning within the simpler framework of CCS might have been good start. But π is a lot more expressive and this is a strong incentive to develop a notion of reversible π-calculus. Besides, one could think of bootstrapping the system and encode reversible π into π.

Finally, the example of the internal sum given in the last section is strongly suggesting that transactional mechanisms can be understood in terms of RCCS. One starts with a rough encoding of the external sum, which is the simplest possible transaction in some sense. And since RCCS provides a foolproof deadlock escape mechanism on reversible actions, carefully choosing them results in a correct encoding. We feel that one contribution of the current paper is to lay down the foundations to explore this matter further.

2. 1 A

 1 Syntax for Backtrack Simple processes. Simple processes are taken from CCS [1]: Actions: α ::= a | ā | . . . Action on a channel | τ Silent action Processes: P ::= 0 End of process | α i .P i Guarded Choice | (P | P ) Fork | (a)P Restriction

4. 2 Definition 7

 27 Causal equivalence Lemma 6 (Loop) For any forward transition t : R µ:α -→ S, there exists a backward transition t * : S µ:α * -→ R and conversely. Given s a forward trace, one can then obtain s * a backward trace, by applying repeatedly the lemma and reversing all transitions in s. Let t 1 = R µ1:ζ1 -→ S 1 and t 2 = R µ2:ζ2 -→ S 2 be two coinitial transitions, t 1 and t 2 are said to be concurrent if µ 1 ∩ µ 2 = ∅. Lemma 8 (Square) Let t 1 = R µ1:ζ1 -→ S 1 and t 2 = R µ2:ζ2 -→ S 2 be concurrent transitions, there exists two cofinal transitions t 2 /t 1 = S 1 µ2:ζ2 -→ T and t 1 /t 2 =

  (x.0|x.a.P |x.b.Q), with x chosen reversible and a, b irreversible. With the usual notational simplifications, and representing locked memories with heavy angles | | :R → (x)( 2 , x 1 0 | | • | 1 , x 2 P | 3 x.b.Q) =: R a R → (x)( 3 , x 1 0 | 2 x.a.P | | • | 1 , x 3 Q) =: R bUsing clauses 2, 3, 4, one can tag further memories as locked:R a = (x)( | 2 , x| |1| 0 | | • | | 1 , x| |2| P | |3| x.b.Q) R b = (x)( | 3 , x| |1| 0 | |2| x.a.P | | • | | 1 , x| 3 Q)

This crucial property can be recast in topological terms, by saying that RCCS is the universal cover of CCS.

General sums are not allowed in the syntax; here as in the following, all sums will be supposed guarded.

The converse decomposition as r; r * would not work. Indeed, a backward transition can create some new forward possibility. Consider for instance * , a, b.P 0 that can go to * , b, a.0 P in a backward step followed by a forward one. There is no way these two steps can be swapped or be cancelling each other as in the argument above.

The fact that (P ) has an empty memory is essential in the statement. We may consider again the same example * , a, P 0 which can move, while its projection ϕ( * , a, P 0) = 0 can't.

By weak external sum, we mean that R has infinite traces where it constantly hesitates between its irreversible actions a and b.


Jesus Gonzalez-Feliu

Bruno Faivre D'arcier

Josep-Maria Salanova Grau

Tiphaine Hervé

Fernando Zubillaga

Zeljko Jeftic

Jean-Baptiste Thebaud

Bruno Faivre

The deployment of urban logistics solutions from research, development and pilot results. Lessons from the FREILOT Project

Keywords: urban logistics services, deployment, cost-benefit analysis, barriers, business model

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

Introduction

Urban commercial and goods transport is a necessary but disturbing activity. To deal with the main nuisances related to it (mainly congestion, noise, global warming and local pollution), public and private stakeholders have studied and developed methods and solutions of different nature and dimensions. We observe in transport research hundreds of works dealing with the subject of commercial and goods transport, but the number of operational urban logistics systems is very small. This is the case of urban consolidation centres (UCCs) but not only. Indeed, although several projects have been developed and tens of pilots and demonstrators have been seen in the last ten years, most of them end without a deployment of the developed technologies or organizational solutions. However, also a few projects have resulted on operational solutions nowadays implemented or in mature solutions able to be deployed. In the first group we observe the UCCs of Padova in Italy, the proximity delivery services of Chronopost, Colizen and La Petite Reine in France.

In the context of the above this paper aims to present the main issues related to the deployment of urban logistics solutions as suggested by research and development results, and tested in the context of real urban environment demonstration actions. First, we will present the main stages in deploying a technological or organizational solution, based the scientific and practice-related state-of-the art. Then, we present one example extracted from the FREILOT1 project (the Delivery Space Booking service) and its main evaluation results. After presenting the main business model elements, the focus of this paper will be on cost benefit analysis and deployment barriers. Finally, we propose a set of guidelines for public authorities and transport practitioners to deploy urban logistics solutions.

Deployment issues in the FREILOT project

The FREILOT project has been carried out between March 2009 and September 2012. It is focused not on pure or applied research but in the phases of demonstration and deployment. For that reason, 5 technological solutions have been implemented and tested in four European cities, enabling services that are related to four service domains covering the entire delivery operation scope. The domains and service related to each of them are summarized in the following:

• Traffic management domain o Service 1: Intersection Control Optimised for Energy Efficiency (EEIC): The FREILOT freight distribution vehicles get moderate priority when they approach the intersection, this increases non stopping and improves the traffic flow and energy consumption. At the same time, they get information about the traffic light phases (when it will be in red, green...) and therefore, drivers can adapt their speed. This facilitates an active collaboration and interaction between vehicles and traffic light management systems, as the drivers could adapt their speed and reduce stops, improving also city's road security.

• Vehicle operation domain o Service 2: Acceleration and Adaptive Speed Limiters (AL & ASL): The service solution proposed in FREILOT gives the possibility to define geographical zones to facilitate adaptive vehicle speed or acceleration limitation. This can be done by the fleet operator or by the city council in order to regulate the access and the accessibility conditions of certain areas of the cities, such as pedestrian streets or limited traffic zones, among others.

• Driver behaviour domain o Service 3: Enhanced "Eco Driving" Support (EDS): The solution adopted in FREILOT, promotes efficient driving, reduces emissions and noise pollution by reducing non-ecodriving behaviours like rapid acceleration, noise and fuel consumption, and thereby also emissions.

• Fleet management domain o Service 4: Delivery Space Booking (DSB): The service solution proposed in FREILOT gives the possibility to plan the deliveries, by reducing travel times, improving traffic flow conditions and therefore, reducing energy consumption and working time for delivery execution. This service will provide the basis for enhancing the use of city delivery facilities by the existing distribution demand and therefore will improve the service supplied by the city.

Different stakeholders can be interested on such services provisioning and exploitation. Two main goals have been identified [START_REF] Elorza | FREILOT. Urban Freight Energy Efficiency Pilot. D.FL.6.1 Business model[END_REF] for involving service provisioning:

• Public Goal: Administrations, like cities or other road authorities, are the Service Direct Users or customers, in the EEIC and DSB services.

• Private Goal: Depending on the FREILOT service analysed, the technology providers will be the Service Providers (VOLVO, RENAULT Trucks, PEEK, GERTEK) and the Fleet Operator will be the Service Direct Users in all 5 FREILOT services.

In order to study the deployment issues of such service enabling technologies, it is important to craft the necessary environment and context to bring these services to real life operation of the city. To do this, a business model is needed. A starting point for building the business model is the selection of target market segments. This model describes the value that is delivered to customers, how customers are being charged, and what business context and processes need to be built in order for the business to be successful. On the other hand the identification of all possible barriers for the deployment of the services will be listed and linked to potential solutions. For understanding the value to stakeholders it is necessary to understand what the individual benefits of each service are and what is needed to bring and keep them alive and profitable. It is then important to provide a consequent cost benefit analysis to support the business model and help decision makers find arguments and solutions to the identified barriers. Finally, an exploitation plan describes the induction of the business and how to sustain and expand the business. One pillar of the plan is the certification and regulatory actions that need to be performed.

This comes down to the following structure for the business model strategy, where overall process and specific work is listed [START_REF] Elorza | FREILOT. Urban Freight Energy Efficiency Pilot. D.FL.6.1 Business model[END_REF]. In this paper, we will focus on cost benefit analysis and on deployment enablers and barriers for two systems, i.e. DSB and EEIC).

The delivery space booking service

In the FREILOT pilot cases, two DSB applications have been tested, one in Bilbao and one in Lyon. In this section we introduce them, as well as the main conclusions of the evaluation results.

DSB device in the city of Bilbao

The Delivery Space Booking service application for Bilbao uses the Urban Merchandising Distribution Management (UMDM) system, which has been implemented by GERTEK, the company currently managing the parking system in Bilbao. UMDM is an innovative system for the real-time management of urban delivery spaces, built upon the Open Parking System (OPS) functionality. This is currently the only system that guarantees rotation in parking place usage through real-time control of maximum time limit parking slot occupation and time limit of return to the restricted zone. The UMDM system allows a real-time booking procedure if there is a free slot that no one is using. The system also allows fixed periodic bookings for a period of 3 months allowing in this way a medium time organization to fleet operators. The UMDM system is however neither able to provide an Estimated time of Arrival (ETA) nor to manage conflicts due to drivers not respecting the booking plan. The system allows the fleet manager to book in advance an urban delivery space specifying the time of the day required and the type of vehicle to be used. For the road operator, it provides the possibility to optimise the management of delivery spaces through better knowledge of the delivery time period and duration in order to improve the flow of vehicles, to reduce negative impacts due to double lane stops, to reduce consequent traffic congestion and to reduce negative environmental impacts in urban areas. Through real-time centralization with control by truck type identification, the UMDM system guarantees the fulfilling of the freight space city ordinance, i.e., maximum allowed parking time, scheduling of each delivery space usage, identifying vehicles that are not allowed to use the delivery space etc. The initial booking procedure is done via Internet by fleet operators. The system also supports bookings directly on the parking machine near the delivery bay. All data and real-time operations are stored/ updated in the main server, which will be supported by a maintenance office. UMDM is also prepared to interface with an additional identification system based on Detection loops and sensors which can identify vehicles that are not allowed in the delivery space as well as double parked cars.

Table 1. General requirements of the DSB service in Bilbao

For pilot purposes the loading/unloading timetable is from Monday to Friday from 8:00 am to 13:00 pm.

Public and private truck operators can participate in the pilots.

Loading/unloading operation time is fixed to 30 minutes. However due to some extra requirements the slot might vary in order to find the optimum time frame for the operations.

The same truck is able to book as many slots as required in one day.

However the same truck can never book two consecutive slots.

Real-time booking lasts for 30 minutes. However depending on the circumstances the system can supply more time.

• If the bays are free for more than 30 minutes the user will have this extra time. E.g. 16 min + 30 min = 46 min. • If the time remaining to the use of the delivery space is less than 30 minutes the system won't be able to supply any loading/unloading slots. • If the loading/unloading activity finishes before the time is over, the remaining time will be available for the next real-time booking.

During the pilot even trucks over the permitted weight (9.5 tons) are allowed to use the delivery spaces in order to find the validity of the service for all types of trucks. These trucks must have a special permit.

The system assigns the bays in the order listed below: (in order to allow trucks to have 2 or 3 bays):

• Bay 1 -in the right extreme.

• Bay 3 -in the left extreme if there are 3 places.

• Bay 2 -in the middle, always the last bay.

Each delivery space is equipped with a city parking toll system and it is painted for the pilot in a unique and easily recognizable way:

• Each bay has a painted identification number, which will go from 1 to 3

• Each bay has 5 LEDs (Light Emitting Diodes) to operate it.

Drivers must identify themselves with a chip card when parking in the bay.

The delivery space booking application of Bilbao consists then of three subsystems: an invehicle application for handling delivery space reservations, a delivery space operator backoffice system and a fleet operator back-office system. Two use cases of booking a loading and unloading space are supported:

1. Internet booking A fleet manager uses a web-based back-office system connected to the delivery space operator back-office. Once the vehicle is at the delivery space it should identify to the delivery space operator back-office which grants or denies the access to the delivery space area. There are two different ways of booking through internet:

-Fixed booking: This option implies that the reservation will last up to 3 months. This system provides fleet operators with a medium term time horizon organization of delivery plan improving current fleet management functions.

-Daily booking: This option will be used if the fleet operator wants to book the delivery space for a concrete day for 30 minutes. This operation should be performed at the latest 1 hour in advance. In both cases the time slot for booking is 30 minutes.

Real-time booking

Drivers are also allowed to book delivery spaces during the execution of their delivery schedule. This kind of reservation must be done through parking toll poles in real-time if the delivery space is not occupied and free of reservation and has not been reserved at this time. This function is quite important as it will discourage private cars to park at the delivery spaces.

DSB device in the city of Lyon

The Delivery Space Booking application for Lyon is based on the work done in the European project Cooperative Vehicle-Infrastructure System, CVIS. The goal of this application is to support the driver, fleet manager and road operator (including parking zone operator) in the booking, monitoring and management of the urban parking zones for freight driver activities. The system allows the fleet manager to book in advance an urban parking zone specifying the time of day required, the duration required, the type of vehicle to be used, and possible dangerous goods transported. For the road operator, it describes the possibility to optimise the management of parking zones through better knowledge of the delivery time period and duration in order to: improve the flow of vehicles, reduce all negative impacts due to double lane stops, reduce consequent traffic congestion and reduce urban environmental impacts. The application is based on dynamic delivery space booking algorithms, taking advantage from the experience being made on the CVIS Parking Zone application development. As the objective of the pilot is to implement economically sustainable solutions which can be kept running even after the end of the FREILOT timeline. The application is scalable (starting from a 1st level configuration with the possibility to include additional functionalities and components by means of open interfaces). The proposed solution is based on Application Service Provider (ASP) software (derived from the CVIS Parking Zone Booking system developed by Thetis). The main stakeholders (Fleet operators, Municipality, Enforcement personnel) can access the application functionalities through the Internet with PCs and/or portable devices.

Table 2. General requirements of the DSB service in Lyon

The Fleet Operator can make requests for "delivery space slots", specifying the time of day required, the duration required and the parking area. The Vehicle System is able to accept a request from the Driver for a delivery space at a specific location, at a specific time, with a given duration for a specific type of vehicle. Regarding the parking area, time of day and duration, the Delivery Space Booking application is able to identify the nearest parking slot available. If necessary the Delivery Space Booking application will generate a response which proposes an alternative time slot and communicate this to the Vehicle. If necessary the Delivery Space Booking application will generate a response which proposes an alternative parking zone (with a parking slot associated) and communicate it to the Vehicle. The Vehicle provides the possibility to accept updates to the delivery space slot and the possibility for the Driver to accept or reject an updated slot.

The vehicle provides updates of its Estimated Time of Arrival (ETA) to the parking system as the vehicle approaches the delivery space. The Vehicle identifies itself when it is within a defined distance of the delivery space and it informs the Delivery Space Booking application. The Delivery Space Booking application processes the ETA and responds to the Vehicle with an indication of the availability of the requested delivery space. The Delivery Space Booking application manages every event raised by the possible parking infrastructure (if any) and knows the status of the Parking area. On receiving a Vehicle ETA, the Delivery Space Booking application determines if the delivery space is free at the given time. The Vehicle processes updated delivery space or holding zone bookings from the Delivery Space Booking application and presents the information to the Driver. The Parking System processes updated ETAs from vehicles and proposes alternate delivery space slots. The vehicle identifies the arrival at the delivery space and then notifies the Delivery Space Booking application The Delivery Space Booking application has the ability to detect that a Vehicle has exceeded the requested length of time at the delivery space. If a vehicle that currently occupies the delivery space is exceeding its booked time, the Delivery Space Booking application will send an alert to the enforcement personnel. When leaving the delivery space, the vehicle informs the Delivery Space Booking application that the delivery space is now free.

The delivery space booking application consists of two subsystems: an in-vehicle application for handling parking zone reservations and a parking zone operator back-office system. To reserve parking slots, a fleet manager uses the web-interface of the parking operator backoffice. During the vehicle trip, the estimated time of arrival is estimated to detect late or early arrival at the parking. At the parking entrance, the vehicle notifies the parking operator backoffice which grants or denies the access to the parking area.

Pilot operations and evaluation results.

Each system has been tested in its corresponding city. Bilbao's demonstration started in June 2010 and finished in December 2011, involving 45 companies and 95 vehicles. Lyon's action started in January 2011 and finished in June 2012, involving 4 companies and 6 vehicles. The pilots'details as well as the data collection issues and operational problems are seen in [START_REF] Blanco | FREILOT. Urban Freight Energy Efficiency Pilot. D.FL.4.1 Evaluation methodology and plan[END_REF] and [START_REF] Blanco | FREILOT. Urban Freight Energy Efficiency Pilot. D.FL.4.1 Evaluation methodology and plan[END_REF]. Since the aim of the paper is to present deployment issues, we present only the main results of the evaluation that are used for the deployment analyses. However, the evaluation was larger and included the collection and analysis of various data :

• Records from the reservation systems (of different nature and with different information for each city).

• GPS data collection for the analysis of instantaneous fuel consumption and CO 2 emissions (for a detailed description of this method, see Pluvinet etal, 2012).

• Infraction counting campaign (3-4 weeks baseline and 2-4 weeks pilot).

• Traffic counting (manual for Lyon, manual and authomatic for Bilbao).

• Qualitative analysis via questionnaire (mainly in Bilbao).

The main results of the evaluation are synthesised in below. First, we show in the following table the direct gains for a truck on each DSB, in a deployment situation. To obtain the gains shown below, we need to ensure a minimum capacity, without what it is not possible to deduce any gain due to the saturation of parking place, even when cars are not on delivery bays. For an in-depth DSB evaluation, see [START_REF] Blanco | FREILOT. Urban Freight Energy Efficiency Pilot. D.FL.4.1 Evaluation methodology and plan[END_REF]. Travel time is intended on the DSB's influence area (the loss is due to the security and the tranquillity drivers feel when legally parking their vehicle with respect to double line parking and other practices). However, another impact of DSB's less easy to quantify (at least directly from evaluation results) is that of traffic improvement due to the usage of a coherent network of delivery bays. That effect will be further quantified, from evaluation data and a simulation with a network of DSB's in a given city.

Cost benefit analysis

The cost benefit analysis (CBA) is the most used economic calculus tool for assessing the deployment of strategies in different fields [START_REF] Boardman | Cost-Benefit Analysis: Concepts and Practice, 3rd Edition[END_REF]. CBA provides a protocol for assessing the efficiency impacts of proposed policies. The patterns for the CBA are derived from standard CBA methodologies (for a review and CBA patterns, see DG [START_REF] Dg Regio | Guide to Cost Benefit Analysis of Investment Projects[END_REF]. Cost-benefit analysis are practical ways of assessing the desirability of projects, where it is important to take a long view (looking at repercussions in the further, as well as the nearer, future) and a wide view (allowing for side-effects of many kinds on many stakeholders and/or areas). In other words, it implies the enumeration and evaluation of all the relevant costs and benefits. This involves drawing on a variety of traditional sections of economic study -welfare economics, public finance, resource economics -and trying to weld these components into a coherent whole. For those reasons, we will develop a cost-benefit analysis derived from the method proposed by DG REGIO (2008).

Methodology and hypotheses

A CBA method consists in listing on one side all investment and operational costs, year after year, for a given time horizon (in general 30-40 years for infrastructure projects, i.e. DG [START_REF] Dg Regio | Guide to Cost Benefit Analysis of Investment Projects[END_REF]. Then benefits are also listed in the same time horizon. Then, year by year, benefits are confronted to costs and their difference is discounted (in France, by 4% for public bodies) in order to take into account the availability of money at different years.. Finally, the sum of these discounted amounts lets calculate the Net Present Value on a pre-determined period of time, from which can be derived the Internal Rate of Return (IRR). Although each technology has different settings and is associated to specific assumptions and hypotheses, we need to define a set of common assumptions to all scenarios in order to compare and assess them. The general hypotheses are associated to the way the money is obtained to invest and to the stakeholder that is making investments.

First, we assume a hypothetic city, making abstraction of the country. We assume a VAT of 20% and, for each system personnel costs equal to those of employees working during the pilot implementation, operation and evaluation phases (in case of pilots in different cities, the retained costs will be precised in the corresponding section). We assume the investor is a public authority, mainly a city, and the money to invest is available. If the public authority needed to loan it, interest rates should be added to the CBA, but as a first approach the assumption of money availability let the various readers have a first idea of profitability without complicating the analyses. Another important assumption concerns the time period where investments are made. Oppositely to public transport infrastructures (tramways, subways, urban-suburban trains), investments are not supposed to be made before the first year of operation, but the systems are introduced gradually. This assumption enforces that of money availability.

The CBA will be made on a 10-year horizon, which is enough long to ensure a return of investment and enough short to not need a strong technology change or replacement during the operation period. We also assume the level of operating costs and revenues as constant over this period. The discount rate is assumed to be the French public one, i.e. 4%. This rate varies from one country to another, and can be updated (as well as personnel costs and VAT)

when adapting the scenario assessment to cities of one precise country. Last but not least, we suppose that the target IRR (internal rate of return, i.e. the level of profitability requested by the investor) is that of the French public sector, i.e. 4%.

All simulations are based on the same city, a virtual 2.000.000 inhabitant urban area created from real data [START_REF] Modum | Mutualization and Optimization of Urban Freight Trips[END_REF]. Using the tools of evaluation in this context, i.e. generalising local effects to a city point of view, we estimate the costs and the benefits for the two main stakeholders: the city (or public authorities) and the transport carriers (or individuals).

Scenario characteristics and assumptions

When assessing a scenario, for a CBA or other forecasting analyses, it is important to explain well the context and the input variables by defining all the parameters and setting the various assumptions that allow building the scenario. In this section we present the main characteristics of the scenario that will simulate the deployment of a DSB service in the virtual city as well as the assumptions that have been made. To build a deployment scenario under realistic commercial, tactical and operational conditions, we suppose that the solution tested in Bilbao has been further developed and can be applied to existing parking machines in order to allow the possibility to make private car parking payment (for private parking places around the DSB) and booking operations for the DSB systems on the same machine. In that way, existing machines can be used for both private parking and DSB services. We suppose that all delivery bays with the DSB technology are deployed in a central area (about 3.5 km²). A total number of 100 DSB will be operational in 5 years, and we assume a total number of users (per year) of 1200 vehicles. We assume that one user corresponds to one vehicle and then one vehicle uses only one card. Because the cards can be lost, broken or stolen, we estimate that 15% of the users will need to replace their cards each year. The deployment trends of the system and the number of vehicles consequently using it are reported on the following table:

Economic cost-benefit analysis

First, an only economic cost-benefit analysis is made. To do this, we take the viewpoint of the service manager, on an economic perspective. We assume then that investment funds are available and that the installed devices are fully operational the year after they are deployed and the number of new carriers are operating and benefiting from the system the same year they become customers of the system, paying a yearly fee independently on the year period they start using it. The cost structure is the following: To finance the system and also to make it more efficient, it is necessary to ask a fee to the users, in order to both contribute to its development and be more involved in using it as well as in defending its good usage. Via an iterative CBA, an unitary benefit of 250€/year is found to lead to an internal return rate (IRR) of near 9%, larger than the requested 4%. Taken into account the sensitivity of the cost model, this IRR is enough to guarantee a return on investment and a correct operational follow-up of the system (in both functional and maintenance aspects). Assuming a VAT value of 20%, the unitary fee for the service is set to 300 € per vehicle and year.

Figure 2. Updated cost-benefit differential trend

After setting the minimum fee, a second analysis is made to include the environmental and social benefits, which are quantified into a monetary value. In this analysis, two viewpoints are studied : first, that of transport carriers (to see the interest of using the DBS service or not), then that of public authorities (to define the public utility rates and eventually reduce the fee by the amount that it is considered to be derived from the advantages the DSB service gives to the city in a collective way). From the evaluation, we observe that environmental and social costs for transport carriers are negligible, since the DSB are few and it is difficult to find a synergy. However, for the city, when positioning the DSB in a limited traffic zone (LTZ), the usage of these systems can be in synergy to the access conditions to the LTZ, and then the traffic nuisance reduction is possible to be taken into account.

User's socio-economic cost benefit analysis

After making an economic analysis for the service manager, it is important to study the service impacts on users and their cost-benefit differential to state on the feasibility of the system's deployment. To do this it seems important to first quantify the benefits of a DSB for a transport company. In this case, we can identify four direct benefits for a carrier:

• Fuel savings, directly translated into economic gains (money savings related to fuel consumption). • Time savings, also directly translated into economic gains (money savings related to timetabling and working hours).

• Distance savings, indirectly translated into economic gains (money savings related to vehicle usage).

• CO2 savings, which can be related to economic gains if a Carbon Tax is assumed.

Distance savings are small compared to each route total distance and the vehicle's life, so the impacts on vehicle usage (wheels, brakes) are assumed as negligible. Time savings directly

(€350 000) (€300 000) (€250 000) (€200 000) (€150 000) (€100 000) (€50 000) €0 €50 000 €100 000 0 1 2 3 4 5 6 7 8 9 10
Cummulated discounted cash flow related to the delivery stops are also negligible (less than 2 minutes per stop, less than the data collection incertitude threshold, although the trend is to increase slightly times, but not enough to result in significant changes on daily working hours). However, DSB leads to a decrease of parking infractions [START_REF] Blanco | FREILOT. Urban Freight Energy Efficiency Pilot. D.FL.4.1 Evaluation methodology and plan[END_REF] which is directly related to traffic improvements that have a positive impact on running time. So the only two variables that result in cost savings are fuel consumption and CO2 emissions, and time savings related to traffic improvement due to DSB usage.

We assume that the DSB areas will be created in order to consent the loading and unloading operations for carriers that are not DSB customers, i.e., to be developed in a non-congested situation. For this reason we assume a development of 100 DSB systems, with a daily time range of 14 hours (from 6:00 a.m. to 8:00 p.m), in order to allow a re-equilibration of the system and maximize the usage of each delivery bay. We extrapolate the results of Bilbao's DSB evaluation with a small calibration concerning small vehicles, the category the less concerned by the system (their characteristics and delivery behaviour show the need of stopping even when no place is available and the possibility to make double parking lines without significantly perturbing the traffic and the environment). In this context, we assume a unitary fuel and CO 2 savings per vehicle per DSB stop as follows: • The deployment of the DSB allows an average usage of the system, per vehicle, as follows:

o First year (16 DSB): 5 stops/route at DSB. o Second year (40 DSB): 8 stops/route at DSB. o Third year and more: 11 stops/route at DSB. • Savings related to double line avoiding are negligible for drivers in terms of fuel consumption and CO2 emissions. Moreover, time savings are negligible on parking but not when running. Indeed, a speed gain related to congestion decreasing has a direct impact on travel efficiency. The speed increase is estimated to be about 2 km/h in average in the considered area, i.e. an average gain in route of 20 min., corresponding to a time savings of 6% with respect to total travel time.

• Fuel savings are estimated in grams, then converted into litres using an average volumetric mass for fuel of 750 g/l. Moreover, a fuel cost of 1.3 €/l is assumed (this is the current value in France, according to CNR (2012), it can be updated to the current value for each country).

• Concerning CO2, we assume a carbon tax for each transport carrier. Although the current value is 17€/ton, we aim to set it to 100 €/ton2 , according to the last European Considerations (French Ministery of Land Use and Transport, 2005). In this configuration, a carrier having a standard route (see [START_REF] Pluvinet | GPS data analysis for understanding urban goods movement[END_REF], for more information about routes using DSB in Bilbao) would pay about 1175 €/truck each year (for trucks making urban distribution as those of DSB pilot). On the another hand, the direct benefits are small since the gain of CO2 and the current carbon prices give an average gain of 16 €/truck each year.

The benefit table for the transport carrier is the following: Assuming a fee of 300 €/vehicle each year, after year 5 and that each transport carrier would have an average benefit of 450 €/vehicle each year leads to a potential gain of 150 € per vehicle and year, mainly due to the congestion reduction (= time savings). Remains then to evaluate the gains for the city but the impacts for carriers are positive mainly due to a global effect: illegal parking reduction and better distribution of parking due to urban goods transport and loading/unloading.

Technology providers' acceptance

In order to ensure the large-scale development of the technologies, the FREILOT business models must convince technology providers that there is a big market for these products. In the case of the in-vehicle systems the solution proposed by the partners is to adapt the technologies to long haul trucks, thus accelerating service enabling technologies components introduction to freight vehicles.

Who will run the back office after the pilot and who will pay for it? During the pilot each system developer run the back office of the tested system, but after the pilot there is the need for a unique body in each city running the back office. For the invehicle systems the back office will define the zones and the speed limitations, but the other architecture issues will be managed by each truck manufacturer in cooperation with the fleet operators. For the DSB there is a need for a back office managing the parking places. The interoperability of the systems must be provided by a standardized platform and system, where the use of standards will give to everyone the possibility to connect. There is also the necessity for enforcement, control methods are needed, such as policy control, third parties or automatic control (cameras).

The economic viability of a private back office must be proved because the cities are not willing to run the back office. They want to decide zones, speed limits, DSB places and other staff, but the back office must be run by a private company. The city is not willing to pay for the back office, since the direct benefits apply only to fleet operators, not to the cities. The cities can pay the initial investment (short term), but not the maintenance (long term). The European Commission must provide rules on how to manage the back offices, in a pan-European back office systems definition.

Different schemes were provided by the partners for the back office:

• If each back office of the whole country is managed by one company, scale economies for a private company managing the DSB of all the cities will apply (always avoiding monopoly). • Another solution for funding is to give the back offices to already existing services paid by the cities (parking places management), scale of economy for the cities.

In order to assist in the management of the DSB places taking advantage of the experience created in the pilot, there is the necessity of developing a guidebook on how to manage the DSB places with the Spanish and French experiences. The booking (DSB) procedure (long term booking, FIFO3 booking) makes it difficult to manage the places. A priority ranking based on the real use of the places and the environmental characteristics of the truck should be implemented.

Another important issue is that of maintenance and service guarantee. If a problem appears, a solving service must be provided. During the pilot, a parking management company (Gertek) in Bilbao and a technical consulting company (Interface Transport) in France were ensuring this problem solving service. However, when technical (related to mechanics or electronics) or information system (related to communication and data exchange) problems appear, both technical and information science staff must be available, at least during the hours the service is active. When a specialised parking management company is involved (i.e. it becomes the service provider and management operator) this possibility is feasible. When a municipal service is assumed, it is important to subcontract technical assistance, with a defined intervention contract, to avoid dysfunctions and difficulties to ensure the service quality.

Drivers and fleet operators' acceptance

In order to increase the market penetration the obtained results must convince small companies and self-employers for using the DSB service. A drivers' point of view (rather than a fleet operators' point of view) can make this task easier, by taking into account the extra work for fleet operators and drivers. Since sharing the machine with car users may cause them time important losses, other technologies such as Bluetooth or WIFI technologies should avoid extra work and save time.

Fleet operators did not interested in actively using the DSB service, as it is reflected by the use of the systems during the pilot [START_REF] Blanco | FREILOT. Urban Freight Energy Efficiency Pilot. D.FL.4.1 Evaluation methodology and plan[END_REF]. In Lyon this was due to technical problems and difficulty to make the system technically operational, whereas in Bilbao it was because the capacity of delivery bays was underused. However, the city of Bilbao has continued the system after finishing the pilot because the transport carriers made pressure to continue it. In order to convince both carriers and public authorities about the benefits, fuel saving and CO 2 reduction indicators must be proved, but also a tax reduction could be applied to them by the cities (also environmental zones commented above). Moreover, a network of DSB must be provided to make the advantages be visible, mainly in terms of traffic positive impact and time savings.

We have also to note that for drivers the service does not imply major changes if delivery spaces are reserved before the delivery route takes place, but have an impact on their flexibility. Therefore, a Smartphone application (as contemplated in the CVIS framework) should help drivers to cancel or change their reservations online if major issues at one stop or during the driving time create an impossibility to reach a reserved delivery space on the reserved period. Furthermore, only a coordinated network of delivery spaces should result on an easily identified positive system, accepted by carriers, but will lead to organizational changes not always seen by drivers as acceptable.

Politicians' acceptance

The role of the politicians is very important in the large-scale implementation of the FREILOT technologies, from the back office management to the promotion of new policies for favouring trucks equipped with FREILOT technologies. Different ideas were proposed by the partners:

• Added value of the system (ambulances, fire brigade…) will favour the support of politicians to the implementation of the technologies.

• Due to the low usage of the system at off peak periods, DSB places could be used for other purposes during off peak hours, enforcing the business model.

The cost of the systems implementation is a key issue for the politicians:

• Civil works for the installation of DSB places are very expensive, also the adaptation of the current machines for hybrid possibilities (parking and delivery) is very expensive (30,000 €). Other technologies (wireless) should be considered, integrating these services within a more complex solution, but reducing costs. • The DSB is only justified in large cities. Its maintenance can be paid by large commercial stores (they are already paying in France and Spain for private parking places), or by grouping smaller stores. An alternative is to ask the city to invest in the DSB places and then rent them. Economic studies (payback period, IRR…) will justify the investment and the renting prices.

Policy

Policy issues are very important for convincing users. Providing FREILOT technology users with advantages will improve the penetration rate and assure the increment in the usage of the technologies. There are some questions related to this issue:

• How to book public places for private users or to private entities or individuals?

• How can the cities ban trucks that are not equipped with these technologies?

• Who can state priority rules to non-public vehicles since it is not allowed in some countries due to unfair competition (public authority giving priority to some fleet operators)? • Which urban stakeholders can be involved into the system by expressing the benefits of national distribution to their business development?

For solving the above questions the partners proposed the following:

• Positive results of the project should prove the benefits for modifying the legal framework. • Consider freight as public service.

• Allow the booking of spaces for specific private activities (car sharing had the same problem and was solved).

• Define environmentally friendly trucks and provide them with privileges.

• Show other advantages (e. g. safety, ambulances, fire brigades…)

Conclusion

This paper has presented the main issues in deploying urban logistics systems. From the example of the delivery space booking system described above, we presented the main questions related to making a business model from the evaluation results and the main implementation conclusions. Moreover, a cost-benefit analysis allowed us to fix the most suitable fees, and the main barriers to the deployment of a DSB service have been identified.

From those results, we can set a group of recommendations to both public and private authorities for the deployment of such systems. The first is that of consultation. As shown in Gonzalez-Feliu and Morana (2010), grouping all the potential stakeholders that can be involved on an urban logistics service can accelerate its implementation once the main tactical decisions are consensual, then make the system be operationally more stable. The FREILOT project, and more precisely, the DSB pilot, has shown the importance of consultation and the implication of all partners to make the service work. Indeed, the cohesion of stakeholders in Bilbao made that more than 50 carriers participating in the pilot, where only 4 in Lyon. Moreover, the city aimed to stop the system after the project, and the transport carriers, although not using actively the system, aimed to continue towards the adoption of an operational system and its deployment, which convinced the city to study other strategies to keep and develop the system. In this sense, the CBA should be a valuable decision support, giving both public and private stakeholders the elements to decide which deployment strategy is the best. Moreover, although several barriers have been identified, the communication and the consensus helped to break some of them.

Finally, it is important to lead to a robust business model, with a mature technology and a solid cost-benefit balancing schema, in order to support deployment. To do this, the pilot results will be used to develop a hybrid system allowing existing machines to make also DSB reservations, and the expensive movement captors that identify vehicles on the delivery bays can be replaced now by an alternative solution which is less expensive and ready to deploy. In conclusion, to deploy an urban logistics solution, it is important to first ensure the maturity of the proposed services, its operational status, its technical robustness and its capacity to become an economically viable project (with or without public subvention, and the conditions of this support), then to make a high work on standardization and to make a collaborative work among all the partners.

  For an in-depth description of the business model and the analysis of all systems, including the combination of two or more services, see Zubillaga et al. (2012), Jeftic et al. (2012), Aifandopoulou et al. (2012) and Gonzalez-Feliu et al. (2012).

Figure 1 :

 1 Figure 1: Pilot process and deployment strategy chart (Zubillaga et al., 2012)

Table 3 . Gains on a single DSB (on a 120 m area, Gonzalez-Feliu et al., 2012) Indicator Without DSB With DSB Gap in Freilot areas Gap in the entire route

 3

	Travel distance (m)	147	108	-27%	-0.00%
	Travel and stop time(min) 15.25	16.92	+11%	+0.60%
	Fuel consumption (g)	101.4	71.5	-29%	-0.08%
	CO2 emissions (g)	336	235	-30%	-0.01%
	NOx emissions (g)	4.1	2.7	-34%	-0.01%

Table 4 . Deployment trends for the chosen scenario Year 0 Year 1 Year 2 Year 3 Year 4 Year 5

 4

	Year
	6+

Table 5 . Cost structure DSB -INVESTMENT COSTS

 5

	Cost type	Year 0	Year 1	Year 2	Year 3	Year 4	Year 5
	Back office investment	27,000 €	0 €	0 €	0 €	0 €	0 €
	Infrastructure and civil works	40,246 €	60,369 €	50,308 €	50,308 €	50,308 €	0 €
	Other investment costs	10,000 €	10,475 €	16,000 €	11,000 €	10,500 €	10,460 €
	Total investment costs	77,246 €	70,844 €	66,308 €	61,308 €	60,808 €	10,460 €
			DSB -OPERATIONAL COSTS
	Cost type	Year 0	Year 1	Year 2	Year 3	Year 4	Year 5
	Functional costs	0 €	0 €	0 €	0 €	0 €	0 €
	Police enforcement	0 €	40,000,€	40,000,€	40,000,€	40,000,€	40,000,€
	Maintenance	0 €	57,904,€	80,560,€	99,440,€	118,320,€	137,200,€
	Other operational costs	0 €	113,€	338,€	638,€	863,€	938,€
	Total operational costs	0 €	98,017,€	120,898,€	140,078,€	159,183,€	178,138,€

Table 6 . Benefit structure and yearly balances

 6

		Year 0	Year 1	Year 2	Year 3	Year 4	Year 5	Over year 6
	Number of vehicles	0	150	450	850	1150	1250	1250
	Investment COST	77,246 €	70,844 €	66,308 €	61,308 €	60,808 €	10,460 €	10,460
	operational COST	0,00 €	98,016 €	120,897 €	140,077 €	159,182 €	178,137 €	178,137 €
	Total COST	77,246 €	168,861 €	187,205 €	201,385 €	219,990 €	188,597 €	188,597 €
	Individual economic benefit	250 €	250 €	250,00 €	250 €	250 €	250 €	250 €
	Total economic benefit	0 €	37,500 €	112,500 €	212,500 €	287,500 €	312,500 €	312,500 €
	Balance of total costs	-77,246 €	-131,361 €	-74,705 €	11,114 €	67,510 €	123,902 €	123,902 €
	Balance of operational costs	0 €	-60,516 €	-8,397 €	72,422 €	128,317 €	134,362 €	134,362 €

Table 7 . Fuel and CO 2 savings for DSB in a deployment situation

 7

	Vehicle type Fuel savings (ml) CO 2 savings (g)
	Van	0	0
	Small truck	32	82
	Big truck	40	101
	We make the following assumptions:

Table 8 . Benefit monetary conversion, for each savings category

 8

	Type of gain	Stakeholder	Economic gain (€/year)
	Vehicle usage Transport operator 0 €/year
	Time savings Transport operator 350 €/year
	Fuel savings	Transport operator 85 €/year
	CO 2 reduction Transport operator 15 €/year
	Total savings Transport operator 450 €/year

Urban Freight Energy Efficiency Pilot, Information and Communications Technologies Policy Support Programme (ICT PSP). Information Society and Media Directorate. Grant agreement no.:

Pilot type B.

That assumption is the estimated cost of CO 2 in 2020-2030, according to French Ministery of LandUse and Transport (2005) .

First In First Out, i.e., the first to book is the first to have the right to park at the chosen time period.

Acknowledgment

This paper has been partially financed by the EU ICT PSP project n° 238930 -FREILOT (Urban Freight Energy Efficiency Pilot). The authors also like to acknowledge Christian Ambrosini, Mathieu Gardrat, Pascal Pluvinet and Jean-Louis Routhier (Laboratoire d'Economie des Transports), Rosa Blanco and Eva Garcia (CTAG), Garoa Lekuona and Nerea Rojas (ML Cluster Euskadi), Philippe Bossin (Interface Transport) and Irantzu Bores (Gertek) for their help in collecting an preparing the data for the proposed analyses, as well as for their valuable suggestions to improve this paper.

Deployment barriers

After the identification phase, the barriers were grouped for further discussion with the involved stakeholders. This grouping can be expressed in the following questions:

1. Who will run the back office? 2. How to improve the drivers and fleet operators' acceptance? 3. How to improve the technology providers' acceptance? 4. How to improve the politicians' acceptance? 5. How to solve the policy problems?