Daniel Hirschkoff

Tom Hirschowitz

Damien Pous

Alan Schmitt

Jean-Bernard Stefani Mai

Component-oriented programming with sharing: containment is not ownership

Keywords: Component-oriented programming, higher-order process algebras, sharing Programmation par composants, algèbres de processus d'ordre supérieur, partage

Component-oriented programming yields a tension between higher-order features (deployment, reconfiguration, passivation), encapsulation, and component sharing. We propose a discipline for component-oriented programming to address this issue, and we define a process calculus whose operational semantics embodies this programming discipline. We present several examples that illustrate how the calculus supports component sharing, while allowing strong encapsulation and higher-order primitives.

Wide-area distributed systems and their applications are increasingly built as heterogeneous, dynamic assemblages of software components. This modular structure persists during execution: such systems provide the means to control their run-time modular configuration, which encompasses automatic deployment, unanticipated evolution, passivation, run-time reconfiguration, and introspection. This expressive power conflicts with the strong encapsulation properties generally expected from modular programs.

A key tension point is component sharing, which allows two remote components to encapsulate a common component, as depicted in Figure 1, where the component L (e.g. a software library) is shared among C and D. How does one preserve encapsulation in this case? In particular, what happens to L and D if A removes C from the configuration? How can C replace L by L , without necessarily impacting D? Essentially, the difficulty lies in combining (1) encapsulation with fine-grain, objective control over communications, (2) locality passivation, migration, and replication, and (3) access to shared components with simple communication rules.

Previous models of component-oriented programming do not completely address these three requirements. Models that do not address requirement (3) comprise process calculi with hierarchical localities that feature local communications only (i.e., no direct communication between arbitrarily distant localities in the locality forest) [START_REF] Castagna | The Seal calculus revisited: Contextual equivalence and bisimilarity[END_REF][START_REF] Cardelli | Mobile ambients[END_REF][START_REF] Levi | Controlling interference in ambients[END_REF][START_REF] Bugliesi | Boxed ambients[END_REF][START_REF] Coppo | M3: Mobility types for mobile processes in mobile ambients[END_REF][START_REF] Stefani | A calculus of Kells[END_REF]. Indeed, sharing is representable in such models, but at the expense of complex routing rules which are difficult to maintain. Models that do not have this routing complexity problem, but are weak on requirement [START_REF] Bettini | The KLAIM project: Theory and practice[END_REF], include the Cell calculus [START_REF] Liu | Modules with interfaces for dynamic linking and communication[END_REF] and process calculi with localities that do not restrict communications betwen localities [START_REF] Fournet | The reflexive chemical abstract machine and the Join-calculus[END_REF][START_REF] Hennessy | Resource access control in systems of mobile agents[END_REF][START_REF] Yoshida | Assigning types to processes[END_REF][START_REF] Wojciechowski | Nomadic Pict: Language and infrastructure design for mobile agents[END_REF][START_REF] Hennessy | SafeDpi: a language for controlling mobile code[END_REF][START_REF] Bettini | The KLAIM project: Theory and practice[END_REF][START_REF] Ravara | Lexically scoped distribution: what you see is what you get[END_REF]. The tKlaim calculus [START_REF] De Nicola | Global computing in a dynamic network of tuple spaces[END_REF] is a recent variant of Klaim that allows the establishment of different communication topologies between localities. However, the calculus still falls short of full encapsulation of sub localities, since there is no objective control over process migration and execution.

Our starting point to solve the issue of component sharing is that, from the standpoint of the latter kind of models (weak on (1)), the problem is reminiscent of the aliasing problem in object-oriented languages [START_REF] Hogg | The Geneva convention on the treatment of object aliasing[END_REF]: sharing is easy, but encapsulation is problematic. To solve this problem, Clarke et al. introduce ownership types [START_REF] Clarke | Object Ownership and Containment[END_REF][START_REF] Clarke | External uniqueness is unique enough[END_REF], which attribute to each object o an owner that controls the references to o. We adapt this idea of ownership to the setting of process calculi. However, instead of designing a type system to preserve encapsulation, we enforce it at the level of the operational semantics, as follows. We split the usual forest of localities into two graphs: the ownership forest and the containment graph. Locality passivation must be local for the ownership forest, and communication must be local for the containment graph. As in type systems for ownership, we require, by scoping constraints in our semantics, that owners be dominators: the owner of a component c dominates (in the ownership forest) all the components holding references to c. Owing to this condition, the aliasing problem does not arise: when updating a component c, its owner has access to all references to c. Moreover, the containment graph may be an arbitrary directed graph, which allows component sharing. The resulting language, an extension of the Kell calculus [START_REF] Stefani | A calculus of Kells[END_REF], turns out to be an interesting model of component-oriented programming, as we show by encoding key aspects of the Fractal component model [START_REF] Bruneton | An open component model and its support in Java[END_REF].

Our main contributions are: [START_REF] Bettini | The KLAIM project: Theory and practice[END_REF] we propose a programming discipline for component-oriented programming to address the issue of component sharing, while preserving encapsulation and higher-order features;

(2) we define a process calculus whose operational semantics embodies this programming discipline; [START_REF] Bugliesi | Boxed ambients[END_REF] we argue that our calculus is suitable to represent most idioms of component-oriented programming, by reviewing key concepts from a concrete component model; [START_REF] Cardelli | Mobile ambients[END_REF]

Components and the Kell calculus

After giving an informal description of the Kell calculus [START_REF] Stefani | A calculus of Kells[END_REF], which is our starting point, we present the main elements of a concrete component model, the Fractal model [START_REF] Bruneton | An open component model and its support in Java[END_REF]. We discuss to which extent Fractal component configurations without sharing can be interpreted as processes of the Kell calculus. We then present various examples of component configurations with sharing, and explain informally how we extend the Kell calculus with sharing to deal with these examples.

The Kell calculus

The Kell calculus is a higher-order process calculus with hierarchical localities (called kells), local communication, and locality passivation. Actions in the Kell calculus are communication actions and passivation actions. Communication is said to be local as it may occur only within a kell, between a kell and its sub kells, or between a kell and its immediate parent, as illustrated below. In pattern a ↓ x , the arrow ↓ denotes a message that should come from a sub kell.

3. Receipt of message a Q .T residing out of the enclosing kell by local trigger a ↑ x P .

a Q .T | b[a ↑ x P ].S → T | b[P {Q/x}].S
In input pattern a ↑ x , the arrow ↑ denotes a message that should come from the outside of the immediately enclosing kell.

These constructs may be combined using join patterns [START_REF] Fournet | The reflexive chemical abstract machine and the Join-calculus[END_REF] that are triggered only when the required messages are simultaneously present, as in the following example (note that | has higher precedence than ).

a Q .T | b[c R .U | (a ↑ x | c y P )].S → T | b[U | P {Q/x, R/y}].S
Communication with other localities has to be explicitly programmed in the language. For instance, in order to exchange messages, two sibling kells need the help of their common parent, as depicted in the following example.

a[(c ↓ x c x ) | b[c P .Q] | e[(c ↑ x T )]] → a[(c ↓ x c x ) | c P | b[Q] | e[(c ↑ x T )]] → a[(c ↓ x c x ) | b[Q] | e[T {P/x}] ]
In this example, the parent locality contains a permanent forwarder c ↓ x c x that pulls messages of the shape c P out of its sub kells. This allows sub kells to receive these messages using an up pattern c ↑ x . The construction (ξ P ) denotes a replicated trigger, i.e., a trigger which persists after a reaction, and is in fact a shorthand for νt.Y t,ξ,P | t Y t,ξ,P , where Y t,ξ,P = (t y | ξ P | y | t y ).

Passivation in the Kell calculus is depicted in the following example, where the kell named a is destroyed, and the process Q it contains is used in the guarded process P .

a[Q].T | (a[x] P ) → T | P {Q/x}
Assume, for instance, that we want to model the dynamic update of component b, where the new version P of the component program is received on channel a. We could do so, in one atomic action, using the following join pattern where the new version b[P ] is spawned, replacing the previous b component.

a P | (a x | b[y] b[x]) | b[Q] → b[P ]

The Fractal component model and its interpretation in the Kell calculus

Fractal is a general component model which is intended to implement, deploy, monitor, and dynamically configure complex software systems, including in particular operating systems and middleware. This motivates the main features of the model: composite components (to have a uniform view of applications at various levels of abstraction), introspection capabilities (to monitor and control the execution of a running system), and re-configuration capabilities (to deploy and dynamically configure a system).

A Fractal component is a run-time entity which is encapsulated, which has a distinct identity, and which is either primitive or composite (built from other components). Bindings between components are described explicitly, either by local, primitive bindings, using explicit component interfaces, or by remote, composite bindings, using components whose role is to embody communication paths. Features like encapsulation and interfaces are rather standard. The originality of the Fractal model lies in its reflective features and in its ability to define component configurations with sharing. In order to allow for well scoped dynamic reconfiguration, components in Fractal can be endowed with controllers, which provide a meta-level access to a component internals, allowing for component introspection and the control of component behaviour. A Fractal component consists of two parts: contents, that correspond to its internal components, and a membrane, which provides so-called control interfaces to introspect and reconfigure the internal features of the component. The membrane of a component is typically composed of several controllers.

