Charlotte Héricé

Manon Bonnet-Save

André Garenne

Jean-Marie Cabelguen

Thomas Boraud

Setting A Behavioral Task For Assessing Decision Making In Urodele Amphibian

INTRODUCTION

Decision making implies cortical-basal ganglia (BG) loops, but the respective roles of each structure are still debated. Urodeles, by their similitude with mammals in BG organisation, offer a much less level of complexity in understanding this process by the presence of fewer neurons. Therefore, we decided to set up a behavioral test of decision making in this animal. Moreover, their regenerative capacities make them a unique model to study post-lesional plasticity of this process networks. To our knowledge, urodele is the earliest group of limbed vertebrates in which decision-making has been successfully addressed yet.

ANIMALS

All the experiments were performed on fully metamorphosed amphibian urodeles (Pleurodeles waltlii) (13 months post-hatching). We used 20 animals for the behavioral test and 7 for the DA system lesion (preliminary results obtained for 2 out 7 animals are reported).

BEHAVIORAL TEST

Animals have been trained in associating a polarized light direction to the position of an obscure shelter [START_REF] Taylor | Spatial Orientation by Salamanders Using Plane-Polarized Light[END_REF]. Then they were tested according to the feature of the light (non polarized light, NPL; polarized light, PL). Note that the direction of the polarization and the N-S direction of the magnetic field were perpendicularly oriented, both during training and test.

DOPAMINERGIC SYSTEM LESION

The animals were deeply anaesthetised via immersion in a 0.1% aqueous solution of tricaine methanesulfonate (MS-222). The micro-pipette containing a 6-OHDA solution was inserted into the brain through a small hole surgically drilled at the junction of the parietal and frontal bones in the cranial midline.

Injection site [START_REF] Parish | Midbrain dopaminergic neurogenesis and behavioural recovery in a salamander lesion-induced regeneration model[END_REF]. The red dot indicates the 6-OHDA injection site, directly into the third ventricle at the level of diencephalic/mesencephalic dopaminergic (DA) neurons.

Identification of DA neurons : Immunohistochemical identification.OT: Optic Tectum. DA-Mb: DA cells groups of the midbrain. Antibodies raised against tyrosine hydroxylase (TH). The study will be focused on the ventral diencephalic/mesencephalic TH + cells, which are consistently affected by 6-OHDA administration in the third ventricle.

The number of successive steps during each walking episode (A) and the step duration (C) were mesured for each animal before, 7 days and 10 or 13 days after the 6-OHDA injection. A similar quantification was performed for swimming cycles (B, D).

The effect of 6-OHDA. The 6-OHDA lesion induced clear short-term effects on the walking behavior. By contrast, the swimming behavior seemed unaffected.

FUTURE DIRECTION

This paradigm gives us access to a motor decision making mode. In a second step, we will perform selective electrical lesions of the pallium (i.e. the cortex in lower vertebrates), the thalamus and the basal ganglia to determine the respective role of each structure. We will then study implication of dopamine in this behavioral task by 6-OHDA lesions.

  Training tank. Animals were housed under a 12h:12h polarized light:dark cycle and trained 4 times a day during 3 weeks.Test arena. Testing sessions occurred once a day and by 3 tries for each tested condition.Results field reresentation. Polarized light vector (blue arrow) and terrestrial magnetic orientation (red arrow).Angle occurrence probability. Following training, the number of animals in the success zone is increased, showing that training is effective.

SOURCES

Video recordings are available by flashing the QR-code. Mail contact: charlotte.herice@u-bordeaux.fr


Pierre Andreoletti
email: pierre.andreoletti@univ-orleans.fr

Pierre Gazé
email: pierre.gaze@univ-orleans.fr

Maxime Menuet
email: maxime.menuet@univ-orleans.fr

« Can a Platform Make Profit with Consumers' Mobility? A Two-Sided Monopoly Model with Random Endogenous Side-Switching »

Keywords: JEL Codes: L11, L13, L86 externalities, side-switching, two-sided markets externalités, mobilité inter-faces, marchés à deux faces

Can a platform make profit with consumers' mobility? A two-sided monopoly model with random endogenous side-switching ✩ Une plateforme peut-elle capter la mobilité des consommateurs en rente ?

Un modèle de marché à deux faces en monopole avec une mobilité inter-faces endogène et aléatoire.

Introduction

In two-sided markets (TSM), two sets of agents interact on a firm or an organization called a platform. Each group of agents generates indirect network externalities that positively (with some exceptions) affect the utility of the agents of the other group. A lot of activities are characterized by these specific cross externalities. For example, malls must attract buyers and sellers, newspapers sell its services to readers and advertisers, card payment systems must develop the merchants' acceptance in order to attract new cards holders etc.

An abundant literature has produced a fruitful analysis in several directions. [START_REF] Armstrong | Competition in two-sided markets[END_REF] For example, pricing within the platform (Hagiu 2006; Schmalensee 2002), competition between platforms (Armstrong 2006; Caillaud and Jullien 2003; Chakravorti and Roson 2006) and antitrust issues (Evans 2003; Rysman 2007; Evans and Schmalensee 2013) are important topics of TSM economics. We would like to contribute to the pricing analysis for a specific class of TSM characterised by agents' migration from one group to another one. We think that side-switching in TSM is a fruitful topic that deserves further theoretical investigation. Gazé and Vaubourg (2011) have identified this particular type of TSM. Indeed, there exist numerous examples of such TSM. In the auction website eBay, in all payment systems, in electronic marketplaces (like "Amazon Marketplace") people can achieve a transaction in one group then make another transaction in the other group. In a first time period, an agent can act as a buyer and in a second time period he can move to the other group and become e.g. a seller. These specific class of TSM raises new interesting economic questions. Do the side-switching behavior has consequences on the firm's strategy ? What impact has mobility on prices and profits?

One potential consequence of mobility is the raise of the platform's transactions number. If agents can move quickly and easily from a group to another group (e.g. with two mouse clicks), the platform can mechanically develop the market demand. For example, in the electronic market E-bay, a consumer can discover the platform from the buyer side and then have the idea and the possibility of selling second-hand objects on the sellers' side. Then, we conceive easily that mobility encourages a growth in market demand and potentially an increase of business for the firm. Actually, we are looking for more subtle mechanisms in order to have a better understanding of the "economics of mobility". We want to show that side-switching can affect prices and profit even without market growth.

In the case of a duopoly market Gazé and Vaubourg (op. cit.) demonstrate that the agent's mobility affects the equilibrium of the firms. They show that under a specific set of constraints, the firms' profit increase with the rate of the mobility of agents. The mechanism that generates profit is explained by changes in the set of prices that reflect a complex game of rewards and penalties. Firms obtain a profit from the heterogeneity of platform's consumers and from their mobility inside the TSM. Nevertheless, this analysis has a number of limitations. One of these limitations is the exogenous rate of changing face. In this paper we would like to remove this restriction; we will show that the platform considers the mobility rates as strategic variables.

We conceive a model to highlight the effects of mobility on prices and profit of the firm which produce TSM services. We suppose that the firm is a monopoly that faces two groups of agents who can switch to the other group when their migration enhances their satisfaction. So their probabilities of departure from a group to the other are totally endogenous to the pricing of the monopoly. The monopoly has a direct impact on the size of the two groups when it modifies its prices. We show that the firm encourages agents' mobility in order to raise its profit. Therefore, in our model, the mobility corresponds to the fluctuation of the sizes of the two sides, thus the side-switching allows the firm to adjust the size of both groups to an optimal level. Then, this framework suggests that the monopoly has the possibility of enhancing the quality of the platform by stimulating the side-switching. The rest of the paper is organized as follows. In Section 2, we describe the important assumptions of our model concerning consumers, firm and the timing of action. Equilibrium of period one and period two are calculated in Section 3. In Section 4, we discuss our theoretical results.

A platform that faces mobile consumers

The consumers

The firm sells its service to two groups of agents denoted a and b. We call "consumers" agents of both sides since they consume the output of the monopoly. So this denomination can be used to describe e.g. the buyers side as well as the merchants side. Conforming to a TSM framework, the participation of one group raises the value of participating for the other group. Consumers interact through the platform and their utility is positively affected by cross network externalities.

