Mathieu Lefebvre
email: mathieu.lefebvre@ulg.ac.be

Ferdinand M Vieider
email: vieider@gate.cnrs.fr

# Marie

Claire Villeval
email: villeval@gate.cnrs.fr

The Ratio Bias Phenomenon: Fact or Artifact?

Keywords: ratio bias, financial incentives, error rates, experiment JEL Classification: D-03, D-81, I-19

The ratio bias--according to which individuals prefer to bet on probabilities expressed as a ratio of large numbers to normatively equivalent or superior probabilities expressed as a ratio of small numbers--has recently gained momentum, with researchers especially in health economics emphasizing the policy importance of the phenomenon. Although the bias has been replicated several times, some doubts remain about its economic significance. Our two experiments show that the bias disappears once order effects are excluded, and once salient and dominant incentives are provided. This holds true for both choice and valuation tasks. Also, adding context to the decision problem does not change this outcome. No ratio bias could be found in between-subject tests either, which leads us to the conclusion that the policy relevance of the phenomenon is doubtful at best.

MOTIVATION

Echos of the importance of the ratio bias phenomenon are increasingly heard especially in health economics. [START_REF] Pinto-Prades | The Influence of the Ratio Bias Phenomenon on the Elicitation of Health States Utilities[END_REF] found that people accept less risks when health risks are represented as cases in 1000 than when they are represented as cases in 100. [START_REF] Bonner | How to Make a Risk Seem Riskier: The Ratio Bias versus Construal Level Theory[END_REF] found that risk of cancer is perceived as greater when subjects are told that "36,500 people die from cancer every year" compared to when they are told that "100 people die from cancer every day", and that the ratio bias thus overwhelms the immediacy effect of using days instead of years [START_REF] Trope | Temporal Construal[END_REF]. Even worse, [START_REF] Yamagishi | When a 12.86% mortality is more dangerous than 24.14%: Implications for Risk Communication[END_REF] found that cancer was perceived as riskier when described as killing 1,286 out of 10,000 people than when described as killing 24.14 out of 100 people. If the ratio bias is indeed as strong as these claims suggest, it may have important implications for policy design, since risks communicated depend on the time-frame in which they are expressed.

