Tanja Ažderska
email: atanja@e5.ijs.si

Co-evolving trust mechanisms for catering user behavior

Keywords: trust, bias, context, reputation, recommendation, rating

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

Introduction

Few decades ago, trust was a feeling and a reality. The curiosity of "feelings often diverging from reality" made trust a major constituent of social studies. Person A may believe that B is trustworthy, although that is not the case, but A may also believe in the opposite (B being non-trustworthy), although it may not be the case. This led to the creation of social models of trust. Nowadays, trust has also come to represent people"s beliefs in the entities met in the virtual world, leading to the design of many computational models of trust. However, the models that represent the relationship between A and B can easily fail to capture both sides of the story: how much A trusts B, and whether B is really trustworthy. In other words, how much the model resembles reality, how much it comes closer to human perceptions and actions, and how much the two differ. In this study, we take the stance that trust has its own representatives in the online environment. We recognize reputation, rating, and recommender systems (henceforth denoted as RRR systems) as the online representative of trust. We see the elements of the three (RRR) systems as ones that are different, but in often complement one another. However, the adequate combination of RRR depends on many factors, and the failure to recognize those factors leads to inconsistencies in the work of the RRR system as a whole. Moreover, user behavior is largely influenced by the work of those systems, and it largely influences the systems performance as well.

The contribution of our work is in the following: we detect and analyze four factors that influence the work of RRR systems when they are required to co-evolve as a single solution for providing good user experience, system reliability and result accuracy. Those factors are context, risk, dynamics and privacy. We put users in the core of RRR systems, and investigate the inter-dependencies between RRR systems and user behavior with respect to the four identified factors. We analyze several types of cognitive biases that users exhibit in their online experiences with RRR systems. Then, we perform an experimental study that will allow us to identify several types of cognitive biases exhibited by the users, and that were not investigated in an RRR setting so far. Based on the identified factors and the findings of the experimental study, we propose a framework for addressing some of the issues attributed to users" biased behavior and explore the possibility of employing hidden signals in the RRR systems for the purpose of capturing some types of user behavior.

To provide a clear picture of our understating of social trust and its online representatives, in the following section we define the concepts. Then, we present related work in the area with the effort to move closer to each other the social and the technical aspect. Finally, we present the stated contributions throughout Sections 4 and 5. We conclude in Section 6.

2

The Notion of Trust and its Online Representatives

Trust

From a social perspective, trust can be defined from two general aspects: cognitive and affective. The former is represented by concepts like rational choices, learning loops, institutional protocols, pattern detection, and imitation of established norms.

Affective aspects, on the other hand, are mainly seen in the emotional side of trust interactions, and they account for the human feelings. As feelings are heavier on energy, whereas thoughts are heavier in information, affective properties often "take the blame" for contributing to cognitively biased decisions [START_REF] Zajonc | Feeling and thinking: Preferences need no inferences[END_REF]. The "social" literature on trust and reputation is exhaustive [START_REF] Zajonc | Feeling and thinking: Preferences need no inferences[END_REF][START_REF] Conlisk | Why Bounded Rationality?[END_REF][START_REF] Castelfranchi | Trust is much more than subjective probability: Mental components and sources of trust[END_REF]. Clearly, when seeing trust as a purely social phenomenon, it can only be ascribed to living beings, and manifested through the property of trustworthiness of entities that are not necessarily living beings themselves. However, the ability to trust nowadays is disentangled from purely social contexts. A trusting entity can be any agent capable to resolve cognitive conflicts, or do preferential filtering, ranking, or sorting. This makes the definition and even the purpose of trust hard to grasp and determine. The blurred line of where the human factor starts or stops to influence trust and trustworthiness, usually leads to neglecting the affective side when defining the computational analog of trust. This, in turn, leads to the inability to predict the behavior of systems where trust models are deployed. These effects are caused by the highly non-linear nature of the trust phenomena, which do not allow a system to be designed according to the elegant principles of mathematical linearity and probabilistic averaging. Hence, knowing the composition of the system parts does not contribute a lot to inferring the properties of the system as a whole. It is critical to consider the interactions and dependencies between the entities that comprise the system, and capture the additional phenomena and properties that emerge from those interactions. Complementing this with the strong contextual dependence of trust explains why researchers have a hard time formalizing trust, and incorporating it into online scenarios analogous to those in the traditional social networks. Following Gambetta [START_REF] Gambetta | Can We Trust Trust?"Trust:Making and Breaking Cooperative Relations 5[END_REF], we give the following initial definition: Definition 1a. Trust is the belief, i.e., the subjective probability that an entity will perform in a way likely to bring the expected benefit, or not do an unexpected harm.

Considering trust only as a subjective probability leaves out an extremely important concept related to trust, that of risk. This fact has also been the catalyst of a vigorous debate between economists and social psychologists [START_REF] Castelfranchi | Trust is much more than subjective probability: Mental components and sources of trust[END_REF]. In circumstances where one entity relies on another, trust choices include a certain level of risk. Josang [5] defines two different types of trust, Reliability and Decision trust. The former covers the aspect of trust as stated by Definition 1a. The latter considers the risk brought about by the uncertainty of transactional outcomes and is used to extend our first definition: Definition 1b. Trust is the extent to which one entity is willing to depend on others" decisions and actions, accepting the risk of a negative (undesired) outcome.

Online representatives of trust

Despite the relatively interchangeable use of trust and reputation in the research community, it is essential to understand the difference between the two. Definition 2a. Reputation is the general standing of the community about an entity"s trustworthiness, based on the past behavior, performance, or quality of service of that entity, in a specific context, i.e., a domain of interest. Definition 2b. A system that facilitates the process of calculating and managing reputation is called a reputation system.

Hence, reputation is the amount of context-aware trust, i.e., a quantitative representation of the trust that the society places in an entity, bound by the domain of interest. In addition to reputation systems, we consider rating and recommendation systems to also be online representatives of trust. We define them as follows: Definition 3. Rating systems manage the evaluation or assessment of something, in terms of quality, quantity, or a combination of both. Definition 4. Recommender systems are a subclass of information filtering systems that seek to predict the rating or preference that a user would give to an item or a social element they had not yet considered, using a model built from the features of an item (content-based) or the user's social environment (collaborative filtering) [START_REF] Ricci | Introduction to Recommender Systems Handbook[END_REF].

We use the terms trust mechanisms and RRR systems interchangeably in this work.

3 Related work

Social

Some of the work done in social and behavioral sciences that inspired computational trust research was discussed in the previous section [START_REF] Zajonc | Feeling and thinking: Preferences need no inferences[END_REF][START_REF] Conlisk | Why Bounded Rationality?[END_REF][START_REF] Castelfranchi | Trust is much more than subjective probability: Mental components and sources of trust[END_REF]. Neuroscience has also re-vealed that emotions and cognition, present in different areas of the human brain, interfere with each other in decision making, often resulting in a primacy of emotions over reasoning [START_REF] Macmullen | Feelings in history, ancient and modern[END_REF]. A very similar, although deceptively simple idea stands behind the outstanding work in Perceptual Control Theory: our perceptions are the only reality we can know, and the purpose of all our actions is to control the state of this perceived world [START_REF] Powers | Behavior: The Control Of Perception[END_REF]. The psychology of making trust-related choices is directly related to how people think and feel, perceive and decide. The brain has developed complex mechanisms for dealing with threats and risks. Understanding how it works and when it fails is critical to understanding the causal loop between trust-related perceptions and trust-related choices. An area with remarkable results about the irrationality, bias, and unpredictability of human actions in various circumstances and mindsets is Behavioral Economy [START_REF] Kahneman | Maps of Bounded Rationality: Psychology for Behavioral Economics[END_REF][START_REF] Ariely | Predictably Irrational: The Hidden Forces That Shape Our Decisions[END_REF][START_REF] Kahneman | Subjective probability: A judgment of representativeness[END_REF]. In the context of preferential reasoning, their analyses show that users are often unaware of their taste, even for experiences from previously felt outcomes. Not only this reveals that taste is much more subtle than preference, but it shows that preference itself is not a stable property of human reasoning [START_REF] Ariely | Tom Sawyer and the construction of value[END_REF]. Experiments on persistency of user preferences about identical items at different instances of time proved significant fluctuation in the repeated preferential choices [10][13]. In contract and utility theory, the potential of employing trust mechanisms for dealing with information asymmetry was recognized long ago. When the possibility of post-contractual opportunism creates a context of moral hazard, trust mechanisms are employed for sanctioning undesired behavior. Another context of information asymmetry is adverse selection, and arises when one is required to choose a transaction partner whose type (good or bad) is unknown. In his work, Akerlof analyzes the effect of social and trading reputation on transaction outcome and market maintenance [START_REF] Akerlof | The Market for "Lemons": Quality Uncertainty and the Market Mechanism[END_REF]. The study demonstrates that goods with low quality can squeeze out those of high quality because of the information asymmetry present in the buyers" and sellers" knowledge about the products -the problem of so called "lemon markets". Reputation mechanisms would balance this asymmetry, helping buyers make better-informed decisions by signaling the behavioral types of sellers, and at the same time providing incentives for sellers to exchange high-quality goods. Thus, Akerlof makes an instructive distinction between the signaling and the sanctioning role of RMs, which was only recently considered in computer science.

Technological