A consumer that joins face j, j ∈ {a, b}, yields at period i, i ∈ {1, 2}, obtains the following level of utility:

u a i := α a N b i -p a i , u b i := α b N a i -p b i . (1)
We denote α j as the cross network externality parameter and N j i as the number of face j's consumers at period i. The parameter α a (resp. α b ) measures the benefit a group-a (resp. group-b) agent enjoys from interacting with each group-b (resp. group-a) agent. Finally, p j i is the price charged to the consumers of group j during the period i. We assume that consumers must buy one platform's service during each period of time. The market demand is the same in period one and two but the respective size of groups can vary from one session to the other. In addition, the total number of consumers N > 0 is given by:

N := D a (u a 1 ) + D b (u b 1 ), (2)
where D j (•) are demand functions which will be defined in the Subsection 3.1. We do not focus our analysis on the total size of the market but on the demand repartition on the two faces. We assume that there is no market growth from period 1 to period 2. This hypothesis means that firm is not able to earn more profit by attracting new customers on the market during the period 2. This is not realistic but it is useful to analyse and isolate the role played by mobility. In formal word, we suppose that in period 2 utility is big enough so that consumers prefer join the platform instead of staying out 3 of the market (the market is fully served). Finally, participation's conditions are given by net consumer's expected utilities must be positive or null, i.e. E(u j i ) ≥ 0, i ∈ {1, 2}, j ∈ {a, b}, where E(•) is the expectation.

The platform

We focus our analysis on the most simple market structure since we assume that only one firm faces all the consumers. We choose the monopoly paradigm in order to highlight the effects of mobility on the economic link between the firm and the consumers. Obviously, in the monopoly market structure no competitive effects can alter the repercussions of side-switching on the firm's equilibrium. Our model allows us to consider the consumers probability of side-switching as an indirect strategic variable at the firm's disposal. We will show that through an appropriate set of prices, the firm can impact the repartition of the demand into the two groups and in fine make additional profits. For simplicity, we assume all production costs equal to zero. Finally, as usual, the constraint of the platform's budget is given by: p a i + p b i ≥ 0, i ∈ {1, 2}.

Timing of actions

We consider a two-stage game. Following Armstrong (2006), we suppose that the size of each face is directly determined by a function of the consumer's utilities. The platform set two prices in the first period that maximized its profit; one price for the face a and one price for the face b. Once the transactions are done, consumers and firm are engaged in the second period. Consumers move to the other face if they want, i.e. if their move increases their utility. In the same time, firm set the two second period prices. The two-session game is then finished. Note that pairs of profit-maximizing prices determine the relative size of each platform's face. In other words, the probability of switching from a face to the other is totally endogenous. In addition, consumers are homo economicus: they have no ex ante preference for being a member of one group instead of belonging to the other group. They choose the side they want to become a member by taking into account prices and externalities strength (i.e. the size of the other side and the level of the externality parameters).

Analysis and equilibrium

First period

In the first period, as Armstrong (2006), the number of consumers buying the service on each side, denoted N a 1 and N b 1 , and are given by the demand system:

N a 1 := D a (u a 1 ) = D a (α a N b 1 -p a 1 ), N b 1 := D b (u b 1 ) = D b (α b N a 1 -p b 1 ). ( 3
)
We assume that the functions D j (•), j ∈ {a, b}, are increasing and differentiable on a concave support. The demand on each side at monopoly prices is assumed to be positive.

Then, the plarform's program is to maximize the profit of first period Π

1 := p a 1 N a 1 +p b 1 N b 1 . Thus, the profit-maximizing prices (p a * 1 , p b * 1 ) satisfy: 2 p a * 1 = D a D ′ a -α b N b 1 and, p b * 1 = D b D ′ b -α a N a 1 , (4)
where D ′ j is the slope of the demand function at fixed participation of the other side. Replacing in (3) yields the optimal demands N a * 1 (resp group a, α a N a 1 ). The total number of consumers is then defined by

1 = D a (α a N b * 1 -p a * 1 ) and N b * 1 = D b (α b N a * 1 -p b * 1 ). Notice that p a * 1 (resp. p b * 1 ) is
N := N a * 1 + N b * 1 .
As usual, the first period allows to endogenous the numbers of the consumers in both sides. [START_REF] Caillaud | Chicken and egg: Competition among intermediation services providers[END_REF] In first period, the consumers enter or go out on a side of the market (a, or b) according to their level of utilities (D a (u a 1 ), or D b (u b 1 )). In second period, the market is closed (no entry and exit), but the consumers who entered in first period can now change side. For example, a consumer entered in first period on the side a, as buyer, can switch on the side b, as seller.

Second period

Our analysis of mobility is organized into three stages. First, we characterize equilibriums in absence of mobility, where consumers stay in their origin groups. Secondly, we determine equilibriums with stochastic mobility, where this mobility will be endogenous to expected consumers' utilities. Finally, we analyze differences between these two equilibriums and the consequences of the mobility for the firm.

Absence of mobility

In absence of mobility, the platform's program is to maximize the profit of second period

Π 2 := p a 1 N a 2 + p b 2 N b 2 .
By definition, the consumers stay in their first period group, so we can write: N j 2 = N j * 1 , j ∈ {a, b}, where N j * 1 are optimal demand functions defined in first period by equations ( 3) and (4). In addition, consumers' participation constraints are given by: u

a 2 = α a N b * 1 -p a 2 ≥ 0, and u b 2 = α b N a * 1 -p b 2 ≥ 0. Thus, the prices (p i * 2 , i = a, b) maximizing the profit are: p a * 2 = α a N b * 1 , and p b * 2 = α b N a *
1 , which are quite intuitive since the best the firm is to extract all the consumer surplus. Finally, the optimal profit on absence of mobility is simply

Π * 2 = tN a * 1 N b * 1 , (5)
where t := α a + α b measures the totality of external effect. Despite the simplicity of this results, the case without mobility allows to establish a brenchmark on the level of the profit. Our analysis is then to compare the profit in the case with stochastic mobility with the profit (5) without mobility.

Stochastic mobility

We defined the isidiosyncratic random variable, denoted by X n , which represent the membership group of the consumer n in period 2,

n ∈ {1, • • • , N }, where N = N a * 1 + N b * 1
is given by the first period. In other word, if the consumer n is a member of the site j in period 2, then X n = j, j ∈ {a, b}. In addition, we assume that these consumers make their decision independently, so that N a 2 (respectively N b 2 ) the number of agents in face a (resp. b) at the second period is a sum of N independent and identically distributed random variables given by:

N a 2 := N n=1 1 {Xn=a} , (6)
(resp. N b 2 := N -N a 2 )
, where 1 is the indicator function. [START_REF] Chakravorti | Platforms competition in two-sided markets: The case of payment networks[END_REF] We denote f a := P(X 1 = a) and f b := 1 -f a = P(X 1 = b), where f j represents the proportion of consumer in face j at period 2. Otherwise, there is an equivalent interpretation where f j represents the probability for a consumer to be in face j at the end of the second period. Thus, we determines the choice of belonging to each consumer probabilistically. The membership group of every consumers is not known in a certain way, but we know that they have a probability f a (resp. f b ) to belong in the side a (resp. b) at the end of the second period.

Obviously the mean of N a 2 , denoted E(N a 2 ), is given by: E(N a 2 ) = f a N , and similarly

E(N b 2 ) = N -f a N = f b N .
However, the mobility is a dynamic process, and assume that there is a price couple which ensures a stable equilibrium at the end of the second period. Condition i. guarantees an optimal equilibrium for consumers, and condition ii. ensures an optimal equilibrium for the platform. Thus, when i. and ii. are satisfied, the mobility stops, because neither the platform, nor consumers can hope for a better gain.

It is what we call stable equilibrium. The Definition 1 is constructive and implies the following Proposition. In a similar way we prove that u a 2 < u b 2 is impossible.

Proposition 1 implies that at equilibrium both faces bring the same utility to consumers. Indeed, for a given set of prices, external effects make converge the levels of utilities. We are now able to obtain explicit expressions for the proportions (f j , j = a, b).

Corollary 1. Let the prices (p a 2 , p b 2 ) assure one equilibrium at second period. Thus we have,