Representing a Fractal component (without sharing) in the Kell calculus is relatively straightforward. A component named a, takes the form a[P | Q], where process P corresponds to the membrane of the component, and process Q, of the form c

1 [Q 1 ] | . . . | c n [Q n ],
corresponds to the contents of the component, with n sub components c 1 to c n . Interfaces of a component can be interpreted as channels on which a component can emit or receive messages. The membrane P is composed of controllers implementing the control interfaces of the component.

The Fractal model specifies several useful forms of controllers, which can be combined and extended to yield components with different reflective features. Let us briefly describe some of them, and sketch their interpretation in the Kell calculus.

An attribute of a component is a configurable property that can be manipulated by the means of an attribute controller. It can be interpreted as some value held in a memory cell by a component membrane. A membrane providing an attribute controller interface is easy to program, by emitting the current value of the attribute on a private channel and by providing channels to read and update this value.

νs.(get

↑ r | s v r v ) | (set ↑ v | s v s v ) | s 0
A contents controller supports an interface to list, add, and remove sub components in the contents of a component. A membrane providing a simplistic contents controller interface could be of the form Add | Rmv | . . ., with the following definitions (in which the contents controller interface is manifested by the cc channel carrying the request type (where \add means a name that is exactly add ), the name c of the targetted component, and either the program of the added component (including both membrane and contents) or a channel r to return the removed component).

Add =(cc ↑ \add , c, x c[x]) Rmv =(cc ↑ \rmv , c, r (c[x] r c, x ))
A less simplistic encoding would take into account additional details, such as exception conditions (e.g, the possible absence of a component to remove). However, the above definitions convey the essence of the contents controller.

A life-cycle controller allows an explicit control over the execution of a component. As an illustration, we can define a membrane P providing a simple interface to suspend and resume execution of sub components (where the life-cycle interface is manifested by the lfc channel, and a sub component c is supended by turning it into a message on a channel of the same name as the component).

P =Suspend | Resume | . . . Suspend =(lfc ↑ \suspend, c (c[x] c x )) Resume =(lfc ↑ \resume, c (c x c[x]))
Again, a more realistic implementation would be more complex, but this section only aims to show that capturing the operational essence of a reflective component model such as Fractal (without component sharing) is relatively direct using the Kell calculus. For another example, Schmitt and Stefani [START_REF] Schmitt | The Kell calculus: A family of higher-order distributed process calculi[END_REF] provide an interpretation of a binding controller, allowing to bind and unbind its client interfaces to server interfaces.

Component sharing

Component sharing arises in situations where some resource must be accessed by several client components. A first example of such a situation is that of a log service, which merely provides client components the ability to register status information. Figure 1 depicts an example configuration, where L is the log service component, and C and D are client components. In this case, communications are unidirectional, from the client components to the shared component, and the log service maintains its own mutable state. Passivation of a client does not affect the execution of the log service or the processing of logging requests previously sent by that client. Figure 1 can illustrate as well a second example of component sharing, that of a shared programming library or module. In this case, the communication between client components C and D and the library L is bidirectional (typically, a request/response style of communication). The expected behavior in presence of passivation is different from the first example: if a client is passivated, requests to functions in the library should be suspended along with the rest of the client activity.

As a third example, consider a database service used by several components of a system (for instance, a directory service), which can again be depicted as in Figure 1. Here, the communications between clients and the service are bidirectional, but they are no longer independent as in the previous example, for the database service maintains a mutable state that can be viewed and updated by each client component.

The previous examples correspond to pure software architectures and describe configurations on a single machine. One can also consider mixed software/hardware configurations. For instance, consider the case of a router R connecting several networks N i with i ∈ I. Each network N i connects machines m ij with j ∈ J i . There are several ways to model such a configuration in the Kell calculus without sharing. If one wants to model the networks as components and have messages be directly exchanged between machines and the networks, and between the networks and the router, then the locality of communications and the tree structure of kells impose the following shape:

R   i∈I N i   j∈Ji m ij [. . . ]    
where i∈I P i means the parallel composition of the processes P i .

Such an approach is not satisfactory because the passivation of the router or of a network, e.g., to model their failure, implies the passivation of several machines. A solution consists of modelling a network N i by a channel n i , as in Fig. 2. Machines send outbound messages on the channel msg with the destination i∈I;j∈Ji

m ij (msg k, l, x n i k, l, x ) | (n ↑ i \i, \j, x x) | P ij | R   i,j∈I;i =j (n ↑ i \j, l, x n j j, l, x )   | i∈I (n ↓ i k, l, x n i k, l, x )

The calculus