Understanding the behavioral implications of users in the field of computational trust is crucial, as the user factor in the processes met in online trust mechanisms is omnipresent. As online representatives of trust, RRR systems are also assigned the role of "devices" that help decision-making under information asymmetry (reputation and rating systems), and information overload (recommendation systems). In the former case, they have sanctioning and signaling role, and in the later case -directing and filtering role. The goal of employing RRR systems is to reduce the complexity that arises from information overload, and to lower the uncertainty present in the contexts of information asymmetry. Depending on the general context, however, the combination of the three (reputation, recommendation, and rating) requires different structuring to achieve the desired goals. This is discussed further in the following section. RRR systems rely to a great extent on preference inputs from users. Bias in these inputs may have a cascading error effect on the performance of the applied algorithms. This does not only affect the accuracy of the results, but it also influences the perceived system reliability. Hence, user preferences are malleable and affect system performance, but they are also largely influenced by the information provided by RRR systems. Yet, biased behavior, its causes and effects, are relatively unexplored issues in the field. But the fact that only a narrow set of cognitive biases has been tackled by the research community does not imply there are no significant studies made in this regard. In [START_REF] Chevalier | The Effect of Word of Mouth on Sales: Online Book Reviews[END_REF] and [START_REF] Resnick | Trust among strangers in internet transactions: Empirical analysis of eBay" s reputation system[END_REF], authors investigate the so called self-selection bias, whereby users only rate the items (movies) they like most, causing extremely high average rating for the rated items. Such ratings are representative only for a specific group of users, but do not truthfully depicture the item"s general quality. Furthermore, self-selection bias was proved to not only be a transient phenomenon, but also a steady state in the system [START_REF] Kramer | Self-Selection Bias in Reputation Systems[END_REF]. Although seemingly absurd, there is also one positive implication from this result of "self-selection bias" sustainability: if there was a strategy in the managerial principles of some company to cause inflated ratings for certain products by the "first-mover effect" [START_REF] Lieberman | First-mover advantages[END_REF], this effect would be flattened out on the long run. Such issues may appear to have purely economic nature, but they seriously compromise the reliability and performance of current RRR systems. The high impact of online reviews on product sales was demonstrated in [START_REF] Chevalier | The Effect of Word of Mouth on Sales: Online Book Reviews[END_REF], uncovering some of the motifs behind companies" efforts to appear competitive on the market. Positive rating bias was noted throughout systems of different nature. eBay is claimed to owe its success to its reputation/feedback system, yet out of the 57% of the users that decide to leave feedback, 99% issue positive feedback [START_REF] Resnick | Trust among strangers in internet transactions: Empirical analysis of eBay" s reputation system[END_REF]. Moreover, large amount (41%) of users prefers to stay silent rather than to leave a negative feedback. A proposal to interpret silence as part of the user feedback was proposed in [START_REF] Dellarocas | The Sound of Silence in Online Feedback: Estimating Trading Risks in the Presence of Reporting Bias[END_REF].

Cognitive Bias and its loops of causality in RRR systems

Cognitive bias describes a replicable pattern in perceptual distortion, inaccurate judgment, or illogical interpretation [START_REF] Ariely | Predictably Irrational: The Hidden Forces That Shape Our Decisions[END_REF]. Clearly, bias can be noticed in both perceptions and actions, and the two are bound by the way people process their perceptions in order to take an action (including non-action). The paradox that arises in RRR systems is that, although user preferences are overly biased and affect the system performance and reliability, the preferences themselves are largely influenced by the ratings and the results provided by RRR systems. In this section, we explore the causes and effects related to cognitive bias in RRR systems, and we identify four major factors that influence these causal loops of biased behavior.

Context and Bias

Context is the set of circumstances or facts that surround a particular event or situation. Here, we analyze three general contexts in which an online interaction can take place: one with pure collaborative elements, one with collaborative and competitive elements, and one with collaborative, competitive, and monetary elements. Clearly, each subsequent context includes the elements of the previous, implying added system complexity. Therefore, it is crucial to understand which elements can be ade-quately combined in order to meet a system design-goal, without encumbering its performance and flexibility to the extent of edging users out. Once a reputation score becomes part of users" profiles, the users themselves become identifiable by their reputation, as if it guards their "online brand". Hence, maintaining a stable identity is crucial for the joined reputation value to make sense. On the other hand, being equipped with an online identity as a synonym for one"s reputation gives rise to some new dimensions in the context of impression management. Once reputation is used as a signal for the user behavioral type, pure collaborative context ceases to exist. The requirement for conducting a successful impression management adds a competitive component to the system, and makes the reputation explicitly recognized as part of a person"s social capital. Coupling this with the presence of bias implies that inflated (overly positive) reputation values in a system devaluates the reputation itself, as if the presence of reputation value defeated its purpose. Such a situation creates the need for additional incentives that will shift the reference for a good behavior from impression management to another context. What is often done in this regard is applying monetary elements to provide incentives for a desired behavior, which brings its own issues. Mixing purely collaborative context with monetary elements was already proved to throw a shadow on both the social intentions and the opportunity for monetary gain [START_REF] Ariely | Predictably Irrational: The Hidden Forces That Shape Our Decisions[END_REF]. In addition to these more subtle influences, there are more detrimental effects that arise from inadequately combining such contextelements. Including monetary elements drastically increases the complexity of the system, and introduces inter-locking dependencies between the trust mechanisms and the outside environment. From a systemic perspective, this implies that the boundaries of the system are open to additional disturbances [START_REF] Luhmann | Risk: a sociological theory[END_REF]. As a result, claiming predictability of the users" reputation scores, or moreover, of user and system behavior, diminishes, and failing to recognize this leads to system degradation, and eventually, system failure. This is also the core idea behind the Tragedy of Commons [START_REF] Hardin | Tragedy of the Commons[END_REF].

The soundness of the matters elaborated above was also demonstrated in practice. By announcing its Partner"s Program1 in May 2007, YouTube explicitly offered its highest rated users to earn revenue from advertisements placed next to their videos. This instantly triggered series of events of users blaming each other for using automated programs to inflate their videos" ratings2 . While the effect of these blames is related to the tragedy of commons [START_REF] Hardin | Tragedy of the Commons[END_REF], the effect of using programmed agents to inflate one"s own rating is known as the Cobra effect [START_REF] Siebert | DerKobra-Effekt :wie man Irrwege der Wirtschaftspolitik vermeidet[END_REF]: the solution of a problem makes the problem worse. These effects are often result of systemic ignorance, and only retrospectively analyzed by many system designers.

Pure collaborative contexts exist when a reputation is used internally in the system (for e.g., to provide a reference or serve as a regulator for the flow of some system processes), also implying keeping users" reputation private, or if the acquiring of reputation is not bound to one"s performance, i.e. it is not used for signaling purposes.

Clearly, when making the decision of which contextual elements to choose as part of a system, context is intimately related to risk. With the addition of each element, the complexity increases, and the perceived risk is hardened by additional factors. Furthermore, privacy appears worthy of consideration as an option for limiting the detrimental effects of added complexity. The goal of this study is to have a holistic look on RRR systems through the defined factors, rather than analyzing each of them independently. Therefore, the next section examines the link between risk and bias.

Risk and Bias

Risk is conceived as the possibility of triggering unexpected, unlikely, and detrimental consequences by means of a decision attributable to a decision maker [START_REF] Luhmann | Risk: a sociological theory[END_REF]. Uncertainty is part of every online interaction. The extent of uncertainty, the expected utility, and the cost required for performing an action, influence the perceived risk a transaction brings. The field of prospect theory offers an incredible amount of experimental work demonstrating the myriad of cognitive biases that people exhibit when faced with risk and uncertainty [START_REF] Kahneman | Subjective probability: A judgment of representativeness[END_REF]. A phenomenon that binds risk and uncertainty is the so called pseudo-certainty effect, which reflects the tendency of people to be riskaverse if the expected outcome is positive, but risk-seeking when they want to avoid negative outcomes. While it is a curiosity to inspect the properties of each bias independently, in reality biases are often coupled together, acting as both the cause and the effect of human perceptions and actions. The property of non-linearity we assigned to trust systems implies that complementing few biases together does not mean that their causes and effects will work in an additive fashion. Prospect theory has demonstrated that people underutilize consensus information, and when given descriptive facts about the quality of a person, they make choices regardless of the statistics offered about that person [START_REF] Kahneman | Subjective probability: A judgment of representativeness[END_REF]. Josang et al. provide a formal proof of this phenomenon known as the base-rate fallacy, and give a formal framework for accounting for this fallacy in a computational setting [START_REF] Josang | The base rate fallacy in belief reasoning[END_REF]. Information offered in RRR systems is to a great extent a statistic produced by the collective efforts of the community members. This information can be represented in various ways -numerically, descriptively, as a single or multi-valued component, or as a combination of those. Therefore, it is important to explore how users perceive different types of information, and whether the descriptive and the numerical representation of an entity"s quality can collide in users" perception. This is something we also investigate in our experimental study.

Dynamics and Bias

To some extent, we already touched on the issue of dynamics and bias when discussing the inconsistency of user preferences over time [START_REF] Ariely | Predictably Irrational: The Hidden Forces That Shape Our Decisions[END_REF]. Here, we stay more in the context of trust and reputation, and connect the dynamics-factor with the previously defined -risk and context. From the definitions of trust and reputation (Definitions 1and 2), it becomes clear that the dynamics of trust differs from the dynamics of reputation. This discrepancy cannot be captured by any model, as both trust and reputation are in reality intangible matters. Yet, the social models and protocols for detecting malice seem to be successful. In RRR systems, one way the dynamics of reputation is embedded in the models is through discounting the relevance of gathered information by some time-factor. However, such approach disregards the importance that some information had in the past in terms of its impact on the outcome. In other words, discounting by recency and frequency is not equal to discounting by impact. Doing the former may provide disin-centives for the users who take important actions at a lower rate. Closely related to this issue is the bias of rosy retrospection, which is a tendency to rate past events more positively than they were actually rated when the event occurred [START_REF] Kahneman | Subjective probability: A judgment of representativeness[END_REF]. This reflects the importance of accounting for the time-interval between item-consumption and provided feedback about that item. Unfortunately, our current experimental study does not tackle any of the concepts related to dynamics. However, as a disintegrable part of the bigger picture of online trust mechanisms, dynamics must be taken into consideration. Our future work will devote more attention to this factor.

Privacy and Bias

In [START_REF] Adamic | Rating Friends Without Making Enemies[END_REF], authors show that individual interpretations of trust and friendship vary, and the two concepts are correlated to other characteristics of a social tie and to each other in a non-symmetric way. Furthermore, they provide evidence that raters consider how a ratee"s reputation might be affected by the feedback. This fear of bad-mouthing and reciprocation in the context of impression management is directly related to the fear of retaliation in e-commerce systems [START_REF] Resnick | Trust among strangers in internet transactions: Empirical analysis of eBay" s reputation system[END_REF]. Together, these factors also help to explain patterns like higher reciprocity in public ratings, and the near absence of negative ratings. Given this reluctance to publicly leave negative feedback, the question arises: why offer multi-valued choice for item evaluation in the first place. Moreover, why showing it publicly if it affects the users" decisions to an extent that makes it useless. Closely related to privacy and the context of impression management are the concepts of individual and group behavior, and similarly, individual and group bias. Whereas most of the biases we mentioned so far were characteristic for an individual, we would fall extremely short on a useful discussion if we do not touch upon group behavior as well. After all, building reputation is essentially a social process, regardless of the fact that trust individuals cherish for one another underlies this process.