f a = p b 2 -p a 2 N t + α a t , and
f b = p a 2 -p b 2 N t + α b t , (7)
with the conditions 0 ≤ f a ≤ 1 and 0 ≤ f b ≤ 1.

Proof: See appendix.

We can see that (f j , j = a, b) are endogenous to prices and external effects. Also we notice that the proportion of agents migrating in face j increases with the utility of group j. [START_REF] Evans | The Antitrust Analysis of Multi-Sided Platform Businesses[END_REF] The intuition for this is that when u a 2 rises (with a p a 2 decrease or α a increase), ceteris paribus, the expected utility for the group a reduces, therefore, consumers are less incited to move in group a, thus f a decreases. In addition, the condition on the Corollary 1 easily implies:

0 ≤ f j ≤ 1, j ∈ {a, b} ⇔ -N α b ≤ p a 2 -p b 2 ≤ N α a . (8)
The computations of endogenous probabilities show that consumers go to the other face considering price's faces differential and the relative strength of network externalities. Not surprisingly, we see that a consumer is more likely to move to the cheapest face and also to the group that confers the highest externality.

In our model, the platform's profit at the second period is the random variable:

Π2 = p a 2 N a 2 + p b 2 N b 2
, where N j 2 are determined by (6). Moreover, the platform's program is to maximize the mean of Π2 ,6 denoted by Π 2 , which is given by

Π 2 (p a 2 , p b 2 ) := E[ Π2 (p a 2 , p b 2 )] = p a 2 N f a + p b 2 N f b . Namely, by (7), Π 2 (p a 2 , p b 2 ) = N (p a 2 α a + p b 2 α b ) t - (p a 2 -p b 2 ) 2 t . (9)
We now resume the constraints for the second period: the first is the condition (8), the second are consumers' participation constraints:

E(u j 2 ) ≥ 0, j ∈ {a, b} ⇔ p a 2 α b + p b 2 α a ≤ α a α b N.
And the constraint of the platform's budget is simply p 2 a + p 2 b ≥ 0. Thus, the space of prices at second period, denoted by C 2 , is

C 2 := {(p a 2 , p b 2 ) ∈ R 2 |p a 2 α b + p b 2 α a ≤ α a α b N ; -N α b ≤ p a 2 -p b 2 ≤ N α a ; p a 2 + p b 2 ≥ 0}. ( 10
)
As a consequence, the optimal prices (p a * 2 ,p b * 2 ) at equilibrium should satisfy

{p 2 * a , p 2 * b } := argmax (x,y)∈C2
Π 2 (x, y).

Theorem 1. (prices at equilibrium) The optimal prices (p a * 2 , p b * 2 ) are given by:

p a * 2 = α a N a * 1 + N b * 1 2 and, p b * 2 = α b N a * 1 + N b * 1 2 .
As a consequence the optimal proportion are given by f * a = f * b = 1 2 , and the mean of the profit at equilibrium by:

Π * 2 := E( Π * 2 ) = (N a * 1 + N b * 1 ) 2 t 4 . (11)
Proof: See appendix.

In the equilibrium, the price p a * 2 (resp. p a * 2 ) is equal to the mean of the consumers' number ((N a * 1 + N b * 1 )/2) adjusted by the external parameter α a (resp. α b ), which represent the benefit a group-a (resp. group-b) agent enjoys from interacting with each group-b (resp. group-a) agent. With this prices, each consumer will choose either side with equal probability (1/2), and the mean of the consumers' number in second period is the same in both sides:

E(N a * 2 ) = E(N b * 2 ) = N f * a = N/2.
We note that in the case without mobility (in the Subsection 3.2.1), if the number of consumers in each side was a strategic variable for the platform, the optimal profit Π * 2 = tN a * 2 N b * 2 would be maximized when N a * 2 = N b * 2 = N/2, which is the case at equilibrium with mobility. Thus, the case with mobility enables the firm to change the number of consumers to maximize the demand and the profit, but this case is risky for the platform. Therefore, we easily obtain the variance of Π * 2 : 7

Var( Π * 2 ) = N 4 (p a * 2 -p b * 2 ) 2 = N 3 16 (α a -α b ) 2 .
It is interesting to remark that mobility introduces uncertainty both for firm and consumers. The mobility gives birth to a specific kind of risk: the possibility that the group which gives utility (or profit) has a decreasing size in the future. For the monopoly, the variance of expected profit is increasing with the differential of externality parameters (α a and α b ). The larger is the difference between α a and α b the larger is the gap between expected prices p 2 * a and p 2 * b . For this reason, the firm could realize a smaller turnover if consumers go massively to the cheapest face. For consumers, the expected utility depends on the size of the other group. The higher is the consumers' mobility the higher is the variance of the size of the groups.

Thanks to Theorem 1 we can easily determine the impact of mobility on the platform's income. We call S the extra profit that the firm can earn from the consumer's mobility: [START_REF] Gazé | Electronic platforms and two-sided markets: A side-switching analysis[END_REF] Indeed the profit can be written:

Π2 = p b 2 N + (p a 2 -p b 2 )N a 2 . Thus, Var( Π2 ) = (p a 2 -p b 2 ) 2 Var(N a 2 ) = (p a 2 -p b 2 ) 2 fa(1 -fa).
Corollary 2.

S := E( Π * 2 -Π * 2 ) = t 4 (N a * 1 -N b * 1 ) 2
Proof: See appendix.

There are two noteworthy implications of this extra profit. First, we notice that the larger is the spread between the initial sizes of groups, the greater is the extra profit. The intuition is that in this model the mobility corresponds to the fluctuation of the sizes of the two sides by the platform. Indeed, in the first period, this sizes of the two groups are optimal according to the consumers' participations, i.e. the demand functions D a and D b given by (3). Therefore, the first period à la Armstrong (2006) determine the total level of demand:

N = N a * 1 + N b * 1 .
During the second period, as the market is closed, the optimal average sizes of two sides are determined to maximize this demand's repartition (EN a 2 = EN b 2 = N/2). Thus, the optimal profit with mobility is simply the maximum of the profit without mobility when the number of consumers in both sides are adjusted by the platform. In this way, the mobility which is actually the possibility for consumers to switch, allows the firm to set prices that maximize the level of demand, and determine the optimal average size of groups. Finally, the larger is the gap between the two populations of consumers in period one, the larger is the extra profit S, since the optimal size is the same for both groups. Second and not surprisingly implication, we notice that the profit is increasing with the sum of external effects t, with t := α a + α b .

Discussion

If mobility is not possible, standard TSM economics show that firm adjusts prices to the level of externality that a group of consumers generates. The central idea is that the price is adjusted by the external benefit that a group brings to the other group (the more a consumer brings value to the other group the smaller is the price). We can see this specific way of setting prices as "a reward pricing". If mobility is possible, modification in size group is a mechanism that raises profit in itself. The firm receives incitation to set prices that homogenizes the number of consumers in each group. At the end of this process (that is to say in period 2), there is no "reward pricing" anymore. Therefore, the mobility allows the firm to adjust the size of both groups to an optimal level that it yields a extra profit. But, we can wonder why the repartition of consumers in each group wouldn't be optimal during the first time period?

In several TSM, consumers discover the platform by one side without thinking about the benefit they can obtain by belonging to the other side. They progressively acquire information that lets them see the utility they can expect by switching to the other side. E.g a BlaBlaCar consumer can discover the site one day when he needs to travel. After experimenting rides as a passenger, he can become a driver who offers rides. Thanks to his experience, this consumer may maximize his satisfaction by belonging to the driver's side that is not the side that attracted him first to the site. These mechanisms can explain why consumers can choose the suboptimal side of the platform when they enter into the market. Actually, mobility gives the consumers an opportunity to enhance their satisfaction. This is the reason why it is profitable for the firm.

In addition, can we find in the industry some illustrations of these special relationships between the firm and their consumers? Do the firms really encourage mobility?