The syntax of the calculus is in Figure 4. It is based on a denumerable set of variables x and a denumerable set of names a. Processes include the standard null process 0, variables x, parallel composition P |Q, and name creation νa.P , plus some less standard constructs. Messages have the shape a P .Q, where P is a list of processes (we use • in the following to denote a list of •'s). In a P .Q, Q is called a continuation, because it is triggered synchronously upon consumption of the message. Kells have the shape a[P ].Q, where a is the name of the kell, P is its contents, and, as for messages, Q is its continuation. The calculus admits references * a as processes, for referencing remote kells named a, as informally described in § 2.

Resources

The reduction relation is based on a labelled transition system (LTS), whose labels represent a trade of resources r. As discussed below, such a trade is typically written F 1 F 2 , where F 1 and F 2 are formulas, to express that the process undergoing the transition offers the resources described by F 2 , provided the environment provides the resources in F 1 . In particular, the reacting trigger ξ P trades some basic resources (messages, passivated kells) against a reaction token written : if the environment provides the expected resources, then the trigger reacts. When composing processes, the corresponding transitions are composed, which may involve the annihilation of some resource requests and corresponding offers, in case they meet.

As defined in Figure 4, there are two kinds of resources. Basic resources include messages

( M | a ↓ ( M ) | a ↑ ( M ))
, where M ::= a P , passivated kells (a[P ]), consumed references ( * a), and permissions (a). They are generated directly from processes. For example, a message a P .Q trades a reaction token against a P , yielding the transition a P .Q a P -----→ Q. As explained in §2.1, we want to control the locality of communications, so this transition should happen in the same kell as the transition involving the reacting trigger, and trades involving should only take place at the same level as the reaction.

On the other hand, we cannot completely restrict trades to the level of the reaction, e.g., because the consumed resources may come from shared kells, which syntactically may reside far above the reaction site. This leads us to consider several kinds of reaction tokens, each of them determining the position of the considered transition relatively to the reacting trigger. These reaction tokens are called spots s ∈ Spots.

More precisely, consider a process S|b[a[(ξ P )|Q]|R], where the reacting trigger is ξ P . We have just seen that resources matching the reaction token provided by ξ P may only come from Q. Immediately above a, i.e., in R, trades may use the information that the reaction lies in some sub kell named a. Thus, in R, is viewed as the sub reaction token a[ ]. Further above a, e.g., from S, it becomes the less precise internal reaction token [ ], which only indicates that the reaction lies in some sub kell.

Formulas Formulas are the labels of our LTS. Intuitively, they count the resources offered and requested by the considered process. Formally, formulas are defined as in Figure 4, and considered equivalent modulo the following equation schemes:

F 1 |F 2 = F 2 |F 1 (1) F | = |F = F (2) r / ∈ Spots r|r ⊥ = (3) s|s ⊥ = s (4) .
Equation ( 3) specifies that basic resources (non-spots) are used linearly: they may be consumed only once; (4) specifies that one spot may satisfy several requests, as a join pattern consumes several messages.

MATCH ξ : F → Θ ξ P F ---→ Θ(P ) REF * a a ---→ * a DOWN a[ M . P |P ].Q a a ↓ ( f M ) ------→ a[ P |P ].Q UP * a| M. P a[ ] a ↑ ( f M) --------→ * a| P HERE M.P M ----→ P PASSIVATE canon(P ) a[P ].Q a[P ] -----→ Q SUP * a * a ----→ 0 NEW P F -→ Q a / ∈ FN(F ) νa.P F -→ νa.Q PAR P 1 F1 -→ P 1 P 2 F2 -→ P 2 P 1 |P 2 F1|F2 ----→ P 1 |P 2 BOT P -→ P HOT P F s ---→ Q hot(F ) SN(F ) # {a} ∪ DN(P ) a[P ].R F a(s) -----→ a[Q].R COLD P F -→ Q cold(F ) SN(F ) # {a} ∪ DN(P ) a[P ].R F -→ a[Q].R

Transitions

The LTS is defined in Figure 5. Rule MATCH describes reaction, using the notion of matching defined below, which is a three arguments judgement written ξ : F → Θ, where Θ is a substitution.

A substitution is an element of (Vars → fin Processes) × (Names → fin Names), i.e., a pair of a finite map from variables to processes and a finite map from names to names. Capture-avoiding substitution is defined as usual on processes, and written Θ(P ). Define the negation F ⊥ of a formula F by distributing it over resources, given that

r ⊥ ⊥ = r. Let F 1 F 2 denote F ⊥ 1 |F 2 .
The rule states that if ξ : F → Θ, then the trigger ξ P has a transition to Θ(P ), under the label F . Thus, the reaction happens only if the environment provides the resources F (recall that spot stands here for the firing of the trigger).

By rule REF, at the level of a reaction, a reference may generate a permission to receive messages from the kell it points to. This permission is then used in rule DOWN to actually consume the corresponding messages. By rule UP, a reference to the reacting kell allows the reaction to consume messages from the kell holding the reference. By rules HERE, PASSIVATE, and SUP, a reaction may consume messages, active kells, and references at its top-level. In rule PASSIVATE, we use the notation canon(P ) to mean that P has no active ν. This means that such ν's must have been extruded before by structural congruence. Formally, a context C is a process with exactly one occurrence of the special variable 2. Textual replacement of 2 with some process P (possibly with capture) is written C{P }. A process P is in canonical form, written canon(P ), iff for all context C = 2, if P = C{νa.Q}, then C{νa.Q} ≡ νa.C{Q}.

The other rules specify how the transition relation is closed under active contexts. Rule NEW handles the case of ν. Rule PAR combines the resources of several parts of the process. If one argument provides the resources requested by the other, then the trade occurs. Formally, two derivations having an occurrence of the MATCH rule can be put together using this rule: the restriction to only one active trigger per reaction is enforced by the rule for reduction, presented below. Rule BOT closes transitions under parallel composition with spectator processes.

Rule HOT allows to wrap an already existing reaction inside some parent kell: a transition

P F s ---→ Q is seen from the enclosing kell as a[P ].R F a(s) -----→ a[Q].R
, where the operation a(s) over spots is defined by a( )

∆ = a[ ], and a(b[ ]) ∆ = a([ ]) ∆ = [ ].
The rule is subject to two side conditions. First, F must be hot, written hot(F ), which means that F matches the syntax

F ::= | b ⊥ | b ↓ ( M ) | b ↑ ( M ) | F |F,
and additionally SN(F ) # DN(P ) (see below). Intuitively, the presence of s in the label of the conclusion imposes that the reaction occurs in P , so the side condition means that a reacting kell only has three kinds of interactions with its context: 1) it (partially) specifies the place of reaction; 2) it exhibits authorizations to access shared kells; 3) it consumes messages through references to shared kells (in both directions). The second side condition enforces the fact that references point to the closest kell in the hierarchy, as informally stated in §2.3. We call the defined names DN(P ) of a process P the set of all a's such that P ≡ ν b.Q|a [R]. for some Q, R, b, with a / ∈ b. Moreover, a formula is in canonical form iff, for each resource r, it does not contain both r and r ⊥ . We define the scoped names SN(F ) of a formula F in canonical form as follows: for resources r of the shape a ↓ ( M ), a ↑ ( M ), a, and a[ ], let SN(r) ∆ = {a}; for other resources r, let SN(r)

∆ = ∅. Additionally, let SN(F 1 |F 2 ) ∆ = SN(F 1 ) ∪ SN(F 2 ) and SN(F ⊥ ) ∆ = SN(F ).
The rule prevents resources consumed through a reference * a to escape the scope of any kell named a. For instance, a request for a message of the shape a ↓ (b P ) through a reference * a is supposed to be consumed in (one of) the closest kell(s) named a. Such a request leads to the formula a ⊥ |a ↓ (b P ) s: if a down message is found in a, using formula a a ↓ (b P ), then the reaction occurs. However, if P 1

a ⊥ |a ↓ (b P ) s ----------→ P 2 , then we do not want c[P 1 |a[Q 1 ]] a ⊥ |a ↓ (b P ) s ----------→ c[P 2 |a[Q 1 ]
] to hold, because the message ought to be found in

Q 1 . Here, DN(a[Q 1 ]) = {a} which is not disjoint from SN(a ⊥ |a ↓ (b P )) = {a}.
Note that this check is done only when crossing kell boundaries. Indeed, we allow the presence of more than one kell named a in parallel to the reacting trigger.

Symmetrically to rule HOT, rule COLD allows to transfer resources from kells containing references * a to the reacting kell a, which may be syntactically distant. Let F be cold, written cold(F ), iff F matches the syntax F ::

= b[ ] ⊥ | b ↑ ( M ) | F |F .
Rule COLD says that any transition with a cold label is viewed identically from outside the ambient kell, provided the scoping conditions are met. In practice, rule COLD is only used to transfer the consumption of up messages (created by rule UP) through kells.

Matching Figure 6 defines the matching relation. Rule M-PAR states that matching a pattern ξ 1 |ξ 2 is like matching ξ 1 and ξ 2 separately, and then combining the result. In the rule, + denotes the union of finite maps with disjoint domains. By rule M-HERE, matching a pattern a • η against a resource a P boils down to match η against P (as defined below). Rule M-ELSEWHERE handles the cases of down and up messages. Given a pair ζ consisting of a name a and argument patterns η, we let ζ α stand for a α η . Similarly, given M-PAR Reduction Finally, reduction, written →, is the smallest relation satisfying the rule

ξ 1 : F 1 → Θ 1 ξ 2 : F 2 → Θ 2 ξ 1 |ξ 2 : F 1 |F 2 → Θ 1 + Θ 2 M-HERE η : P → Θ a • η : a P → Θ M-ELSEWHERE ζ • : M → Θ ζ α : a α ( M ) → Θ M-PASSIVATE a[x] : a[P ] → {x → P } M-SUP * a : * a → ∅ M-PROC x : P → {x → P } M-NAME a : * b → {a → b} M-CST \a : * a → ∅ M-NEG b = c a != b : * c → {a → c} M-NIL : → ∅ M-CONS η : P → Θ 1 η : P → Θ 2 η, η : P, P → Θ 1 + Θ 2
P ≡ P P s -→ Q Q ≡ Q P → Q •
As exactly one spot is allowed, this rule guarantees that exactly one trigger fires.

Examples

Let us first present a simple example.

Example 1 Consider the following configuration.

A = a[(e ↑ 1 x | e ↑ 2 y P ) | c Q ] | l 1 [e 1 U | * a] | l 2 [e 2 V | * a | (c ↓ z R)]
The component a can emit the message c Q , which implies that a reference * a to a can be used to access this message. Hence we have the following reduction.

A → a[(e ↑ 1 x | e ↑ 2 y P )] | l 1 [e 1 U | * a] | l 2 [e 2 V | * a | R{Q/z}]
The component a can also receive messages from both components l 1 and l 2 since it is a shared sub component of both. Hence we have the following reduction.

A → a[P {U, V /x, y} | c Q ] | l 1 [ * a] | l 2 [ * a | (c ↓ z R)]
Let us now give an example of dynamic binding and reconfiguration in the calculus. We now review the examples of §2.3 within our calculus. First, assume given two components Queue[. . .] and Pair [. . .], working as follows. They expect messages from their parent components, on channels Queue.push, Queue.pop, Pair .fst , and so on. The channels of these messages identify the action to execute. The messages contain a return channel name and the corresponding arguments. On the return channel, Queue and Pair send messages which have to be picked up as down messages by the client parent component. For convenience, we use the syntactic sugar let x = a( P ) in Q for νb.a b, P |(b ↓ x Q), with some fresh b used as return channel. For instance, let x = Queue.push(P, Q) in R uses the result x of pushing P on top of Q in R.

(c, j) | state q let x = Pair .pair (c, j) in let q = Queue.push(x, q) in state q ) | (Printer .lpq ↑ (r) | state q r q | state q )] | A[B[. . .] | C[ * Printer | . . .]] | D[ * Printer | F [. . .]]
The shared library example can be represented similarly. We can however emphasize the code server aspect of the example with a representation that only requires a unidirectional communication between the clients and the shared library. The shared library is thus modelled as a code server that allows an instance of the library code to be made available on request in the client component that requires it.

Lib[!Lib.get P

] | A[B[. . .] | C[ * Lib | . . .]] | D[ * Lib | F [. . .]]
Finally, we review the router example from Figure 2, which is more direct than Examples 3 and 4 because it does not require any data structure: we just assume that names include integers.

Example 6

The router example is depicted in Fig. 7. It is very similar to Fig. 2: the router is identical and shared between the networks, the networks are now kells shared between machines and may directly pull messages out of machines and the router. This encoding allows the failure of the router or a network to only impact inter-machine communication, it also segregates messages in different networks.

Conclusion

Component sharing, as experienced with component models providing it, is a feature that proves extremely useful when describing or programming software architectures or systems with shared resources. We have presented in this paper an extension of the Kell calculus that provides a direct, formal interpretation of component models with sharing. To our knowledge, this is the first calculus offering (1) encapsulation with i∈I;j∈Ji