In [START_REF] Zhang | Anchoring effects of recommender systems[END_REF], authors study the anchoring effect that item ratings have on user preferences. They find that users" inclination towards providing positive feedback is additionally amplified if users see the current rating that an item got by the rest of the community members. That people imitate, or do what others do, especially when having no determined preferences, is nothing new. This is often the cause of what is known as group polarization, bandwagon effect, or herd behavior, depending on the field of study that identifies it [START_REF] Kahneman | Maps of Bounded Rationality: Psychology for Behavioral Economics[END_REF]. In the context of RRR systems, a study on group polarization on Twitter showed that, like-minded individuals strengthen group identity [START_REF] Yardi | Dynamic Debates: An Analysis of Group Polarization Over Time on Twitter[END_REF]. In other words, when part of group situations, people make decisions and form opinions that are extreme than when they are in individual situations. For RRR systems, this implies that it is not only important to acquire a significant amount of user feedback, but to also investigate whether this amount of user opinions was inferred from sufficient number of independent sources. A formal apparatus for resolving such issues in a computational setting can be found in [START_REF] Pope | Analysis of Competing Hypotheses using Subjective Logic[END_REF], where the author provides a framework for reasoning with competing hypothesis using Subjective Logic.

The following section describes the experimental study and analyzes the findings through the factors defined above. Moreover, it proposes some ways to address the revealed issues.

Experimental work

Objectives: The major objective of this survey was to provide data that will help us investigate the compatibility between users" perceptions of the RRR system and its design objectives, but also reveal new directions for reasoning about the interrelations between users and systems. The main questions we aim to answer are: ─ Which descriptive model resembles closest user perception of numerical feedback? ─ How does a slight difference in the "tone" of presented choices in the two descriptive models influence users" decision? ─ How does the presence/absence of different contextual elements influence user choice, and is it related to the nature (numerical or descriptive) of the alternatives? Design and Methodology: Two types of methods were used to gather the necessary data -an online survey method3 was chosen for better geographical spread of respondents, speed of data collection and independence of participants" opinions; and direct (one-on-one) interviews were performed to capture some of the subtleties that are ungraspable by only observing the outcomes of the systems. Such subtleties are the discrepancy between preferences of the majority of individuals and the group preference, the huge difference in the choices made as new contextual elements are introduced or taken away, the difference and inter-dependence between trustworthiness and acquaintanceship, etc. Each survey contained the same two questions, but offered slightly different evaluation choices. The questions represented real reviews for HP Laptop taken from Epinions4 . To not disturb the flow of the paper, they are given in the Appendix. All three groups were asked to rate the reviews for their usefulness. The first group (Survey 1) was asked to give a numerical rating on a scale 1 to 5 (1 = lowest and 5 = highest rating). The second and the third group were offered descriptive evaluation choices. However, among the possible answering choices for Survey 2, there were also such that stated explicit negative experience (Not useful at all), whereas the answering choices for Survey 3 varied from neutral to positive.

Table 1. Statistics about the experimental setting

Respondents: The experimental work is conducted over a population (both female and male) of 86 people, at the age of 20 -50. Its completion required no special technical knowledge, and subjects had no difficulty understanding the assignment. Respondents were divided into 5 groups. Three groups of 22 people were formed for each survey type. Table 1 were also additionally interviewed. The results from these interviews are presented in the final subsection. In addition to the three groups, another 20 users were asked to independently evaluate each review (10 users per review). They expressed their evaluations both numerically, as in Survey 1, and descriptively, as in Survey 2.

Results:

The following subsections show the major findings from this experimental study. Although the experiment was of relatively small scale, some interesting results were revealed with respect to the given objectives.

Distinction bias

As a first step in revealing the potential presence of cognitive bias in our experimental setting, we compare the results from the individually evaluated reviews with those obtained by the three surveys, where the two reviews were put together for evaluation.

The goal is to reveal the potential presence of a distinction bias, manifested as a tendency to view two options as more dissimilar when evaluating them simultaneously than when evaluating them separately. This bias is often exploited in commerce scenarios, when sellers aim to sell a certain product (anchor) by placing it along with another -decoy product that appears as the worse option when put together with the anchor [START_REF] Ariely | Predictably Irrational: The Hidden Forces That Shape Our Decisions[END_REF]. Fig. 1 presents the results from the 20 independent evaluations of the two reviews. The horizontal axis shows the rating values, whereas the vertical -the number of users who provided the rating. As shown, both reviews were evaluated as equally useful, 2 on a 1 to 5 scale, and descriptively qualified as Somewhat Useful. Fig. 2 shows the difference in ratings between the two reviews for each of the surveys.

Clearly, that they do not match with those shown in Fig1. In all three cases, Review 1 was evaluated as being better than Review 2. The mean values for the ratings of Review 1 and Review 2 for the three surveys are given in Table 2. Since preferences are often formed through distinction between given options, joint evaluation of recommendations may often result in a choice mismatch. The consequence is that the choice that appeared as the best option may not provide the best user experience, leading to dissatisfaction. Clearly, the issues of distinction bias and anchoring effect are important to account for in the design of RRR systems. The question is: what is the cause of those biases, what their effects are, and how to account for them in practice. The next section aims to provide the answer.

Numerical-Descriptive discrepancy and Positive Bias

In order to address distinction bias and anchoring effect, we must first understand if and how the presented evaluation choices affect the user opinion. This section investigates which of the descriptive surveys comes closest to the one with numerical ratings. The practical implication is in exploring if the current RRR systems that offer numerical ratings really match the user understanding about the meaning of those ratings. For that purpose, we compare the rating distributions of the two reviews for Survey 1 to those of Survey 2 and Survey 3. The results are shown in Fig. 3 and Fig. 4 respectively. It can be noticed that there is a good match for the distributions of Review 1 in both of the cases. However, compared to the distributions on Fig. 1, there is still a great difference between the average rating value for Review 1 (1.9) provided by the independent user evaluations, and the average rating value for Review

Positive bias and the Framing effect

In this section, we analyze the two surveys with descriptive evaluation choices. They differ slightly by the tone of positivism, although both offer five choices. Survey 2 contains more explicit negative statements, while the choices in Survey 3 vary from neutral to positive. The question we want to answer is How does a difference in descriptive choices affect users evaluation? To do that, we compare the rating distribution of the reviews for Survey 2 and Survey 3. The results are given in Fig. 5a) and b). They reveal large difference in the evaluations of the reviews between the surveys, although the offered choices differ only slightly. This demonstrates that people tend to draw different conclusions from the same information, depending on how that information is presented, known as the framing effect. On Fig. 5a), this effect is demonstrated as a slight smoothing of the exaggerated positives. Complementing these results with those shown on Fig. 2b), we can conclude that for Survey 2, the ratings for the two reviews also come close to each other. One interesting result is the high mean rating value for Review 2 in Survey 2. Compared to the results on Fig. 1, we see that the presence of a positive bias is higher when users are offered to chose between neg- ative-positive evaluations, compared to a setting where they are required to choose between neutral-positive. In the next section, we use these findings to form our proposal on how to address some of the issues of the explored biased behavior.

Proposal: Hidden signals and "shades of grades"

The remarkably higher number of neutral evaluations demonstrated by the experiment (Fig. 5b)), which is even higher than the positive evaluations for Review 2 (Fig. 5a)), not only confirms the reluctance of users to give negative ratings, but also points out the importance of neutral vote as a connector between negative and positive. In addition to introducing neutral as a "shade" between negative and slightly positive, another finding in our study is that introducing Very Useful as a shade between Quite Useful and Extremely Useful shifts the exaggerated positives towards lower ratings. Both of these effects smooth the effects from positive bias, but also better capture people"s perception of the offered choices. This might also explain why the offline model of social reputation succeeds to detect untrustworthy individuals without requiring consensus on someone"s trustworthiness. The offline world offers numerous opportunities to pick on the hidden clues behind people"s intentions. We consider the idea of introducing such hidden signals in the online RRR systems worth exploring. The framework we propose for addressing the presented issues of biased behavior can be summarized as follows: first, by accounting for the specific context elements, we propose disentangling the collaborative, competitive and the monetary elements when deciding on the RRR design. Second, by accounting for those context elements, a decision should be made about which of them are desirable as public features. Then, it is crucial to determine the right representation of publicly displayed features in a way that fits the users" perception of the feature"s meaning. Finally, by introducing hidden signals and shades of grades about the qualitative types of the entities, a better and more truthful distribution of the results can be obtained.

5.5

Closing the loop: The market of lemons on the market of opinions?

This section will close the loop of our study on cognitive bias by returning to the point where we started the discussion -context. The impact of context in the formation of cognitive bias required more interactive work with the respondents of the survey. Therefore, we additionally interviewed 30 people. The results are the following: Q1. If you know that, depending on the ratings given for their reviews, reviewers will get proportionally higher/lower amount of money, would you give the same grade? The purpose of these questions was to investigate the reasoning of the respondents as they were required to switch between contexts. The interview is of very small scale, but still pointed to new directions for reasoning about user behavior through the elaborated contextual elements. There is, however, a deeper meaning of the obtained results: the exaggerated positives, the slight change in evaluation options followed by high difference in evaluations, and the rest of the biases we explored, may be merely the effects of user behavior in RRR systems. Different combination of particular contextual elements leads to different manifestation of the effects from those biases. Introducing monetary elements must be done with great caution, as it may cause information to be treated as a limited resource of monetary value, or as a trading resource in the process of acquiring social capital. This in turn leads to squeezing entities (items, agents, users) of potentially high quality out of the system, leading to what we refer here to as "the market of lemons on the market of opinions".

Concluding Remarks and the Way Forward