The booking site Airbnb is a good example of a TSM with mobility. Airbnb's simplicity has made it easy for people to find accommodation in private residences and to book them easily. Consumers can discover the site during a trip by the renter side and then, once back home, become an offeror of a room in his flat, i.e. make a side-switching. The same mechanism prevails for the electronic payment system Paypal. Paypal users can receive or sent funds (i.e. make a side-switching) very easily, with very low transaction costs and almost no constraints. That is true as well for the emblematic electronic platform Ebay which easily permits its consumers to become sellers through the Amazon Marketplace program. We think that common features of Ebay, PayPal and Airbnb (and other major electronic platforms) imply similarity in business management for these successful firms. Mobility is quality; it is the reason why these firms develop advertising programs, discount prices or didactic tutorials to give incentives to consumers to make some business into the other side of their favorite platform. We think that our model is consistent with these observations. Consumers' side-switching is a natural way to develop the business but it is also an attractive method of consumers' surplus extraction.

Conclusion

The possibility of changing from a face to the other appears to consumers like an improvement of product's quality. Since the platform is a monopoly, it can capture the increase of the consumer's utility and make additional profit compared to the first period of time. In this model, mobility is a valuable feature for consumers which enhance quality's product. Actually, this is a strong economic explanation for the profitability of the mobility. Finally our paper shows that, in a specific context, mobility is a strategical variable in the TSM industry.

According to our results, it would be interesting to study the TSM in a dynamic model. For example, we would define an intertemporal "cyclic" model with two phases. During phase one, we can imagine a firm that encourage the dissymmetry between the two sides. For example, the platform could attract many consumers to one side in the case of a new market. In the case of an existing market, the platform would encourage the whole population to move (or stay) to a certain side of its business. Then in the second phase, and according to our model's results, we could imagine a firm which takes advantage of the initial gap between the two groups. With such a dynamic model, conditions under which the alternation of phases is profitable for the firm should be obtained. The existence of one TSM implies that λ 3 = λ 4 = 0. Indeed, if it is not the case, the totality of the consumers may move to the same face, and the TSM disappear. So we now deal with the case λ 2 = 0 and then λ 1 = 0. First, if λ 2 = 0 and λ 1 > 0 the system (A1) becomes,

                         ∂ x L = -N t α a + 2 t (
       ∂ x L = -N t α a + 2 t (p a 2 -p b 2 ) + α b λ 1 = 0, ∂ y L = -N t α b -2 t (p a 2 -p b 2 ) + α a λ 1 = 0, p a 2 α b + p b 2 α a = α a α b N.
After resolution of this system, we find:

       p a 2 = N t α a , p b 2 = N t α b , λ 1 = N t > 0.
If λ 2 > 0 and λ 1 = 0, the system (A1) becomes,

       ∂ x L = -N t α a + 2 t (p a 2 -p b 2 ) -λ 2 = 0, ∂ y L = -N t α b -2 t (p a 2 -p b 2 ) -λ 2 = 0, p a 2 = -p b 2 .
Once the system is solved, we find λ 2 = -N 2 < 0 which is impossible because Lagrange multipliers are positive. So in this case, there are no points who verify KKT conditions. Finally, there is only one minimum p 0 := (N α a /t, N α b /t) complying the first order conditions and the constraint of TSM's existence. Taking (p a 2 , p b 2 ) = p 0 , we have,

f a = p b 2 -p a 2 N t - α a t = 1 2 = f b ,

  equal to the elasticity of the group's participation D a /D ′ a (resp. D b /D ′ b ), adjusted downward by the external benefit of group b, α b N b

Definition 1 .

 1 (Equilibrium at second period) The prices (p a 2 , p b2 ) define the equilibrium at second period if: i. No agent can improve his utility by changing group, ii. The mean profit of the platform is maximal.

Proposition 1 .b 2 )

 12 If prices (p a 2 , p b 2 ) assure equilibrium at second period, then u a 2 , defined in Definition 1, assuring the equilibrium at second period. If u a 2 > u b 2 , then agents migrate in face a. So, N a 2 increases and N b 2 decreases. Therefore by the external effects and since the prices are fixed, u a 2 decreases and u b 2 increases. According to Definition 1, this process is stopped when u a 2 = u b 2 .

p a 2 -p b 2 ) + α b λ 1 -

 221 λ 2 -λ 3 + λ 4 = 0, ∂ y L = -N t α b -2 t (p a 2 -p b 2 ) + α a λ 1 -λ 2 + λ 3 -λ 4 = 0, λ 1 (p a 2 α b + p b 2 α a -α a α b N ) = 0, λ 2 (p a 2 + p b 2 ) = 0, λ 3 (-N α b -p a 2 + p b 2 ) = 0, λ 4 (p a 2 -p b 2 -N α a ) = 0.(A1)

2 (p 0 ) = p a 2 f a N + p b 2 f b N = N 2 t 4 .

 24 Finally, it is obvious that O := (0, 0) ∈ C 2 , and Π 2 (O) = 0. So, there is a point (O), such as Π 2 (O) > -Π 2 (p 0 ) = -N 2 t/4, thus p 0 is a local minima of -Π 2 , i.e. a local maxima of Π 2 . As a consequence, we have Π * 2 = Π 2 (p 0 ).

For the proof seeCaillaud and Jullien (2012).

Another model could be to assume that the consumers' number in every side is an exogenous parameters, however this implies a loss of generality.

1 {Xn=a} = 1 if Xn = a, 0 else.

It is straightforward to show from equation (7) that: ∂fa/∂p b 2 ≥ 0, ∂fa/∂p a 2 ≤ 0, ∂fa/α b ≤ 0 and ∂fa/∂αa ≥ 0, reciprocally for f b .

Another method consists of maximizing the intertemporal profit Π = Π 1 + βΠ 2 , where β is the discount rate. But such a method does not distinguish simply the following two mechanisms: first the market entry (as our first period), and second the side-switching (as our second period). However, the maximization of the intertemporal profit, by setting prices for two periods is a possible extension of our model.

Appendix

Proof of Corollary 1 According to Proposition 1:

Proof of Theorem 1

The platform's program at the second period is given by the minimization problem (P ): min

where the mean profit Π 2 is the continuously differentiable function given by ( 9) and C 2 is given by (10). First note that C 2 is a compact space of R 2 , therefore (P ) admits at least one solution. Also the function Π 2 does not admit critical points: it does not exist (x, y) ∈ C 2 such that ∇Π 2 (x, y) = 0, where ∇ is the gradient. Consequently, the solution of the problem (P ) is on the boundary of the space C 2 . The Lagrangien L of (P ) is given by

where λ = {λ i ; i = 1 • • • 4} represent lagrange's multipliers. Then, Karush-Kuhn-Tucker (KKT) first order conditions are given by the following system, Proof of Corollary 2 By ( 5) and ( 11), we have

And by (2), N := N a * 1 + N b * 1 , thus (A2) becomes


Ahmed Hassan

Roberto Palmieri

Binoy Ravindran

Binoy Ravindran Transactional

Transactional Interference-less Balanced Tree

Keywords: Balanced Trees, Transactional Memory, Semantic Synchronization, Concurrent Data Structures

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

Introduction

With the growing adoption of multi-core processors, the design of efficient data structures that allow concurrent accesses without sacrificing performance and scalability becomes more critical than before. In the last decade, different designs of the concurrent version of well-known data structures (e.g., lists, queues, hash tables) have been proposed [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF]. Balanced binary search trees, such as AVL and Red-Black trees are data structures whose self-balancing guarantees an appealing logarithmic-time complexity for their operations.

One of the main issues in balanced trees is the need for rotations, which are complex housekeeping operations that re-balance the data structure to ensure its logarithmic-time complexity. Although rotations complicate the design of concurrent balanced trees, many solutions have already been proposed: some of them are lock-based [START_REF] Nathan G Bronson | A practical concurrent binary search tree[END_REF][START_REF] Crain | A speculation-friendly binary search tree[END_REF][START_REF] Crain | A contention-friendly binary search tree[END_REF][START_REF] Afek | The CB tree: a practical concurrent self-adjusting search tree[END_REF][START_REF] Arbel | Concurrent updates with RCU: search tree as an example[END_REF][START_REF] Drachsler | Practical concurrent binary search trees via logical ordering[END_REF], while others are non-blocking [START_REF] Brown | A general technique for non-blocking trees[END_REF][START_REF] Ellen | Nonblocking binary search trees[END_REF][START_REF] Howley | A non-blocking internal binary search tree[END_REF][START_REF] Natarajan | Fast concurrent lock-free binary search trees[END_REF].