m ij * N i | (n ↓ i \i, \j, x x) | P ij | R   i,j∈I;i =j (n ↑ i \j, l, x n j j, l, x )   | i∈I N i * R | (n ↓ i k, l, x n i k, l, x ) | (msg ↑ k, l, x n i k, l, x )
access to shared components with simple communication rules. Our approach draws on a distinction between ownership and containment inspired by recent works on ownership types and the control of aliasing in object-oriented programming languages. In contrast to these works, however, our approach avoids the burden of a type system, by primitively distinguishing ownership from containment, thus enforcing the programming discipline directly in the operational semantics.

The work we have presented here is only preliminary, however. First, the standard issues appearing when one introduces a new process calculus remain to be dealt with, e.g., the development of a bisimulation-based behavioral theory, or of static analyses to ensure semantic properties of processes. Furthermore, it would be interesting to study the exact relation between approaches to object containment and ownership in object-oriented languages and in the Kell calculus with sharing. At a minimum, we need to investigate the different benchmarks used in the object-oriented programming community and study how they are handled in our calculus.

Second, two important, inter-related questions remain, that pertain (1) to the control of communications with shared components, and (2) to the control over dynamic binding. The first issue concerns a potential security hole in our design. It can be succinctly stated as follows: in the extended Kell calculus presented here, the construct νa.a[a[P ]] is not a perfect firewall, while it is in the plain Kell calculus. This is due to the fact that P may have references to shared kells, which may in turn allow P to emit and receive messages from its environment. We see two posssible solutions to this problem.

First, one could annotate each kell construct a[•] with explicit sieves on communications with shared components. For instance, let us write a[P ] A , where A ::= ∅ | * | a | ¬ a represents the names of shared components the present component is allowed to communicate with. Then, define the interpretation of annotations by ∅ = Names, * = ∅, a = Names \ a, and ¬ a = a. The semantics of these consructs is given by a simple modification of the rules HOT and COLD, given by adding textually the side condition SN(F )# A to both of them. With these new constructs and rules, we recover the perfect firewall equation for νa.a[a[P ] ∅ ] ∅ : P cannot communicate with the environment outside of a.

The second, more radical solution is to introduce a second ν operator, say ∇, that would not cross component boundaries. Channel names bound by ∇ would then represent communication channels, while free names and names bound by ν would represent global names. Distant communication would be restricted to channels, thus preventing an incoming piece of code to arbitrarily communicate with distant components. Global names would serve for matching against local messages. We conjecture that the presence of ν and ∇ avoids the need for directional patterns (↑, ↓, •). The calculus thus collapses to a simpler version. The second solution might also turn out to solve the second problem (which is not the case of the first solution): the distinction between local channels and global names might give rise to a fine-grain account of dynamic binding, provided the pattern language is enriched adequately.

FFigure 1 : A configuration with sharing 1

 11 Figure 1: A configuration with sharing

1 .

 1 Receipt of local message a Q .T on port a bearing process Q and continuation T by local trigger (input construct) a x P . a Q .T | (a x P ) → T | P {Q/x} 2. Receipt of message a Q .T residing in sub kell b by local trigger a ↓ x P . b[a Q .T ].S | (a ↓ x P ) → b[T ].S | P {Q/x}

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: A router configuration

3 .

 3 References are also used to send names in messages, as illustrated in matching rules M-NAME, M-CST, and M-NEG below. Finally, the calculus features first-class reduction rules, called triggers, which are written ξ P . Here, ξ denotes a list of patterns, where each variable and name is bound at most once (see the definition of scoping below). A pattern ξ may be a kell pattern a[x] for passivation of active kells, a reference * a, for suppression of containment links, or a message pattern a α η , for plain communication. In the message pattern, η denotes a list of argument patterns of the shape x, a, \a, or a != b. The first two kinds of argument patterns respectively represent input of processes and names. The third kind \a tests the equality of the corresponding message argument with a. The last kind a != b checks that the argument is different from b, and inputs it as a. The direction α indicates where the received message should come from: ↑ messages come from a parent kell, • messages come from the current kell, and ↓ messages come from a sub kell.Processes are scoped as follows. Name restriction is a binder, as usual. Moreover, given a trigger ξ P , the defined identifiers DI( ξ) of ξ bind in P . We define DI( ξ) as follows. Given an argument pattern η, define DI(x) ∆ = {x}, DI(a) ∆ = DI(a != b) ∆ = {a}, and DI(\a) ∆ = ∅. Then, let DI( ξ) be the disjoint union of all DI(ξ), for ξ in ξ, with DI(a[x]) = {x}, DI( * a) = ∅, and DI(a α η ) the disjoint union of all DI(η), for η in η. Let structural congruence ≡ be the smallest congruence including, as usual, associativity and commutativity of parallel composition, neutrality of 0 w.r.t. |, extrusion of name restriction above |, ν, and a[•].P , and renaming of bound variables and names.

Figure 5 :

 5 Figure 5: The LTS

Figure 6 :

 6 Figure 6: Matching

Example 2

 2 Consider the following configuration, which models a running component receiving instructions to update its sub component c with a new code P (d), which uses a service named d. A = update c, P (d) | * a | a[(update ↑ b, x (b[y] b[x])) | c[P c ] | d[P d ]] It reduces in two steps to * a | a[(update ↑ b, x (b[y] b[x])) | c[P (d)] | d[P d ]], where the references to d in P (d) have been dynamically bound to d[P d ].