Trust is a feeling, a model, and a reality, with people in their core. Understanding how they work and how closely they resemble each other is essential for their design practices. Our work detected and analyzed context, risk, dynamics and privacy as factors that influence both the work of RRR systems and the users" understanding of that work. We explored the relation between RRR systems and user behavior with respect to those factors and analyzed few types of biases exhibited through the users" online experiences with RRR systems. In an experimental study that included 86 users, we found that users exhibit distinction bias, positive bias, anchoring effect, and framing effect. These have not been investigated in such a holistic manner for any of the current RRR systems. Based on the identified factors and the findings of the experimental study, we proposed a framework for tackling some of the issues attributed to users" biased behavior and address the possibility of employing hidden signals and shades of grades in the RRR systems for the purpose of capturing some of the detected biases.

Our future work will concentrate on investigating more the factor of dynamics. As we already referenced Perceptual control theory and Subjective Logic as an apparatus that provides formal reasoning with respect to human beliefs and perceptual behavior, the major part of our work will be directed towards joining the ideas of the two and employing them to formalize trust relationships under biased user behavior.

Fig. 1 .

 1 Fig. 1. Rating distribution for each review by offline users a) Numerically b) Descriptively

Table 2 .Fig. 2 .

 22 Fig. 2. Rating Distribution for the two reviews for a) Survey 1, b) Survey 2 and c) Survey 3

Fig. 3 .

 3 Fig. 3. Difference in Rating Distribution between Survey 1 and 2 for a) Review1 b) Review2

Fig. 4 .

 4 Fig. 4. Difference in Rating Distribution between Survey 1 and 3 for a) Review1 b) Review2

Fig. 5 .

 5 Fig. 5. Difference in Rating Distribution between Survey 2 and 3 for a) Review 1; b) Review 2

  22 answered: No, one or two grades lower. 1 was Not Sure; 7 answered Yes; Q2. What if you yourself were a reviewer and the amount of money you would get depended on the amount of money other reviewers for the same product get? 27 answered Definitely a lower grade; 3 answered Still the same grade. The 3 who gave the 2b) answer were additionally asked: Q3. If you see that the opinion you consider of low quality is the one that got the highest number of votes, would you reason the same the next time? 2 answered: No; 1 answered Yes.

  summarizes these statistics. 30 of the 66 survey respondents

	Survey Info.		Type of Survey
	Respond.	Survey 1	Survey 2	Survey 3
	Info.	1-5 Num. Feedback	Neg.Descriptive	Neutral-Pos. Descriptive	Total
		1	Not useful at all	Neutral
		2	Hardly useful	Somewhat useful
	Answering choices	3	Somewhat useful	Quite useful
		4	Quite useful	Very useful
		5	Extremely useful	Extremely useful
	Responded	22	22	22

http://www.youtube.com/creators/

http://gigaom.com/video/real-or-robot-the-lisanova-controversy/

www.surveymonkey.com

www.epinions.com

Acknowledgments. Authors wish to thank Tomaž Klobučar, Dušan Gabrijelčič and Borka Jerman Blažič for the devoted time and energy, their opinions, critiques, and immensely beneficial discussions regarding the topics of this work.

Appendix: Survey Questions (Reviews) Review 1: User Rating: OK; Ease of Use: 2;Quality of Tech Support: 1 Pros:1)Intel core i3 processor;2)Finger Print Sensor;3)Battery life Cons:1)Build material;2)Intel integrated graphics;3)320GB hard disk space The Bottom Line: This laptop is not recommended to any one, because of poor support quality. The products of HP were good 3 years ago. People loved them for their looks, reliability, performance and budgeted price. But after 2008 the reliability ratio of HP as compared to its competitors is far below in almost all aspects including price, performance, looks and the most important reliability. I myself was a big fan of this company but after facing the failure of consecutively two the PCs' from this company, I changed my view. My wife had this laptop and I bought this laptop for her as her birthday present three months ago, but just after two months, the screen got dead spot (small black spots) and the hing connecting the screen with keyboard also got broken. Still the laptop was running fine but last week its keyboard also stopped working, which sucks. All the money I paid for it gone in vain. My experience about: PROCESSOR: Intel core i3 processor clocked at 2.1 GHZ works really very fine for multitasking but it is not designed to handle more tasks. This pc is fine for web-surfing, word-processing, office work, watching movies. GRAPHICS: Intel integrated graphics are not capable of running blue ray movies silky smooth. BUILD MATERIAL: This laptop is made of seriously very cheap plastic. Its glossy surface is just a fingerprint magnet and you have to clean up the laptop after every single use. The glossy screen also causes panic while watching movies in sunlight. LACK OF HDMI PORT: This laptop lacks some of the most important port which is included in the laptops of this price range, i-e; HDMI port. The sound quality is good, battery life is also impressive and last about 3 hours (6 cell) even when watching movies. The security feature like Finger Print Sensor works great. Its light weight makes it easier to carry this laptop everywhere but it can't be called ultraportable laptop. Over all this laptop isn't recommended to any one whether the person is student or house wife.

[Recommended: No] Review 2: User Rating: Excellent; Ease of Use: 5; Quality of Tech Support: 4 Pros: I would buy another computer from HP Cons: multiple hardware faults. (i.e hard to type and sensitive mouse pad) HP ProBook 4530s is a extremely good product. The computer is lightweight and rugged. It's able to be put in a backpack and stuffed wherever you need to go. When i bought and received the computer i liked how the computer didn"t come with a lot of extra software junk. Next, i like having a numeric pad and i will continue to buy computers with them from now on. For just web browsing and playing light computer games this computer is extremely fast. The key pad is not sensitive enough and i have to hit the keys hard a lot. Also if you have multiple fingers close to the mouse pad, the mouse pad goes crazy due to its many settings. The speaker system is excellent the loudest system i have heard on any computer system. The software for the finger ID gets weird every now and then i have to input my fingers a couple of times to log in. The settings are easy to change on the computer. The battery life is average to other computers. The computer hardware is nicely laid out and easy to find. Computer is worth the price i paid for it. [Recommended: Yes]


Mihir R Gohel
email: mihirgohel@gmail.com

Bhavesh N Gohil
email: bngohil06@gmail.com

A New Data Integrity Checking Protocol with Public Verifiability in Cloud Storage

Keywords: cloud storage, data integrity, public verifiability, Trusted Third Party Auditor (TPA)

Cloud computing is the long dreamed vision of computing as a utility, where users can remotely store their data into the cloud so as to enjoy the on-demand high quality applications and services from a shared pool of configurable computing resources. By data outsourcing, users can be relieved from the burden of local data storage and maintenance. It also eliminates their physical control of storage dependability and security, which traditionally has been expected by both enterprises and individuals. This unique paradigm brings about many new security challenges, which need to be clearly understood and resolved. This work studies the problem of ensuring the integrity of data storage in Cloud Computing. To ensure the correctness of data, we consider the task of allowing a third party auditor (TPA), on behalf of the cloud consumer, to verify the integrity of the data stored in the cloud. This scheme ensures that the storage at the client side is minimal which will be beneficial for thin clients.

Introduction

A new computing technology in today's world, called cloud computing, has been enabled to reality because of the rapid development of processing and storage technologies, ubiquitously available Internet, cheaper and more powerful computing resources than ever before. In this cloud computing technology, computing resources (e.g., CPU and storage) are provided as general utilities that can be leased or released by users in an on-demand fashion. In a cloud computing environment, the role of service provider is divided into two: the infrastructure providers who manage cloud platforms and lease resources according to a usage-based pricing model, and service providers, who rent resources from one or many infrastructure providers to serve the end users. The emergence of cloud computing has made a immense impact on the Information Technology (IT) industry over the past few years, where large companies such as Google, Amazon and Microsoft, IBM endeavor to provide more powerful, reliable and cost-efficient cloud platforms, and small and medium business (SMB) enterprises try to reshape their business models to gain benefits from this new paradigm.

The cloud computing offers several benefits like scalability, rapid elasticity, ubiquitous network access, rapid deployment, pay-as-you go lower cost, low cost disaster recovery and data storage solutions. While cloud offers these advantages, it also must ensure that they get the security aspects right.

One fundamental facet of this computing model is that data is being centralized or outsourced into the cloud. From the data owners' perspective, storing data remotely in a cloud brings the new and challenging security threats to the outsourced data. Since cloud providers (CP) are separate, data outsourcing actually relinquishes the owner's ultimate control over the fate of their data. As a result, the correctness of the data in the cloud is put at risk due to the various reasons. Although the infrastructures under the cloud are much more powerful and reliable than personal computing devices, they still face a broad range of both internal and external threats to data integrity.

For benefits of their own, there are various motivations for CPs to behave unfaithfully toward Cloud Consumers regarding the status of their outsourced data. For example, the storage service provider, which experiences Byzantine failures occasionally, may decide to hide the data errors from the clients. Other examples include CPs, for monetary reasons, reclaiming storage by discarding data that has not been or is rarely accessed [START_REF] Juels | PORs: Proofs of Retrieva ility for Large Files[END_REF], or even hiding data loss incidents to maintain a reputation [START_REF] Ateniese | Prova le Data Possession at Untrusted Stores[END_REF].

As data owners no longer physically possess the storage of their data, traditional cryptographic primitives for the purpose of data security protection cannot be directly adopted [START_REF] Juels | PORs: Proofs of Retrieva ility for Large Files[END_REF][START_REF] Ateniese | Prova le Data Possession at Untrusted Stores[END_REF]. In particular, simply downloading the data for its integrity verification is not a practical solution due to the high cost of I/O and transmission across the network. Considering the large size of the outsourced data and the owner's constrained resource capability, the tasks of auditing the data correctness in a cloud environment can be expensive for data owners [START_REF] Juels | PORs: Proofs of Retrieva ility for Large Files[END_REF][START_REF] Ateniese | Prova le Data Possession at Untrusted Stores[END_REF]. Moreover, from the system usability point of view, data owners should be able to just use cloud storage as if it is local, without worrying about the need to verify its integrity.