People are said to incur into ratio bias whenever they prefer to bet on prospects expressed as a ratio of large numbers to betting on normatively equivalent or superior prospects expressed as a ratio of small numbers (e.g. they prefer betting on 10 red balls in an urn with 100 balls rather than on one red ball in an urn with 10 balls). [START_REF] Miller | When a Coincidence is Suspicious: The Role of Mental Simulation[END_REF] first showed how a given event seems more suspicious to people when it results from a low number of occurrences than when it results from a high number of occurrences, keeping probabilities constant. [START_REF] Kirkpatrick | Cognitive-Experiential Self-Theory and Subjective Probability: Further Evidence for Two Conceptual Systems[END_REF] replicated this finding for preferences between prospects with equal probability expressed with different ratios. [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF] showed that people are not only ready to pay for their preference for the urn with the higher absolute number of balls, but they keep committing the bias even when they are explicitly told the probabilities involved in the different choices (see also [START_REF] Pacini | The Relation of Rational and Experiential Information Processing Styles to Personality, Basic Beliefs, and the Ratio-Bias Phenomenon[END_REF].

If one were to accept this evidence, the ratio bias phenomenon would deserve a place in a long list of cognitive biases that have shed doubt on the existence of the perfectly rational homo oeconomicus of traditional economic models. In particular, decision makers have been found to reverse their preferences between choice and pricing tasks [START_REF] Lichtenstein | Reversals of Preference Between Bids and Choices in Gambling Decisions[END_REF][START_REF] Tversky | Preference Reversals[END_REF], to shy away from unknown probabilities when normatively equivalent known probabilities are available [START_REF] Chow | Comparative Ignorance and the Ellsberg Paradox[END_REF]Ellsberg, 1961;[START_REF] Kocher | Selection in Markets for Risky and Ambiguous Prospects[END_REF], to be unduly influenced by preexisting situations [START_REF] Eisenberger | Willingness-to-Pay and Willingness-to-Accept for Risky and Ambiguous Lotteries[END_REF][START_REF] Kahneman | Anomalies: The Endowment Effect, Loss Aversion, and Status Quo Bias[END_REF][START_REF] Roca | Ambiguity Seeking as a Result of the Status Quo Bias[END_REF], and many more. Even in this long list of rationality failures, the ratio bias phenomenon seems particularly troubling. Its disconcerting nature from the point of view of economic rationality rests in the observation that it does not rely on any level of cognitive complexity-an inferior probability prospect is chosen over one offering a better probability of winning in plain knowledge of the probabilities involved. There is neither an issue of obviously missing information as in ambiguity aversion (Einhorn and Hogarth, 1985;[START_REF] Frisch | Ambiguity and Rationality[END_REF][START_REF] Trautmann | Causes of Ambiguity Aversion: Known Versus Unknown Preferences[END_REF], nor any complexities as may be involved in pricing versus simple choice tasks which have been used to explain preference reversals [START_REF] Schmidt | Explaining Preference Reversal with Third-Generation Prospect Theory[END_REF].

However, the economic stability of the ratio bias has not yet been established and it is thus premature to derive policy recommendations from the experimental findings cited above. Indeed, several aspects of existing experimental manipulations appear unconvincing from an experimental economist's point of view, and could be driving at least part of the results. First, experiments are usually conducted without salient and dominant financial incentives [START_REF] Camerer | The Effects of Financial Incentives in Experiments: A Review and Capital-Labor-Production Framework[END_REF]Smith, 1982). While sometimes incentives have been provided, they are very small, with differences in expected values between the superior and inferior prospects generally below $0.05. Second, subjects are often explicitly told to follow their gut feeling (e.g. [START_REF] Denes-Raj | The Generality of the Ratio-Bias Phenomenon[END_REF][START_REF] Kirkpatrick | Cognitive-Experiential Self-Theory and Subjective Probability: Further Evidence for Two Conceptual Systems[END_REF], and experiments are generally conducted individually, involving direct observation of the decision by the experimenter. This seems apt to introduce an experimenter demand effect by making it clear to subjects what is expected of them [START_REF] Greenwald | Within-Subject Designs: To Use or Not to Use[END_REF][START_REF] Minor | Experimenter-Expectancy Effect as a Function of Evaluation Apprehension[END_REF][START_REF] Sawyer | Demand Artifacts in Laboratory Experiments in Consumer Research[END_REF]. Since monetary incentives are generally absent or low, there is no significant cost of conforming to the experimenter's view.

Third, psychology students are generally used for the tests. Since psychology students are used to participating in many experiments as part of their course requirements, and since deception is routinely used in these experiments, they may be particularly prone to fall prey to experimenter demand effects [START_REF] Hertwig | Experimental Practices in Economics: A 6 Methodological Challenge for Psychologists?[END_REF].

Last, typical experiments do not control for potential error rates or noise in the observations, and may thus overestimate the ratio bias effect. In typical ratio bias experiments, the urn with the larger number of balls is always inferior or equal in probability, while there is no control for cases in which the large urn is superior. Not controlling for error rates, [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF] find that between 61% and 54% of subjects choose the large urn when the latter offers a probability of 9/100 against a 1/10 probability of the small urn. Dale et al. (2007) include a control for error rates.

They find that while about 41% of choices indicate a ratio bias, there are also 25% of choices which are suboptimal in the opposite direction, thus indicating an extremely high noise rate.

In this paper we test the economic stability and relevance of the ratio bias phenomenon. In order to do this, we carried out several experiments. In experiment 1 we implement a design adapted from [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF], but we introduce some first attempts at debiasing by introducing monetary prizes for some subjects and by trying to prevent potential demand effects.

Experiment 2 introduces financial incentives of varying sizes for all subjects, and explicitly controls for error rates. Also, we test the bias with choice tasks as well as with valuation tasks. Moreover we compare decisions made in neutral tasks and in contextualized frameworks. Finally, we test for occurrence of ratio bias both within-and between-subject. The latter approach in particular may be important to ascertain the policy relevance of the phenomenon, since risks are generally communicated in only one way, and not comparatively in two different formats as has been done in existing experiments. Experiment 1 finds results that are qualitatively similar to the ones reported in the psychology literature, with a persistent ratio bias. However, the rates of bias are reduced substantially compared to the ones found in earlier experiments. Experiment 2 tries to replicate this result with deterministic incentives, as well as introducing randomization in the sequence of choice pairs. Choices of the large urn are significantly reduced in this setting. Furthermore, controlling for errors shows that the remaining occurrences of the ratio bias can be attributed exclusively to the presence of large levels of noise. We thus conclude that the ratio bias is an artifact due to methodological flaws present in the existing literature.

The remainder of this paper is organized as follows. Section 2 presents the design and the results of our experiment 1. Section 3 introduces the protocol and the results of experimetn 2. Section 4 concludes.

EXPERIMENT 1: TESTING FOR ECONOMIC SIGNIFICANCE

This experiment was conducted to establish whether the ratio bias is economically significant-that is, whether the bias still occurs when decisions are made for real money or whether it is merely an artifact deriving from demand effects or issues in information presentation. While the ratio bias has been tested with monetary incentives before, we argue that such incentives were not large enough to fulfill the precepts of salience and dominance. [START_REF] Kirkpatrick | Cognitive-Experiential Self-Theory and Subjective Probability: Further Evidence for Two Conceptual Systems[END_REF] used a prize of $1.

Denes-Raj and Epstein (1994) offered a prize of $5 in their high stakes condition in experiment 2, with differences in expected value between the two urns at or below 5¢. Dale et al. (2007) used monetary prizes of 5¢ or 10¢. In order to test for the effect of such incentives, we compare a hypothetical treatment to a treatment in which financial incentives are provided. We propose to use a large prize to make the decision economically significant for subjects. Also, we want to avoid a potential demand effect that may have occurred in previous experiments. In order to achieve this, we go through some lengths to assure subjects of the confidentiality of their decisions.

Experimental design

Subjects: 166 subjects were recruited from a list of volunteers at Erasmus University Rotterdam, the Netherlands. Subjects were run in groups of approximately 15 people. These groups were randomly assigned to either the hypothetical condition (N=86) or the real-stakes condition (N=80). The average age of the subjects was 21.8 years, and 58% were male. All subjects were paid a flat fee of €15 ($23) to carry out the task described below in addition to several other, unrelated, tasks. No additional earning possibilities were mentioned in the recruitment process in order to avoid a possible selection bias into the real-incentive treatment.

Incentive manipulation: In the hypothetical treatment, subjects were paid the participation fee and dismissed once they had completed the questionnaire. In the real incentives treatment, 1 out of every 5 subjects additionally played for real money. The prize to be won was €80. Monetary incentives were implemented using a random incentive mechanism [START_REF] Abdellaoui | Combining Bayesian Beliefs and Willingness to Bet to Analyze Attitudes towards Uncertainty[END_REF][START_REF] Harrison | Estimating Individual Discount Rates in Denmark: A Field Experiment[END_REF][START_REF] Holt | Risk Aversion and Incentive Effects[END_REF][START_REF] Myagkov | Exchange Economies and Loss Exposure: Experiments Exploring Prospect Theory and Competitive Equilibria in Market Environments[END_REF]. One of the tasks was randomly selected for real play. Since other tasks not described in this paper were also included in the random extraction mechanism, the probability of having at least one ratio bias task extracted was 1/3 conditional on being selected for real play. The 8 answers had then the same probability of being extracted.

We wanted subjects to feel as unobserved as possible in order to avoid potential demand effects. To assure them of their anonymity, subjects in the real payoff condition obtained a randomly generated number that was associated to their questionnaire. 20% of these numbers were then extracted, and the choices indicated on the corresponding questionnaire were played for real money. Subjects could then later pick up their winnings by presenting their number to a secretary on a different floor. This procedure guarantees that subjects remain anonymous and thus avoids also the introduction of additional confounds [START_REF] Vieider | Separating Real Incentives and Accountability[END_REF].

Task: Subjects were presented with eight choices between two urns containing 10 and 100 balls respectively. The small urn was kept constant at one red (winning) ball out of 10. The composition of the large urn was varied so as to provide increasingly worse probabilities of winning, from 10, 9, 8,...,3 winning balls out of 100. These choices were presented sequentially on the same page, in a design adapted from the one used by [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF]. The large urn was always placed below the small urn (see appendix A). In addition to these choice tasks, subjects were asked to indicate their willingness to pay (WTP) for the equal probability urns only. This WTP questions was not incentivized.

Hypotheses. We hypothesized that a ratio bias would be observed in the choices. This hypothesis implies that for the equal probability urns choices of the large urn would be significantly greater than 50% (randomization). For cases in which the large urn is inferior, any choices of the large urn can be interpreted as ratio bias. However, we formally test for the null hypothesis that the choice frequency of the normatively inferior large urn is greater than a 5% error rate.1 Also, we hypothesized that subjects would be willing to pay significantly more for the large urn than for the small urn when the two urns offer equal probabilities of winning.

Results

We first look at the case in which the two urns provide equal probabilities of winning aggregating across the incentive conditions. The hypothesis that people randomize between the two urns when they offer equal probabilities of winning is strongly rejected (p < 0.001, binomial test).2 Indeed, 68% of subjects choose the large urn when the two urns offer the same probability of winning.

Though WTP was found to be somewhat higher for the large as compared to the small urn (€5.66 versus €5.24), the effect fails to reach significance (t(165) = 0.83, p = 0.389).

As one might expect, the choice proportion of the large urn is strongly reduced when the probability of winning in the large urn is progressively reduced, as can be seen in Figure 1.

However, 23% of subjects still choose the large urn when the probability of winning is reduced to 9/100. The number of people choosing the inferior large urn is then progressively reduced for worse probabilities of winning with the large urn, but dives under 10% only once the large urn offers a probability of winning that is 5% smaller than the one in the small urn. The hypothesis that the choice of the inferior large urn is equal to a 5% error rate is rejected for all but the last two urns in the series of 8, which offer probabilities of winning that are inferior by 7% and 8% than the one offered by the small urn respectively. While these numbers appear large at first sight, they are substantially smaller than choices of the inferior large urn previously observed in the psychology literature. Comparing the findings to the ones in [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF], we find that only the choice pattern for the two equal probability urns is roughly comparable. Indeed, Denes-Raj and Epstein find that 61% and 54% (in their experiments 1 and 2 respectively) choose the inferior large urn when the probability of the latter is lowered to 9/100. 23% and 34% still choose the large urn when the latter offers a probability of winning of 5/100, which is 5% lower than in the small urn. The choice frequencies they find for the inferior urn are thus substantially larger than the one we find in this experiment, running at 23% for 9/100 and 9% for 5/100. The question of whether the effect is economically significant remains to be answered. We thus proceed to testing whether the provision of economic incentives makes a difference. Figure 1 shows choice proportions for the large urn by probability of winning that is foregone by that choice.

At first sight, incentives seem to increase the ratio bias for all but the largest probability differences.

To test whether this difference is significant, we estimate random-effects Probit models on the eight sequential choices that were presented to the subjects. The random-effects model is justified by the fact that each subject makes repeated decisions. The dependent variable is the choice of the large urn. The independent variables include a dummy variable for the incentive treatment and the difference in probability of winning between the two urns, They also include demographic variables controlling for gender and age. We estimate four models separately. As can be seen from the results reported in Table 1, incentives do not have a significant effect. As one might expect, the difference in probability of winning between the two urns exerts a strong influence on choices. There is also a strong gender effect, while age exerts no significant effect-which is hardly surprising, given the low variability of age in the subject population.

Discussion

With 23% of choices of the large, inferior urn, when the latter offers a probability of winning of 9/100 against the 1/10 of the small urn, we do indeed find a ratio bias. However, this bias appears to be much weaker than its occurrences previously observed in the literature. Indeed, [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF] found between 61% and 54% of choices of the large inferior urn for the same probability, and Dale et al. (2007) found about 42% of choices of the large urn for the same probability difference. Incentives are not effective at further reducing the bias found. It thus seems that the weakening of the bias stems from the measures put into place to avoid experimenter demand effects.

One potential criticism is however that incentives provided were too low to make the decisions seem important to the subjects. Although the nominal prize was high, the probability of extraction of any single choice in the ratio bias task was only 1/120. While no difference between random incentives and deterministic incentives has generally been found in the literature [START_REF] Hey | Do Subjects Separate (or Are They Sophisticated)?[END_REF][START_REF] Lee | The Effect of the Background Risk in a Simple Chance Improving Decision Model[END_REF][START_REF] Starmer | Does the Random-Lottery Incentive System Elicit True Preferences? An Experimental Investigation[END_REF], the probability of extraction in this task was indeed extremely low, and certainly outside the range for which effects of random incentives have been tested. Also, the combination of random extraction of one subject, random extraction of one out of three tasks, and random extraction of one choice within that task may have created a feeling of irrelevance.

A second criticism that can be brought against the results presented above is that error was not explicitly controlled for. While it is true that choices for the inferior urn for the smallest probability difference of 1% are still hovering around 23%, it is not unthinkable that a large proportion of these choices were due to noise and that the relevance of the ratio bias phenomenon is thus much lower than a first look at the data would suggest. Indeed, Dale et al. (2007) found error rates that are very similar to the occurrence of the bias in our experiment, even though they still found a significant ratio bias in excess of those errors. Admittedly, the employment of a 5% error rate against which to test the occurrence of the bias used above is utterly arbitrary and will be dealt with in experiment 2.

A number of other criticisms can be brought against the design. Indeed, one could argue that the sequential presentation of the choices in a fixed order induces some coherence effect by which subjects who have chosen the large urn when the two urns were probabilistically equivalent are more likely to stick with the choice of the large urn. Another potential criticism is that the bias persists due to the artificiality of the laboratory task. Indeed, context has sometimes been shown to improve rationality [START_REF] Griggs | The Effects of Rule Clarification, Decision Justification, and Selection Instruction on Wason's Abstract Selection Task[END_REF], though the existing evidence on the ratio bias seems to rather point in the direction of an accentuation of irrationality when context is added [START_REF] Pinto-Prades | The Influence of the Ratio Bias Phenomenon on the Elicitation of Health States Utilities[END_REF][START_REF] Yamagishi | When a 12.86% mortality is more dangerous than 24.14%: Implications for Risk Communication[END_REF]. Since however no incentives were provided in previous experiments, nothing can be said about their economic significance.

EXPERIMENT 2: CONTROLLING FOR ERROR AND UNIVERSAL INCENTIVES

Experiment 2 tries to obviate to the potential criticisms described above in several ways. First of all, we introduce deterministic incentives whereby every subject plays for real money. Second, we introduce some control choices in which the large urn is superior, which enables us to explicitly control for the error rate. Dale et al. (2007) control for error rates and still find a significant ratio bias. However, the incentives they provide are in the order of 5¢-10¢, which implies a negligible difference in expected value between the two urns. By making incentives more salient, we want to test whether the phenomenon is indeed stable. We thus use two stake levels, regular stakes which are already superior to the stakes found in previous experiments on the ratio bias, and a treatment in which stakes were increased by a factor of 10.

In addition, we try to minimize experimenter demand effects by reassuring subjects of their anonymity and by randomizing both the order in which choices appear as well as the position in which the options are presented within one choice (i.e. whether the small urn is located above or below the large one). Furthermore, we use both certainty equivalent (CE) and pricing tasks in addition to choices and we introduce context into some decision problems to test the robustness of the ratio bias to the nature of tasks. Last, we implement both a between-subject design and a withinsubject design to investigate the potential policy relevance of the ratio bias phenomenon.

Experimental design: General remarks

Subjects. The experiment has been conducted at GATE (Groupe d'Analyse et de Théorie Economique), at the University of Lyon, France. 78 undergraduate students from the local engineering and business schools were recruited using the ORSEE software developed by [START_REF] Greiner | An Online Recruitment System for Economic Experiments[END_REF]. 64% of subjects were female, the average age was 22. Sessions were conducted in the computer laboratory in groups of 20 subjects. In one High-Stakes session only 19 subjects showed up. One more subject in the High-Stakes condition had to be sent away because of technical issues with the computer station. We thus ended up with 40 subjects in the Low-Stakes condition and 38 subjects in the High-Stakes condition.

Structure. Several tasks were used to explore the ratio bias phenomenon. In addition to choice tasks similar to the ones used in experiment one, we also used investment and insurance tasks, as well as a context-free task in which certainty equivalents were elicited. Also, we elicited values both within and between subject to test for policy relevance of the issues discussed. The three types of choices are discussed separately below. Subjects were reassured about their anonymity, and all instructions were provided on the computer screen (see Appendices). Finally, differently from Dale et al. (2007) and [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF], but similarly to our experiment 1, urns were not visually displayed. This difference seems however not to be crucial, given that studies without visualization have also found a large ratio bias [START_REF] Bonner | How to Make a Risk Seem Riskier: The Ratio Bias versus Construal Level Theory[END_REF][START_REF] Pinto-Prades | The Influence of the Ratio Bias Phenomenon on the Elicitation of Health States Utilities[END_REF][START_REF] Yamagishi | When a 12.86% mortality is more dangerous than 24.14%: Implications for Risk Communication[END_REF].

The experiment was conducted using the REGATE software [START_REF] Zeiliger | A Presentation of Regate, Internet Based Software for Experimental Economics[END_REF]. Subjects were given a show-up fee of €5 ($7). Average earnings were €23.62 ($35) for an experiment that lasted less than 30 minutes. 1 4

Choice tasks

Task. The task consisted in repeated choices between lotteries. Subjects made 25 choices in total.

The choice pairs were designed in such a way as to allow us to control for error, as well as to explore potential drivers of the ratio bias phenomenon. Both the order of the choice pairs and the location of the large versus small urn on the screen (above versus below) were randomized for each subject. Each choice pair involved a choice between one large urn and one small urn. 3 choice pairs provided the same probability for the large and small urn; 18 choice pairs provided a better probability of winning in the small urn than in the large urn; and 4 choice pairs provided a worse probability of winning in the small urn than in the large urn to control for random errors. A list of the choice pairs used is provided in Appendix B, together with a screenshot of the choice setting subjects faced on the computer.

Incentives. Incentives were varied randomly within subject between a prize of €2, €7, and €12 ($3, $10, and $18) for half the subjects. The other half was assigned to the High-Stakes condition, in which the prize was varied randomly between €20, €70, and €120 ($30, $100, and $180). For one choice pair, the prize was kept fixed at €4 and €40 in the two conditions. This was done to insure comparability with the comparative investment task described below-since no interesting results emerged from this comparison, it will not be mentioned further. This randomly extracted prize as well as the descriptions of the two urns were displayed prominently on the screen for each decision.

Every subject played one of the 25 choices for real money, with each choice having the same probability of being played for real. The random draw for this choice task (as well of the random draws for the following tasks) was operated at the very end of the session so that its outcome could not influence further choices.

Hypotheses. We hypothesize that the proportion of choices for the large urn when the latter provides the same probability as the small urn is significantly greater than 50%. Also, we hypothesize that the choice frequency of the large urn is significantly greater than the error rate (that is, the proportion of choices for the large urn when the latter provides probabilities of winning that are inferior to the ones provided by the small urn is significantly higher than the number of choices of the small urn providing inferior probabilities of winning). We also want to test whether varying incentives within subjects produces significant differences in behavior. Finally, we were interested if the ratio bias phenomenon may be reduced with very high stakes varied between subjects.

Results. General choice patterns are summarized in Figure 2 separately for the Low-and High-Stakes conditions. Overall, the large urn was chosen only 47% of the time when offering the same probability of winning as the small urn. We thus cannot reject the null hypothesis that in cases of equal probability the large urn will be chosen 50% of the time (p = 0.33, binomial test). When the large urn is inferior, it is chosen on average 7.19% of the time. The ratio bias in this experiment is thus much smaller than the one observed in experiment one. Looking now at the error rate, we see that the small urn is chosen on average 9.61% of the time when it is inferior. We can thus not reject the hypothesis that the frequency of choices consistent with a ratio bias explanation is the same as the error rate (t(77) = -0.47, p = 0.64). We next look at the influence of within-subject stake variations, between-subject stake variations, and several other potential explanatory variables. We have estimated the determinants of the probability of choice of the large urn by means of four random-effects Probit models. The independent variables include the normalized prize that captures the within-subject variation of stakes, and a dummy variable indicating the High-Stakes condition. We also include a dummy variable ('large urn superior') indicating the choice pairs in which the large urn is superior, used to control for error, and another dulmmy variable ('equal probability') indicating that the two choices offered the same probability of winning. We also control for the probability difference between the two urns, calculated as the probability of winning with the small urn minus the probability of winning with the large urn. In the last regression, we include demographic variables. Table 2 reports the results of these regressions. Table 2 shows that neither the within-subject variation in prizes (normalized across stakes conditions) nor the between-subject stake variation have any significant effect on decisions. As expected, when the large urn is superior subjects are significantly more likely to choose it than when it is inferior. In contrast, when the two urns provide an equal winning probability people are less likely to choose it than when it is inferior. The difference in the probability of winning exerts no further influence. Gender is no longer significant.

Discussion. At first sight, there seems to be a small ratio bias, even though it stays below 10% on average. Controlling however for error rates, these regressions show that these choices are entirely due to error or noise, inasmuch as there is no systematic preference pattern for the larger urn. This result remains stable across different stake levels, both within-and between-subject. The latter finding can be explained by the fact that choices of the large urn are already substantially reduced in the Small-Stakes condition. Indeed, providing stakes of €7 ($10) on average to every participant combined with randomization and confidentiality of choices seems already to be sufficient to eliminate the bias. Given that choices of the inferior urn are already very low in the baseline condition, multiplying the stakes by a factor of 10 has no further effects.

Since some of the recent claims on the importance of the ratio bias phenomenon have been obtained through rating tasks rather then choices, we next examine comparative evaluations.

Comparative valuation tasks: Adding context

Employing comparative rating tasks rather than choice tasks generally adds context in addition to the different elicitation method used. Health economics issues generally studied however have the disadvantage of not easily allowing for the introduction of real incentives. We thus propose to use an investment task to add context whilst being able to implement the value elicitation in an incentive compatible way. In addition to the investment task, we also use an insurance task to test whether negative outcomes may be more prone to ratio bias than positive outcomes. While using losses has been found to produce less ratio bias than gains in choice tasks [START_REF] Denes-Raj | Conflict Between Intuitive and Rational Processing: When People Behave Against Thir Better Judgment[END_REF][START_REF] Kirkpatrick | Cognitive-Experiential Self-Theory and Subjective Probability: Further Evidence for Two Conceptual Systems[END_REF], the risk rating tasks used in the health economics literature do generally involve losses and have found a very large ratio bias [START_REF] Bonner | How to Make a Risk Seem Riskier: The Ratio Bias versus Construal Level Theory[END_REF][START_REF] Pinto-Prades | The Influence of the Ratio Bias Phenomenon on the Elicitation of Health States Utilities[END_REF][START_REF] Yamagishi | When a 12.86% mortality is more dangerous than 24.14%: Implications for Risk Communication[END_REF].

Tasks. In the investment task, subjects were presented with two investment projects, project A and project B. The two projects were displayed on the same screen, and choices had to be made between investing increasing amounts in each one of the investment projects and not investing (choice lists in Appendix C). Project A offered a probability of success of 7/100, and project B of 61/1000. In 1 9 the insurance task, subjects were offered to buy insurance against a low probability loss of their €5 ($7) show-up fee (see Appendix C). The risks in the insurance task were 59/1000 and 423/10000 respectively.

Incentives. Both tasks described above were played for real money. For the investment task, subjects were given an initial endowment of €0.60 (90¢) in the Low-Stakes condition, and €6 ($9) in the High-Stakes condition. The prize to be won in the two investment tasks was of €4 ($6) in the Low-Stakes condition and €40 ($60) in the High-Stakes condition. In the insurance task, the amount to be lost was not varied and stayed fixed at the show-up fee of €5 ($7). For either task, at the end of the session one of the two investment projects or insurance scenarios would first be randomly selected for real play. Then one of the decisions would be selected and played for real. In the investment task, if a subject had decided not to invest for the selected line, she could keep her endowment and the game was over. If she had selected to invest, the investment amount was subtracted from the endowment and the prospect was played out. An analogous procedure was used for the insurance task.

Hypotheses. The two investment projects and insurance scenarios are characterized by different probabilities, as well as being represented with small versus large ratios. We thus hypothesize that the difference that subjects are willing to pay over the expected value of the investment (or the expected loss in the insurance case) will be larger for the large ratio than for the small ratio.

Results. Five subjects in the investment task and two subjects in the insurance task were excluded from the analysis because they switched multiple times between the certain amount and the prospect for at least one of the two investment projects; therefore it was impossible to calculate the 0 willingness-to-pay for these subjects. Since probabilities differ in the two investment opportunities, a test for equality of amount invested is not adequate. We thus calculate the difference between the highest amount subjects are willing to invest in each project and the expected value of the investment, and test for equality of this premium. The mean values of the premia are reported in Table 3 separately for low and high stakes. No High-Stakes condition existed in the comparative insurance task; all subjects played for the show-up fee of €5 ($7). Table 3 also reports the mean amount subjects are willing to pay for the insurance in excess of the expected value of the loss. While the excess premia appear to be much lower in the High-Stakes than in the Low-Stakes condition, we cannot reject the null hypothesis that the two premia are the same in the Low-Stakes condition (t(39) = 0.58, p = 0.56). For the High-Stakes condition, we find a marginally significant difference between the two premia (t(32) = -1.99, p = 0.06). Notice however that this effect goes in the opposite direction of the one predicted by the ratio bias hypothesis. In the insurance task, testing the null hypothesis that the premium paid over the expected value of the loss is equal in the two scenarios, we reject that hypothesis in favor of the one that the premium is higher for the larger ratio (t(78) = 2.08, p = 0.04). This would lead us to conclude that ratio bias does indeed occur. Before we jump to such a conclusion, it is however instructive to take a closer look at the data. For scenario A, 39 subjects out of 76 (51.32%) never switch between the sure amount and the prospect, with an 1 overwhelming majority of those who never switch (33/39) willing to buy insurance at any amount it was offered at (and the remaining 6 never willing to buy insurance). A similar finding holds for scenario B, in which 41 out of 76 subjects (53.95%) never switch. Again, an overwhelming majority of subjects who never switch (33/41) are willing to take out insurance at any cost it was offered at.

The results of the previously reported t-test thus seems to be due to a ceiling effect in the prices at which insurance was offered. Indeed, we cannot reject the hypothesis that the number of subjects who never switch is the same for scenarios A and B (t(73) = -1.0, p = 0.32). Given that the expected value is lower for scenario B, these subjects are likely to drive the results. Carrying out the same test as above only for subjects that do switch and are thus not at the margin, we accept the null hypothesis that no ratio bias exists (t(29) = 0.48, p = 0.64).

Discussion. We find no ratio bias when we add context to the decisions, and when decisions consist in comparative pricing tasks instead of straight choice tasks. A ratio bias is found neither for gains nor for losses. However, in the insurance task we lose some power due to the ceiling effects described above. Indeed, due to the choice list employed for the elicitation of the willingness-to-pay for insurance, the maximum willingness-to-pay that could be stated was about 3-4 times the expected value of the loss, depending on the scenario. Quite a few subjects were willing to pay more than that amount to buy insurance. This finding is consistent with findings in the literature on strong loss aversion [START_REF] Kahneman | Prospect Theory: An Analysis of Decision under Risk[END_REF][START_REF] Köbberling | An Index of Loss Aversion[END_REF][START_REF] Schmidt | What is Loss Aversion?[END_REF] and the excessive uptake of insurance [START_REF] Hogarth | Risk, Ambiguity and Insurance[END_REF].

In addition, we find the typical pattern of risk seeking for small probability gains. Subjects are on average willing to invest an amount in excess of the expected value of the prospect in the investment task. This finding is consistent with the evidence presented in the literature on probability weighting, and in particular with overweighting of small probabilities [START_REF] Abdellaoui | Parameter-Free Elicitation of Utility and Probability Weighting Functions[END_REF][START_REF] Bleichrodt | A Parameter-Free Elicitation of the Probability Weighting Function in Medical Decision Analysis[END_REF][START_REF] Tversky | Advances in Prospect Theory: Cumulative Representation of Uncertainty[END_REF][START_REF] Wu | Curvature of the Probability Weighting Function[END_REF]. Also, this risk seeking behavior seems to be reduced in the High-Stakes condition, which is also consistent with previous findings in the literature [START_REF] Battalio | Testing Between Alternative Models of Choice under Uncertainty[END_REF][START_REF] Holt | Risk Aversion and Incentive Effects[END_REF]. Since this finding has however wider implications, it is described in a separate paper in order not unduly complicate the exposition [START_REF] Lefebvre | A Note on the Effect of Between Subject Stake Variations on Risk Attitude[END_REF].

At this point, there is still one objection that can be raised to our analysis. Indeed, while all existing studies on the ratio bias employ either choice or rating tasks -and hence a strictly comparative setting -the potential policy relevance of the phenomenon may derive from the fact that probabilities represented as large ratios are overestimated more than equivalent small-ratio probabilities when considered in isolation. We thus next examine results on between-subject tests of the ratio bias phenomenon.

Between-subject data: Policy relevance

Recent results on the ratio bias phenomenon especially in the medical domain have been used to draw conclusions on the importance of the phenomenon for risk communication and policy issues.

While we have not been able to replicate the ratio bias phenomenon in the experiments presented above, for risk communication and policy issues it would arguably be more important to know whether such a bias in risk evaluation might exist when only one way of communicating the risk is used at a time. Indeed, in reality risk is generally communicated just in one way, and it seems thus crucial to know whether a ratio bias is observed between subjects before proceeding to policy recommendations. To our best knowledge, this issue has never been addressed before. We thus introduced some between-subject rating tasks at the outset of the experiment before any comparative tasks were introduced in order to test for this hypothesis. We also added context in some of them, to see if such context may make a difference. Details are reported below.

Tasks. Three different tasks were introduced in a between-subject design in order to test for a between-subject ratio bias phenomenon. Each subject saw one of three ratios in the description of the problem. We used three ratios instead of two to create more variance. The assignment of the ratio was randomly and independently determined for each subject and for each one of the three tasks (ratios are reported in Table 4). Task one (the neutral task) consisted in repeated choices between an increasing certain amount of money and a prospect offering the opportunity to win a prize. The second task (the insurance task) offered the opportunity to buy insurance against the possibility of losing the prize won in the neutral task. It was to be played out for real money at the end of the session only in case a subject had won the prize in task one. In task three (the investment task), subjects were asked to choose for subsequent amounts whether they would rather keep the amount or invest it. Incentives. The neutral task was to be played out for real money, offering a prize of €10 ($15) in the Low-Stakes condition and €100 ($150) in the High-Stakes condition. Subjects were asked to choose between a sure amount (certainty equivalent,) and playing the prospect for increasing certain amounts (see Appendix D). One line would be selected for real play at the end of the session, and the subject would either be paid the sure amount or play the prospect according to her choice for that line. In the investment tasks, subjects were initially endowed with €0.60 (90¢) in the Low-Stakes condition and €6 ($9) in the High-Stakes condition. They were asked whether they were willing to invest increasing amounts of their endowment, with a potential return of €4 ($6) in the Low-Stakes condition and €40 ($60) in the High-Stakes condition. One choice was then selected through a procedure analogous to the one used in the neutral task, except that if they had chosen to invest, the corresponding amount was now subtracted from their endowment before playing the prospect. The insurance task was to be played out conditional on a subject having won the prize in the neutral task only. A procedure analogous to the one in the investment task was then used to determine payoffs (all choice lists can be found in Appendix D).

Hypotheses. We hypothesize that subjects have a higher certainty equivalent the larger the urn in the neutral task, since probabilities are equal in those tasks. For the insurance task, we hypothesize that subjects are ready to pay a higher amount in excess of the expected value of the loss (probabilities are now different) as we pass from representations per day to month and year. Analogously, we hypothesize that for the investment task subjects are willing to invest more in excess of the expected value as we move to larger ratios.

Results. In the neutral task, six subjects were dropped because they switched multiple times. All of these subjects were in the High-Stakes condition. We dropped for the same reason two subjects in the insurance task and six subjects in the investment task. Table 5 displays the mean valuation of the subjects in each task and for each ratio. Running an Anova on the certainty equivalents for the three different ratios in the neutral task, no significant difference is found (F(2,69) = 0.63, p = 0.54). The null hypothesis of equal certainty equivalents for different ratios can thus not be rejected. No significant difference is found if the same Anova is run separately for the Low-and the High-Stakes conditions, although we again find a reduction in risk seeking for high stakes.

In the insurance task, since probabilities of losing are now different we calculate the excess premium that subjects are willing to pay over the expected value of the loss for each ratio, and run an Anova on these derived values. In the Low-Stakes condition, there is a marginally significant effect indicating a ratio bias (F(2,37) = 2.83, p = 0.07). This effect is however not significant in the High-Stakes condition (F(2,33) = 2.27, p = 0.12). Also, a closer look at the data reveals that the result is mostly driven by a substantial amount of subjects (37/76 or 48.68%) who never switch, and who are equally distributed across the different ratios. All but one of these subjects choose to insure at any price the insurance is offered at. Once those subjects are eliminated, no significant differences persists between the excess premia paid for the different urns. In the investment task, since probabilities of success are again different for the different ratios, we calculated the excess investment premium over expected value that subjects were willing to pay for each ratio. Running an Anova on this index for the Low-Stakes condition, we find a significant difference (F(2,35) = 3.28, p = 0.05), indicating the presence of ratio bias. Running the same Anova for the High-Stakes condition, the difference is no longer significant (F(2, 31) = 0.93, p = 0.41).

Discussion. In general, we detect no ratio bias in the three between-subject tasks described in this section. Although at first glance there seems to be a marginally significant effect in the insurance setting, closer inspection of the data reveals that this finding is driven entirely by a ceiling effect on amounts that can be selected for insurance. This ceiling effect seems to derive from extreme loss aversion that is summed to the overweighting of small probabilities as discussed for the comparative insurance task above. Also, while there is some evidence for the ratio bias phenomenon in the investment task for small stakes, this effect is no longer present for large stakes.

We thus conclude that the alleged policy relevance of the ratio bias phenomenon is doubtful at best.

CONCLUSION

From the experiments conducted, it results clearly that the ratio bias that has been observed in choice tasks in the literature results from a combination of the failure to control for error, the presence of experimenter demand effects, and the absence of salient and dominant incentives.

Indeed, by reducing the possibility of demand effects in experiment 1 we observe a frequency of ratio bias that is greatly reduced as compared to previous studies. Introducing significant incentives for everybody, further reducing the possibility of demand effects, and controlling for errors causes the ratio bias to disappear in experiment 2. This finding is robust even when context is added to the decision problem, and for gain as well as loss formulations. Finally, no ratio bias is found systematically in between-subject tests either, with only some evidence in the investment task that does not resist an increase in monetary stakes. These results cast serious doubts on claims about the policy relevance of the ratio bias phenomenon.

Figure 1 :

 1 Figure 1: Choices of the normatively inferior large urn for decreasing probabilities of winning.

Figure 2 :

 2 Figure 2: Percentage of choices of the large urn by difference in the probability of winning for the Low-and the High-Stakes conditions

Table 1 :

 1 Determinant of choice of the large urn in experiment 1 (random-effects Probit models)

		I	II	III	IV
	Incentives	0.173 [0.038]	0.319 [0.013]	.293 [.011]	0.295 [0.011]
		(0.155)	(0.283)	(.280)	(.279)
	Difference in	-68.107 [-2.633]***	-69.221 [-2.502]***	-69.267 [-2.498]***
	winning		(4.920)	(5.187)	(5.192)
	probability
	Male			-.990 [-.049]***	-1.012 [-0.050]***
				(.287)	(0.288)
	Age				0.037 [0.001]
					(.046)
	Constant	-1.184***	0.069	0.668*	-0.121
		(0.112)	(0.212)	(0.275)	(1.014)
	Nr. of subjects	166	166	166	166
	Nr. of observations	1328	1328	1328	1328
	Log-likelihood	-575	-375	-370	-369
	Wald χ 2	1.26	192	180	180
	p>χ 2	0.26	<0.001	<0.001	<0.001
	Note: Marginal effects in square brackets, standard errors in round brackets; * significant at 5% level, ** significant at
	1% level, *** significant at 0.1% level, two-sided.

Table 2 :

 2 Determinants of choice of the large urn in experiment 2 (random-effects Probit models)

		I	II	III	IV
	Normalized	-0.001 [0.000]	-0.001 [.000]	-0.001 [0.000]	-0.001 [0.000]
	prize (within)	(0.001)	(0.001)	(0.001)	(0.001)
	High-Stakes	0.107 [0.031]	0.121 [0.030]	0.122 [0.030]	0.107 [0.026]
	(between)	(0.122)	(0.144)	(0.144)	(0.147)
	Large urn	2.593 [0.804]***	3.049 [0.872]***	3.049 [0.872]***	3.044 [0.872]***
	superior	(0.112)	(0.123)	(0.164)	(0.164)
	Equal probability		1.572 [0.363]***	1.560 [0.532]***	1.560 [0.532]***
			(0.107)	(0.121)	(0.121)
	Probability difference			-0.331 [-0.081]	-0.370 [-0.090]
				(8.504)	(8.515)
	Male				-0.124 [-0.030]
					(0.153)
	Age				-0.003 [-0.001]
					(0.012)
	Constant	-1.227***	-1.679***	-1.677***	-1.571***
		(0.107)	(0.130)	(0.143)	(0.218)
	Nr. of subjects	78	78	78	78
	Nr. of observations	1950	1950	1950	1950
	Log Likelihood	-699	-584	-584	-584
	Wald χ 2	540	662	662	662
	p>χ 2	<.001	<.001	<.001	<.001
	Note: Standard errors in round brackets, marginal effects in square brackets; * significant at 5% level, ** significant at
	1% level, *** significant at 0.1% level, two-sided.

Table 3 :

 3 Mean amounts in excess of expected values (premia) that subjects are willing to pay, in €

		Project/Scenario A	Project/Scenario B
	Investment -Low-Stakes*	1.46	1.39
		(0.21)	(0.25)
	Investment -High-Stakes	0.89	0.48
		(0.31)	(0.34)
	Insurance	0.42	0.47
		(0.04)	(0.04)

Note: * Values are normalized to high stakes amounts through multiplication by 10; standard deviations in brackets.

Table 4 :

 4 Ratios presented to subjects in the between-subject ratio bias tasks

	Framing	Low Ratio	Medium Ratio	High Ratio
	Neutral task	1/10	10/100	100/1000
	Insurance task	(3/day)/80000	(72/month)/80000	(783/year)80000
	Investment task	7/100	59/1000	423/10000

Table 5 .

 5 Mean valuations in the between-subject tasks

Note: Standard deviations are in brackets.

The value of 5% used is completely discretionary. This problem will be dealt with explicitly in experiment

All p-values reported are two-sided, unless specified otherwise.

0 Appendix C -Screenshots of the comparative investment task -Experiment 2 1 Screenshots for the comparative insurance task -Experiment 2 3 Screenshot for the insurance task -Between-subject design -Experiment 2 4 Screenshot for the investment task -Between-subject design -Experiment 2

The authors thank S. Ferriol for programming the experiment. Financial support from the EMIR program of the French National Agency for Research (ANR) is gratefully acknowledged (BLAN07-3_185547).

Appendix A. Choices between lotteries to detect ratio bias -Experiment 1

Problem 1 Bag A contains 10 poker chips, 1 red chip and 9 green chips. Bag B contains 100 poker chips, 10 red chips and 90 green chips. You can win €80 by extracting a red chip from one of the two bags. Which bag do you choose? Bag A (1 red chip and 9 green chips) Bag B (10 red chips and 90 green chips) Problem 2 Bag A contains 10 poker chips, 1 red chip and 9 green chips. Bag B contains 100 poker chips, 9 red chips and 91 green chips. You can win €80 by extracting a red chip from one of the two bags. Which bag do you choose?


Jean-Pierre Banâtre

Michel Banâtre

Christine Morin

Jean-Pierre Banatre

Michel Banatre

Implementing atomic rendezvous within a transactional framework

Keywords: stable storage CSP, rendezvous, atomicity, transactions, parallelism

The transaction concept has been widely used as a powerful tool for the reliable structuring and programming of applications in several fields such as databases, distributed systems ... In this paper, we address the problem of implementing the CSP rendezvous whithin a transactional framework. In fact, several authors have studied the problem of implementing CSP rendezvous on networks of machines but our transactional approach is original. Their research mainly concentrates on the implementation of a fair non-deterministic choice and assumes a correct functioning of processors and communication media

In this paper, we propose an efficient transactional implementation of atomic rendezvous in presence of processor failures in a multiprocessor machine. Both atomicity and efficiency are obtained by using special hardware devices : high speed stable storages. .

1.Introduction.

Remote procedure call (RPC) appears to be a widely used paradigm for providing communication between programs written in a high level langage and running on different nodes [ll]. When a remote procedure is invoked, the caller is suspended, the parameters are transmitted across network to the node where the callee is to be executed and after completion of the callee, the results are passed back to the caller which resumes its execution.

There are many attractive aspects to this communication facility : simple semantics, efficient implementation. The major issue faced by the system programmer of a RPC facility is the problem related with node and communication failures. In particular a precise semantics of a call has to be defined which determines policies to be obeyed after detection of a failure [START_REF] Birrell | Implementing Remote Procedure M I S[END_REF].

Another important paradigm for providing communication between programs (or processes) in a high level language is the rendezvous [START_REF] Hoare | Communicating Sequential Processes[END_REF]. Two processes are involved in a rendezvous, a CH2807-6/89/0000/0119/$01 .OOO 1989 IEEE producer and a consumer. Production of an item and consumption of the same item are synchronized (the producer waits till the consumer is ready and vice versa). When both producer and consumer are ready, the information exchange takes place atomically and if the rendezvous is successful the two processes go on in parallel or execution of both processes is interrupted just before the rendezvous commands. This is the "aLl or nothing" property characterizing atomicity.

Several authors have studied the problem of implementing CSP rendezvous in a distributed context [START_REF] Bemstein | Output guards and Nondeterminism in "Communicating Sequential Processes[END_REF], [4]. They mainly concentrate on implementation of a fair non-deterministic choice and assume a correct functioning of processors and communication media. In this paper, we address the problem of efficient implementation of atomic rendezvous on a multiprocessor machine in presence of failures. Once the rendezvous to be done is chosen (we do not discuss this problem here), we guarantee that either the rendezvous is successful or nothing happens.

In the following, we consider rendezvous as it is defined in CSP, a language for Communicating Sequential Processes, proposed by Hoare [START_REF] Hoare | Communicating Sequential Processes[END_REF]. For the purpose of this paper, the following description of inpudoutput commands syntax and meaning is sufficient.

Communications between processes Pi and Pj (i#j) are expressed by the send and receive commands Pi ! x and Pj ? x respectively. Output command Pi ! x (in text of Pj) expresses a request to Pi to receive a value from P,. Input command Pj ?

x (in text of Pi) expresses a request to P, to assign a value to the (local) variable x of Pi. Execution of Pj ? x and Pi ! y is synchronized (Pi waits at Pj ? x until Pj is ready at Pi ! y and vice versa) and results in assigning the value of y to x.

Section 2 deals with architectural issues. In particular, a stable storage device which is used intensively in order to implement atomicity is described. The general model of atomic

I I9
rendezvous implementation are presented in section 3 and the associate transaction management system is described in section 4. Finally section 5 contains a brief review and discussion.

Architectural issues.

Machine architecture.

Our reference machine is made out of N processors connected via a global bus. Each processor (e.g., M68030) can access a local memory and a special device (stable storage) which will be described later. The processor normally accesses its local memory and its stable storage through a local bus. Figure 1 illustrates this machine architecture. In the following, we will refer to a processor, its local bus, its local memory and stable storage as a node.

2.2. Stable storage description.

2.2.1.Hardware architecture.

Stable storage provides memory that has high probability of surviving processor and communication media failures. As an abstraction, stable storage has the important property that writes are atomic, that is, they either happen or they don't happen. Lampson and Sturgis [8] have proposed an implementation of this abstraction some years ago. Their idea was to use two different disk drives with independent failure processors. Each logical page was represented by two physical pages, one on each disk drive. A write to a logical page involved writing f i t to one physical page, and then writing to the other physical page. In practice, few real systems implement stable storage with two disks because of the expense in writing to two disks for every update.

The stable storage device used (called SSB) is built from two banks of non-volatile, random access memory [l], each bank consisting possibly of several megabytes of memory (the board has battery backup power in case of power failure). Of course, accesses to the banks are mutually exclusive. Although the algorithms related to atomicity are essentially the same in spirit as Lampson and Sturgis's, our stable storage differs in three ways : (i) the processor writes to one bank, and the object manager internal to the board writes from the first bank to the second, thus freeing the processor from waiting for two write operations ; (ii) the SSB is part of the processor address space, in this case it is necessary to implement a way of controlling secure access to the board, (iii) the SSB provides atomic operations on group of objects (or data structures) which can be sparse in memory. These facilities are provided by the object manager which closely controls any access to an object. A complete description of SSB is given in [l].

2.2.2.Stable storage functionalities.

In order to manage objects (i.e. data structures), several primitive operations are offered by the Stable Storage, let us describe the most useful ones :

creat-stb-obj ([outlstb-obj, [inlsize).

This primitive creates a stable object. The size of the new destroy -stb -obj ([in] stb -obj 1.

The stable object located at address stb-obj is destroyed. object is given as argument.

read-stb ([in] stb -obj, [outladd).

The stable object located at address stb-obj is read and transferred into RAM storage at address add.

write-stb ([in] stb -obj, [inladd). The contents of the object located at address add in RAM storage are written at address stb-obj in stable storage.

grp-write-stb ([in]stb-obj-list, [inlx-list). This primitive allows the atomic update of a group of objects located in stable storage as explained in the following example.

Example.

Consider three integer stable objects 0 1 , 0 2 , 0 3 : The execution of the operation grp-write-stb ((01,02,03), (O,O,O)) produces one of the two following results depending whether it is successful or not.

0 1 0 2 0 3
On fig. 3.1, the operation has been successful and all three objects have.been updated. On fig. 3.2, the operation has failed and has produced no effect. In our implementation, the primitive operation grp-write-stb is used for instance to atomically update queues. The object group is then composed of queue elements and pointers. It is also used to update checkpoints. In this case, the object group is constituted of all the objects which represent a process state.

2.2.3.Performance.

Unlike disk access time, accessing this new stable storage is on the order of accessing main memory, which is a big win. For instance, with a stable storage built with high performance disks (15 ms access time), an update operation takes 30 milliseconds for four bytes. The same operation takes only 9 microseconds in SSB. In fact, access time to SSB is only 2.7 times access time to a normal RAM but with a lot of advantages, in particular write atomicity and protection.

The performances achieved by such a stable storage are comparable with the performances of a normal RAM memory. This observation leads us to think that such a memory could be used to store efficiently such information as checkpoints. Measurements show that the time required for saving an object of more than hundred 32-bits words in SSB is approximatively 2.5 ps per word. So the time required for saving a checkpoint of two hundred bytes (50 words of 32 bits) is 125 ps. This is still quite reasonable compared to the average 0.2 ms necessary for an inter-processor communication via the global bus. Optimizations would even be possible, which would make it possible to reduce the amount of information saved in a checkpoint.

Fault hypothesis.

The machine is designed to survive two kinds of faults : -hardware faults, such as the crash of a processor for internal (hardware misfunctioning) or external reasons (power failure ...) software faults. These faults are detected at the hardware level through their consequences which, most of the time, happen to be an incorrect memory access.

Processors are assumed to be "fail-stop" [13], so they possess the following properties :

(i) After the detection of an error, the processor interrupts its activity (fail-fast property).

(ii) The crash of a processor can be detected by the other processors of the system.

(iii) Every processor can access two kinds of storage facilities : a volatile memory (RAM) and a stable storage.

(iv) The stable storage of a fail-stop processor can always be read by another fail-stop processor.

A crashed node is assumed to be repaired and restarted after a finite delay.

The communication medium is considered as unreliable. Actually message loss, duplication and desequencing are possible. However, the contents of a message cannot be altered during a node to node transfer. Finally, the communication medium can be unavailable during a finite amount of time.

Implementation of atomic rendezvous : general principles.

The implementation of atomic rendezvous relies on the concept of atomic transaction [START_REF] Gray | Notes on data base operating systems[END_REF], [8]. Actually, using the transaction concept to implement the rendezvous is motivated by simplicity:

a transaction is associated to every rendezvous, well-known commit protocols for atomic actions can readily be applied, This section introduces the major components of the transactional system which has to be set up in order to solve the problem. We first give a brief description of the hierarchical structure of the system and then show how the rendezvous mechanism is mapped on this structure.

System structure.

Our system has to provide the transaction model to applications. It is organized in three layers organized as displayed on fig. the application layer where CSP processes communicate the transaction layer which implements the notion of atomic transaction. Transaction management processes exchange informations via a reliable communication system. Every node Ni possesses its unique local transaction manager TMi which may communicate with managers TMj Q#i) in order to implement atomic actions involving more than one process.

the communication layer which implements a reliable communication system by using the stable storage facilities. Appropriate protocols are implemented in a cooperative way by processes (called CMi) located on system nodes. A complete description of this communication system can be found in [IO]. with rendezvous.

3.2.Brief sketch of the solution.

Consider two application processes Pi (located on node Ni)

and Pj (located on node Nj) (fig. 5). On this figure Si (resp. Sj) represents the state of Pi ( resp. Pj) before execution of the rendezvous, and Si' (resp. Sj') represents the state of Pi (resp. Pj) after the execution of the rendezvous.

An atomic rendezvous possesses the "all or nothing" property :

(i) If a failure occurs during the execution of the rendezvous then Pi (resp. Pj) are backed up to Si (resp Sj). The rendezvous has not been completed.

(ii) If no failure occurs, then Pi (resp. Pj) reaches state Si' (resp. Sj') and the. rendezvous has been achieved.

Let Ctx-Pi be the current state of process Pi, Check-Pi be the last checkpoint of process E5 stored in stable storage and Tij the transaction implementing a rendezvous between processes Pi and Pj. A queue in-mess, and a variable result are located in stable storage, and shared between application processes and their transaction manager. The implementation of atomic rendezvou-s between processes Pi and Pj can then be described as follows (fig. 6) :

Node i Node j

1 Figure 6 : A rendezvous execution.

Step (I), process Pi reaches the rendezvous operation Pj ! x.

It sends its rendezvous request to its node transaction manager TMi. In fact, Pi's request is stored in TMi's queue in-mess.

The following piece of program describes the processing done on behalf of Pi.

tr-UID I (sender-UID, receiver-UIDi failure #exception handling has to be performed#

--

Instruction (a) updates atomically a group of objects in stable storage. This group is made up of Check-Pi (initialized with Ctx-Pi), the queue in-mess (initialized with a rendezvous request) and the result variable which is undefined while the transaction associated to the rendezvous is not completed.

During the execution of the transaction implementing the rendezvous, processes Pi and Pj are waiting (instruction b).

After the completion of the transaction, the variable result is set up to failure or success. In case of failure, Pi and Pj are backed up to state Si and Sj and possibly, a failure exception is signaled to both processes. Actually such an exception mechanism is not present in CSP, it could well be introduced in order to face such exceptionnal situations.

Step (2), process Pj reaches the rendezvous operation Pi ? y. It sends its rendezvous request to the transaction manager TMj and the same processing as above is initiated.

Step (3), the two transaction managers TMi and TMj cooperate to manage the transaction associated to the rendezvous requested by Pi and Pj. They reliably communicate by using the communication layer.

Transaction management for rendezvous implementation.

This section details the management of transactions implementing atomic rendezvous. After a short presentation of transaction representation and of data structures used for communications between transaction managers, we describe the behaviour of transaction managers.

Transaction representation.

The main purpose of a transaction management process is the creation and control of transactions implementing state indicates the state of the transaction :

."undefined", if the transaction is currently being executed,

."ready-to-commit", if the transaction can be locally committed (the overall transaction encompassing two sites) will be committed if both sites are ready to commit, ."impossible to commit", if the transaction cannot be locally committed. The overall transaction encompassing two sites will be aborted, . "committed", if the transaction is successful, . "aborted", if the transaction is a failure.

time out defines the maximal time duration granted to the transaction. This parameter is set up by the site which creates the transaction.

data receives the data to be exchanged during the rendezvous.

address contains the address (in the receiver address space) where the above data has to be stored as a consequence of the communication.

The transaction descriptor and the corresponding entry in the table are created and initialized through the invocation of an operation called create-tr (tr-UID, <param>).

Sender-TM

is not yet created. The structure of transaction management messages can be described as: an output communication queue, out-mess, for storing output messages directed towards external transaction managers.

a queue, called creation-request used .to store rendezvous requests not yet handled by a transaction.

data-

4.3.Description of a transaction manager.

This section describes the two major issues to be tackled by the transaction manager : transaction creation and transaction termination.

4.3.1.Transaction creation.

The main problem to be tackled concerns the unicity of the transaction associated to a rendezvous. Actually, due to the symmetry of the rendezvous mechanism, it is possible that two processes involved in a rendezvous make a request for a transaction creation at the same time. However only one transaction has to be created. For example, consider two application processes Pi and Pj which have to communicate by rendezvous. In that order requests are made to transaction managers TMi and TMj in order to create the transaction Tij. The creation of Tij amounts to attribute a unique identifier (UID) to this transaction and to initialize appropriate data structures. Transaction managers TMi and TMj have to cooperate in order to ensure the unicity of the UID. Several situations have to be considered depending on the ordering in time of the requests for transaction creation.

A transaction manager deals with two types of messages : (i) messages from (or to) application processes and (ii) messages from (or to) other transaction managers.

The contents of these messages may be described as follows -Messages of type (i) contain the identity of the sender and that of the receiver plus the data to be transferred (in case of output) or the address to which the data has to be stored in case of input.

case 1: Process Pi reaches the rendezvous after Pj (fig. 8). TMi is aware of Pj rendezvous request and it receives a rendezvous request from Pi.

-Messages of type (ii) are concerned with transaction creation and management. The structure of transaction creation messages is the following :

where sender-TM (resp. receiver-TM) is the identity of the sender transaction management (resp. receiver transaction manager). Rdv-process contains the identity of the two processes involved in the rendezvous. tr-UID contains a transaction unique identifier or skip when this field is undefined, i.e., the transaction corresponding to Rdv-process Pi (on node i) requests a rendezvous with Pj (on node j).

Th4i has no information about an hypothetic rendezvous request from Pj (fig. 11).

[(PiPj), info] (fig. 12). Process Pi stores in TMi's queue in-mess the message We distinguish two cases in our explanation : processing done by TMi (case 3.1) and processing done by TMj (case 3.2).

[m. TMj. UID-Tij , (ti. Pj)] case 3.1 : Process TMi receives the message [TMj,TMi,skip,(Pi,Pj)]. The message [TMi,TMj,skip,(Pi,Pj)] is already present in its queue creation-request (fig. 15).

out-mess[TMi]

Figure 15 : State of TMi's queues at time tl (before processing the rendezvous request).

Our problem is to decide if TMi has to provide UID-Tij or to wait that TMj sends it UID-Tij. To solve that problem, we decide that the transaction manager which holds the smallest UID provides UID-Tij. Let us assume that the property UID-TMi<UID-TMj holds. So, TMi is allowed to call the operation deliver-UID which retums UID-Tij associated to the rendezvous in order to locally create the transaction Tij by It locally creates the transaction Tij by calling the operation create-tr (UID-Tij, in-mess.TMilj].info). Its in-mess, out-mess and creation-request queues are updated (fig. 18). There is no information anymore about the current rendezvous between Pi and Pj in TMj's queues since created Tij and knows that TMi did the same.

TMj has locally

4.3.2.Transaction management.

Two actions are performed in a transaction :

-the effective transmission of the data, -the atomic termination of the transaction. Our protocol is very classical, it is a two phases protocol similar to the one described in [LAMP-811. Consider a transaction Tij between two processes TMi and TMj implementing a rendezvous between Pi and Pj. The master process of the transaction Tij (let us assume that it is process TMi) is the sender of the message m exchanged in the rendezvous. The process which receives m is the slave process of Tij (let us assume that it is process TMj). Let desci (resp. descj) be the transaction descriptor of Tij on the node where process Pi (resp. Pj) is located. The management of transaction Tij can be described with the following rules :

I26

Rule 1 When TMi sends m to TMj, it sets a timeout and stores "undefined" in desci.state.

Rule 2

When a Tij's timeout is elapsed on TMi (resp. TMj) node then desci.state (descjstate) i s c h a n g e d t o

"not-ready-to-commit".

Rule 3

When TMj receives m, if descj.state has the state "undefined" then, TMj sends a ready-to-commit message to TMj and stores "ready-to-commit" in descj.state.

Rule 4

When TMj receives m, if descj.state is in " n o t -r e a d y -t o -c o m m i t " state then TMj sends a not-ready-to-commit message to TMi.

Rule 5

When a ready-to-commit message is received by TMi, if desci.state is equal to "undefined" the transaction Tij is locally committed else it is aborted. A commit message (in the former case) or an abort message (in the latter case) is sent to the remote process.

Rule 6

When a commit (respectively abort) message is received by TMj, the rendezvous is locally committed (respectively aborted).

We do not develop in more details protocols dealing with atomicity as they have already been presented elsewhere, [8], P I , 151, 1121 ...

5.Review and discussion.

This paper has presented an unusual application of the transactional model to the solution of synchronous communication scheme known as rendezvous. The major problem to be tackled was related to the atomicity property of the rendezvous : either the communication happens completely or not at all. The difficulty comes from the symmetric behaviour of the rendezvous which allows either the producer or the consumer to take the initiative of the C0m"iCatiOn. This difficulty does not arise in a RPC communication scheme where the calla is clearly the initiator of the communication.

We have chosen to solve the problem by applying the transactional model. A transaction is associated to every rendezvous and well-known commit protocols are used to implement atomic termination. Timestamping mechanisms are used to logically date every event in the system, thus permitting appropriate coordination for the creation of a transaction.

In our solution, a key role is played by stable storage devices which provide atomic access to group of objects. This notion of group of objects is absolutely central to our proposal as it allows the atomic creation and update of a checkpoint. In other words, the stable storage provides a hardware implementation of some basic transactions, one of which (used in this proposal) is the atomic update of a group of objects.

The important aspect to be emphasized concerns the efficient implementation of atomic rendezvous. For this purpose, it is clear that a stable storage device is absolutely necessary. However, as typical stable storages are built from disks, performances achieved are quite poor. This is the reason why very few proposals deal with the implementation of atomic operations in general and more specifically with atomic rendezvous. These proposals are generally concerned with data base management systems where the size of data to be processed is important (files) and can be stored on a double-disc stable storage (e.g. [5]). In ARGUS [9], an effort has been made in order to allow the programmer to define its own atomic actions. However, the implementation of atomic actions has not been optimized at all as stable storage is "emulated" on a single disk. Our approach which uses a high speed RAM-based stable storage make it realistic to implement efficiently such communications schemes as atomic remote procedure call or rendezvous.

Figure 1 :

 1 Figure 1 : Machine architecture.

Figure 2 :

 2 Figure 2 : Stable object group.

Fig. 3 . 1 Fig. 3 . 2 Figure 3 :

 31323 Fig. 3.1

Figure 4 :

 4 Figure 4 : System organization.

Figure 5 :

 5 Figure 5 : Two CSP processes.

  (a) grp_write_stb(Check-Pi<-Ctx-Pijn-mess~l <-[ ( ~& r -~s e c e i v e r -~) , i n f o ] ~~t < -u n & f i n e d ) ; (b) while #result=undefined# do wait #termination of the atomic transaction associated to the rendezvous# od; (c) if #result=failure# then Ti.

Figure 7 :

 7 Figure 7 : Transaction representation.

4 . 2 .

 42 Messages handled by transaction managers.Each local manager manages three queues (located in stable storage) in order to handle communications :an input communication queue, in-mess, for storing input messages sent by external transaction managers or stored by local application processes.

Figure 8 :

 8 Figure 8 : Pj reaches the rendezvous before Pi.

Figure 9 :

 9 Figure 9 : State of TMi's queues at time t 2 (before processingthe rendezvous request).

Figure 10 :

 10 Figure 10 : State of TMi's queues at time t2 (after processing the rendezvous request).

Figure 11 :

 11 Figure 11 : Pi reaches its rendezvous operation.

Figure 12 :

 12 Figure12: State of TMi's queues at time t l (before processing the rendezvous request).

Figure 13 :

 13 Figure 13 : State of m i ' s queues at time t l (after processing the rendezvous request).

case 3 :Figure 14 :

 314 Figure 14 : Pi and Pj reach their respective rendezvous operation at the same time.

  calling create-tr (UID-Tij,in-mess.TMiIjl.info). It informs TMj that the transaction Tij is created by sending him the message [TMi,TMj,UID-Tij,(Pi,Pj)]. Its queues in-mess and out-mess are updated (fig. 16).

Figure 16 :case 3 . 2 :

 1632 Figure 16 : State of TMi's queues at time tl (after processing the rendezvous request).

Figure 17 :

 17 Figure 17 : State of TMj's queues at time tl (before processing the rendezvous request).

Figure 18 :

 18 Figure 18 : State of TMi's queues at time tl (after processing the rendezvous request).