One of the main limitations of concurrent data structures is that they do not compose. For example, atomically inserting two elements in a tree is difficult: if the method internally uses locks, issues like managing the dependency between operations executed in the same transaction, and the deadlock that may occur because of the chain of lock acquisitions, may arise. Similarly, composing nonblocking operations is challenging because of the need to atomically modify different places in the tree using only basic primitives, such as a CAS operation. Lack of composability is a serious limitation of the current designs, especially for legacy systems, as it makes their integration with third-party software difficult. In this paper we focus on composable (transactional) balanced trees.

Although the research has reached an advanced point in designing concurrent trees, transactional trees have not reached this point yet. There are two practical approaches, to the best of our knowledge, that enable transactional accesses on a tree: 1) The first approach is Transactional Memory (TM) [START_REF] Herlihy | Transactional memory: Architectural support for lock-free data structures[END_REF] which natively allows composability as it speculates every memory access inside an atomic block;

2) The second approach is Transactional Boosting [START_REF] Herlihy | Transactional boosting: A methodology for highly-concurrent transactional objects[END_REF] (TB), which protects the transactional access to a concurrent data structure with a set of semantic locks, eagerly acquired before executing the operation on the concurrent data structure. Both TM and TB have serious limitations when used for designing transactional trees. Those limitations originate from the same reason: they are both generic, and they do not consider the specific characteristics of balanced trees, which instead are heavily investigated in literature. For example, TM considers every step in the operation, including the rotations, as low-level memory reads/writes, which clearly increases the number of false conflicts. On the other hand, TB uses the underlying concurrent tree as a black-box, which prevents any further customization, and may nullify the internal optimizations of the concurrent tree due to the eagerly acquired semantic locks.

Recently, a third trend, which we name Optimistic Semantic Synchronization (OSS), has emerged to overcome the limitations of the above approaches. Examples of this new approach include methodologies like [START_REF] Afek | Towards consistency oblivious programming[END_REF][START_REF] Avni | Brief announcement: Cop composition using transaction suspension in the compiler[END_REF][START_REF] Xiang | Software partitioning of hardware transactions[END_REF][START_REF] Hassan | Optimistic transactional boosting[END_REF][START_REF] Hassan | On developing optimistic transactional lazy set[END_REF][START_REF] Grasso | Transactional predication: high-performance concurrent sets and maps for STM[END_REF]. We used the word optimistic because all of these solutions share a fundamental optimism. In fact, the common idea behind the aforementioned methodologies is to split data structures' operations into a traversal phase and a commit phase. A transaction optimistically executes the traversal phase without any locking and/or speculation, and it defers the commit phase to the commit time of the enclosing transaction. Unlike TM and TB, OSS only provides guidelines to design transactional data structures, and it leaves all the development details to the data structure designer, thus enabling the possibility of adding further (data structure-specific) optimizations.

OSS is clearly less programmable than TM and TB, but it has the potential to provide better performance and scalability, especially when applied to complex data structures, like the case of balanced trees. Due to their high abstraction level, none of the methodologies listed above discusses in detail how they can be applied to balanced trees without nullifying the body of work related to highly optimized concurrent (non-transactional) balanced trees.

Inspired by OSS, in this paper we present TxCF-Tree, the first balanced tree that is accessible in a transactional, rather than just a concurrent, manner without monitoring (speculating) the whole traversal path (like in TM) or nullifying the benefits of the efficient concurrent designs (like in TB). TxCF-Tree offers a set of design and low-level innovations, but roughly it can be seen as the transactional version of the recently introduced Contention Friendly Tree (CF-Tree) [START_REF] Crain | A contention-friendly binary search tree[END_REF]. The main idea of CF-Tree is to decouple the structural operations (e.g. rotations and physical deletions) from the semantic operations (e.g. queries, logical removals, and insertions), and to execute those structural operations in a dedicated helper thread. This separation makes the semantic operations (that need to be transactional in TxCF-Tree) simple: each operation traverses the tree non-speculatively (i.e., without instrumenting any accessed memory location); then, if it is a write operation, it locks and modifies only one node. In an abstract way, the TxCF-Tree's semantic operations can be seen as composed of a traversal and commit phases, which makes CF-Tree a good candidate for being transactionally boosted using OSS.

In addition to the new transactional capabilities, TxCF-Tree claims one major innovation with respect to CF-Tree, which is fundamental for targeting high performance in a transactional (not only concurrent) data structure. Although CF-Tree decouples the structural operations, those operations are executed in the helper thread with the same priority as the semantic operations, and without any control on their interference. With TxCF-Tree, we make the structural operations interference-less (when possible) with respect to semantic operations. This property is highly desirable because structural operations do not alter the abstract (or semantic) state of the tree, thus they should not force any transaction to abort. To reduce this interference, one operation should behave differently if it conflicts with a structural operation rather than with a semantic operation.

TxCF-Tree uses two new terms, which help to identify those false-interleaving cases and alleviate their effect: structural lock, which is a type of lock acquired if the needed modifications on the node do not change its abstract (semantic) state; and structural invalidation, which is a transactional invalidation raised only because of a structural modification on the tree rather than having actual conflicts at the abstract level. In TxCF-Tree, transactions do not abort if they face structural locks or false-invalidations during the execution of their operations. We further reduce the interference of the helper thread by adopting a simple heuristic to detect if the tree is almost balanced. If so, we increase the back-off time between two helper thread's iterations.

We assessed the effectiveness of TxCF-Tree1 through an evaluation study. Our experiments show that TxCF-Tree performs better than the other transactional approaches (TB and STM) in almost all of the cases.

Background

Optimistic Semantic Synchronization. We use the term Optimistic Semantic Synchronization (OSS) to represent a set of recent methodologies that leverage the idea of dividing the transaction execution into phases and optimistically executing some of them without any instrumentation (also called unmonitored phases). In this section, we overview some of those approaches.

Optimistic Transactional Boosting (OTB) methodology [START_REF] Hassan | On developing optimistic transactional lazy set[END_REF][START_REF] Hassan | Optimistic transactional boosting[END_REF] is the optimistic version of TB. It lists three guidelines to convert any optimistic concurrent data structure into a transactional one. According to OTB's first guideline, every data structure's operation is split into three phases: traversal, which is executed without any instrumentation and/or locking until reaching the position of interest in the data structure; validation, which checks the validity of the unmonitored traversal's outcome; and commit, which acquires the necessary locks and performs the actual modifications. OTB provides transactional capabilities by i) saving the outcome of the traversal phase into local semantic read/write-sets to be used during the validation and commit phases; and ii) deferring operation's commit phase until the commit of the whole transaction. The unmonitored traversal phase is the actual source of OTB's performance gains as it clearly reduces false conflicts. The second guideline of OTB discusses the necessary and sufficient steps to make this transactional version semantically opaque [START_REF] Guerraoui | On the correctness of transactional memory[END_REF], which means that if the data structure is only accessed using its defined APIs, then all of its operations are semantically consistent at any time of the transaction execution, even though opacity may not be ensured at the memory level (e.g., due to the unmonitored traversal phase). The third guideline of OTB is to optimize the data structure internally.

Consistency Oblivious Programming (COP) [START_REF] Afek | Towards consistency oblivious programming[END_REF][START_REF] Avni | Brief announcement: Cop composition using transaction suspension in the compiler[END_REF] splits the operations into the same three phases as OTB (but under different names). We observe two main differences between COP and OTB. First, COP is introduced mainly to design concurrent data structures and it does not natively provide composability unless changes are made at the hardware level [START_REF] Avni | Brief announcement: Cop composition using transaction suspension in the compiler[END_REF]. Second, COP does not use locks at commit. Instead, it enforces atomicity and isolation by executing both the validation and commit phases using TM transactions.

Partitioned Transactions (ParT) [START_REF] Xiang | Software partitioning of hardware transactions[END_REF] also uses the same trend of splitting the operations into a traversal (called planning) phase and a commit (called update) phase, but it gives more general guidelines than OTB. Specifically, ParT does not restrict the planning phase to be a traversal of a data structure and it allows this phase to be any generic block of code. Also, ParT does not obligate the planning phase to be necessarily unmonitored, as in OTB and COP. Instead, it allows both the planning and update phases to be transactions.