In this paper, we are dealing with the problem of implementing a protocol for Public verifiable remote data integrity check, where data owners can resort to an external third party auditor (TPA) to verify the integrity of outsourced data when needed. Third party auditing provides a transparent yet cost-effective method for establishing trust between data owner and cloud server. Public verifiable remote integrity check relaxes users from the computation and online burden for periodical integrity check, especially desirable when the user is equipped with a low end computation device (e.g. smart phone, PDA) or is not always connected to the Internet.

 We propose a data integrity checking protocol for cloud storage, which can be viewed as an adaption of Sravan Kumar et al.'s protocol [START_REF] Kumar | Data integrity proofs in cloud storage[END_REF]. The proposed protocol inherits the protocol for data integrity verification, and supports public verifiability.  The problem is further complicated by the fact that the owner of the data may be a small device, like a PDA or a mobile phone, which have limited CPU power, battery power and communication bandwidth. Hence a data integrity proof that has to be developed needs to take the above limitations into consideration. The scheme should be able to produce a proof without the need for the server to access the entire file or the client retrieving the entire file from the server. Also the scheme should minimize the local computation at the client as well as the bandwidth consumed at the client.

Related Work

The simplest Proof of data integrity can be made using a keyed hash function (F).

In this scheme the Cloud Consumer (CC), before archiving the data file F in the cloud storage server (CSS), pre-computes the cryptographic hash of F using (F) and stores this hash as well as the secret key K. CC transfers this key and pre-computed hash value to Trusted Third Party Auditor (TPA), to verify the integrity of the file F at regular interval. To check if the integrity of the file F is lost the TPA releases the secret key K to the cloud archive and asks it to compute and return the value of (F). By storing multiple hash values for different keys the verifier can check for the integrity of the file F for multiple times, each one being an independent proof. Though this scheme is very simple and easily implementable the main drawback of this scheme are the high resource costs it requires for the implementation. At the verifier side this involves storing as many keys as the number of checks it want to perform as well as the hash value of the data file F with each hash key. Also computing hash value for even a moderately large data files can be computationally burdensome for some clients (PDAs, mobile phones, etc). At the archive side, each invocation of the protocol requires the archive to process the entire file F. This can be computationally burdensome for the archive even for a lightweight operation like hashing [START_REF] Kumar | Data integrity proofs in cloud storage[END_REF].

Recently, much of growing interest has been pursued in the context of remotely stored data verification [START_REF] Juels | PORs: Proofs of Retrieva ility for Large Files[END_REF][START_REF] Ateniese | Prova le Data Possession at Untrusted Stores[END_REF][START_REF] Kumar | Data integrity proofs in cloud storage[END_REF][START_REF] Jianhong | Secuirty storage in the Cloud Computing: A RSA-based assumption data integrity check without original data[END_REF][START_REF] Nepal | DIaaS: Data Integrity as a Service in the Cloud[END_REF]. Zhang and Chen have proposed an Integrity check scheme based on well-known RSA Security assumption called A RSA-based Assumption Data Integrity Check without Original Data [START_REF] Jianhong | Secuirty storage in the Cloud Computing: A RSA-based assumption data integrity check without original data[END_REF]. In which they uses the concept of Random Oracle Model and RSA to verify the intactness of data. The proposed scheme is proven to be secure in Random oracle model.

Surya et al. have also proposed a protocol for the same called Data Integrity as a Service (DIaaS) [START_REF] Nepal | DIaaS: Data Integrity as a Service in the Cloud[END_REF]. The proposed protocol needs to have complex infrastructure to be implemented. i.e., Trust Management Service (TMS), Cloud Storage Service (CSS), Key Management Service (KMS) and Integrity Management Service (IMS). The proposed protocol also performs more no. of encryptions and hashing to verify the integrity.

Ari Juels and Burton S. Kaliski Jr. proposed a scheme called Proof of retrievability for large files using "sentinels" [START_REF] Juels | PORs: Proofs of Retrieva ility for Large Files[END_REF]. In this scheme, unlike in the key-hash approach scheme, only a single key can be used irrespective of the size of the file or the number of files whose retrievability it wants to verify. In this scheme special blocks (called sentinels) are hidden among other blocks in the data file F. To make the sentinels indistinguishable from the data blocks, the whole modified file is encrypted and stored at the archive. As this scheme involves the encryption of the file F using a secret key it becomes computationally cumbersome especially when the data to be encrypted is large. Hence, this scheme proves disadvantages to small users with limited computational power (PDAs, mobile phones etc.) [START_REF] Kumar | Data integrity proofs in cloud storage[END_REF]. The schematic view of this approach is shown in Figure 1. Sravan Kumar R and Ashutosh Saxena have proposed scheme for data integrity proof [START_REF] Kumar | Data integrity proofs in cloud storage[END_REF], which does not involve the encryption of the whole data but encrypts only few bits of data per data Block, thus reducing the computational overhead on the clients. The client storage overhead is also minimized as it does not store any data with it. So the scheme suits well for thin clients. But the proposed scheme restricts the remote data verifiability to private only. It doesn't allow any third party auditor to verify the integrity of data, on behalf of client. The clients themselves need to devote their computation resources to perform frequent integrity checks. Hence, this scheme burdensome the client.

The Proposed Data Integrity Checking Protocol in Cloud Storage with Public Verifiability

In our proposed data integrity protocol, we inherit the support of data integrity from [START_REF] Kumar | Data integrity proofs in cloud storage[END_REF], and support of TPA from Qian Wang et al. [START_REF] Qian | Ena ling pu lic verifia ility and data dynamics for storage security in cloud computing[END_REF]. In our proposed data integrity protocol, the client doesn't need to store any data with it. Verifier needs only a single cryptographic key and two functions which generate a random sequence. The client before storing the file at the archive, preprocesses the file and appends some meta data to the file and stores at the archive. The client then transfers the key and functions to the TPA to audit the file frequently. At the time of verification the TPA uses this meta data to verify the correctness of data. Our proposed scheme neither prevents the archive from modifying or deletions data nor preserves data privacy against TPA. Representative network architecture for cloud data storage with TPA is illustrated in Fig. 2.

Setup phase

Let the client C wishes to the store the file F with the archive. Let this file F consist of n file blocks. We initially preprocess the file and create metadata to be appended to the file. Let each of the n data blocks have m bits in them. The initial setup phase is represented in Fig 3 and can be described in the following steps: 1) Generation of metadata: Let g be the function defined as

( ) * + * + * + (1)
Where is the number of bits per data block which we wish to read as meta data. The function generates for each data block a set of bit positions within the bits that are in the data block. Hence ( ) gives the bit in the data block. The value of is in the choice of the client and is a secret known only to him. Therefore for each data block we get a set of bits and in total for all the blocks we get * bits. Let represent the k bits of meta data for the block. 2) Encrypting the meta data: Each of the meta data from the data blocks is encrypted by using a suitable algorithm to give a new modified meta data . Without loss of generality we show this process by using a simple XOR operation. Let be a function which generates a bit integer for each .

* + (2)
For the meta data ( ) of each data block the number is added to get a new bit number .

(3)

In this way we get a set of new meta data bit blocks.

3) Appending of meta data: All the meta data bit blocks that are generated using the above procedure are to be concatenated together. This concatenated meta data should be appended to the file F before storing it at the cloud server. The file F along with the appended meta data ̌ is archived with the cloud.

4) Transferring the meta data attributes to TPA: Client now transfers the two functions and to trusted TPA. TPA audits the file F archived with cloud by using these two functions g and h at the time of data integrity verification.

Fig. 3. (a)

A data file F with n data blocks (b) a data block j, having m bits, is selected to preprocess c randomly selected its outcome of function g d preprocessed its are appended to data file F, the encrypted file F will e stored at cloud.

Verification phase

Let the TPA want to verify the integrity of the file F. It throws a challenge to the archive and asks it to respond. The challenge and the response are compared and the TPA accepts or rejects the integrity proof. Suppose the TPA wishes to check the integrity of block. The TPA challenges the cloud storage server by specifying the block number and a bit number generated by using the function . The TPA also specifies the position at which the meta data corresponding the block is appended. This meta data will be a bit number. Hence the cloud storage server is required to send bits for verification by the client. The meta data sent by the cloud is decrypted by using the Number and the corresponding bit in this decrypted meta data is compared with the bit that is sent by the cloud. Any mismatch between the two would mean a loss of the integrity of the clients' data at the cloud storage.

Conclusions and Future Works

To ensure cloud data storage security, it is critical to enable a third party auditor (TPA) to evaluate the service quality from an objective and independent perspective. Public verifiability also allows clients to delegate the integrity verification tasks to TPA while they themselves can be unreliable or not be able to commit necessary computation resources performing continuous verifications.

In this paper we have worked to facilitate the client in getting a proof of integrity of the data. Our proposed scheme is developed to reduce the computational and storage overhead of the client with public verifiability as well as to minimize the compu-tational overhead of the cloud storage server. We also minimized the size of the proof of data integrity so as to reduce the network bandwidth consumption.

At the client we only store two functions, the bit generator function g, and the function h which is used for encrypting the data. Hence the storage at the client is very much minimal compared to all other schemes [1-2, 4-5] that were developed. Hence this scheme proves advantageous to thin clients like PDAs and mobile phones.

Our scheme applies only to static storage of data. If archived file modifies dynamically, then client has to preprocess the file each time he modifies the file. Also scheme doesn't preserve privacy of data against TPA. Hence developing on this will be a future challenge.

Fig. 1 .

 1 Fig.1. Schematic views of a proof of retrievability based on inserting random sentinels in the file F[START_REF] Juels | PORs: Proofs of Retrieva ility for Large Files[END_REF]

Fig. 2 .

 2 Fig. 2. Cloud Data Storage Architecture with TPA [6].


Gérard Le Lann

On safety in ad hoc networks of autonomous and communicating vehicles: A rationale for time-bounded deterministic solutions

Keywords: Vanets, Strings, Self-Driving Vehicles, Safety, MAC Protocols, Reliable Inter-Vehicular Communications, Time-Bounded Message Dissemination, Agreements, Anonymity