Example 3 Example 4

 34 The log service example can be represented as follows (reproducing the configuration of Figure 1 with L = Log). Log[ * Queue | . . . code to actually log . . . | (Log.log ↑ x | state y let z = Queue.push(x, y) in state z )] | A[B[. . .] | C[ * Log | . . .]] | D[ * Log | F [. . .]] In the rest of the program, the encapsulation links to Log are represented by occurrences of the reference * Log. The ownership of Log by, say, o is encoded by the fact that the sub component Log appears at the top-level in o. The implicit scope of Log, restricted to processes encapsulated in o, ensures that o is a dominator of Log. The shared printer example can be represented as follows, where c stands for "client", and j stands for "job". Printer [ * Queue | * Pair | . . . code to actually print . . . | (Printer .lpr ↑

Example 5

 5 The shared library example can be represented as follows, where !a P stands for νb.(a P .b |(b a P .b )).

Figure 7 :

 7 Figure 7: A better router configuration

  additionally, we propose a new, more modular, presentation of the Kell calculus. The paper is organized as follows. §2 briefly presents the Fractal model, discusses the modeling of Fractal components in the Kell calculus, and introduces informally several examples of component sharing. §3 extends the Kell calculus with primitive component sharing. § 4 shows how to program several component sharing examples within the obtained calculus. § 5 concludes the paper with a discussion of future research.


Anastasios Dosis
email: dosis@essec.com.

Abhinay Muthoo
email: a.muthoo@warwick.ac.uk

Malin Arve

Pauli Murto

Herakles Polemarchakis

Petros Sekeris

Juuso Valimaki

Experimentation in Dynamic R&D Competition *

Keywords: Experimentation, learning, dynamic R&D competition, inefficiency JEL CLASSIFICATION: C73, D83, O31, O32

We study a two-stage, winner-takes-all, R&D race, in which, at the outset, firms are uncertain regarding the viability of the project. Learning through experimentation introduces a bilateral (dynamic) feedback mechanism. For relatively low-value products, the equilibrium stopping time coincides with the socially efficient stopping time although firms might experiment excessively in equilibrium; for relatively high-value products, firms might reduce experimentation and stop rather prematurely due to the fundamental free-riding effect. Perhaps surprisingly, a decrease in the value of the product can spur experimentation.

INTRODUCTION

Research and Development (R&D) exhibits at least three characteristics. First, it is a dynamic, risky process. This is well documented in the pharmaceutical industry where the development of a new drug requires several phases to be completed. 1 It has been esti-mated that less than 1% of the compounds examined in pre-clinical trials make it into clinical trials and only 20% of the compounds entering clinical trials survive the development process and gain FDA approval. 2 The pre-clinical and clinical testing phases generally take more than a decade to complete. Second, firms (or research teams) usually compete with one another for being the first to cross the finish line. Winners are usually allocated a patent which provides exclusive rights to market the product and/or entertain a first-mover advantage. Last, given its dynamic nature, R&D entails learning as firms continuously update their beliefs regarding the viability of the project. As is well known, information (i.e., learning) has the characteristics of a public good; a discovery by one firm has a positive impact on other firms that experiment on a similar project.

In this paper, we study a model of dynamic R&D competition that encompasses all the characteristics described above. Two firms engage in a two-stage winner-takes-all race. The first firm that completes the two stages first is allocated a patent and monopoly profits for a given period. In the example given above on the development of a new drug, the research stage may refer to research in the lab whilst the development stage may refer to pre-clinical and clinical trials. Both firms start the race equipped with similar bandit technologies on which they can experiment. The technologies are perfectly correlated; they are either both armed in good or in a bad state. A technology that is armed in a good state generates a success with positive probability; a technology that is armed in a bad state never generates a success. This implies that with some positive probability a stage is never completed successfully as is evident, for instance, in the pharmaceutical industry. Firms independently and simultaneously decide on the intensity of experimentation with every unit spent on experimentation having an opportunity cost that arises from exploiting an existing certain project. Crucially for our analysis, firms decide on their intensity of experimentation on a period by period basis; a firm might stop experimenting for some time but restart at any point in the future.

Uncertainty is gradually resolved as firms experiment on a given technology. Every failure is a signal that the technology is armed in a bad state; hence, it makes firms more pessimistic regarding its viability to generate the required breakthrough. An important assumption is that firms observe one another's actions and outcomes which introduces a bilateral (dynamic) feedback mechanism. On the one hand, a failure of one firm imposes a negative information externality to the rival as is now more likely that the technology is armed in a bad state; a success imposes a positive information externality as it now becomes commonly known that advancement to the next stage is feasible. On the other hand, success by one firm imposes a negative competition externality on the rival as the latter needs to catch up in the race. In other words, the rival has a lag in the race arising from the fact that it still needs to invest resources and successfully pass the research stage before competing head-to-head with the leader. Our goal is a detailed study of the interplay between these two countervailing externalities.

We characterise the unique symmetric subgame perfect Nash equilibrium of the game by partitioning the set of parameters into two sets. For relatively low-value products, advancement of one firm to the development stage discourages the rival from remaining in the race; the negative competition externality offsets the positive information externality. This result is in line with early papers in the patent races literature (e.g., [START_REF] Fudenberg | Preemption, leapfrogging and competition in patent races[END_REF], [START_REF] Harris | Perfect Equilibrium in a Model of a Race[END_REF]), who argue that an early advantage is sufficient for the race to degenerate into a monopoly. Perhaps the most interesting case arises for relatively high-value products. In this case, the positive information externality offsets the negative competition externality; hence, the laggard finds it profitable to stay in the race. We show that at the switching point (i.e., the cutoff value above which the positive externality offsets the negative externality), there is a downward jump discontinuity in the payoff of the leader. Intuitively, the leader would prefer the race to degenerate into a monopoly instead of competing with the laggard even if the former enjoys a first-mover advantage.

We characterise the equilibrium stopping time as a function of the value of the product. We find that the stopping time is everywhere continuously decreasing in the value of the product but exhibits an upward jump discontinuity at the switching point. This discontinuity arises from the discontinuity in the continuation payoff of the leader; advancement by one firm to the development stage is accompanied by an increase in experimentation by the rival which has a negative impact on the continuation payoff of the firm that advanced first. The model implies that (i) the intensity of experimentation decreases in the belief, and, (ii) around the discontinuity, a decrease in the product's value can spur experimentation.

We study the welfare properties of the symmetric equilibrium. The symmetric equilibrium is everywhere inefficient: when at least one firm has advanced to the development stage, firms experiment excessively because they do not internalise the negative externalities they impose on one another (e.g., [START_REF] Loury | Market structure and innovation[END_REF], [START_REF] Lee | Market structure and innovation: a reformulation[END_REF]); when both firms are in the research stage, firms might either experiment excessively or insufficiently. The latter is a result of the free-riding effect and is particularly prevalent in the strategic experimenation literature (e.g., [START_REF] Keller | Strategic experimentation with exponential bandits[END_REF]).

Casual observation suggests that the dynamic feedback mechanism can be important in real-world races. When [START_REF] Bednorz | Possible high T c superconductivity in the Ba-La-Cu-O system[END_REF] announced that they had discovered superconductivity in ceramic materials at 35 o Kelvin -a temperature that seemed impossible before -physicists realised that other high-temperature superconducting material are feasible. Following a conference that took place in New York, during which [START_REF] Wu | Superconductivity at 93 K in a new mixed-phase Y-Ba-Cu-O compound system at ambient pressure[END_REF] presented superconducting materials at much higher temperature (around 90 o Kelvin), "...hundreds of scientists, Nobel laureates as well as the greenest graduate students, went on a work rampage. It was indeed a race, a race to obtain fame and patents. 3 As it is evident in this example, discovery by one firm might result in an increase of effort by rivals to be the first to cross the line.

Related Literature. The paper is related to several strands in the literature. Early papers by [START_REF] Loury | Market structure and innovation[END_REF], [START_REF] Lee | Market structure and innovation: a reformulation[END_REF] and [START_REF] Dasgupta | Uncertainty, industrial structure, and the speed of R&D[END_REF] analyse (effectively static) patent races in which firms invest in R&D only at the outset and investment determines the speed of innovation. All papers show that R&D investment is socially excessive. We also find that R&D investment is excessive but this is more prevalent either in more advanced stages or for relatively low-value products. [START_REF] Reinganum | Dynamic Games of Innovation[END_REF]Reinganum ( , 1982)), [START_REF] Fudenberg | Preemption, leapfrogging and competition in patent races[END_REF] and Harris andVickers (1985, 1987) allow for dynamic models in which firms can only increase their investments (i.e., once a firm drops out, it can never re-enter the race). In [START_REF] Reinganum | Dynamic Games of Innovation[END_REF]Reinganum ( , 1982)), firms accumulate knowledge; when knowledge has the characteristics of a private good (i.e. it can only be used by the firm that accumulates it), then R&D investment is excessive; when knowledge has the characteristics of a public good, then investment is insufficient. [START_REF] Fudenberg | Preemption, leapfrogging and competition in patent races[END_REF] analyse a multistage race and provide conditions under which a race will be characterised by vigorous competition or will degenerate into monopoly. Key is whether the laggard has time to "leapfrog". Harris and Vickers (1987) show that the leader exerts higher effort than the laggard, and effort increases as the gap between competitors decreases. A similar result in obtained in [START_REF] Grossman | Dynamic R & D competition[END_REF] who extend the model of [START_REF] Lee | Market structure and innovation: a reformulation[END_REF] to two stages. They find that (i) when both firms are in the development stage, competition is the most intense; (ii) the leader invests more than the laggard. Although in our model the investment decision is binary (i.e., invest or not invest), we also find that for relatively low-value products, the leader stays active whilst the follower drops out.

Closely related are the papers by [START_REF] Choi | Dynamic R&D competition under" hazard rate" uncertainty[END_REF], [START_REF] Malueg | Dynamic R&D competition with learning[END_REF], [START_REF] Mason | Learning in Contests[END_REF] and [START_REF] Moscarini | Competitive experimentation with private information: The survivor's curse[END_REF] who also study related model of dynamic R&D competition. Similarly to our paper, [START_REF] Choi | Dynamic R&D competition under" hazard rate" uncertainty[END_REF] studies a model with hazard rate uncertainty and identifies the different externalities that might affect R&D investment. Unlike our paper, he assumes that once firms exit the race, they are unable to reenter. 4 In our model firms are free to exit and re-enter anytime. Re-entry is the underlying mechanism of the discontinuity in the stopping times. Unlike [START_REF] Choi | Dynamic R&D competition under" hazard rate" uncertainty[END_REF], we proceed to a welfare analysis and discuss asymmetric equilibria. [START_REF] Malueg | Dynamic R&D competition with learning[END_REF] study a one stage race with hazard rate uncertainty. One of their main results is that as firms become more pessimistic, they reduce investment and possibly exit the race. In our model the interesting insights arise only due to the two stages.

This paper draws insights from the strategic experimentation literature. [START_REF] Bolton | Strategic experimentation[END_REF] study two-armed bandit models with several agents and [START_REF] Keller | Strategic experimentation with exponential bandits[END_REF] extend their framework to exponential bandits. Building on [START_REF] Keller | Strategic experimentation with exponential bandits[END_REF], [START_REF] Bimpikis | Designing Dynamic Contests[END_REF] and [START_REF] Halac | Contests for experimentation[END_REF] study dynamic contest design in which the planner commits to a disclosure policy and reward scheme. Our paper takes the R&D game as given and analyses its equilibria. 5The remainder of the paper is organised as follows. In Section 2, we present the model. In Section 3, we analyse the unique symmetric subgame perfect Nash equilibrium. In Section 4, we study the welfare properties of the unique symmetric equilibrium. In Section 5 we discuss the relevance of the model, the robustness of our results as well as further potential extensions. Section 7 concludes the paper. All formal proofs are provided in the appendix.

THE MODEL

There is a potentially infinite number of periods. Two symmetric, risk-neutral firms are engaged in a race to launch a new product (e.g., a new drug). Development of the new product requires a firm to successfully complete two stages: research and development. Let s denote the stage, where s = r, d. The first firm that successfully completes both stages receives a patent and monopoly profits equal to v.6 Advancement to the development stage requires a firm to successfully complete the research stage, which implies that the two stages are consecutive steps in the production process. Although a firm that completes the research stage qualifies to the development stage, the rival could potentially qualify to the development stage by also successfully completing the research stage. We call a firm that qualified first to the development stage the leader and the firm that is still at the research stage the laggard. In case both firms complete the two stages simultaneously, then the patent is allocated to one of them with equal probability. 7 For simplicity and to highlight the potential inefficiencies, we assume that firms do not discount the future. However, all our results remain valid even under discounting. We discuss this point at the end of the paper.