Transactional Predication (TP) [START_REF] Grasso | Transactional predication: high-performance concurrent sets and maps for STM[END_REF] applies a similar methodology to the aforementioned approaches. However, it solves the specific problem of boosting concurrent sets and maps to be transactional.

Although TxCF-Tree complies with OSS, it is closer to OTB because it uses a well-defined concurrent tree as a base for its design (which fits the terminology of transactional boosting), and it follows the second guideline of OTB to guarantee that the transaction execution is semantically opaque.

Contention Friendly Tree. Contention Friendly Tree (CF-Tree) [START_REF] Crain | A contention-friendly binary search tree[END_REF] is an efficient concurrent lock-based (internal) tree, which finds its main innovation on decoupling the semantic operations (i.e., search, logical deletion, and insertion) from the structural operations (i.e., rotation and physical deletion). The semantic operations are eagerly executed in the original process, whereas the structural operations are deferred to a helper thread. More in details:

Semantic Operations: each semantic operation starts by traversing the tree until it reaches a node that matches the requested key or it reaches a leaf node (indicating that the searched node does not exist). After that, a search operation returns immediately with the appropriate result without any locking. For a deletion, if the node exists and it is not marked as deleted, the node is locked and then the deleted flag is set (only a logical deletion), otherwise the operation returns false. For a successful insertion, the deleted flag is cleared (if the node already exists but marked as deleted ) or a new node is created and linked to the leaf node (if the node does not exist). An unsuccessful insertion simply returns false. In all cases, each operation locks at most one node.

Rotations: re-balancing operations are isolated in a helper thread that scans the tree seeking for any node that needs either a rotation or a physical removal. Rotation in this case is relaxed, namely it uses local heights. Although other threads may concurrently modify these heights (resulting in a temporarily unbalanced tree), past work has shown that a sequence of localized operations on the tree eventually results in a strictly balanced tree [START_REF] Nathan G Bronson | A practical concurrent binary search tree[END_REF][START_REF] Kim S Larsen | AVL trees with relaxed balance[END_REF]. A rotation locks: the node to be rotated down; its parent node; and its left or right child (depending on the type of rotation). Also, rotations are designed so that any concurrent semantic operation can traverse the tree without any locking and/or instrumentation. To achieve that, the rotated-down node is cloned and the cloned node is linked to the tree instead of the original node.

Physical Deletion: The physical deletion is also decoupled and executed separately in the helper thread. In addition, a node's deletion is relaxed by leaving a "routing" node in the tree when the deleted node has two children (it is known that deleting a node with two children requires modifying nodes that are far away from each other, which complicates the operation). The physical deletion is done as follows: both the deleted node and its parent are locked, then the node's left and right children links are modified to be pointing at its parent, and finally the node is marked as physically removed. This way, concurrent semantic operations can traverse the tree non-speculatively without being lost.

Among the concurrent trees presented in literature, we select CF-Tree as a candidate to be transactionally boosted because it provides the following two properties that fit the OSS principles. First, it uses a lock-based technique for synchronizing the operations, which simplifies the applicability of the OSS methodology. Second, CF-Tree is traversed without any locking and/or speculation, allowing the separation of an unmonitored traversal phase. Also, the semantic operations (add, remove, and contains) are decoupled from the complex structural operations (although they can interfere with each other), like rotations and physical removals, allowing a simple commit phase.

Reducing the interference of structural operations

Balanced trees store data according to a specific balanced topology so that their operations can take advantage of the efficient logarithmic-time complexity. More specifically, operations are split into two parts: a "semantic" part, which modifies the abstract state of the tree, and a structural part, which maintains the efficient organization of the tree. For example, consider the balanced tree in Figure 1 2 . The tree initially represents the abstract set {1, 2} (Figure 1(a)). If we want to insert 3, we first create a new node and link it to the tree in the proper place (Figure 1(b)). Subsequently, the tree is re-balanced because this insertion unbalanced a part of it (Figure 1(c)). Semantically, we can observe the new abstract set, {1, 2, 3}, right after the first step and before the re-balancing step. However, without the re-balancing step, the tree structure itself may become eventually skewed, and any traversal operation on the tree would take linear time rather than logarithmic time. Although the structural operations are important, like the aforementioned rotations in our case, they represent the main source of conflicts when concurrent accesses on the tree occur. Two independent operations (like inserting two nodes in two different parts of the tree) may conflict only because one of them needs to re-balance the tree. This additional conflict generated by structural operations can significantly slow down the performance of transactional data structures more than their concurrent versions due to two reasons. First, in long transactions, the time period between the tree traversal and the actual modification during commit may be long enough to generate more conflicts because of the concurrent re-balancing. Second, in transactional data structures, any conflict can result in the abort and re-execution of the whole transaction, which possibly includes several non-conflicting operations, unlike concurrent operations that just re-traverse the tree if a conflict occurs.

Although CF-Tree decouples the structural operations in a dedicated helper thread, which forms an important step towards shortening the critical path of the processing (i.e., the semantic operations), it does not prevent the structural operations running in the helper thread from interfering with the semantic operations and delaying/aborting them. To minimize such a interference, we propose the following simple guideline (named G-Pr ): "Semantic operations should have higher priority than structural operations."

This guideline allows semantic operations to proceed if a conflict with structural modifications occurs. Our rationale is that, delaying (or aborting) semantic operations affects the performance, whereas delaying (or aborting) structural operations only defers the step of optimizing the tree to the near future.

TxCF-Tree

In this section, we discuss how to boost CF-Tree to be transactional using the OSS principles. The key additions of TxCF-Tree over CF-Tree are: i) supporting transactional accesses; and ii) minimizing the interference between semantic and structural operations. to simplify the presentation, we focus on the changes made on CF-Tree to achieve those two goals, and we briefly mention the unchanged parts whose details can be found in [START_REF] Crain | A contention-friendly binary search tree[END_REF].

Each node in TxCF-Tree contains the same fields as CF-Tree: a key (with no duplication allowed), two pointers to its left and right children, a boolean deleted flag to indicate the logical state of the node, and an integer removed flag to indicate the physical state of the node (a value from the following: NOT-REMOVED, REMOVED, or REMOVED-BY-LEFT-ROTATION). The node structure in TxCF-Tree is only different in the locking fields. In CF-Tree, each node contains only one lock that is acquired by any operation modifying the node. In TxCF-Tree, each node has two different locks: a semantic-lock, which is acquired by the operations that modify its semantic state (either the deleted or the removed flag); and a structural-lock, which is a acquired by the operations that modify the structure of the tree without affecting the node itself (i.e. modifying the right or left pointers). Each lock is associated with a lock-holder field that saves the ID of the thread that currently holds the lock, which is important to avoid deadlocks.

TxCF-Tree implements a set interface with the semantic operations: add, remove, and contains. Extending TxCF-Tree to have key-value pairs is simple, but for clarity we assume that the value of the node is the same as its key.

Structural Operations

The helper thread repeatedly calls a recursive depth-first procedure to traverse the entire tree. During this procedure, any unbalanced node is rotated and any logically removed node is physically unlinked from the tree. To minimize the interference of this housekeeping procedure, we use an adaptive back-off delay after each traversal iteration. We use a simple hill-climbing mechanism that increases (decreases) the back-off time if the number of housekeeping operations in the current iteration is less (greater) than the most recent iteration. While acknowledging the simplicity of the adopted heuristic, it showed effectiveness in our evaluation study.

Physical Deletions. We start by summarizing how the helper thread in CF-Tree physically deletes a node N n ( marked as deleted and at least one of its children is null). First, both N n and its parent N p are locked. Then, the node's left and right children fields are modified to point back to the parent (so that the concurrent operations currently visiting N n can still traverse the tree, without experiencing any interruption) and then N n is marked as REMOVED and unlinked by changing N p child to be N n 's child instead of N n .

TxCF-Tree modifies this mechanism by providing less-interfering locking. Specifically, we only acquire the structural-lock of N p because its semantic state will not change. On the other hand, both the semantic-lock and the structurallock have to be acquired on N n because N n 's removed flag, which is part of its semantic state, should be set as REMOVED. To further minimize the interference, the locking mechanism uses only one CAS trial. If it fails, then the whole structural operation is aborted and the helper thread resumes scanning the tree.