Ad hoc networks of autonomous vehicles endowed with inter-vehicular communication (IVC) capabilities are in our future. Avoidance of accidents in safety-critical (SC) scenarios is a major concern. We show that IVCs can "solve" safety-related problems that are not within the grasp of sensing/robotics. A rigorous definition of SC IVCs is given, based on the Bounded Move (BM) requirements. Longitudinal SC scenarios in ad hoc strings and lateral inter-string SC scenarios as they arise on highways are examined. Since current WAVE standards (IEEE 802.11p, ETSI ITS-G5) fail to meet the BM requirements by huge margins, novel solutions are sought. We present the cohort construct-a string with a specification, a deterministic MAC protocol that also achieves fast string-wide message dissemination, and two distributed agreement algorithms. Worst-case time bounds achieved by these solutions are given, showing that they meet the BM requirements. Anonymity issues are briefly addressed.

Introduction

Vehicular networks range from platoons with a lead vehicle piloted by a human driver to open ad-hoc vehicular networks, a.k.a. VANETs, comprising communicating autonomous vehicles. Safety issues appear to be the least studied in this area. The focus of our work is on safety-critical (SC) scenarios, where severe accidents (severe injuries and fatalities) inevitably occur when such scenarios are not handled correctly. In addition to on-board sensing/robotics, IVCs are considered for achieving safety properties. Since both technologies have known intrinsic limitations (in addition to experiencing temporary or permanent failures), using them redundantly is mandatory for meeting safety regulations. We show that IVCs can "solve" safety-related problems that are not within the grasp of sensing/robotics. We consider VANETs on highways, which are settings where velocities can be very high, thus exacerbating safety problems-acceptable delays in cyber space, and response times in the physical space, shall be very small. Human lives being at stake, delays in cyber space must have strict and proven upper bounds under worst-case conditions (vehicular density, channel contention, concurrency and failures). We are thus led to look for deterministic solutions, radically different from today's WAVE standards. Upper bound for MAC access delays (resp., message dissemination or agreement delays) is denoted λ (resp., Δ).

Safe automated driving on highways and today's WAVE standards

In the current ITS literature, the term "safety" is used without being given a precise definition. That must be corrected. In our case, a fundamental open question is: What is the exact meaning of "safety criticality"? We have devised unambiguous definitions, stated as the Bounded Move (BM) requirements-see Subsection 3.1. Via discussions with foreign colleagues active in the IEEE 802 Committee, we have comforted our early diagnosis regarding today's WAVE standards for V2X communications (IEEE 802.11p and ETSI ITS-G5): designed for providing "best effort" V2V and V2I communications (mobile access to Internet and cloud services (infotainment, weather data, traffic conditions, etc.)), they are inappropriate for the handling of SC IVCs. A major weakness lies with CSMA/CA (MAC-level protocol). Obviously, there cannot be such bounds as λ and Δ with CSMA/CA. Moreover, stochastic average delays in moderate/worst-case contention conditions are exceedingly high, due to medium-range omnidirectional communications, radio (resp., interference) range in the order of 250 m (resp., 400 m). Consider the following highway setting, not uncommon at pick hours in many countries: 3 lanes each direction and dense traffic (1 vehicle per 12.5 m). A simple calculation leads to the following result: any vehicle may experience (destructive) interferences from up to 384 vehicles. Even if one assumes some "reasonable" communications activity ratio, say 25%, one finds that up to 96 vehicles may be contending for channel access. Under such conditions, current WAVE standards fail to meet the BM requirements by huge margins. This is shown in [Y13] where MAC delays induced by the IEEE 802.11p protocol are evaluated via analytical modeling and NS-2 simulations. For various channel loads, assuming 1 vehicle every 12 m, highest stochastic delays range between 75.3 ms and 211.8 ms. Requirement BM 0 is not met with such values for λ (worst-case delays are theoretically unbounded). Lack of acknowledgements with multicast and broadcast communications is another major weakness. It is simply impossible to argue about safety (even less to prove safety) when a sender does not know whether a message carrying SC data has been correctly delivered to intended recipients or has been lost. Reliance on V2I communications via terrestrial infrastructures and nodes, such as road-side units (WAVE, WiFi, LTE or 5G relays), rather than direct V2V communications, can only lead to poorer results. Reachability is not guaranteed since SC conditions may develop anywhere anytime, far away from a terrestrial node. Mixing SC communications and ordinary communications within terrestrial nodes is a violation of the very fundamental segregation/isolation principle in SC applications. Security threats are safety threats since it is very easy to jam or to spy on a terrestrial node. Moreover, terrestrial nodes may be used for launching all sorts of attacks, man-in-the-middle attacks for example. Delays can only get worse than with direct V2V communications, since transiting via a node inevitably introduces additional latencies. The delivery of every SC message must be acknowledged, which exacerbates the latency problems. What happens when a terrestrial node fails? Trying to tweak existing WAVE standards is vain and unjustified. Since collisions can only involve vehicles that are very close to each other, short-range directional communications suffice. Novel solutions for SC IV communications and SC IV coordination are briefly presented in Subsections 3.2 and 3.3. Message passing with these solutions is anonymous-see Subsection 3.4. Future standards specifically aimed at SC IVCs may emerge from solutions similar to those presented herein.

Recent results

Solutions to safety related problems necessarily rest on worst-case analyses. They can only be conducted with constructs that have specifications, also necessary for reasoning about (and proving) properties. Cohorts-strings with a specification [START_REF] Lann | Safety in vehicular networks-On the inevitability of short-range directional communications[END_REF], appear to be an early example of cyber-physical constructs appropriate for ad hoc vehicular networks. The cohort concept, originally devised for minimizing the number of vehicles involved in a collective rear-end collision, has proven to be fruitful regarding safety-related problems in general. A cohort that moves at velocity v cannot comprise more than n*(v) members [START_REF] Lann | Safety in vehicular networks-On the inevitability of short-range directional communications[END_REF]. In [START_REF] Lann | A collision-free MAC protocol for fast message dissemination in vehicular strings[END_REF], we have refined this concept as follows, so as to mirror real mobility patterns: n*(v) is an inverse function of v, i.e. the fastest the smallest (or vice versa). Which we write as follows: v.n*(v) ≤ b. Values of bound b may be part of future standards aimed at safety. (String and cohort are used interchangeably in the sequel.)

The Bounded Move (BM) requirements

Safety related problems would receive trivial solutions if one could assume that vehicles involved in a SC scenario do not move while messages are being exchanged. Since this is unrealistic, the best we can aim at is to quantify distances travelled in worst-case conditions. That is the purpose of the BM requirements, where σ stands for the smallest "car slot" (σ = smallest car size + smallest IV gap), i.e. 7 m approximately: -BM 0 : a MAC protocol is acceptable only if the distance travelled in λ time units by any vehicle is significantly smaller than σ.

-BM 1 : a string-wide acknowledged message dissemination algorithm is acceptable only if the distance travelled in Δ d time units by any vehicle is smaller than σ.

-BM 2 : a string-wide or an inter-string agreement algorithm is acceptable only if the distance travelled in Δ a time units by any vehicle is smaller than 2σ. Solutions to safety related problems that come with no worst-case time bounds simply cannot be trusted, since it is impossible to tell whether they meet such requirements or any others equally constraining and unambiguous. Bounds λ and Δ are established by resorting to analytical calculus. Simulations are irrelevant. Our solutions can be compared against other protocols/algorithms only if their worst-case time bounds are given (not our duty), be they obtained by analytical calculus, asymptotic analyses, or (max,+) algebra-to name a few possibilities.

SWIFT: A deterministic MAC protocol and an efficient algorithm for string-wide dissemination of acknowledged messages

In cohorts, members assign themselves consecutive integers, called ranks, starting from 1 for an isolated vehicle. See for how ranks are computed whenever cohort membership is modified. SWIFT, a collisionfree MAC protocol, is based on member ranking and small beamwidth directional RF antennas that are power controlled [START_REF] Bazan | A survey on MAC protocols for wireless ad hoc networks with beamforming antennas[END_REF]. They can be built out of WAVE conformant omnidirectional antennas. The level of power used by a vehicle that transmits a 1-hop LOS neighbor-to-neighbor (N2N) message to its predecessor or its successor is a function of the gap (approx. a 2-15 m range) with the targeted neighbor. Short range power control does not eliminate interferences with vehicles beyond a targeted neighbor. Via a worst-case analysis, one finds h, the highest number of contiguous members that are within the interference range of a transmitter. Integer h is a measurement of spatial reuse. Lobes of small beamwidth antennas may encompass adjacent lanes. This is taken into account in the design of SWIFT, which rests on a slotted channel, aligned to UTC, thanks to GPS receivers, backed by on-board clocks. Cheap clocks suffice, since drifts need not be small. Channel slot allocation is conducted according to ranks. Every member owns 2 slots per frame (2h slots in each frame), h slots serviced downstream, followed by h slots serviced upstream. Members which own the same rank modulo h can transmit in the same time slot, in the same direction, without interfering with each other. Since h is a small integer, spatial reuse is good. Fast symmetrical string-wide dissemination of acknowledged N2N messages mandates that the ordering of channel accesses must match the ranking and the counter-ranking of members, which is not feasible with CSMA/CA or TDMA protocols-SWIFT is not equivalent to conventional TDMA [H15]. Acknowledgements of N2N messages sent in one direction are piggybacked on N2N messages flowing in the opposite direction, entailing a negligible overhead. String-wide message dissemination serves to build common knowledge, which is essential for achieving SC IV coordination. We have established the following bounds: -Worst-case channel access delay: λ = 2hθ, θ standing for the largest message transmission duration.

-Worst-case string-wide acknowledged message dissemination delay in the presence of f faulty N2N links, for a string comprising n members and moving at velocity v:

Δ d (n,f) = 2hθ {f +1+ (n-1)/h}, n ≤ n*(v).
Considering conservative numerical figures (h = 4, θ = 1 ms), one finds λ = 8 ms, i.e. 0.56 m for v = 250 km/h (highest velocity referred to in WAVE standards). Requirement BM 0 is met. Valuation of bound b is not arbitrary. With v in km/h, and n*(250) = 4 (highest number of rear-end collisions in "brick wall" conditions), we have b ≤ 1,000. Let us check Δ d for two extreme cases: v = 180 (n* = 5) and v = 10 (n* = 100). Assuming up to 1 loss (message or acknowledgement) per N2N link, not leading to a string split, we have f < n*. One finds (dist standing for distance travelled): Δ d (5,4) = 48 ms, and dist ≤ 2.4 m; Δ d (100,99) = 1 s, and dist ≤ 2.78 m. Requirement BM 1 is met, despite the fact that every N2N message must be sent twice. Assuming no losses, we find: Δ d (5,0) = 16 ms, and dist ≤ 0.8 m; Δ d (100,0) = 208 ms, and dist ≤ 0.58 m. Note the significant reductions in distances travelled. This shows that results regarding safe or/and "cooperative driving" with IVCs (e.g., CACC) based on ignoring message losses are of limited practical relevance.