In every stage, firms each have symmetric bandit technologies on which they can experiment. Firms choose their intensity of experimentation x ∈ [0, 1]. Every dollar spent on experimentaion has an opportunity cost c. This cost can be interpreted as the the profit that the firm can earn by operating an alternative project of certain returns. An important assumption is that each firm decides on its intensity of experimention on a period by period basis. In particular, we assume that a firm that has stopped experimenting for some time can freely re-commence at any future point.

Every technology is armed either in a good or a bad state. As is standard in the strategic experimentation literature, the two technologies are perfectly correlated; either both are in a good or a bad state. The common prior belief that the technology is in a good state is α 0 < 1. A technology generates a success or a failure. One success is required for a firm to advance from the research to the development stage and two successes are required for a firm to be allocated the patent. We assume that successes occur independently in the two technologies. If a technology is armed in a good state and a firm chooses an intensity x, then the probability of a firm generating a success is px, where p < 1; if a technology and Strack (2015) and [START_REF] Bimpikis | Disclosing information in strategic experimentation[END_REF], who analyse how information disclosure can improve learning. is armed in a bad state the correspondng probability of generating a success is zero regardless of the intensity of experimentation.8 Therefore, only if the technology is armed in a good state, success is ever possible; if the technology is armed in a bad state, success is never possible. The two states represent the potential uncertainty that firms face when undertaking R&D; firms do not know if the product can ever be developed.

Uncertainty is resolved gradually if firms experiment; if at least one firm succeeds in the research stage, both firms become certain that the technology is in a good state; a failure delivers bad news and both firms become more pessimistic about the viability of the technology to generate the breakthrough. In particular, suppose that the belief is α and only one firm experiments at intensity x, then, following a failure, the belief that the technology is in a good state is downgraded to

α = α(1 -px) (1 -α) + α(1 -px) (1)
The posterior belief deteriorates faster the higher is p and/or x; i.e., the higher is the probability of success if the technology is in a good state, the more informative is a failure. Figure 1 represents two cases for α 0 = 0.9. In Panel 1a, p = 0.1, x = 1 and in Panel 1b, p = 0.01, x = 1. One can see that the posterior belief deteriorates considerably faster in Panel 1a.

THE UNIQUE SYMMETRIC EQUILIBRIUM

Symmetric Equilibrium and Notation. We assume that firms each simultaneously and independently take actions every period by having observed one another's actions and outcomes in the previous periods; therefore, we study a dynamic game of complete information. We characterise the unique symmetric subgame perfect Nash equilibrium. Both Firms in the Development Stage. Suppose first that both firms have qualified to the development stage. We impose the following assumption which implies that experimentation is always profitable for a sufficiently high belief.

Assumption 1. v ≥ 2c p
The equillibrium intensity of experimentation depends on the relative value of the product. Given Assumption 1, it is relatively straightforward to see that firms each choose a strictly positive intensity. Suppose that in every period, firm i chooses (constant) intensity x i and firm j chooses (constant) intensity x j ; then, the (static) expected payoff of firm i is

p 2 x i x j 2 + px i (1 -px j ) v -cx i = p(1 - px j 2 )v -c x i (2)
Due to Assumption 1, it is clear that Eq. ( 2) is strictly increasing in x i for every x j . This implies that in the unique symmetric equilibrium, both firms will choose to experiment at a maximum intensity in every period. We summarise the analysis in the following lemma.

Lemma 1. Suppose that both firms have qualified to the development stage; then, in the unique symmetric equilibrium xdd = 1 and

Vdd = 1 2 v -vdd (3)
where vdd = 2c p(2 -p) (4)
Proof. See the Appendix.

It is insightful to consider the effect of changes in parameters on the continuation value. It is straighforward from inspection of Eq. ( 4) that vdd is strictly increasing in c and p; hence, by inspection of Eq. ( 3), one can straightforwardly deduce that (ceteris paribus) an increase in c or an increase in p decrease Vdd . The effect of p on vdd and Vdd is a consequence of a strategic effect: an increase in the probability of success of both firms makes experimentation less attractive for each firm conditional on the rival experimenting at a maximum intensity. It is relatively straightforward that the leader exploits its position and, given Assumption 1, always experiments at a maximum intensity. For relatively low-value products, the leader remains a monopolist; for relatively high-value products, the laggard stays in the race and also experiments at a maximum intensity. 9 Given stationarity, the necessary and sufficient condition for the laggard to be active is

One Firm in the

p(1 -p) Vdd -c ≥ 0 (5)
where p(1 -p) represents the probability that the laggard succeeds and the leader fails (conditionally on both experimenting at a maximum intensity) in which case both firms find themselves in the development stage and each earns a continuation payoff equal to Vdd . 10 Straighforward algebra reveals that the laggard remains active if and only if the value of the product is greater than

vrd ≡ vdd + 2c p(1 -p) (6)
9 Conventionally, we assume that, conditionally on the rival's strategy, when a firm is indifferent between staying active or not it remains active.

10 The (static) expected payoff of the laggard if it experiments at intensity x rd whilst the leader experiments at intensity x dr is:

p(1 -px dr ) Vdd -c x rd
Because, as we argued above, the leader always experiments at maximum intensity x dr = 1; hence, the necessary and sufficient condition for the laggard to experiment is given in Eq. (5).

Eq. ( 6) implies that, conditionally on the leader experimenting at a maximum intensity, a markup over vdd is required to incentivise the laggard to remain active given that this needs to catch up in the race. From inspection of Eq. ( 6), one can see that vrd is strictly increasing in c and p -i.e., an increase in the cost of experimentation or an increase in the probability the breakthrough occurs both decrease the threshold value of the product above which the laggard experiments.

We summarise the unique symmetric equilibrium in the following lemma.

Lemma 2. Suppose that one firm is in the research stage and the other firm is in the development stage; then, in the unique symmetric equilibrium xdr = 1 and

xrd = 0, if v ≤ vrd 1, otherwise (7)
The equilibrium continuation payoffs of the two firms are respectively

Vrd = 0, if v ≤ vrd 1 2 (1-p) Vdd 1-p 2 -vdd , otherwise (8)
and

Vdr = v -c p , if v < vrd 1 2 (1-p) Vdd +v 1-p 2 -vdd , otherwise (9)
Proof. See the Appendix.

From inspection of Eqs. ( 8) and ( 9), one can see that an increase in the cost of experimentation or an increase in the probability the breakthrough occurs all decrease both continuation payoffs. We complete the section with a remark that is key for the remainder of the paper. Lemma 3. (i) Vdd and Vrd are continuous and increasing in v with Vrd being strictly increasing for v ≥ vrd , (ii) Vdr is continuous everywhere, strictly increasing for v < vrd and v > vrd but exhibits a (downward) jump discontinuity at v = vrd .

Proof. See the Appendix.

Lemma 3 states that although Vdd and Vrd are continuous and increasing in v, Vdr exhibits a downward jump discontinuity at v = vrd . Intuitively, when the value of the product exceeds the threshold above which the laggard enters the race, competition reduces the continuation payoff of the leader. As we show below, this result has significant implications on the equilibrium stopping times and welfare.

Both Firms in the Research Stage. The next and last step in the characterisation of the symmetric equilibrium is to study the subgame in which both firms are in the research stage. We have shown above that, once a firm succeeds in the research stage, there exists a unique symmetric equilibrium for all parameter values, which we have characterised in Lemma 1 and Lemma 2.

Suppose therefore that both firms are in the research stage. We first characterise the equilibrium stopping time of any of the firms experimenting. The expected (static) payoff of firm i by experimenting at intensity x i in a period when the belief is α, provided that firm j does not experiment, is αp Vdr -c x i (10) which defines a unique cutoff in the posterior belief below which experimentation is not profitable.11 This cutoff is given by

ᾱ = min 1, c p Vdr (11)
We now study the behaviour of ᾱ as a function of v and obtain the following result.

Proposition 1. The equilibrium stopping time ᾱ is continuous and strictly decreasing for v < vrd and v > vrd ; it exhibits an upward jump discontinuity at v = vrd .

Proof. Note that for v < vrd , c p Vdr = c pv -c which, given Assumption 1, is less than one. The discontinuity in ᾱ is an immediate consequence of the discontinuity in Vdr .

Proposition 1 is one of the main results of the paper. It states that the equilibrium stopping time is everywhere continuous and strictly decreasing but exhibits an upwards jump discontinuity at v = vrd . This discontinuity arises from the discontinuity of Vdr as discussed in Lemma 3.

A natural question that arises concerns the characterisation of equilibrium intensity of experimentation for α > ᾱ.12 To study this, let us write the (static) expected payoff of firm i by experimenting at intensity x i in a period when the belief is α, provided that firm j experiments at intensity x j :