Rotations. In CF-Tree, a right rotation (without losing generality) locks three nodes: the parent node N p , the node to be rotated down N n , and its left child N l . Then, rotation is done by cloning N n and linking the cloned node at the tree instead of N n (similar to physical deletion, this cloning protects operations whose "unmonitored" traversal phase is concurrently visiting the same nodes. More details are in [START_REF] Crain | A contention-friendly binary search tree[END_REF]). Subsequently N n is marked as REMOVED (in case of leftrotation it is marked as REMOVED-BY-LEFT-ROTATION) and nodes are unlocked.

In TxCF-Tree, rotations also use a less intrusive locking mechanism. Both N p and N l acquire only the structural-lock because the rotated-down node N n is the only node that will change its semantic state (and thus needs to acquire the semantic-lock ). Also, we found that there is no need to lock the parent node (i.e., N p ) at all. This is because the only change to N p is to make its left (or right) child pointing to N l rather than N n . This means that N p 's child remains not null before and after the rotation. Only the helper thread can change it to null in a later operation by rotating the node down or physically deleting its children. On the other hand, semantic operations only concern about reading/changing the deleted flag of a node, if the searched node exists in the tree, or reading/changing a (null) link of a node, if the searched node does not exist in the tree. Thus, modifying the child link of N p cannot conflict with any concurrent semantic operation, thus it is safe to make this modification without locking. Similarly, if all the sub-trees of N n and N l are not null, then no structural locks are acquired, and the only lock acquired is the semantic-lock on N n .

Semantic Operations

According to OSS, each operation is divided into the traversal, validation, and commit phases. We follow this division in our presentation.

Traversal. The tree is traversed by following the classical rules of the sequential binary search tree. Traversal ends if we reach the searched node or a null pointer. To be able to execute the operation transactionally, the outcome of the traversal phase is not immediately returned. Instead it is saved in a local semantic read/write sets. Each entry of those sets consists of the following three fields. Op-key: the searched key that needs to be inserted, removed, or looked up. Node: the last node of the traversal phase. This node is either a node whose key matches op-key (no matter if it is marked as deleted or not) or a node whose right (left) child is null and its item is greater (less) than op-key. Op-type: an integer that indicates the type of the operation (add, remove, or contains) and its result (successful or unsuccessful).

Those fields are sufficient to verify (by the transaction validation) that the result of the operation is not changed since the execution of the operation, and to modify the tree at commit time. All the operations add an entry to the read-set, but only successful add and remove operations add entries to the write-set.

Before traversal, the local write-set is scanned for detecting read-after-write hazards. If the key exists in the write-set, the operation returns immediately without traversing the shared tree. Moreover, if a successful add operation is followed by a successful remove operation of the same item (or vice versa), they locally eliminate each other, in order to save the useless access to the shared tree. The elimination is done only on the write-set, and the entries are kept in the read-set so that the eliminated operations are guaranteed to be consistent.

Validation. The second phase of TxCF-Tree's operation is the validation phase. To have a comprehensive presentation, we show first the validation procedure in CF-Tree, and then we show how it is modified in TxCF-Tree.

Algorithm 1 Operation's validation in CF-Tree. In Algorithm 1, the validation in CF-Tree succeeds if the node's key is not physically removed and either the node's key matches the searched key (line 5) or its child (right or left according to the key) is still null (line 11). Otherwise, the validation fails (lines 3 and 12). This validation is used during add/remove operations as follows (details are in [START_REF] Crain | A contention-friendly binary search tree[END_REF]): each operation traverses the tree until it reaches the involved node, then it locks and validates it (using Algorithm 1). If the validation succeeds, the operation stops its traversal loop and starts the actual insertion/deletion. If the validation fails, the node is unlocked and the operation continues the traversal. In [START_REF] Crain | A contention-friendly binary search tree[END_REF], it has been proven that continuing the traversal is safe even if the node is physically deleted or rotated by the helper thread, due to the mechanism used in the deletion/rotation, as discussed in Section 4.1 (e.g., modifying the left and right links of the deleted node to be pointing to its parent before unlinking it).

Algorithm 2 Example of semantic opacity.

1: @Atomic initially the tree is empty 2: procedure T1 3: if tree.contains(x) = false then 4:

if tree.contains(y) = true then 5:

... hazardous action 6: end procedure 7: @Atomic 8: procedure T2 9: tree.add(x) 10: tree.add(y) 11: end procedure In TxCF-Tree, this validation procedure is modified to achieve two goals. The first goal regards the correctness: since TxCF-Tree is a transactional tree, validation has also to ensure that the operation's result is not changed until transaction commits; otherwise, the transaction consistency is compromised. As an example, in Algorithm 2 let us assume the following invariant: y exists in the tree if and only if x also exists. If we use the same validation as Algorithm 1, T 1 may execute line 3 first and return false. Then, let us assume that T 2 is entirely executed and committed. In this case, T 1 should abort right after executing line 4 because it breaks the invariant. Aborting the doomed transaction T 1 should be immediate and it cannot be delayed until the commit phase because it may go into an infinite loop or raise an exception (line 5). To prevent those cases, all of the read-set's entries have to be validated (using Algorithm 3 instead of Algorithm 1) after each operation as well as during commit.

Algorithm 3 Operation's validation in TxCF-Tree. The second goal regards performance: if the node is physically removed or its child becomes no longer null (which are the invalidation cases of CF-Tree), that does not mean that the transaction is not consistent anymore. It only means that the traversal phase has to continue and reach a new node to be validated. It is worth noting that aborting the transaction in those cases does not impact the tree's correctness, while its performance will be affected. In fact, this conservative approach increases the probability of structural operations' interference. For this reason we distinguish between those types of invalidations and the actual semantic invalidations, such as those depicted in Algorithm 2. The modified version of the validation is shown in Algorithm 3. The cases covered in CF-Tree are considered structural-invalidations (lines 9 and 25), and the actual invalidation cases are considered semantic-invalidations (lines 15 and 22). Algorithm 4 Read-set validation in TxCF-Tree. Algorithm 4 shows how to validate the read-set. For each entry, we firstly check if the entry's node is not locked (lines 4-9). In this step we exploit our lock separation by checking only one of the two locks because each operation validates either the deleted flag or the child link. Specifically, if the node's key matches op-key, node's semantic-lock is checked, otherwise the structural-lock is checked. Moreover, if the entry's node is locked by the helper thread, we consider it as unlocked because the helper thread cannot change the abstract state of the tree. The only effect of the helper thread is to make the operation structurally invalid, which can be detected in the next steps.

The next step is to validate the entry itself (line 10). If it is semanticallyinvalidated, then the transaction aborts (line 18). If it is structurally-invalidated, the traversal continues as in CF-Tree and the entry is updated with the new node (lines 12-16), then the node is re-validated. If the operation is a successful add/remove, the related write-set entry is also updated (line 16).

Commit. The commit phase (pseudo code in [START_REF] Hassan | Transactional interference-less balanced tree[END_REF]) is similar to the classical two-phase locking mechanism. The nodes in the read/write sets are locked and/or validated first, then the tree is modified, and finally locks are released.

From the commit procedure of TxCF-Tree it is worth mention the following points. The first point is how TxCF-Tree solves the issue of having two dependent operations in the same transaction. For example, if two add operations are using the same node (e.g. assume a transaction that adds both 3 and 4 to the tree shown in Figure 1). The effect of the first operation (add 3) should be propagated to the second one (add 4). To achieve that, the add operation uses the node in the write-set only as a starting point and keeps traversing the tree from this node until reaching the new node. Also, the operations lock the added nodes (3 and 4 in our case) before linking them to the tree. Those nodes are unlocked together with the other nodes at the end of the commit phase. Any interleaving transaction or structural operation running in the helper thread cannot force the transaction to abort because all the involved nodes are already locked. Also, the other cases of having dependent operations, such as adding (or removing) the same key twice and adding a key and then removing it, are solved earlier during the operation itself (as mentioned in the traversal phase).