Time-bounded distributed agreements

Eligo and LHandshake [START_REF] Lann | Fast distributed agreements and safety-critical scenarios in VANETs[END_REF] are distributed agreement algorithms aimed at achieving safe IV coordination in the presence of concurrent conflicting events and/or inputs to agreement, referred to as "proposals". Timebounded agreement (TBA) problems arise whenever p members, 1 < p ≤ n, issue conflicting proposals concurrently, entailing unfeasible maneuvers (e.g., acceleration request(s) and string split request, or deceleration request(s) and string insertion request(s)). (Concurrency issues are almost totally ignored in the literature devoted to IV coordination.) All string members shall reach the same decision D in bounded time, at UTC times comprised within an interval of size ε. Stipulated properties are as follows: -Validity: Decision value D = Ψ{proposed values}.

-Agreement: No two members decide differently.

-Time-Bounded Termination: Every member decides in at most Δ a time units.

-Synchronicity: ε shall be such that the difference between distances travelled by the member earliest to post D and the latest to do so is an order of magnitude smaller than σ. Ψ stands for any appropriate function in cyber-physics. Eligo (I choose in Latin), which builds on SWIFT, solves the TBA problem in strings, achieving bound Δ a denoted Δ swa . LHandshake, which builds on Eligo, solves the TBA problem as it arises in sets of strings circulating in adjacent lanes, achieving bound Δ a denoted Δ isa . Extending the results given in [START_REF] Lann | Fast distributed agreements and safety-critical scenarios in VANETs[END_REF], we have Δ swa (n,f,p) = 2hθ {1+p+2[f + (n-1)/h}. Assume p = (n/10. Let us check that Eligo meets BM 2 in both cases. v = 180 km/h: Δ swa (5,0,1) = 32 ms, and dist ≤ 1.6; Δ swa (5,4,1) = 96 ms, and dist ≤ 4.8. v = 10 km/h: Δ swa (100,0,10) = 488 ms, and dist ≤ 1.36; Δ swa (100,99,10) = 2.072 s, and dist ≤ 5.76. • Worst-case lateral inter-String agreement delays. Let g stand for the number of consecutive members that must reach agreement, e.g., that receive an insertion request from an adjacent vehicle (g < 5 in realistic cases). We have shown that LHandshake achieves Δ isa (g,f,p) = 2σ max +Δ swa (g,f,p), where σ max stands for the worst-case delay involved with transmitting and delivering a V2V message (a join request, a response), MAC access delay included. Whether LHandshake meets the BM 2 requirement depends fully on σ max , which may take unbounded values with WAVE standards. Novel protocols for lateral V2V communications are sought (on-going work).

The broadcasting of medium-range omnidirectional V2V messages is believed to suffice for coping with non-LOS SC scenarios, e.g., accidents. Alas, the reliable broadcast problem has no time-bounded solutions-the case with VANETs (see Section 2). Something else is needed for coordinating the behaviors of vehicles heading toward crashed vehicles (brutal braking and random lane changes lead to more accidents) or crossing an intersection with no traffic lights safely and efficiently. For the latter case, circumventing impossibility results appears feasible with cyber-physical solutions (the cohort construct and hybrid radio/optical communications).

Naming and anonymity

IP/MAC addresses appear in WAVE conformant V2V messages. Periodic beaconing (1-10 Hz) is based on assuming that beacons are delivered reliably, and in time (to be useful), a flawed assumption. The building of inaccurate "maps" of proximate vehicles contributes to overloading communication channels and on-board computers. There are better ways for building situational awareness. Finally, doing this amounts to breaching anonymity voluntarily. Every vehicle reveals its existence and time-dependent geolocations to unknown recipients within a disc of radius in the order of 250 m, making tracking, spying and hacking much easier. Solutions based on pseudonyms issued by a trustable third party (a cloud-based authentication body) cannot be considered either: they rest on V2I communications, and they suffer from known limitations [W10]. Names that appear in N2N messages are integers (member ranks). There is no possible linkage between such names and identifiers proper to a vehicle (IP/MAC addresses, plate number). Moreover, rank/vehicle mappings change arbitrarily often in ad hoc vehicular strings. Consequently, tracking, spying or hacking are hardly feasible, only by an adjacent vehicle within the directional lobe of the targeted "victim". Which eavesdropper would be interested in learning that an adjacent string decides to set its velocity to 55 km/h? Authentication issues do not arise within a string (no masquerading is feasible with ranks). Across strings, there are simple solutions based on hybrid radio/optical communications. None of these properties hold with today's WAVE standards.


Arnaud Casteigts

Ralf Klasing

Yessin M Neggaz

Joseph G Peters

Calcul

Calcul de paramètres minimaux dans les graphes dynamiques

Keywords: Réseaux dynamiques, Test de propriétés, Généricité, Connexité temporelle

à 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

Over the last decade, research has highlighted the importance of characterizing and testing properties in dynamic networks, studying patterns, and analyzing their dynamics. These networks can be modelled in various ways. When time is discrete, a common model is to represent the network as a sequence of static graphs G = {G 1 , G 2 , ..., G δ }, where each G t = (V, E t ) represents the state of the network at a time t (a.k.a. untimed evolving graphs). In [START_REF] Casteigts | Tester efficacement la T-intervalle connexité dans les graphes dynamiques[END_REF], we presented an optimal solution to the problem of computing a stability parameter called T -interval connectivity, i.e. the largest T such that all graphs in every consecutive subsequence of length T share a common connected spanning subgraph. The algorithm operates at a high level, manipulating the graphs in the sequence as atomic elements with two types of operations: a composition operation and a test operation. Using intersection of two graphs as the composition operation and connectivity of a graph as the test operation, a hierarchy of intersection graphs is built such that the whole sequence is T -interval connected if and only if all the composed graphs in row T of the hierarchy are connected (see Figure 1a for an illustration). The algorithm "walks" within this hierarchy building the required graphs on demand. The walk strategy is optimal in that the algorithm computes the maximum value of T using only O(δ) intersections and connectivity tests.

In this paper, we generalize this framework to use various composition and test operations, which yields solutions to other problems using the same strategy that we used for T -interval connectivity. We formulate a minimization version of the strategy (T -interval connectivity is a maximization problem) and illustrate it with three pairs of composition and test operations. These operations make it possible to compute three parameters that relate to specific properties of dynamic networks discussed in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]. They are (1) BOUNDED-REALIZATION-OF-THE-FOOTPRINT, where the goal is to find the smallest duration d such that if any edge is present in some G i (with i ≤ δd), then it must be present again in some G i with i ≤ i + d; (2) TEMPORAL-DIAMETER, where the goal is to find the smallest duration d such that a temporal path (journey) exists between every pair of nodes in every window of size d (see e.g. [START_REF] Huyghues-Despointes | Forte ∆-connexité dans les flots de liens[END_REF]); and (3) ROUND-TRIP-TEMPORAL-DIAMETER, which asks the same question for back and forth journeys (which is not the same as solving the second problem twice).

By using the proposed general framework, we can reuse most of the high-level logic of the algorithm and focus instead on the specific aspects of each problem through the composition and testing operations. This approach is especially relevant when the changes between two consecutive graphs are arbitrary. If that is not the case, or if the graphs are sparse, then using low level dedicated data structure might be a more relevant approach.

G 1 G 2 G 3 G 4 G (1,1) G (2,2) G (3,3) G (4,4) G (5,5) G (6,6) G (7,7) G (8,8) G (1,2) G (2,3) G (3,4) G (4,5) G (5,6) G (6,7) G (7,8) G (1,3) G (2,4) G (3,5) G (4,6) G (5,7) G (6,8) G (1,4) G (2,5) G (3,6) G (4,7) G (5,8) (a) G 1 G 2 . . . × × × × × × × (b)
k such that ∀i ∈ [1, δ -k + 1], {G i , G i+1 , ..., G i+k-1 }
has property P (in other words, any subsequence of G of length k satisfies P). We present here a general strategy that relies on a virtual hierarchy of graphs which is computed on demand. The hierarchy consists of rows

G 1 , G 2 , . . . , G δ where G k = {G (1,k) , G (2,k+1) , . . . , G (δ-k+1,δ) }. We use G k [i] to denote the i th graph of row G k , that is the graph G (i,i+k-1)
. The first row G 1 of the hierarchy corresponds to the graphs of the sequence G (or to simple transformations of these graphs); that is, G (i,i) corresponds to G i . Then, the hierarchy is defined by applying some composition operation • that computes a graph in a higher row from two graphs in lower rows. By doing this, the graph G (i, j) is the (iterated) composition of the graphs in the original subsequence {G i , G i+1 , . . . , G j-1 , G j }.

Observe that the graphs in row G k are the (iterated) composition of subsequences of length k in the original se-

quence. An example of the hierarchy based on the intersection operation from [START_REF] Casteigts | Tester efficacement la T-intervalle connexité dans les graphes dynamiques[END_REF] is shown in Figure 1a. Finally, in addition to the composition operation, we consider a test operation which maps any graph of the hierarchy into {true, f alse}. For example, in [START_REF] Casteigts | Tester efficacement la T-intervalle connexité dans les graphes dynamiques[END_REF] this operation tests whether the given graph is connected.

The general framework that we propose makes it possible to solve minimization or maximization problems by focusing only on the composition and test operations, while the high-level logic of the algorithm remains the same. More precisely, there is one high-level algorithm for minimization problems, and another for maximization problems. Due to space limitation, we describe only the minimization version here, and refer the reader to [START_REF] Casteigts | Tester efficacement la T-intervalle connexité dans les graphes dynamiques[END_REF] for an example of a maximization algorithm, albeit described in a less general way, and to Chapter 4 of [START_REF] Neggaz | Automatic Classification of Dynamic Graphs[END_REF] for further details (e.g. proofs) about the minimization version.

For a minimization problem relative to some property P to be solvable within our framework, the following conditions must hold on the composition operation • and the test operation test:

(1) test(G (i, j) ) = true ⇔ {G i , G i+1 , . . . , G j-1 , G j } satisfies P; (2) operation • is associative, that is (G (i, j) • G (i , j ) ) • G (i , j ) = G (i, j) • (G (i , j ) • G (i , j ) ); and (3) it holds that [ G (i, j ) = G (i, j) • G (i , j ) ∧ (test(G (i, j) ) = true ∨ test(G (i , j ) ) = true ) ] ⇒ test(G (i, j ) ) = true.
Then the problem amounts to finding the lowest row in which all graphs satisfy the test.

High-level Strategy for Minimization Problems

We propose a strategy based on the generic composition and test operations defined above. The algorithm is then instantiated in Section 4 to solve three specific minimization problems by plugging in the appropriate operations. We describe the algorithm with reference to Figure 1b that shows an example of execution. The algorithm starts by computing the first graph G 1 [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] and then traverses the hierarchy from left to right by computing a new adjacent graph at each step: the next graph in the same row or the graph with the same index in the row above, depending on the result of the test operation on the current graph. We call this traversal process a walk. The walk goes up in the hierarchy if the test is negative, otherwise it moves forward in the same row. If the walk hits the right side of the hierarchy and the last visited graph G k [δk + 1] in the row G k satisfies the test operation, then it terminates and outputs k. Otherwise, it terminates and outputs k + 1. If the walk reaches G 1 [δ] and the test is negative, then the algorithm outputs 0 indicating that the dynamic graph G does not have the property.

Graphs computation: Intermediate graphs called ladders (in grey in Figure 1b) are computed by composing incrementally a graph G (i, j) with the adjacent bottom graph G (i-1,i-1) (left ladder) or G ( j+1, j+1) (right ladder), providing useful shortcuts in the construction. Then, the graphs resulting from the walk (red/dark graphs in Figure 1b) are computed as follows: When the walk moves one step forward in the same row, the next graph is computed from the right and the left ladders (e.g. G 4 [6] = G 2 [6] • G 2 [8]) or from the ladder to which it belongs and an adjacent bottom graph (e.g. G 4 [4] = G 1 [4] • G 3 [START_REF] Whitbeck | Temporal reachability graphs[END_REF]). If the walk climbs a step (moves up) in the hierarchy, then the next graph is computed from the preceding graph in the walk and the next graph in G 1 (instead of using ladders).

Although this computation does not require the use of ladders, the process continues to build a right ladder as the walk goes up for later use (if the walk later moves forward on the same row).

As it turns out, this general algorithm for minimization problems has the following convenient property which is crucial for correctness of two of the problems described in Section 4.

Lemma 1 (Disjoint sequences property). If the algorithm performs a composition of two graphs G (i, j) and G (i , j ) , then the corresponding sequences {G i , G i+1 , . . . , G j } and {G i , G i +1 , . . . , G j } are disjoint and consecutive. That is, in any execution,

G (i, j ) = G (i, j) • G (i , j ) ⇒ j = i -1.
Theorem 1. This minimization algorithm has a cost of Θ(δ) composition operations and test operations (see [START_REF] Casteigts | Tester efficacement la T-intervalle connexité dans les graphes dynamiques[END_REF] for proof).

Illustration of the Framework

We illustrate the general framework by solving three minimization problems: BOUNDED-REALIZATION-OF-THE-FOOTPRINT, TEMPORAL-DIAMETER, and ROUND-TRIP-TEMPORAL-DIAMETER. We define each problem within the framework and provide the corresponding operations for composition and test. The reader is referred to Chapter 4 of [START_REF] Neggaz | Automatic Classification of Dynamic Graphs[END_REF] for more details.

Bounded Realization of the Footprint

The footprint G of a dynamic graph G is the graph that contains all the edges that appear at least once, that is ∪{G 1 , G 2 , ..., G δ }. We consider the problem of finding the smallest duration b such that in any window of length b, all edges of G have appeared at least once (BOUNDED-REALIZATION-OF-THE-FOOTPRINT). Composition and test operations: Finding these operations is straightforward. By taking the union of two graphs as composition operation (starting with {G (i,i) } = {G i }), it follows that the lowest row G k such that all graphs equal the footprint indicate, by definition, the answer k. So, the composition operation is union and the test operation is equality to footprint (with labelled nodes, not to be mistaken with isomorphism).

Temporal Diameter

A dynamic graph might never be connected at one time, and yet offer a form of connectivity over time and space based on journeys (or temporal paths). A journey is a sequence of adjacent edges which are available at increasing dates (with possible intermediate pauses). This concept has different definitions depending on the model. In a sequence of graphs, one may consider that at most one hop can be performed in each G i for each journey. Other definitions are possible, but we consider this one here. Then, the temporal diameter of G at time t is the smallest duration d such that for all nodes u and v, u can reach v through a journey before time t + d. We consider the problem of finding the smallest duration d such that the temporal diameter of G is less or equal to d at any time t < δ-d (problem TEMPORAL-DIAMETER). In other words, any subsequence of length d is temporally connected. Several solutions exist to this or similar problems (e.g. [START_REF] Huyghues-Despointes | Forte ∆-connexité dans les flots de liens[END_REF][START_REF] Whitbeck | Temporal reachability graphs[END_REF]), which operate at a lower level of abstraction. Here, we show how the problem fits elegantly within the proposed framework.

The hierarchy built here is one of transitive closures of journeys. Therefore, each G (i, j) is a directed graph such that an edge (u, v) exists if and only if u can reach v in G by starting after (or at) i and arriving before (or at) j. As a special case, G (i,i) is the directed (symmetric) version of G i . Then, the answer is the smallest k such that every graph in row G k is a complete graph (i.e. every subsequence of length k is temporally connected).

cat

G (i, j) G (i , j ) = G (i, j) ∪ G (i , j ) ∪ G (i, j)→(i , j ) = Figure 2:
Example of concatenation of transitive closures. Edges in G (i, j)→(i , j ) are added after the union.

Composition and test operations: The hierarchy is built through a concatenation of transitive closures, cat(G (i, j) , G (i , j ) ), with the restriction that i = j + 1 (Lemma 1), defined as follows. First make the union of both graphs, then add an additional edge (u, v) if there exists a node w such that (u, w) ∈ E(G (i, j) ) and (w, v) ∈ E(G (i , j ) ).

See Figure 2 for an example. Then, the test operation consists of verifying if the graph is complete.

Round-trip Temporal Diameter

We address here the more complex property of round-trip temporal connectivity defined by the existence of a back-and-forth journey from any node to all other nodes. The round-trip temporal diameter of a graph G at time t is the smallest duration d such that, between time t and t + d, there is a journey J (u, v) from any node u in the graph to any other node v and a journey J (v, u) from v to u which starts after the arrival of the journey J (u, v).

We consider the problem ROUND-TRIP-TEMPORAL-DIAMETER of finding the smallest d such that the round-trip temporal diameter of G is less or equal to d at any time t ≤ δd.

Composition operation:

The composition operation in our case is the concatenation of round trip transitive closures rtcat(G (i, j) , G (i , j ) ) with the restriction that i = j + 1 (Lemma 1), that computes the round trip transitive closure of journeys G (i, j ) i.e. (u, v) ∈ G (i, j ) iff at least one journey from u to v exists in the sequence {G i , G i+1 , ..., G j }, and edges {(u, v) ∈ E(G (i, j ) )} are labelled with two dates: departure(u, v, G (i, j ) ) the latest departure of any journey in the sequence, and arrival(u, v, G (i, j ) ) the earliest arrival of any journey in the sequence. Note that labels on the same edge may or may not be departure and arrival of the same journey and that departure(u, v, G (i,i) ) = i and arrival(u, v, G (i,i) ) = i. The composition is as follows. First, compute the graph

G ∪ = G (i, j) ∪ G (i , j ) which is the union graph G (i, j) ∪ G (i , j ) with arrival(u, v, G ∪ ) = min(arrival(u, v, G (i, j) ), arrival(u, v, G (i , j ) )) and departure(u, v, G ∪ ) = max(departure(u, v, G (i, j) ), departure(u, v, G (i , j ) ) if (u, v) ∈ G (i, j) ∩ G (i , j ) .
Otherwise, the edge is added with the initial dates. A graph of extra-edges G (i, j)→(i , j ) is then computed as follows: (u, v) ∈ G (i, j)→(i , j ) iff a set of nodes extra = {w : (u, w) ∈ E(G (i, j) ) and (w, v) ∈ E(G (i , j ) )} exists (not empty). arrival(u, v, G (i, j)→(i , j ) ) = min{arrival(w, v, G (i, j) )} and departure(u, v, G (i, j)→(i , j ) ) = max{departure(u, w, G (i, j) )} : w ∈ extra. Finally, the round trip transitive closure rtcat(G (i, j) , G (i , j ) ) = G ∪ ∪ G (i, j)→(i , j ) (see Figure 3).

Test operation:

The test operation used for this problem is the round trip completeness test, that is, test if the graph is complete and if, for all edges {(u, v)} in the graph, arrival(u, v, G (i, j) ) ≤ departure(v, u, G (i, j) ). -→ v (shifted toward the tip) represent respectively arrival(u, v, G (i, j) ) and departure(u, v, G (i, j) ).

Figure 1 :

 1 Figure 1: (a) Example of partial hierarchy from [2] using intersection as the composition operation. (b) Example of execution of a minimization algorithm (not related to (a) which corresponds to a maximization problem).

Figure 3 :

 3 Figure 3: Example of round trip transitive closures concatenation. Labels arr and dep on an edge u arr, dep

  Let G be a graph sequence {G 1 , G 2 , ..., G δ } and let P be a boolean predicate (hereafter called property) defined on a consecutive subsequence {G i , G i+1 , ..., G j } ⊆ G. The minimization (resp. maximization) problem on G with respect to P is the problem of finding the smallest (largest)

	2 Overview and main definitions

† This work has been supported by ANR projects ESTATE (ANR-16-CE25-0009-03) and by "the Investments for the future" Programme IdEx Bordeaux CPU (ANR-10-IDEX-03-02).