α(px i (1 -px j ) Vdr + (1 -px i )px j Vrd + p 2 x i x j Vdd ) -cx i (12)
To explain Eq. ( 12), note that if the state is good, with probability px i (1 -px j ) firm i succeeds and firm j fails, in which case the corresponding continuation payoff is Vdr ; with probability (1 -px i )px j firm i fails and firm j succeeds in which case the corresponding continuation payoff is Vrd ; with probability p 2 x i x j , both firms succeed and the corresponding continuation payoff is Vdd . The last term is the cost of experimentation.

To characterise the symmetric equilibrium intensity of experimentation, let us re-write Eq. ( 12) as

α[pV dr -p 2 x j ( Vdr + Vrd -Vdd )] -c x i Expected Payof from x i ,x j ≥0 + apx j Vrd Expected Payoff from x i =0 (13)
If α(p Vdr -p 2 ( Vdr + Vrd -Vdd )) ≥ c, Eq. ( 13) is increasing in x i for every x j (and strictly increasing if the inequality is strict); if α(p Vdr -p 2 ( Vdr + Vrd -Vdd )) < c, Eq. ( 13) is increasing in x i for x j ≤ (p Vdrc α )/p 2 ( Vdr + Vrd -Vdd ) (and strictly increasing if the inequality is strict) and strictly decreasing for x j > (p Vdrc α )/p 2 ( Vdr + Vrd -Vdd ). In the latter case, in the unique symmetric equilibrium, the two firms experiment at a strictly-less-than-maximum intensity; each firm experiments at an intensity that makes the rival indifferent between experimenting or not.

We summarise the unique symmetric equilibrium in the following proposition.

Proposition 2. Suppose that both firms are in the research stage; then, in the unique symmetric equilibrium, for every α ≥ ᾱ:

xrr (α) = min 1, p Vdr -c α p 2 ( Vdr + Vrd -Vdd ) (14)
By inspection of Eq. ( 14), one can see that an implication of Proposition 2 is that experimentation is higher the higher is α and the lower is c. This implies that firms might start the race by experimenting at a maximum intensity but might reduce their intensities as they become more pessimistic regarding the viability of the project. Furthermore, the intensity of experimentation crucially depends on whether v ≶ vrd . In particular, we know from Lemma 2 that for v < vrd , Vrd = 0 as the laggard finds it unprofitable to continue experimenting; for v > vrd , Vrd = 0 and hence reduces equilibrium experimentation as each firm expects the other firm to suffer the cost of experimentation.13 This is a consequence of the fundamental free-riding effect that has been highlighted in the strategic experimentation literature (e.g., [START_REF] Bolton | Strategic experimentation[END_REF], [START_REF] Keller | Strategic experimentation with exponential bandits[END_REF]): the benefit of any of the firms from not experimenting might be positive since, conditional on the rival experimenting, there is a positive externality from a potential release of good news.

The equilibrium stopping time is depicted in Figure 2: the horizontal axis represents v; the vertical axis represents α. The stopping time is everywhere continuously decreasing but exhibits an upward discontinuity at v = vrd .

Another implication of Propositions 1 and 2 is that the intensity of experimentation is not always increasing in the value of the product. To see this, consider a (α, v) combination in the shaded region A in Figure 2. In this region firms will stop experimenting as we explained above. Suppose now that during a recession the value of the product falls. For the same posterior belief, such a fall will be accompanied by an increase in experimentation as firms find it profitable to enter the race knowing that the leader will also be the winner of the race. We now describe the socially optimal policy and discuss in what ways the equilibrium differs from it and thus we examine the potential inefficiencies that might arise during the race.

First, note that, due to the assumption of no discounting, it is never socially optimal to invest in both technologies in the same period, in any of the stages. This is because the social cost of operating one technology, given that the other technology is active, is positive, whereas the social benefit is zero, i.e., the incremental value of succeeding in one technology is zero if the other technology succeeds. In fact, if both technologies are operated by a benevolent social planner, it is strictly dominant to experiment at a maximum intensity in at most one technology. Therefore, our objective is to examine the conditions under which it is socially optimal to operate one technology.

Suppose first that the research stage has been successfully completed. Whilst in the development stage, Assumption 1 implies that it always is socially optimal to experiment at a maximum intensity in exactly one technology.

The expected value of the product if one technology has advanced to the development stage is

V * d = v - c p (15)
Now suppose that no technology has advanced to the development stage. We wish to characterise the optimal stopping time, i.e., specify the unique threshold belief below which it is socially optimal to stop experimenting.

If the belief is α, the expected payoff of commiting to a plan of experimentation {x ω } T ω=t from period t till period T is given by the value function:

V * t (α) = αpx t V * d -cx t + (1 -αpx t )V * t+1 (α ) ( 16
)
where α is given in Eq. ( 1). It is only straightforward that if αpV * d -c > 0, the planner will choose to experiment at a maximum intensity in period t, or x t = 1. The optimal stopping time is characterised if in Eq. ( 16) one imposes that V * t (α) ≥ 0 and V * t+1 (α ) < 0. In other words, the optimal stopping time is the last experiment such that the payoff is positive. The optimal stopping time is given by

α * = min 1, c pV * d (17)
In fact, one can characterise the unique threshold in the value of the product above which experimentation is socially optimal for a sufficiently high belief. This is specified in the following proposition.

Proposition 3. The socially optimal stopping time α * is everywhere continuously strictly decreasing. Moreover, α * = ᾱ for v < vrd and α * > ᾱ for v ≥ vrd .

Proposition 3 states that the optimal stopping time is decreasing in v. Furthermore, it coincides with the equilibrium stopping time for v < vrd but is strictly greater than the equilibrium stopping time for v ≥ vrd . The latter is a result of the fundamental free-riding effect: even if it is socially optimal to continue experimenting firms stop prematurely.

Given the analysis thus far, it is not difficult to see that equilibrium experimentation is always inefficient. Nonetheless, different types of inefficiencies arise based on (i) the stage at which firms are, and, (ii) parameter values. To be more precise, we analyse the different types of inefficiencies by starting from the end and moving backwards. The following corollary summarises the possible inefficiencies when both firms have advanced to the development stage.

Corollary 1. Suppose that both firms have qualified to the development stage; then both firms experiment at maximum intensity in equilibrium whilst it is socially optimal to experiment at a maximum intensity only in one technology.

Corollary 1 is in line with the early contributions by [START_REF] Loury | Market structure and innovation[END_REF], [START_REF] Lee | Market structure and innovation: a reformulation[END_REF] who show that firms may undertake excessive R&D because they do not internalise the negative externalities they impose on one another.

We can now study the subgame starting after one firm advances to the development stage while the rival firm is still in the research stage. We saw in Lemma 2 that there is a critical cutoff below which the firm in the research stage exits the race. The following corollarly highlights the possible inefficiencies.

Corollary 2. Suppose that one firm has qualified to the development stage while the rival is still in the research stage; then, (i) for v < vrd only the firm that is in the development stage experiments at a maximum intensity in equilibrium as is socially optimal, (ii) for v ≥ vrd , it is socially optimal for only the firm that is in the development stage to expiriment at a maximum intensity but both firms experiment at a maximum intensity in equilibrium.

Corollary 2 states that for products that are not sufficiently lucrative, advancement to the development stage by one firm is sufficient for the race to degenerate into a monopoly; for sufficiently lucrative products, duplication of investment arises as firms do not internalise the negative externalities they impose on one another. The former results is in line with early papers in the patent races literature (e.g., [START_REF] Fudenberg | Preemption, leapfrogging and competition in patent races[END_REF], [START_REF] Harris | Perfect Equilibrium in a Model of a Race[END_REF]);14 the latter result is similar to that obtained in Corollary 1.

Suppose now that both firms are in the research stage. As we argued in Proposition 3, ᾱ ≥ α * as Vdr ≤ V * d with the inequality being strict for v ≥ vrd .

Corollary 3. Suppose that both firms are in the research stage; then, it is socially optimal to experiment in at most one technology at maximum intensity but in equilibrium both firms experiment.

Corollary 3 states that apart from over-investment a potential under-investment might arise when both firms are in the research stage: for relatively high belief and/or value products, both firms experiment at a maximum intensity although it is socially optimal to experiment at a maximum intensity at most in one technology; for relatively low belief and/or value products, firms might experiment too little.

All the inefficiencies that characterised in Corollaries 1 and 2 are essentially static in the sense that they do not arise from the dynamics of the model. Unlike Corollaries 1 and 2, the inefficiency described in Corollary 3 is a dynamic inefficiency. The dynamic inefficiency is the result of the dynamics of the model: firms might under-invest due to the fundamental free-riding effect.

DISCUSSION