The second point is how TxCF-Tree preserves the reduced interferences between the structural and the semantic operations without hampering the twophase locking mechanism. The main issue in this regard is that structural invalidations may not abort the transaction. Thus, a transaction cannot lock the nodes in the write-set and then validate the nodes in the read-set because, if so, in case of a structural invalidation, the invalidated operation (which can be a write operation) would continue traversing the tree and reach a new node (which is not yet locked). To solve this problem, we use an inline validation of the entries in the write-set. The write-set entries are both locked and validated at the same time. If the write operation fails in its validation: 1) it unlocks the node; 2) re-traverses the tree; 3) locks the new node; and 4) re-validates the entry.

Correctness

In this section we briefly discuss the correctness of TxCF-Tree (a detailed proof is in [START_REF] Hassan | Transactional interference-less balanced tree[END_REF]). Since we use the OTB methodology to make CF-Tree transactional, the operations of TxCF-Tree are serialized as described in [START_REF] Hassan | On developing optimistic transactional lazy set[END_REF]. The serialization point of a read-write transaction is the point right after acquiring the locks and before the (successful) validation during commit. For a read-only transaction, the serialization point is the return of its last read operation. Both those points are immediately followed by a validation procedure (Algorithm 4). If this validation succeeds, then all the transaction operations are guaranteed to be consistent.

The correctness of the mechanisms used to achieve interference-less structural operations can be inferred as follows. i) Splitting locks into structural and semantic locks does not affect correctness by any mean, because any two conflicting operations (e.g., two operations that attempt to delete the same node, or two operations that attempt to insert new nodes on the same link) acquire the same type of lock. ii) Structural invalidations are raised and handled in the same way as CF-Tree (as we show in Algorithms 1 and 3). Since we use the same approach for rotation and physical deletion (e.g., cloning the rotated down node and linking the physically deleted node to its parent), re-traversing the tree after a structural invalidation is guaranteed to be safe as in CF-Tree itself (see [START_REF] Crain | A contention-friendly binary search tree[END_REF] for the complete proof of validation in CF-Tree). iii) Semantic invalidations preserve the consistency among the operations within the same transaction. Unlike structural invalidations, in those cases, the whole transaction is aborted. iv) The inline validation during commit does not affect the correctness (although it violates two-phase locking) because every inline-validated node is locked before being validated and cannot be invalidated anymore if the validation succeeds. v) Validating the whole read-set after each operation and before committing preserves consistency in the presence of concurrent structural operations. For example, assuming the scenario where a structural operation physically removes a node that is used by a running transaction T1, which can be followed by a semantic operation (executed in another transaction T2) that adds this node in a different place of the tree. Although this new addition will not be detected by T1's validation, the expected race condition will be solved because T1 will detect during the validation (after the next operation or at commit) that the removed flag of the node has been changed (line 8 in Algorithm 3) and will continue traversing the tree. At this point, T1 will reach the same new node as T2, and they will be serialized independently from the structural operation.

Evaluation

In our experiments we compared the performance of TxCF-Tree with the performance of TB and some STM approaches. Our implementation of TB uses CF-Tree as the underlying (black-box) tree, which makes a fair comparison. Regarding STM, we tested three different algorithms: LSA [START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF]; TL2 [START_REF] Dice | Transactional locking II[END_REF]; and NOrec [START_REF] Dalessandro | NOrec: Streamlining STM by abolishing ownership records[END_REF], and, to make plots clear, we reported the best performance collected.

All experiments were conducted on a 64-core machine, which has 4 AMD Opteron (TM) Processors, each with 16 cores running at 1.4 GHz, 32 GB of RAM, and 16KB L1 data cache. Throughput is measured as the number of semantic operations (not transactions) per second to have consistent data points. However, since the benchmark executes 256 no-op instructions in between two transactions, this may result in different throughput ranges for different sizes of transactions. Each data point is the average of five runs.

In Figure 2(a) we show the results for a scenario that mimics the concurrent (non-transactional) case (i.e., each transaction executes only one operation on the tree). We leverage this plot to show the cost of adopting a transactional solution over a pure concurrent tree. Clearly STM does not scale because it "blindly" speculates on all the memory reads and writes. This poor scalability of STM is confirmed in all the experiments we made. On the other hand, both TB and TxCF-Tree scale better than STM and close to CF-Tree (TxCF-Tree is slightly closer). This behavior shows an overhead that is affordable in case one wants to use the TxCF-Tree library even for just handling the concurrency of atomic semantic operations without transactions.

Figures 2(b)-2(g) show the transactional case, in which we deployed five operations per transaction for different sizes of the tree (1K, 10K, and 100K) and different read/write workloads (10% and 50% of add/remove operations). We do not include CF-Tree because it only supports concurrent operations and thus it cannot handle the execution of transactions. TxCF-Tree performs generally better than TB. The gap between the two algorithms decreases when we increase the percentage of the write operations. This is reasonable because the conflict level becomes higher, and it best fits the more pessimistic approach (as TB).

Increasing the size of the tree also decreases the gap between TxCF-Tree and TB. At first impression it appears counterintuitive because increasing the size of the tree means generally decreasing the overall contention, which should be better for optimistic approaches like TxCF-Tree. The actual reason is that, in the case of very low contention, most of the transactions do not conflict with each other and both algorithms linearly scale. Then, when the conflict probability increases, the difference between the algorithms becomes visible. A comparison between Figure 2(e) and Figure 2(g) (which differ only for the size of the tree) confirms this claim. In Figure 2(e), both algorithms scale well up to 32 threads because threads are almost non-conflicting, then TB starts to suffers from its non-optimized design while TxCF-Tree keeps scaling. On the other hand, in Figure 2(g) both algorithms scale until 60 threads because the tree is large.

Summarizing, analyzing the above results we can identify two points that allow TxCF-Tree to outperform competitors: i) having an optimized unmonitored traversal phase that reduces false conflicts, and ii) having optimized validation/commit procedures that minimize the interferences between structural and semantic operations. Both TB and TxCF-Tree gain performance by exploiting the first point, in fact TB itself performs (up to an order of magnitude) better than STM. However, only TxCF-Tree uses an optimized design for a balanced tree data structure, and it makes its performance generally (much) better than TB. In the aforementioned experiments we use two versions of TxCF-Tree, one with the adaptive back-off time in between two helper thread iterations (named BTxCF-Tree), and one without. The results show that this optimization further enhances the performance, especially in the small tree (the cases of 10% add/remove operations). This gain may increase with a more effective heuristic.

The last experiment we report regards the capability of TxCF-Tree to reduce interferences with structural operations. Although breaking down TxCF-Tree's operations to measure this gain is not straightforward, we roughly estimated the gain by quantifying two metrics: the true interferences count, which is simply the actual transactional aborts count; and the false interferences count, which is the count of the cases in which the transaction does not abort because the tree is re-traversed instead or because the operations in TxCF-Tree acquire only one (structural or semantic) lock. In Figure 2(h) the false-interferences are 25%-30% of the total interferences for different sizes of the transactions.

Conclusions

We presented TxCF-Tree, the first interference-less transactional balanced tree. Unlike the former general approaches, it uses an optimized conflict management mechanism that reacts differently according to the type of the operation. Our experiments confirm that TxCF-Tree performs better than the general approaches.

Fig. 1 .

 1 Fig. 1. An insertion followed by a right rotation in a balanced tree.

Fig. 2 .

 2 Fig.2. Throughput with one operation (2(a)), and five operations (2(b)-2(g)) per transaction (labels indicate the size of the tree and the % of the add/remove operations). Figure2(h) shows the percentage of the two interference types using 32 threads.

Figure 2 (

 2 Fig.2. Throughput with one operation (2(a)), and five operations (2(b)-2(g)) per transaction (labels indicate the size of the tree and the % of the add/remove operations). Figure2(h) shows the percentage of the two interference types using 32 threads.

The implementation of TxCF-Tree is available at www.hyflow.org.

We assume that higher keys are in the left sub-tree to match CF-Tree's design.

Acknowledgement Authors would thank Vincent Gramoli and anonymous reviewers for the invaluable comments. This work is partially supported by Air Force Office of Scientific Research (AFOSR) under grant FA9550-14-1-0187.