Model Relevance. The model applies in innovation races in which completion of at least two stages is a prerequisite for a patent to be allocated and, at the outset, firms are uncertain about the overall feasibility of the project. For instance, if only one stage is completed, the requirements of the Patent Granting Authority are not satisfied. For instance in the pharmaceutical industry, the allocation of a patent is granted after a significant period has lapsed and several stages have been completed. One can assume that more than two stages (i.e., N > 2) are required before the product is successfully marketed but successful completion of the first two stages is sufficient for a firm to file an application for the allocation of a patent. In that case v denotes the expected monopoly profit minus the cost required to complete the N -2 remaining stages.

Asymmetric Equilibria. Although we focus on the unique symmetric equilibrium, asymmetric equilibria exist. For instance, an asymmetric equilibrium entails only one firm experimenting at a maximum intensity for relatively low α instead of both firms experimenting. This equilibrium is more efficient than the symmetric equilibrium as it avoids the duplication of investment.

Robustness. Although, we have imposed a number of simplifying assumptions, our results are robust in various alternative specifications. Below we discuss some:

-Discounting: Throughout, we have assumed that firms do not discount the future. This assumption was only for simplicity; all our results are valid even if firms discount the future. The most important implication of discounting regards the socially efficient stopping time. In particular, under discounting, the planner faces an inter-temporal tradeoff: experimenting at maximum intensity in both technologies is costly but increases the probability of success. Hence, an impatient social planner would prefer to invest at a maximum intensity in both technologies. For the reasons explained above, under no discounting the planner faces no inter-temporal trade-off and hence would operate at most one technology at a time.

-Continuous vs. discrete time: Following [START_REF] Bolton | Strategic experimentation[END_REF], most of the literature on strategic experimentation employs a continuous time framework. 15 Instead, we study a discrete-time counterpart of [START_REF] Keller | Strategic experimentation with exponential bandits[END_REF] exponential model, although our results are robust even in continous time.

-Other issues: We have assumed that the same bandit technology is used in both stages. This implies that (i) conditionally on the technology being armed in a good state, the probabilities of success in both stages are the same and (ii) the development stage is certain. Extension to an environment in which firms have different (symmetric) technologies in the two stages is straightforward and would not alter the results.

Avenues for Future Research. One interesting avenue for future research is to study a game in which firms do not perfectly observe the actions and outcomes of one another but they can voluntarily disclose the intermediate breakthrough as in [START_REF] Yildirim | Contests with multiple rounds[END_REF], [START_REF] Gill | Strategic disclosure of intermediate research results[END_REF], [START_REF] Rieck | Information disclosure in innovation contests[END_REF] and [START_REF] Akcigit | The role of information in innovation and competition[END_REF]. In our model, when v < vrd , firms have strong incentive to disclose any intermediate breakthrough as soon as possible to discourage the rival from continuing; when v ≥ vrd , firms would like to hide intermediate breakthroughs to protect themselves from competition. Nonetheless, in either case, the equilibrium intensity of experimentation depends on the beliefs firms entertain regarding the relative position of the rival which makes the analysis considerably more complicated.

Another interesting extension is to assume that firms do not disclose intermediate breakthroughs but receive a private information signal -perhaps due to espionage-regarding the state of the rival. This would also introduce different incentives for experimentation.

CONCLUSION

In this paper we studied a winner-takes-all R&D race as a two-armed bandit model. Two firms that competed on the development of a new product had to pass two stages (Research & Development) before acquiring a patent. Firms possessed identical bandit technologies able to provide them with the breakthrough that was required to complete a stage. Nonetheless, at the outset, firms were uncertain whether their technologies were Proof of Lemma 3. To show that Vdr is discontinuous in v at vrd , it suffices to show that

v - c p > 1 2 (1 -p) Vdd + v 1 -p 2 -vdd ⇔ v - c p > (1 -p) Vdd + v 2 -p - 1 2 vdd ⇔ 1 - 2 2 -p v > (1 -p) Vdd 2 -p + c p 1 - 1 2 -p ⇔ v > Vdd + c p ⇔ v - c p > 1 2 v - c (2 -p)p ⇔ v > c p • 2(1 -p) 2 -p ⇔
which is always satisfied.

  Figure1

  Research and One in the Development Stage. Having characterised the equilibrium behaviour of the two firms if both have advanced to the development stage and the corresponding equilibrium continuation payoffs, we can now study the subgame in which one firm is in the research stage and the rival is in the development stage.

  Figure 2

Table 1 :

 1 conditional on the rival being in stage s , where ss ∈ {rd, dr, dd} xrr (α) Symmetric equilibrium intensity of experimentation when both firms are in research and the belief is α Vss Symmetric equilibrium continuation payoff of a firm that is in stage s conditional on the rival being in stage s , where ss ∈ {rd, dr, dd} Notation A strategy for each firm defines the intensity of experimentation every period for any history of play. To simplify notation, let xss and Vss denote the equilibrium intensity of experimentation in stage s, conditional on the other firm being in stage s , and the equilibrium continuation payoff of a firm that is in stage s if the rival firm is in stage s , where ss ∈ {rd, dr, dd}. By definition, in a symmetric equilibrium in which both firms are in the same stage, the intensities of experimentation and continuation payoffs of the two firms are equal. Note also that if at least one firm qualifies to the development stage, the problem becomes stationary; hence, if a decision is optimal in one period, it remains optimal every period. Let also xrr (α) denote the intensity of experimentation conditional on both firms being in the research stage and the posterior belief is α.

	v	Value of the product
	p	Marginal probability of success if the state is good
	c	Marginal cost of experimentation
	α 0	Prior that the state is good
	x i	Firm i's intensity of experimentation
	xss	Symmetric equilibrium intensity of experimentation of the firm that is in
		stage s,

Discontinuation of research can result from toxicity, carcinogenicity or any other manufacturing difficulties that researchers discover during pre-clinical or clinical trials. See[START_REF] Dimasi | Success rates for new drugs entering clinical testing in the United States[END_REF][START_REF] Dimasi | The price of innovation: new estimates of drug development costs[END_REF][START_REF] Dimasi | Innovation in the pharmaceutical industry: new estimates of R&D costs[END_REF].

[START_REF] Vidali | Superconductivity: the next revolution?[END_REF].

In p. 608, Choi (1991) writes: "... But in models of hazard rate uncertainty, the payoff structure of the race could be that of a waiting game. Every firm might prefer the other firms to enter the race first. After observing the performance of other firms, it will enter if the other firms do well and the race is considered to exhibit a high enough hazard rate. Another possibility is that both firms enter the race, and after some time without success by either firm, one of them drops out. The firm that drops out could reenter once the remaining firm succeeds in the intermediate-stage discovery..."

Related are the paper by[START_REF] Kremer | Implementing the "wisdom of the crowd[END_REF] [START_REF] Che | Optimal design for social learning[END_REF],Heidhues, Rady,

This corresponds to the sum of the profits from the effective life of the patent.

One can consider different patent allocation rules without substantially change the results. This allocation rule is chosen for simplicity.

We assume that the intensity of experimentation cannot exceed an upper bound; hence, there is always an upper bound in the probability a firm can generate a success. Because experimentation is costly, firms will never choose an intensity greater than one.

Note that, for a given α, this is the maximum "static" payoff a firm can attain, i.e., the payoff if the firm was a "monopolist", where "static" refers to the fact the the continuation payoff is not taken into account.

For α = ᾱ, the unique symmetric equilibrium intensity of experimentation is zero.

Note that Vrd appears only in the denominator, which means that a higher Vrd decreases xrr (α).

This is sometimes called " -preemption".

For an exception see[START_REF] Heidhues | Strategic experimentation with private payoffs[END_REF].

If a compound passes this stage, it moves to pre-clinical (tests in animalsSee https://www.fda.gov/ForPatients/Approvals/Drugs/default.htm.

armed in a good state, in which case the required breakthrough could occur with a strictly positive probability, or in a bad state, in which case the breakthrough could never occur. We assumed that firms observed one another's actions and outcomes.

We analysed the unique symmetric equilibrium of this dynamic game. We showed that for relatively low-value products firms experimented at a maximum intensity and the equilibrium stopping time coincided with the socially efficient stopping time; for relatively high-value products, free-riding could reduce experimentation and firms stopped experimenting prematurely. Perhaps surprisingly, we showed that a decrease in the value of the product could spur experimentation.

APPENDIX

Proof of Lemma 1. To find Vdd , note that if both firms experiment at a maximum intensity every period, the continuation payoff of each firm is

Solving for Vdd , one obtains that

where vdd = 2c/p(2 -p).

Proof of Lemma 2. To find Vrd , note that, as we argued in the text, for v < vrd , the laggard exits the race; for v ≥ vrd , the laggard continues in the race and experiments at a maximum intensity. The laggard's continuation payoff is given by

Vrd which is equivalent to

Regarding the leader's continuation payoff, for v < vrd , it is a monopolist and earns a continuation payoff

which is equivalent to Vdr = v -c p ; for v ≥ vrd , the laggard continues in the race and the leader's payoff is Vrd = pv + p(1 -p) Vdd -c + (1 -p) 2 Vdr which is equivalent to