Yulian Yang
email: yulian.yang@liris.cnrs.fr

Semantic Information Retrieval over P2P Network

Porteurs de nombreux avantages en termes d'évolutivité, de décentralisation et d'autoorganisation, les réseaux P2P se présentent comme une alternative intéressante lorsqu'il s'agit de publier et d'accéder à de l'information. Plusieurs travaux de recherche ont traité du problème du routage des requêtes au sein de systèmes d'information soutenus par des réseaux P2P. Cependant, peu d'entre eux semblent intéressés pour savoir si les mécanismes de routage sémantique de requêtes permettent effectivement de fournir aux utilisateurs des informations sémantiquement pertinentes en fonction de leurs besoins. Ainsi, dans ce travail nous proposons d'étudier l'application de la sémantique à la Recherche d'Information traditionnelle ainsi qu'aux systèmes d'information basés sur des réseaux P2P. Nous démontrons l'écart qui subsiste entre la recherche d'information sémantique et le routage sémantique des requêtes. Finalement, nous présenterons les défis offerts par la recherche d'information sémantique lorsqu'elle est appliquée aux réseaux P2P.

ABSTRACT. As an alternative to publish or access information, P2P network is attracting more and more attention because of its advantages in scalability, decentralization and selforganization. While a lot of research has been focused on semantic query routing in information system over P2P network, little work concerns if semantic query routing can satisfy the requirement of semantic information retrieval, and to what extent the query routing mechanism can provide the information semantically related to users' query. This paper studies the application of semantics in traditional information retrieval and information system over P2P network, demonstrates the gap between semantic information retrieval and semantic query routing, and finally present the challenge of semantic information retrieval over P2P network. MOTS-CLÉS : Recherche d'information, réseau P2P, Sémantique, Echelle Sémantique, Routage Sémantique KEYWORDS: Information retrieval, P2P network, Semantics, Semantic layer, Semantic routing

Introduction

Peer-to-peer (P2P) network refers to the system or application which performs a task in a decentralized manner by employing distributed resources such as computing power, storage, data and network bandwidth (MIL 02). It has the character of scalability, decentralization and self-organization. One of the major applications over P2P network is file/content sharing. Various file sharing systems have been designed and used in real application. For example, the first decentralized file sharing system Gnutella and a number of BitTorrent based services. Although some of these systems have been undergoing a series of the lawsuits, P2P network remains to be an efficient mechanisms for information sharing and acquisition.

As the technology and application of P2P network is developing, the resources in P2P network will become diverse, and the information demand of users will not be satisfied just via key-word matching. For example, the users would not just like to find a movie named 'Inception', which can be implemented by matching the query 'Inception' and the documents' titles. They might want some information expressed by more complicated query, such as 'a file about the history of the pop music' or 'a book written by a female author who was born in Beijing' stored in a distant peer. In this case, information retrieval (IR) over P2P network is supposed to answer the query by exploring the semantics of resources in peers.

Recently, the research on centralized semantic IR has developed rapidly with the technology for semantic web (SET 07). When it comes to IR over P2P network, a lot of work is concentrated on the scalability and the traffic as well as semantic query routing (LUU 08, ROS 08). Semantic query routing refers to forwarding the query to target resources by evaluate their semantic relationship on topic level. However, the queries in semantic IR is often specific, and little work has been done so far to study the gap between semantic query routing and achieve semantic IR.

In this paper, we study the issues of performing semantic IR over P2P network. Specifically, we study the application of semantics in centralized IR system in Section 2, and demonstrate current IR mechanisms over P2P network in Section 3. In Section 4, the gap between semantic IR and semantic query routing is analyzed. The challenges in semantic IR over P2P network are presented in Section 5.

Semantic information retrieval

Semantic IR aims to identify the relevant information to a query via evaluating their semantic relationship rather than key-word matching. We divide it into two levels, according to the semantic relationship between users' queries and the retrieved information. We assume the information to be retrieved is a collection of text documents.

In one level, a query can be answered by evaluating its semantic relevance to the content of each document. For example, the user intends to find the documents about the marriage of Eva Longoria and Tony Parker, which is very popular on the inter-net recently. The semantic IR system is supposed to return the documents about their wedding and divorce, because wedding and divorce are both related to marriage. A lot of approaches are proposed for this, such as the probabilistic approach (JON 00), language model (CRO 03), LSA (DEE 90) and approach employing the theory in machine learning (YUE 07). These approaches assume the terms concurrent in the same context have a common concept. However, these approaches can't represent the semantic relationship between the terms. The specification of the semantic relationship is essential for performing more efficient IR, especially when the query submitted includes multiple keywords (TIA 06).

In the other level, the result of a query not only concerns the content in individual document, but also its relations with the outside information (e.g. the content in the other documents). For instance, the query aims to find documents about 'mobility' whose author once published a paper titled as 'peer to peer computing'. In order to implement such a query, we need to find the author of the paper 'peer to peer computing' in the author list of this paper, then continue to find the other documents written by this author. Thanks to the technology in semantic web, ontology and information extraction, semantic IR in this case is becoming promising (FEN 03), and relevant work has been done in (GRA 05).

Current information retrieval over P2P network

Information retrieval over P2P (P2P-IR) network aims to forward a query to target resources (query routing), perform relevance evaluation on the target resources, and then return the top-k most relevant documents to the user who submits the query. Most of the work in this field focuses on how to achieve semantic query routing, which refers to forward the query to the peers which hold the semantically related resources to it. To a certain extent, it often refers to query routing when people mention P2P-IR.

DHT is the most common type of structured P2P network so far, which indexes the resources in the network via a hash table and distributively stores the table in peers. The indexing granularity of the resources often is the document (LUU 08) or peer (MAT 05). Structured P2P network can response the queries quickly, but it can only support key matching (IVA 06) which present the employment of semantics to a great extent. Relevant work is done in CAN (a semantic P2P layer), which represent each document with a vector and map the documents into a semantic space. Close documents are semantic related in the semantic space. The query is also mapped to the semantic space in the same way. The documents close to it in the semantic space are identified as relevant ones.

In IR over unstructured P2P network, the query has to be flooded through the network to find the peers sharing the relevant data, e.g. Gnutella. Therefore, a lot of research in this subfield mainly concentrate on forwarding the query semantically. Except random walking algorithms (GKA 06), (COH 07) proposed a guided search over associative overlays. (SAR 04) introduced the percolation search algorithm for locating and retrieval content in random network. (ZHU 05) presented an approach which build semantic links between peers and then perform query routing on it.

There also exists some work which employs super-peer mechanism or takes advantage of both structured and unstructured P2P network to perform IR. For example, (PAP 10) proposed to combine DHTs and peer clusters for efficient full-text P2P indexing, (DOU 10) implemented a super-peer based P2P network for organizing similar content in the network. A semantic overlay network was implemented in (CRE 05).

Semantic information retrieval over P2P network

Although a lof of work has been done both in semantic query routing in P2P network and the semantic IR in centralized systems, no existing work concerns to what extent the semantic query routing mechanism can satisfy semantic IR. We will study it in this section.

Semantic information retrieval and semantic query routing

Query routing and IR both aim to find relevant resources, but they have intrinsical difference when it comes to semantic IR. Generally, semantic query routing is often performed on a topic level while semantic IR is more specific. Let's see how semantic IR would fail during the semantic query routing.

In structured P2P network, take semantic layer over CAN for example. The system maps the documents in the network into the semantic space, where each document is represented as a vector and similar documents would be close to each other. The similarity between documents is evaluated by the distance between vectors, and it has no semantic implication. Moreover, the vector for each document is calculated via SVM or LSI. It doesn't include information about the specific relationship between terms or keywords. Therefore, It can not handle very well with the queries with more than one key words. For the queries which concern the documents and its relations with outside information, it would be more difficult for the system to handle.

For semantic query routing in unstructured P2P network, the query is forwarded to the peers which have relevant resources. Here, the problem appears again. How to evaluate the relevance between a query and a collection of resource ? If the relevance is too specific, the query takes the risk that it has no relevance to all the next-hop peers. If the relevance is general, the query would be forwarded to too many peers which no doubt is a waste of traffic. In addition, it still cannot deal with the query like 'documents about mobility whose author once published a paper titled as peer to peer computing', especially when the concerned documents are stored in different peers.

Challenges

In conclusion, the challenges in semantic P2P-IR lies in the following aspects : 1) the user's queries are specific, while query routing over the semantic layer of P2P network is general, often on the topic level. So there is a risk that the query might be forwarded to peers which has no answers to it, but something only related on the topic level, where the topic of the query often can be evaluated via Ontology. Take the web search over P2P network for example, the user would like to request some specific query like 'the possible cause of headache'. The query might be forwarded to the peers which have the resources about 'health', but we have no idea about the probability that the peers has the information of 'the cause of a headache'. Apparently, this will cause a waste of traffic and computing cost if the peers actually have no such information.

2) the 'relevance' and 'related' defined in the semantic layer of structured P2P network is vague. This results in a system which can not provide accurate results for a query. They can not deal with the queries which include several keywords and have explicate relationship among them. Let alone more complicated queries, which might be concerned with multiple documents located in different peers.

3) It's hard to determine the generalization level of the outline for each peer. To make P2P network be a real self-organized one, peers are assumed to manage their resources by themselves, and only share an outline to make sure relevant queries can be forwarded to them. This can also decrease the traffic cost of the network. However, what kind of outline can precisely and concisely represent the resource in a peer, and also facilitate the query routing of the P2P network ?

Conclusion

This paper studied semantic P2P-IR. We analyzed the semantic IR in centralized systems, presented the research achievements and issues in current information systems over P2P network. The challenges of semantic P2P-IR are demonstrated.

Bibliographie

  [COH 07] COHEN E., FIAT A., KAPLAN H., « Associative search in peer to peer networks : Harnessing latent semantics », Computer Networks, vol. 51, n o 8, 2007, p. 1861-1881. [CRE 05] CRESPO A., GARCIA-MOLINA H., « Semantic Overlay Networks for P2P Systems », Agents and Peer-to-Peer Computing, vol. 3601, p. 1-13, Springer Berlin / Heidelberg, 2005. [CRO 03] CROFT W. B., JOHN L., Language Modeling for Information Retrieval, vol. 13 de The Information Retrieval Series, Springer, 2003. [DEE 90] DEERWESTER S., DUMAIS S. T., FURNAS G. W., ET AL., « Indexing by Latent Semantic Analysis », Journal of the American Society for Information Science, vol. 41, 1990, p. 391-407. [DOU 10] DOULKERIDIS C., VLACHOU A., NORVAG K., ET AL., « Efficient search based on content similarity over self-organizing P2P networks », PEER-TO-PEER NETWORKING AND APPLICATIONS, vol. 3, n o 1, 2010, p. 67-79. [FEN 03] FENSEL D., WAHLSTER W., LIEBERMAN H., ET AL., Spinning the Semantic Web : Bringing the World Wide Web to Its Full Potential, MIT Press, 2003. [GKA 06] GKANTSIDIS C., MIHAIL M., SABERI A., « Random walks in peer-to-peer networks : Algorithms and evaluation », Performance Evaluation, vol. 63, n o 3, 2006, p. 241-263.


Sylvie Calabretto

Ontology Alignment in the Urban Domain

Introduction

Concepts in the domain of Urban Civil Engineering are often categorized and described using ontologies. Such ontologies may be designed independently by domain experts who have a minimal communication or no communication between them. As a result, similar concepts may be described differently and their categorization may result in heterogeneous ontologies.

More and more ontology-based urban systems are being built in different countries. However, most of the language-processing oriented ontologies that have been built so far have English or another language as basis. Since there is a growing need for multilingual ontologies, it is natural to ask for multilingual ontology alignment and viewpoint confrontation.

In this chapter, we first introduce several justifications for heterogeneity and give illustrations on urban problems. We then give some definitions on ontology matching and alignment, and some elements on ontology alignment approaches. Then we propose an overview of ontology alignment in urban or GIS domain and of viewpoint confrontation systems. Finally, we present the Hyppodamos tool as a solution for multilingual ontology alignment.

Heterogeneity in Urban Problems

Heterogeneity does not lie solely in the differences between goals of the applications according to which they have been designed or in the expression formalisms in which they have been encoded. They have been different classifications to types S. Calabretto () Institut National des Sciences Appliquées de Lyon (INSA-Lyon), France e-mail: sylvie.calabretto@insa-lyon.fr of heterogeneity: syntactic heterogeneity, terminological heterogeneity, conceptual heterogeneity and semiotic heterogeneity. Usually, several types of heterogeneity occur together. The terminological heterogeneity occurs due to the variations in names when referring to the same entities in different ontologies.

Syntactic Heterogeneity

Syntactic heterogeneity occurs when two ontologies are not expressed in the same ontology language. This happens when two ontologies are modelled by using different knowledge representation formalisms, for instance OWL and F-logic. A solution to this heterogeneity consists in establishing equivalences between constructs of different languages. But this is not always possible. For instance if a language is more expressive than another one, not all F-logic expressions can be translated to OWL.

Terminological Heterogeneity

The terminological heterogeneity occurs due to the variations in names when referring to the same entities in different ontologies. This can be caused by the use of different natural languages, e.

Conceptual Heterogeneity

Conceptual heterogeneity stands for the differences in modelling the same domain of interest. This type of heterogeneity is also called semantic heterogeneity in [START_REF] Euzenat | Towards a principled approach to semantic interoperability[END_REF] or logical mismatch in [START_REF] Klein | Combining and relating ontologies: an analysis of problems and solutions[END_REF]. This can happen because of the use of different axioms for defining concepts or because of the use of totally different concepts (geometry axiomatised with points as primitive objects or with spheres as primitive objects). [START_REF] Benerecetti | On the dimensions of context dependence: partially, approximation and perspective[END_REF] identifies three different reasons for conceptual heterogeneity to hold: difference in coverage, difference in granularity and difference in perspective.

Semiotic Heterogeneity

Semiotic heterogeneity is also called pragmatic heterogeneity in [START_REF] Bouquet | D2.2.1 Specification of a common framework for characterizing alignment[END_REF]. This heterogeneity is concerned with how entities are interpreted by people. In the example of Fig. 4.3, the term "Egoût" is interpreted differently by the Expert 1 and the Expert 2. This type of heterogeneity is very difficult to detect and solve by a computer.

Terminology in Ontology Alignment

Ontology matching aims at finding correspondences between semantically related entities of different ontologies. These correspondences may stand for equivalence as well as other relations, such as consequence, subsumption, or disjointness, between ontology entities. Ontology entities, in turn, usually denote the named entities of ontologies, such as classes, properties or individuals. Ontology matching results, called alignments, can thus express with various degrees of precision the relations between the ontologies under consideration [START_REF] Euzenat | Ontology Matching[END_REF].

Ontology alignment is a set of correspondences between two or more (in case of multiple matching) ontologies (by analogy with molecular sequence alignment). The alignment is the output of the matching process.

Alignments can be used for various tasks, such as ontology merging, query answering, data translation or for browsing the semantic web.

Ontology merging is the creation of a new ontology from two, possibly overlapping, source ontologies. The initial ontologies remain unaltered. The merged ontology is supposed to contain the knowledge of the initial ontologies, e.g., consequences of each ontology are consequences of the merge. This concept is closely related to that of schema integration in databases.

Ontology Alignment Approaches

The ontology alignment problem can be expressed as: in How to find the relationships that hold between the entities represented in different taxonomies?

We can identify two approaches [START_REF] Nogueras-Iso | Building an address gazetteer on top of an urban network ontology[END_REF] for the ontology construction: manual and automated ontology construction.

In the manual approach, we use the matching of terms (names and acronyms) between the different taxonomies. We can consider three categories of matches:

Exact match • Partial match: one concept is broader or narrower No match • Provisional match: taxonomy errors (homonyms) imply erroneous matches •

The automated approaches are used because manual mappings are time consuming and because some mappings may not be successful (content creators have not assigned the correct feature type). Two main approaches have been discussed in the literature: one which exploits the abstract data (nodes) represented by its names (lexical methods) and another which exploits the relationships (edges) between the various classes that form the structure of the ontology, (structural methods). Consequently, some of these techniques attempt to compare text strings that describe the entities in the ontologies (terminology-based ontology alignment) while others calculate the similarity measures between entities taking into account the structure of their corresponding ontologies (structural ontology alignment).

Overview of Ontology Alignment Tools

The state of the art of ontology alignment methodologies was recently surveyed by [START_REF] Euzenat | Ontology Matching[END_REF]. Previously, Rahm and Bernstein surveyed schema matching in databases [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF].

In this section, we cover ontology and alignment tools even if most of them do not focus specifically on the urban domain. A notable exception is offered by [START_REF] Fonseca | Semantic granularity in ontology-driven geographic information systems[END_REF]. They introduce an ontology-driven geographic information system (ODGIS), which is used to drive the creation of ontologies that will enable the integration of geospatial data.

Chimaera [START_REF] Mcguinness | An environment for merging and testing large ontologies[END_REF] is a software tool developed by the KSL group at Stanford, which provides tools for merging ontologies and checking the correctness of ontologies. Chimaera is web-based. Its graphical user interface supports a set of commands accessible via spring-loaded menus as well as drag and drop editing. The interface displays the knowledge base being edited and allows for users to check an automated merging procedure by highlighting the classes that require the user's attention. The authors of Chimeara consider the task of merging two ontologies to be one of combining two or more ontologies that may use different vocabularies and may have overlapping content. The major two tasks are to (1) to coalesce two semantically identical terms from different ontologies so that they are referred to by the same name in the resulting ontology, and (2) to identify terms that should be related by subsumption, disjointness, or instance relationships and provide support for introducing those relationships.

COMA++ [START_REF] Aumueller | Schema and ontology matching with COMA++[END_REF]) is a schema and ontology mapping tool, which is in many ways similar to our own mapping tool. However, both tools have been developed independently. COMA++ supports an iterative and automatic matching of ontology components and multiple matching algorithms. COMA++ supports multiple ontology and schema formats such as OWL, XSD, and XML.

The MAFRA toolkit is a mapping framework for distributed ontologies which adopts an open architecture in which concept mappings are realized through semantic bridges. A semantic bridge is a module that transforms source ontology instances into target ontology instances manually defined. The MAFRA toolkit supports a graphical user interface that provides domain experts with functionalities that are needed for the specification of semantic bridges. In the MAFRA toolkit, the ontologies are represented as graphs and in particular cases as trees using the Touch Graph library (http://www.touchgraph.com).

Falcon-AO [START_REF] Jian | Aligning ontologies with Falcon[END_REF]) is an automatic ontology alignment tool that uses linguistic and graph matching techniques. It attempts to align ontologies using linguistic similarity between two entities relying on their names, labels, comments and other descriptive information. Falcon-AO relies on a graph matcher, which measures the structural similarity between the graphs that represent the ontologies.

Clio [START_REF] Hernández | Clio: a semi-automatic tool for schema mapping[END_REF]) is a graphical tool used for the semi-automatically mapping of relational and XML schemas. In contrast, our mapping tool is mainly intended to match ontologies and therefore supports the mapping of XML and OWL/RDFS ontologies represented in XML, RDFS, OWL, or N3 [START_REF] Berners-Lee | Experience with N3 rules[END_REF]. Using Clio, the user loads a source schema and a target schema and establishes connections between objects in both schemas graphically. Such connections are referred to as value correspondences, which express how one or more objects in the source schema are transformed into a target value. Clio has a mapping engine that incrementally produces database (SQL) queries that realize the mappings implied by the correspondences. The AgreementMaker generates a document that shows the mappings between concepts and can be used in a variety of ways, including in generating database queries.

MapOnto [START_REF] An | Inferring complex semantic mappings between relational tables and ontologies from simple correspondences[END_REF], which is inspired by Clio, is a research prototype for mapping between a database schema and an ontology as well as between two different database schemas. MapOnto works in an interactive and semi-automatic manner, taking input from the user for creating simple attribute-to-attribute correspondence and allowing the user to select a set of logical formulas that can be used to establish correspondences between related attributes. These logical formulas are generated by the tool using knowledge embedded in the ontologies. These logical formulas are ordered to suggest to the user the most reasonable mapping between the two models. MapOnto supports a graphical interface, which is based on Protégé [START_REF] Gennari | The evolution of protégé: an environment for knowledge-based systems development[END_REF]. Unlike our tool, the correspondences between attributes are not represented by lines in the interface, but as logical formulas displayed in a separate pane. [START_REF] Cruz | A visual tool for ontology alignment to enable geospatial interoperability[END_REF] have proposed an integration framework, in geospatial domain, to facilitate access to the information that is contained in distributed and heterogeneous databases [START_REF] Cruz | Handling semantic heterogeneities agreements[END_REF]. Their approach relies on the alignment of ontologies. When such mappings have been established, we say that the two ontologies are aligned or matched. They consider two different architectures: a centralized architecture and a peer-to-peer (P2P) architecture. In the former architecture, there is a global ontology. Each distributed ontology is aligned with the global ontology. As a consequence, a query expressed in terms of the concepts of the global ontology can be translated into a query to one of the distributed or local databases using the mappings that are established during the alignment process. In the latter architecture, a query to a source peer can be translated into a query to a target peer, provided that the ontologies of the two peers have been aligned. Whichever the architecture, querying can be easily extended to new databases, and therefore to new regions.

Nogueras-Iso et al. ( 2000) use URBISOC, a thesaurus focused on Spanish terminology for Town Planning, developed by the CINDOC/CSIC institute (Centre for Scientific Information and Documentation / Spanish National Research Council). The proposition is made through the IDEZar Project (collaboration agreement signed in March 2004 between the City Council and the University of Zaragoza). The Objective of the project is the development of a local SDI for Zaragoza, to facilitate, increase and coordinate the use of spatial data by the Council and to develop applications for the citizens and to provide them with access to public sector information. Formal Concept Analysis (FCA) approach is used (it enables the extraction of a hierarchy of concepts from the feature instances contained in the source repositories) and seems to be more flexible: it allows dynamic building of the ontology (at least, a draft), it doesn't need to define the concepts, it just need to observe the data that exists. They have also created a domain specific ontology that facilitates the interoperability (synchronization, update and merge) of the separate repositories.

Overview of Viewpoints Confrontation Systems

For the purpose of confrontation, we defined the notion of opinion-viewpoint as opposed to the notion of viewpoint which is an emerging paradigm in Computer Science and especially in Information Systems Design (that is, a view angle on an entity). An opinion-viewpoint is a dynamic, non-consensual theory which is expressed on a domain for the purpose of sharing. It can be easily found in Sciences in the process of theory elaboration, and, to give an immediate example, this paper for instance is an opinion-viewpoint.Very few existing systems include confrontation of viewpoints in their functionalities. Indeed, allowing confrontation of viewpoints implies that the notion of viewpoint is well defined. Viewpoints-based systems, such as [START_REF] Bénel | Truth in the digital library: from ontological to hermeneutical systems[END_REF][START_REF] Bénel | Porphyry 2001: semantics for scholarly publications retrieval[END_REF][START_REF] Bénel | Porphyry and Steatite: software layers for sense makers in humantities[END_REF], [START_REF] Porphyry | Porphyry Project[END_REF] and [START_REF] Zaher | The Agorae / Hypertopic approach[END_REF], allow some form of confrontation. Porphyry especially includes a graph filtering system that shows, when several viewpoints are considered, which of them contain a given resource (Fig. 4.4).

The reason why confrontation is not included in the current approaches of collective work is that the same software is generally used by small communities that do not necessarily wish to share their research work [START_REF] Ribière | A viewpoint model for cooperative building of an ontology[END_REF]. Confrontation can only be envisaged either as an inner functionality that works within a single community, or as a general tool that works only on published work.

Generating inventiveness through confrontation is a difficult task in a digital environment. There are three issues that we had to deal with. First of all: confrontation by digital computation. At this level of expertise, when even terminology can vary from an expert to another, any algorithm is overtaken by the complexity of the semantics that is involved in the process. It is important to limit the bias introduced by inaccurate matching algorithms. Therefore, we planned the environment as being used by the experts themselves, and the algorithms as being mere tools to test on the subject of study_validating or refusing their result. The second issue comes right from the solution of the first one: if the experts are supposed to control the environment, it is important to build it such as they can use it without being very proficient with the computer. We have thus kept the GUI as simple as possible, limiting the number of options and merging all algorithms into three options: exhaustive search, The third issue is at the level of data and representation. Digital processing, especially when it comes to matching things, implies that some graph structure will be used. Expressing a urban viewpoint as a graph can also induce a bias. We do not express viewpoints ourselves (at the moment), so we use the solutions taken by whatever source we have for them. For instance, Porphyry uses a representation that puts little constraint in the formalism, arguing that when experts in humanities are involved, interpretation is more important that formalness.

In the following, we show how we have used Porphyry for modelling the glossary of urban, regional and environmental planning terms established in 2004 by Calderon and Ventura (Figs. 4.5 and 4.6).

The Hyppodamos Tool

The goal of the Hyppodamos environment [START_REF] Gesche | Un modèle pour la Confrontation d'opinions numérisées sous Porphyry[END_REF][START_REF] Gesche | Managing difference of opinion in semantic structures[END_REF][START_REF] Gesche | Exploitation de l'hétérogénéité entre points de vue-opinion[END_REF][START_REF] Berdier | Managing heterogeneity in urban ontologies[END_REF]) is to allow an expert to confront and to align several ontologies on compatible subjects. We do not limit ourselves to a single formalism, thus we Fig. 4.5 Revealing of a little bit complex overlapping of terms and definitions created a generic formalism to allow the import from the formalisms used by the software that already allow the expression of viewpoints (Fig. 4.7) (Towntology for instance). We are not limited to a single media either (for now, we use text and images that are the main means of knowledge representation), nor to a single language (however, the expert actually doing the confrontation must still be able to understand what he is working on).

The environment itself is organized according to the computer-aided paradigm: it provides a place where the viewpoints can be imported (a virtual desk), and a set of tools that allow either an automated or a manual processing on them. These tools can be used at any moment, in any state of the viewpoints (Fig. 4.8). Viewpoints are thus never overwritten, instead a save file is issued linking to them.

There are five actions that we expect an expert to use while confronting. Three of them have been included in the environment, and the remaining two have to do with building the graphs (which we assume is already done). They are:

Observation: the main, even though almost passive activity of the expert is to • watch the viewpoints, study them and observe the effects of the other actions on them. Extraction and Organization: the actions involved in graph building. Interesting • patterns have to be extracted from the raw viewpoints (for example a digital paper, or the mind of the expert) and they must be organized within a graph structure.

Connection and Dissociation between patterns of different viewpoints. •

Ontology matching only involves a single action, connection. Its aim is to find matches between patterns of matched ontologies, in order to allow interoperability most of the time. The algorithms we took from this domain have the same goal, finding any relation between the viewpoints. However, since we deal with an expert/ machine partnership where the expert holds the power of decision, this task had to be split in two. Indeed:

1. When identical names are used for different meanings in several points of view, they must be dissociated (it was, for instance, the case of Thebes, a name of many cities in the antique world). 2. Whenever one of the matching algorithms points out that some terms could be connected, and it is not the case, it is also useful to explicitly dissociate them. These dissociations are not only correcting some error of a matching algorithm. Most of the time, they carry just as much sense as most connections. Among the experts using Porphyry especially, terminology can be as much a stake as diverging interpretations on a given subject.

Conclusion: Open Problems and Research Challenges

As a conclusion we can mention some directions in which research on ontology alignment should evolve.

Foundations: Available model-theoretic semantics are sufficiently similar, so they • could eventually converge. Recent work on categorical characterisation of ontology matching raised some questions about the statement in categorical terms of expressive alignments, which go beyond equivalence. Therefore, interesting and useful work could be pursued in this direction [START_REF] Euzenat | Ontology Matching[END_REF].

Representing alignments: In the long term, we expect progress on the framework • for integrating different alignment systems. Infrastructures are now still missing. Such an infrastructure should match ontologies and process the alignment on specified data. Therefore, alignment formats and metadata become crucial. Furthermore, graphical alignment editors are needed. They should be easy to use for ordinary users.

Explaining alignments: there are only a few matching systems that provide a • justification of their results. Explanation is a challenge for ontology alignment as well as user interfaces.

Processing alignments: Currently, many systems are rather monolithic and • provide ontology alignment at once. In the future, we hope to see more modularisation and also more alignment processors to be developed.

  g. Paper vs. Articulo, different technical sublanguages, e.g. Paper vs. Memo, or the use of synonyms, e.g., Paper vs. Article. The Fig. 4.1 is an example in the urban domain. It is based on the glossary of urban, regional and environmental planning terms established in 2004 by Calderon and Ventura (Fig. 4.2).

Fig. 4 . 1

 41 Fig. 4.1 Glossary of urban planning terms in english, french and italian languages

Fig. 4 . 3

 43 Fig. 4.3 Example of semiotic heterogeneity

Fig. 4 . 4

 44 Fig. 4.4 In this first test, the terms are "in flat" (no hyponyms or meronymes). The viewpoints are the three languages. The shared documentary entities are the definitions in one or another language [NB: Look at the terms appearing as synonyms in a same language]

Fig. 4 . 6

 46 Fig. 4.6 Revealing of untranslatable terms from french towards english and conversely


Amadou Diarra

Sonia Ben Mokhtar

Pierre-Louis Aublin

Vivien Quéma

FullReview: Practical Accountability in Presence of Selfish Nodes

Accountability is becoming increasingly required in today's distributed systems. Indeed, accountability allows not only to detect faults but also to build provable evidence about the misbehaving participants of a distributed system. There exists a number of solutions to enforce accountability in distributed systems, among which PeerReview is the only solution that is not specific to a given application and that does not rely on any special hardware. However, this protocol is not resilient to selfish nodes, i.e. nodes that aim at maximising their benefit without contributing their fair share to the system. Our objective in this paper is to provide a software solution to enforce accountability on any underlying application in presence of selfish nodes. To tackle this problem, we propose the FullReview protocol. FullReview relies on game theory by embedding incentives that force nodes to stick to the protocol. We theoretically prove that our protocol is a Nash equilibrium, i.e. that nodes do not have any interest in deviating from it. Furthermore, we practically evaluate FullReview by deploying it for enforcing accountability in two applications:

(1) SplitStream, an efficient multicast protocol, and (2) Onion routing, the most widely used anonymous communication protocol. Performance evaluation shows that FullReview effectively detects faults in presence of selfish nodes while incurring a small overhead compared to PeerReview and scaling as PeerReview.

I. INTRODUCTION

Distributed systems have always been the scene of various software and hardware failures. These failures can have diverse sources such as the crash of machines, bugs, misconfigurations, as well as malicious attacks and users that deliberately tamper with their software to gain some benefit. These failures are especially difficult to deal with when the distributed system spans over multiple administrative domains (also referred to as MAD distributed systems) [START_REF] Aiyer | Bar fault tolerance for cooperative services[END_REF]. Examples of such systems include peer-to-peer systems, computer grids, network services (e.g., DNS), federated information systems and inter-domain routing.

Accountability, which refers to the ability to detect and expose node faults, is a promising paradigm to deal with these types of failures. In the last decade various solutions have been proposed to enforce accountability for specific applications (e.g., anonymous communication [START_REF] Corrigan-Gibbs | Dissent: accountable anonymous group messaging[END_REF], online games [START_REF] Yahyavi | Watchmen: Scalable cheat-resistant support for distributed multi-player online games[END_REF], network storage [START_REF] Yumerefendi | Strong accountability for network storage[END_REF], randomised systems [START_REF] Backes | A practical and provable technique to make randomized systems accountable[END_REF], inter domain routing [START_REF] Haeberlen | Netreview: Detecting when interdomain routing goes wrong[END_REF], virtualised systems [START_REF] Haeberlen | Accountable virtual machines[END_REF]). While these solutions offer strong accountability guarantees, their usability is limited to the specific application domain for which they have been devised. Hence, generic solutions that are not tailored to a specific application have been proposed, some of which rely on trusted hardware (e.g., Trinc [START_REF] Levin | Trinc: Small trusted hardware for large distributed systems[END_REF], A2M [START_REF] Chun | Attested append-only memory: Making adversaries stick to their word[END_REF], Pasture [START_REF] Kotla | Pasture: secure offline data access using commodity trusted hardware[END_REF]) while others are generic software solutions. Our work targets this second category of systems as they do not require users (worldwide) to acquire specific hardware. To the best of our knowledge, PeerReview [START_REF] Haeberlen | Peerreview: Practical accountability for distributed systems[END_REF] is the only protocol that falls into this category of systems. In this protocol, nodes log their interactions with other nodes in a secure log. This log is then periodically audited by a set of other nodes assigned by the system, i.e. the node's monitors. During their audit, the monitors verify that the monitored node did not tamper with its log and that the latter corresponds to a correct execution of the monitored protocol. An attractive result of PeerReview in addition to its wide applicability is that it provides two theoretical guarantees: completeness and accuracy. Informally, completeness refers to the ability to detect (eventually) all the observable faults, while accuracy refers to the ability to never accuse correct nodes of misbehaviour.

PeerReview works under the Byzantine failure model, i.e. a model where a majority of nodes are correct and where a fixed (known) proportion of nodes in the system can behave arbitrarily. While dealing with Byzantine nodes is important, it has been demonstrated that in open collaborative environments selfish nodes, also called free riders, constitute a real threat [START_REF] Adar | Free riding on gnutella[END_REF], [START_REF] Krishnan | The impact of free-riding on peer-to-peer networks[END_REF], [START_REF] Feldman | Free-riding and whitewashing in peer-to-peer systems. Selected Areas in Communications[END_REF], [START_REF] Joao | Can peer-to-peer live streaming systems coexist with free riders[END_REF]. Selfish nodes are nodes that tamper with their software (or download a tampered software developed by others) in order to benefit from the system without contributing their fair share to it.

In PeerReview, nodes are not encouraged to participate to the monitoring of other nodes, which makes it vulnerable to selfish nodes. Specifically, in presence of a proportion of selfish nodes, some nodes in the system can be unsupervised if all their monitors behave selfishly. As a result, these nodes can harm the system without being detected, breaking the completeness property of PeerReview. To measure the impact of this threat in practice, we deployed PeerReview for enforcing accountability in the following two protocols: SplitStream [START_REF] Castro | Splitstream: high-bandwidth multicast in cooperative environments[END_REF], an efficient multicast protocol and Onion routing [START_REF] Goldschlag | Onion routing[END_REF], the most used anonymous communication protocol. Experiments show that in presence of 30% of selfish nodes, 54% and 85% of messages are lost using the first and the second protocols, respectively.

In this paper, we embrace the challenge of designing a selfish-resilient protocol for enforcing accountability in distributed systems and present the FullReview protocol. The objective of FullReview is to force selfish nodes to participate in the monitoring of other nodes while they are executing a given protocol. To reach this objective, the first idea that one may have is to make monitors themselves accountable for their actions by applying PeerReview. We show in this paper that this is not possible because using PeerReview to monitor itself would require that each node's log contains the log of all the other nodes in the system, which is not scalable.

To overcome this problem, FullReview relies on a game theoretic approach to force selfish nodes to stick to the monitoring protocol. Specifically, FullReview is a complete redesign of the PeerReview protocol, in which we have embedded incentives in such a way that it is not in the interest of any node to deviate from the protocol, i.e. we prove that FullReview is a Nash equilibrium [START_REF] Nash | Non-Cooperative Games[END_REF] 1 .

We implemented FullReview and used it to monitor the two protocols SplitStream and Onion routing. Performance evaluation performed on a cluster of 50 machines shows that FullReview is resilient to selfish nodes and that it incurs a reasonable overhead compared to PeerReview. Complementary simulations show that FullReview scales up to 1000 nodes.

The remaining of this paper is structured as follows. First, we present the related works in Section II. Then, we show the impact of selfish nodes in PeerReview and present our system model in Section III. Further, we present an overview of FullReview and its detailed description in sections IV and V, respectively. Finally, we present the performance evaluation of FullReview in Section VI and concluding remarks in Section VII.

II. RELATED WORKS

Building robust distributed systems has been at the heart of many research efforts in the last decade. In this context, a new model called the Byzantine, Altruistic, Rational (BAR) model has been proposed [START_REF] Aiyer | Bar fault tolerance for cooperative services[END_REF]. This model considers three types of nodes: Byzantine nodes are nodes that can deviate arbitrarily from the protocol; rational nodes are nodes that deviate from the protocol if the performed deviation allows them to increase their own benefit according to a known utility function; altruistic nodes are nodes that always stick to the protocol. In this context, a protocol is said to be BARresilient if it tolerates a fixed amount of Byzantine nodes and an unlimited proportion of rational nodes. BAR-resilient protocols often combine game theory by adding incentives that encourage rational nodes to stick to the protocol and accountability techniques that expose Byzantine nodes in case of deviation. In the last years, various collaborative systems have been designed according to this model including protocols for spam resilient content dissemination [START_REF] Ben | Firespam: Spam resilient gossiping in the bar model[END_REF], distributed file systems [START_REF] Aiyer | Bar fault tolerance for cooperative services[END_REF], video live streaming [START_REF] Mol | Give-to-get: free-riding resilient video-on-demand in p2p systems[END_REF], [START_REF] Li | Bar gossip[END_REF], [START_REF] Guerraoui | Lifting: lightweight freerider-tracking in gossip[END_REF], anonymous communication [START_REF] Mokhtar | RAC: a freerider-resilient, scalable, anonymous communication protocol[END_REF] and N-party data transfer [START_REF] Vilac ¸a | N-party BAR transfer[END_REF]. The process by which a new BAR-resilient protocol is designed usually involves the following steps: (1) define the utility function of rational nodes in the considered protocol; (2) list all the possible rational deviations according to the defined utility function; (3) for each identified deviation, propose incentives for rational nodes such that any deviation would engender a loss in the utility perceived by the deviating node and mechanisms that would catch the considered Byzantine deviation; (4) prove that the proposed protocol is a Nash equilibrium. The major limitation of this approach is that it has to be performed manually by a system expert, which is complex and possibly error prone. Furthermore, any modification in the original system requires to rethink the system as a whole, as the latter may introduce new rational or Byzantine deviations. Rational nodes in the BAR-model correspond to selfish nodes in our work.

A grail that security managers may dream of having is a way of automatically transforming a given protocol into a BAR-resilient protocol. Two solutions that go towards this direction have been proposed in the literature. First, Nysiad [START_REF] Ho | Nysiad: Practical protocol transformation to tolerate byzantine failures[END_REF] allows the automatic transformation of a given protocol to a Byzantine resilient system. Nysiad reaches this objective by replicating each node using a variant of replicated state machines (RSMs). However, the resulting system does not deal with rational nodes. Contrarily to Nysiad, PeerReview [START_REF] Haeberlen | Peerreview: Practical accountability for distributed systems[END_REF] allows to automatically detect all sorts of observable deviations, including both selfish and Byzantine deviations, that a node would perform in a given monitored protocol. PeerReview reaches this objective by using tamper evident logs and assigning monitors to nodes, which periodically assess the correctness of a node by comparing its log with a correct execution of the protocol obtained using a reference implementation. However, while PeerReview allows to deter faults in the underlying protocol to which it is applied, it does not detect deviations performed by nodes on its own protocol steps.

Our objective in this paper is to design the first generic protocol that deals with both selfish and Byzantine nodes on any underlying protocol.

III. PROBLEM STATEMENT AND SYSTEM MODEL

We present in this section an evidence that the PeerReview protocol fails to enforce accountability in presence of selfish nodes in Section III-A. We then present our system model in Section III-B.

A. Problem statement

Let us consider a system where nodes can be correct, selfish or Byzantine. As introduced in the previous section, correct nodes follow the protocol, Byzantine nodes can behave arbitrarily and selfish nodes aim at maximizing their benefit with respect to a known utility function. The PeerReview protocol has been designed under the assumption that every node is monitored by a set of monitors and that each monitor set contains at least one correct node that executes all the monitoring steps. In this work, we remove this assumption and consider that any node in the system can behave selfishly if it has an interest in doing so. We show that nodes executing PeerReview can skip some steps of the monitoring protocol without being detected and that such behaviour can have a dramatic impact on the performance of the monitored protocol. We provide in the companion technical report [START_REF] Diarra | Practical accountability in presence of rational nodes[END_REF] a complete analysis of all the protocol steps of PeerReview and list all the selfish deviations that they are subject to. Due to the lack of space, we present here our practical results only. Specifically, to assess the impact of selfish nodes in PeerReview, we performed the following two experiments. In the first experiment, we deployed on one hundred nodes the SplitStream protocol [START_REF] Castro | Splitstream: high-bandwidth multicast in cooperative environments[END_REF], an efficient tree based multicast protocol, monitored by PeerReview. In the second experiment, we deployed one hundred nodes running the Onion routing proLOcol [START_REF] Goldschlag | Onion routing[END_REF] moniwred by PeerReview. In both cases, we used the same experimental settings as the ones described in Section VI. In both experiments, if a selfish node notices that its monitors are selfish (e.g., because they never ask to audit its log), it also behaves seliishly with respect LO the SpliLStream and Onion routing protocols by dropping messages iL receives and lhaL are noL intended Lo him.

We measure the percentage oJ lost messages with respect Lo the proportion oJ sellish nodes in the system. Results, depicted in Figure 1, show that in presence of up Lo 30% of selfish nodes. correct nodes running the SplitStream protocol observe 54')i, of message loss. Similarly. in the Onion routing application. correct nodes experience a loss in their onions that can reach 85% with 30% of seliish nodes in a conliguraLion with live relays. This proportion increases and reaches 100% when the number of relays increases. This is due lo the fact that the probability of having a selfish relay in a path increases proportionally with the number of relays constituting this path. The question we raise in this paper is thus how to enforce accountability in any underlying protocol in presence of selfish nodes? We answer this question in the remaining of the paper.

B. System model

Our target system is composed oJ Lwo protocols: the monitored protocol lo which we will refer as F and the monitoring protocol Lo which we will refer as M.

Fault model. We consider a fixed proportion oJ B y zantine nodes that can Lake arbiu•ary decisions. They can deviate from either For M proLOcols for any reason (e.g .. a failure, a bug, a threat). Purthermore, we consider any number of selfish nodes. These nodes aim at maximising their benefit according to a known utility function. Selfish nodes will deviate from 11, f if they gain some beneiiL in doing so. Specilically, this benefit can be represented along the following axes: Moreover. we assume that selfish nodes are risk al'erse. This means that before perfomling any deviation, a sellish node estimates the probability Lo be detected in the future. If this probability is greater than zero, a seliish node sticks lo the protocol. This assumption is commonly used in BAR systems [l], This assumption makes particularly sense in accountable systems because the detection of a deviation in these systems directly leads to the eviction of the faulty node from the system. Instead, in systems where the penalty is weaker, e.g., a decrease in a reputation value, it appears more appropiiale lo consider differem sellishness models (e.g., risk ailine). This is noL the case of our system.

The BAR model also supposes that selfish nodes join and remain in the system for a long time and seek a long-term benefit. Moreover. selfish nodes do not collude and assume that other nodes are correct.

System assumptions.

As in PeerReview. we assume a crypto graphic identification of nodes. Specifically, each message sent in the network is signed using the sender's cryptographic key. We assume lhaL cryptographic primitives can not be forged and that hash functions are collusion resistant. Moreover. we assume that messages sent by a sender to a given receiver are always received if retransmitted infinitely often. We assume that nodes have a deterministic reference implememaLion of F that can be initialised with checkpoints and Lo which we can i1�jecL inputs in order lo gel the corresponding outputs.

IV. Ful!Revie,v PROTOCOL OYl.!RYIEW

Let us consider a set oJ iV nodes executing a protocol F ddined as a set oJ delernlinislic stale machines. In Ful!Revien•, nodes take part in a classical accountability architecture as depicted in Pigure 2. Specifically, each node i in our system interacts with a set of nodes referred to as i's partners and appearing on its right side in the ligure. In addition Lo its set of partners, node i is assigned a seL of monitors that pe1iodically verify whether 'i sticks lo the specification oJ the protocol F or not. This set of nodes is referred to as m(i) and appears above i in the figure. Svmmetricallv. i monitors a set of nodes: the set of nodes� refetT�d to as m 0 1 (i) and appearing below i in the figure. To perforn1 this monitoring, each node maimains a secure log that is Lamper evident and append only, in which it writes all its interactions with its partners (details on secure logs are given in Section V-A). This log is periodically audited by i's monitors. Each monitor mns a monitoring protocol lvf also described as a set of deterministic state machines. The objective of Ful!Re�•iew is to force selfish nodes to execute all the steps of both protocols F and At and lo detect when Byz;antine nodes deviate from either protocols F or lvi.

m(i): i's monitors � \ I . • ' • \ I , \.! -✓� Et .. / i ', � p(i) ; i ! s pdr Lners ••-+ Mon� Loring .acl1011S ----+Monitored dC Li.
To reach this objective, each node i Logs in its secure log all its actions related to both protocols l' and lvi. Then, i's monitors, i.e. nodes in the set rn(i), pe1iodically perfonu a set of verifications on this log. These verifications. which are depicted in the diagram of hgure :I. allow each monitor to reach evidence ahout the correctness of i. Specifically, each node in rn (i) starts by verifying that i did not tamper with its log (e.g .. that the node did not delete previously inserted enuies). We call this ve1iiicalion, which appears on the top of the diagram. log r:oherence check. We explain how this verification is performed in Section V-131.

huther. each node in m(i) verifies that i holds a unique log for all its partners. We call this verification, which appears second in the diagram, log consi.rtency check. The above I wo velilications are critical for the accountability system to be effective. Indeed, if a node manages Lo add/dekle log enl1ies or to have multiple versions of a log. it could deviate from the protocol without being detected. We explain how this verification is performed in Section V-132.

Moreover. each node in m(i) verifies that the cn111111u nication patterns appearing in i's Log are coherent with Al and l''s stale machines (third velilication in the diagram). This veliiicalion ensures that i's log contains a sequencing of messages that reflect a correct behaviour. 1--ior instance, a correct log should contain periodic requests from i to the set of nodes it monitors. i.e. the nodes in m -1 (i). The ahsence oJ such peliodic messages re1lects a faulty behaviour. We explain how these verifications are performed in FullRn,iew in Section V-B3.

However, a log that exhihits a correct sequencing of messages is not sufficient to guarantee a correct hehaviour. Hence. the last verification that is performed hy i's monitors is lo assess whether i's Log co1Tesponds Lo a correct execution oJ the protocols l' and Al or not. Verifying the confonnance oJ i's log with a conecL execution oJ l' is performed as in the PeerReview protocol. i.e. by re -executing the code of the protocol P using a reference implementation. Specifically. the inputs present in i's log are injected in the reference implementation oJ l' and the produced ompuls are compared with the outputs present in i's log. Mismatching outputs would consliLute an evidence lhaL i did not co1TecLly execute r.

Doing the same velilication for the protocol M is not possi hle. Indeed, as further discussed in Section V-84, re-executing the monitoring code is a recursive task and requires that a node's log contains the log of all the other nodes that are linked LO him in the moni101ing graph (which may possibly be all the nodes in the system). To avoid such an overkill, we identiJy all the computations performed in the protocol Al and ensure Iha! these computations are performed hy a set of nodes in parallel. The outcome of each computation is then collected from the various participating nodes and sent to the nodes' monitors. The laller compare the outcome oJ the compulalion pedonued by their monitored node with respect lo what other nodes have computed. As sellish nodes do 1101 wam LO be ex. posed hy correct nodes, they will always perform the computation correctly. In the diagram of 1--iigure 3, this last verification is performed before the re-execution of P's code because the Latter is more costly. Details or how Ad/Review velilies that nodes co1TecLly executed the computations appeming in both protocols M and l' are desc1ibed in Sections V-B4. 1--iig. 3: FullRe. ' iew monitors decision diagram.

V. Ful/Re, ' iew DETAILED DF.SCRil'TIOK

We start this section hy introducing secure logs, a central component for enforcing accoumabilily (Section V-A). We then presem the Lwo major parts oJ our protocol, i.e. the audit protocol (Section V-B) and the omission failure protocol (Section V-C). hnally. we give some information ahout how we carried out the Nash equilihrium proof for our protocol (Section V-D).

A. Accmmtahility Mols: Tamper Evident lnR Secure Logs are often used lo enforce accountability in distributed systems. A secure log is generally used to store the messages ex. changed by a node with its partners. According Lo the requirements of the accountable system. log entries labelled Po, ... , f1., can contain various information among which an identifier of the logged message, whether the message was sen I or received by the node as well as its parameters. To each log entry e .. corresponds a recursive value h 1, . computed as a hash oJ c . , concatenated with the value or h 1 . ,-i (where / 1._ 1 is a fixed value), and an authenticator n?, which is a message containing the value of h 1 . , signed with i"s private key, i.e. nf = (h.,) 11 ,. Authenticators allow verifying that a node log has 1101 been tampered with. For instance. consider a node j among node's i monitors. If j gets a pair or au1hen1ica1ors a; 1 and ut' corresponding 10 the entries tr, and f/, : of i's log respectively, it can ask i of its log entries Po, ... , fJ.: and recompute h 0 , ... , h, , . If the computed h,, differs from the one held by _j. the latter can accuse i of tampering with its log. Further, j can convince any other correct node or the ntisbehaviour or i by sending to iL the signed authenticators u7 and uf along with the Log entries sent by i.

B. Ful!Review selfi.1• h-re.rilient audit protocol

Using the secure log descrihed ahove, a node _j monitoring the hehaviour of a node i performs a set of verifications to assess lhe correctness of i following the diagram of Figure 3. However. seliish monitors might be templed not to perfom1 lhese verifications. In order lo force monitors lo perform them, we make audits proactive. Specifically. we divide time in rounds and give the responsihility for each node to periodically (e.g., at the end of each round) ask its monitors to audit its log following the diagram depicted in Figure 5 (the Audit_req message sent from i to its monitors m( i)). Then, each monitor performs lhe required ve1ificalions and produces a certificate of correctness if the node passes al I of them. In the opposite case, i's monitors send a proof of mishehaviour to i including the evidence of i's m ishehaviour. which any correct node can recompute. This certificate is then used by i al the beginning of lhe following round in order lo communicate with its paru1ers. Without such a certificate, i's partners will refuse to interact with i. Note that some of i's monitors might he unresponsive (either hecause of a failure or to avoid auditing i's log). We descrihe how we deal with this situation in Section V-C. Finally, after collecting lhe outcome of the audit produced by its monitors (Audil_resp message), i forwards the aggregated outcome lo the monitors of each of its monitor (Fwd_outcome message). This l,rnt step is useful for the monitors of i's monitors (i.e. m(m(i)J) in order to verify whether the nodes they monitor correctly performed their monitoring tasks or not. Furlher details on lhis ve1ificalion are given in Section V-B4.

In the following we descrihe in detail the set of verifica tions performed hy the monitors of each node to assess its correctness.

I) Log coherence check:

Allows verifying that a node's log has not heen tampered with. Consider a node _j that monitors a node i. If J gets a pair of authenticators n? and nf corresponding lo the enuies (: 0 and (:1., or i's log respectively. il can ask i for ils log entries to, ... , t1< and recompute ho, ... , h ., .

Ir the computed h 1< differs from lhe one held by j, the lauer can accuse i of tampering with its log. 1-<urther. j can convince anv other correct node of the mishehaviour of i hv sending to it th� signed authenticators n� and nf along with the log e�tries sem by i. To perfonu this type of vedlication each node shall log each message ii sends as part or the protocols F and Ai and send the corresponding aulhemicator to its partner. Further more, each node shall forward the received authent icators to its partners' monitors. However, selfoh nodes might he tempted not to follow these steps, i.e. avoid attaching authenticators wilh messages they send and/or avoid forwarding received authenticators lo lhe paru1er's monitors. We show how we deal wilh this issue in Section V-B3.

2) Log con. �i11tency check: Node i might he tempted to maintain many correct logs (e.g., one log for each node with whom it interacts). To detect lhis type of misbehaviour. a monitor j that holds a set or aulhenticators sem by i 10 olher nodes verifies that these authent icators helong to the same log. Similarly to the log coherence check, this verification requires th at nodes attach authent icators to all messages they sent and forward received aulhemicators lo their partners' monitors. and lhal monitors perform lhe consistency check. We show how we encourage selHsh nodes lo perfom1 lhese steps in Section V-B3.

3) Verifying communication patterm:

In this part of the protocol, a node in the monitor set of a node i is responsihle for assessing whether the log or i reflects co1Tect communication pal terns with respect to lhe stale machines or J > and M. How ever. it is 1101 possible 10 consider lhe stale machines of these two protocols separately as in some situations steps of AI need to he interleaved with steps of P. i-;or instance. as seen in the log coherence and consistency checks descrihed ahove. nodes need lo send authenticators along with messages related lo F and need 10 forward authenticators received along with mes sages related to 1'. To reach lhis objective, lhe state machine or the protocol Pis automatically augmented with a set of manda tory transitions as depicted in hgure 6. In this figure. and in all the figures depicting automata in the paper. transitions are labelled as follows: (PIM:INI OUT:message_type) where the Jirsl part refers lo whelher the message belongs lo the protocol F or A• l; lhe second part indicates respectively whelher the message is received or sent and the third pa1t is the message type. This figure shows that each time a node is expecting a message as part of the protocol P, it should: ( l) upon receiving lhe message, forward the included authenticator to the sender's monitors (transition labelled (M :OUT :fwd_auth)): or (2) accuse the sender if lhe message did not contain an authenticator hy sending an accusation message to the sender's monitors (transition lahelled (M:OUT:accuse)): or (3) suspect its partner if the latter did not send the expected message (transition labelled (M:IN:timeout)). The uansitions following this latter uansition are Jurlher described in Section V-C. Augmenting all I he 1rai1silio11s of 1' related LO Lhe recep1io11 or messages as shown in Figure 6 forces seliish nodes to allach authenticators LO the messages they send (otherwise. nodes that receive theses messages might accuse them). i-;urthermore, it forces selfish nodes to forward the received authenticators to their partner's monitors (otherwise, their monitors might accuse them of behaving seliishly).

In addition to verifying that a monitored node's log is co herent with the state machine of the P augmented automaton, monitors vedfy that the log is coherent with i\d state machines related lo the audit protocol (descdbed earlier in lhis section) and wilh Ai state machines related to the handling oJ omission failures. The former state machines are depicted in Pigures 7 and 8 while the latter are descrihed in the following section. Specifically. the automaton of Pigure 7 shows the correct communication pallems oJ a node i asking one oJ its monitors for an audit (uansilion labelled (M:OUT:audit_req)). Arter sending his audit request, node i eilher receives a response from its monitor containing the outcome of the audit (transition lahelled (M:IN:audit_resp)) or does not receive a reply (the transition lahelled (M :IN :timeout)). In the former case. node i forwards lhe outcome oJ the audit 10 the monitors oJ all or its monitors. which allows them LO vedfy lhal their monitored node reached the same outcome about the coneclness or i as the olher moniLOrs oJ i. In lhe laller case, i considers thal ils monitor has failed and handles lhis failure as desc1ibed in the following section.

The automaton of hgure 8 shows the correct communi cation patterns of a monitor _j that receives an audit request from a node i that it is monitoring (the transition labelled (M:IN:audit_req)). After lhe reception of this request, node j performs the audit of i's log and sends back lhe oulcome to i (the transition labelled (M:OUT:audit_resp)). 4) Verffying computation.�: In this part of the protocol. each monitor j in the monitor set of a node i verifies that the computations performed by i as parl oJ the protocols l' and M are correct. For lhe computations performed by i and thal are relaled to l', j use checkpoints slored in i's log and initializes the reference implementation it has with the oldest non-verified checkpoint. J--iurther, . J replays all the inputs availahle in the portion of i's log it is auditing and verities that the oulputs produced by lhe reference implemenlalion match with the outpuls stored in lhe log. If the compuled oulputs do not malch wilh the logged ones. j accuses i of misbehaviour. Whether i passes this verification or not, j stores the outcome of the audit along with the authenticators corresponding to the portion of the log of i that it has audited and sends the outcome oJ the audil lo i as prescribed by lhe audit protocol (described earlier in this seclion).

�-

Contrmily to lhe computations related to lhe prowcol F, verifying those related to the monitoring protocol l'vf can not he done hy re-executing the steps of the protocol !If. To intuitively understand why, let us consider the following example, where node i nwnilors node i -1 (among other nodes) and is moniwred by node i + 1 (among other nodes).

At a given e.x.eculion time. the monilor of node i+ 1, say node i + 2 would like to audit node i + J's log to verify that it is correctly performing its monitoring actions regarding the hehaviour of i. To do so, node i + 2 needs to get access to node i's log. which is available in i + l's log. Hence, LO check whether i + 1 has correctly done his monitoring aclions. it needs 10 veriJy whether i + 1 cmrectly audiled i's by replaying lhe audil verificalions itself. However. 10 verify whelher i is effectively correct, i + 2 must ve1iJy whether i correctly executed its monitoring steps with respect to i-I. To do this last verification, i + 2 must verify whether the outcome of i's audit over i -I's log is correct and is thus ohliged to audil ilself il's log. This process dearly leads each node to recursively oblain and audit the logs of all the other nodes that it is connected lo in lhe monitoring graph. which is 1101 practical.

To a void such an overkill. we use incenli ves 10 force sellish nodes to correctly perform the computations taking part of the protocol l\-f instead of recomputing them. Specifically, as described earlier, after receiving the outcomes of the audit sent by its monitors. a node aggregales these resulls and forwards them to lhe monilors oJ ils monilors. These nodes receive an inforn1a1ion oJ lhe lype: (audited node ID, authenticators, monitor ID, outcome) for each of i's monitors that took part in the audit. If a majority of monitors detects a misbehaviour in i's log and one of them, say node j, did not, then j is accused of misbehaviour. In this situalion, j is seUish iJ ii claimed lhat i is correct without perfornring lhe verilicalion or Byzanline iJ ii replied arbitrarily. As selfish nodes do 1101 want to he excluded from the system, they always pe1form the computations related to l'vf correctly. Instead, if a majority of monitors hut J considers that i is correct. J is considered By:i:antine. as a seUish node do nol have any inlerest in accusing a correct node or misbehaviour.

C. Handling omission failures

The handling of onrission failures is done in Ful/Review as depicled in Figure 9. Specifically. iJ a node i wails for a given message from a given node j for too long, i suspecls j (after step ( 1) in the figure). To do so, i creates a challenge for . J and sends this challenge to j's monitors (step (2) in the figure ), who forward the challenge to j (step(\) in the figure). If j is still alive in lhe syslem then it replies 10 the challenge (step (4)). Whelher j replied or not to lhe challenge. afler a given amount oJ time j's monitors send an outcome oJ lhe challenge to i summarizing the situation (step (5)).

A selfish node may he tempted not to suspect a node even if it has waited for too long to receive a message assuming that other nodes wil I take care of that. Si mi larly. a selfish monilor nright be !empted not to forward a challenge send by i lo j assuming thal the olher monilors will do so. These two deviations are 1101 possible in Ful/Revici,• because of lhe verification of communication patterns performed hy monitors on their monitored node's log. Specifically, the automata of hgures 10 and 11 show the correct communication patterns that should be present in the log or a node when, as a monilor. ii receives an onrission failure complaint aboul one of its monilored nodes and when. as a suspected node, it receives a challenge from its monitor. The log of a selfish node should he conform to these automata, otherwise it 1s accused hy its monitors.

In addition, a selfish node might he tempted to suspect a node instead of performing a costly interaction with him. To avoid lhis devialion, we make the cosl oJ suspecting a node higher than the cost of inleracling wilh him. To avoid to overload lhe syslem, we adapl lhis cost to each slep oJ lhe pro LO cols 1' and M. For instance. if sending a message m costs xH of bandwic\Lh Lo node -i. we make the cost or suspecLing a node j to whom i was supposed to send m equal to :r + r,n.

As such, a selfish node i will always prefer to send m instead of suspecting _j. --------=E----SIIZ..------ We canied oul a detailed analysis of all Lhe protocol sLeps of Ful!Review. Por each of these steps we listed all the selfish deviations and the corresponding incentives that prove that selfish nodes do not have any interest in performing them. As a resulL we prove Lhal Ful!Review is a Nash equilibdum. Due LO Lhe lack or space, this analysis is presented in the technical repon available online [START_REF] Diarra | Practical accountability in presence of rational nodes[END_REF].

m (j) -

VI. PL!Rl'OR.\'IAKCL! EVALUATIO�

In Lhis secLion we evaluaLe the performance or PeerR£'1'iew and Ful!Rei,iew with two distrihuted applications: SplitStream and Onion routing. We start hy introducing the two applica tions and our experimental settings in Section YI-A and VI-B. respectively. We Lhen present the perfonnance of FullR£'1'iew in presence or sellish nodes ( Sec Lion VI-C) and in Lhe JaulL free case (SecLion VI-D). Finally, we assess the scalability of Ful!Re,' iew (Section VI-E).

Overall, our evaluation draws the following conclusions. Pirst. we show using real experiments that Ful!Re, • iew can effecLively deLecl JaulLs in presence or seUish nodes. Second, Ful!Review acids a small overhead compared lo PeerRn,iew boLh in terms or lraflic generated and sLOrage. Finally. using complementary simulations, we show that Ful!Review is scal able up to at least I 000 nodes.

A. Applications I) Accotmtahle E,fjicient Multicast: SplitStream 151 is a protocol that organises nodes in a tree structure where each node receives multicast messages from iLs parenL node and forwards Lhem lo ils child nodes. The specificity of SpliLSueam is LhaL ii aims al balancing the forwarding load between nodes.

Il reaches this objecLive by spliLLing the multicast sueam imo suipes and using different mulLicasL trees lo disldbule each stripe. Por our experiments, the source node generated a video stream of 300kh/s, which is a common rate for video-streaming applications. Each packet emitted hy the source was sent Lhrough a different multicast tree where each node had Lwo children.

h1 SpliLSlream. sellish nodes deviaLe by not forwarding updaLes LO Lheir child nodes. As a resulL they can gel the video stream while saving bandwidth. However, in presence of selfish nodes. correct nodes may experience frame loss and consequently receive a degraded version of the video stream.

2) Accountable Awmymous Cm11mu11icatio11: Onion rout ing 1131 is a protocol designed for anonymous communica tions. It is the protocol used in the TOR project 181, which is widely used by thousands of users daily. In Lhis protocol. when a node S wanLs lo send a message lo a node D. ii chooses H other nodes. called relays. Lhal will forward the message up to its destination. Node !3 encrypts successively the message using the public key of each of these relays, which constitutes the onion and then sends it to the first relay. Each relay decrypts one layer or Lhe onion (i.e. removes one layer or encryption) and forwards ii LO the next one until ii reaches iLs final desLinaLion. For Onion routing experiments, each node periodically emitted a packet to a randomly chosen node through a parametric number of relays. In all our experiments, messages have a fixed size of I0kB; smaller messages are padded wiLh additional byLes in order lo meeL Lhis requiremem. Fixing message size is usually done in onion routing as ii avoids an attacker Lo follow the progression of an onion in the system hy comparing the size of frnwarded messages.

In this protocol. a selfish node can choose not to forward an onion that is not intended to him. As a result. the destination will never receive the original message. The objective with designing a sellish-resilielll version or Onion routing is Lo ensme Lhal nodes will forward the onions they receive while providing anonymiLy guarantees.

B. E>. ;p erimental settings

We have measmec\ Lhe perfonnance or SpliLSueam and Onion routing in two configurations: (i) with PeerReriew and (ii) with Ful/Rel' iew. Our experiments have been pe1formed in two different settings. Pirst, we performed experiments in real conc\iLions using the public Giic\'5000 clusLer. In Lhis clusLer we used 50 quad-core physical machines clocked al 2.6GHz with 4GB of RAM Lhal are imerconnected via a Gigabil switch. These experiments have been nm by deploying one logical node per physical machine and corresponding curves are annotated with IG5KI in their lahels. To complement our expeiimenLs. we perr01med simulaLions using the I' eerReview simulawr LhaL has been developed by I'eerRevie11• authors 2. We perfonnec\ simulaLions with up LO 1000 nodes. in order lo as sess the scalability of Ful/Re, • iew. Results of these experiments are annotated with ISIMI in their labels.

C Performance in presence of selfish nodes

In this section we show that Ful/Review tolerates selfish nodes. To this end, we perform two experiments. In the first experiment, selfish nodes follow the model presented in Section III-B. Specifically, they deviate only if they have an interest to do so and if there is no risk to be caught. Instead, in the second experiment, we consider that selfish nodes deviate if they have an interest to do so without considering the risk of exclusion. This latter experiment shows that if they decide to do so, selfish nodes are quickly detected by their monitors and excluded from the system.

For both experiments we used the two applications monitored by PeerReview and FullReview. The number of monitors per node is fixed to 2 and the audit period is set to 10s.

The results of the first experiment are presented in Figure 12. This figure shows the percentage of received messages as a function of the percentage of selfish nodes. SplitStream and FullReview are deployed with 50 nodes on G5K. We evaluate FullReview with different number of relays (5, 10, 20 and 40), that are chosen at random. However, due to lack of space, we present the results with 5 relays only. Increasing the number of relays leads to worst results for PeerReview as the probability to choose a selfish node in an Onion routing path becomes higher. We first observe in this figure that, using PeerReview, SplitStream and Onion routing do not tolerate selfish nodes. Indeed, in presence of only 10% of selfish nodes, only 79% and 66% of messages are received in the SplitStream and Onion routing applications, respectively. This represents a loss of 21% and 34% messages, respectively, which is not acceptable. This percentage decreases when the proportion of selfish nodes increases, reaching 23% in SplitStream and 5% in Onion routing, in presence of 50% of selfish nodes. Instead, using FullReview, we observe that all messages are received in both applications as selfish nodes have no interest in deviating. The results of the second experiment are presented in Figure [START_REF] Goldschlag | Onion routing[END_REF]. In this experiment, we measure the percentage of received messages in SplitStream with PeerReview and Full-Review where selfish nodes start to deviate from the protocol after 20s. This experiment has been launched with 50 nodes using simulations. As explained above, in this experiment, selfish nodes behave selfishly without reasoning on the risk of being detected. Using PeerReview, we observe that selfish nodes impact the system as soon as they behave selfishly, without ever being detected. Using FullReview, we observe that selfish nodes impact the system during a small time frame, corresponding to the audit frequency, after which they are detected and evicted from the system. As a result, all the messages are received for the rest of the experiment. Note that choosing a smaller audit period allows the system to detect selfish nodes more rapidly, but at the expense of some additional overhead, as we show in the next section. PeerReview, 10% selfish FullReview, 10% selfish PeerReview, 50% selfish FullReview, 50% selfish Fig. 13: [SIM] SplitStream percentage of received messages during an experiment in which between 10% and 50% of nodes start to act selfishly after 20s.

D. Performance in the fault-free case

In this section we assess the performance and overhead of FullReview, compared to PeerReview, in the fault-free case. To this end, we perform three experiments. We launch each of the experiments of this section both using simulations and G5K, but we show the results on G5K only. The results using simulations are consistent and can be found in the companion technical report [START_REF] Diarra | Practical accountability in presence of rational nodes[END_REF].

In the first two experiments, we measure the network traffic and the rate at which the logs grow w.r.t. the number of monitors, in PeerReview and FullReview respectively. In the case of Onion routing, an onion path was composed of 5 relays. Figure 14 presents the results for both SplitStream and Onion routing. Each value has been obtained by running the system with 50 nodes during 5 minutes.

In the left figure, each bar represents the traffic due to the payload of the application. On top of this payload is the traffic due to PeerReview, on top of which is the overhead of FullReview in addition to the one of PeerReview. In this figure, we observe that the average traffic per node increases w.r.t. to the number of monitors for both PeerReview and FullReview in the two applications. This is due to all the messages that need to be exchanged between nodes and their monitors. Further, we observe that the overhead due to accountability in the SplitStream application has an overall cost of 14% in PeerReview with two monitors and an extra cost of 7% in FullReview. This overhead grows up to 45% for PeerReview and an additional 31% for FullReview when 5 monitors are used. These costs are much higher if compared to the payload of the Onion routing application. For instance, enforcing accountability in Onion routing using PeerReview generates a traffic of 129kb/s per node while the application itself generates a payload of only 18kb/s per node. However, put into context this result is not bad, as enforcing accountability in anonymous communication protocols is a very challenging task for which existing solutions often require the heavy use of broadcast primitives (e.g., RAC [START_REF] Mokhtar | RAC: a freerider-resilient, scalable, anonymous communication protocol[END_REF], Dissent [START_REF] Corrigan-Gibbs | Dissent: accountable anonymous group messaging[END_REF]). Further, assuming that nodes are connected using Gigabit links (in the case of a LAN) or even using few Megabit links (in the case of a WAN), 129kb/s seems a reasonable overhead. The good news is that if the developer accepts to pay the cost of accountability using PeerReview in a system with a small payload, using a selfish resilient accountability system, i.e. FullReview, would cost him an extra 3kb/s (i.e. 2% more traffic) with two monitors and an extra 15kb/s (i.e. 5% more traffic) with five monitors. Note that, overall, enforcing accountability using PeerReview is more expensive in the Onion routing application than in the SplitStream application because in the former application the full onions are stored in the log while in the latter instead of storing the video chunks received by nodes in the log, we store only their identifier. Indeed, storing onions was the only way we found to enable monitors to verify that a node has correctly decrypted and forwarded an onion it received.

In the right figure, each bar represents the average growing rate of the log of nodes. Similarly to the previous figure, the cost of FullReview is shown as a delta in addition to the cost of PeerReview. Note that logs do not grow forever. Indeed, as in PeerReview, logs are truncated after a given amount of time and audits are performed only for the new parts of the log. Obviously, the longer the logging period chosen by the designer, the higher the probability to deter faults.

Results depicted in this figure show that the log growing rate of the SplitStream application is higher than log growing rate of the Onion routing application, which is due to the fact that the SplitStream application generates more messages to send the video stream than Onion routing, and thus more interactions are added to the log. Further we observe that the higher the number of monitors per node the higher the log growing rate. On the Onion routing application, the overhead in terms of log growing rate is equal to 4.9% when using FullReview with two monitors and increases up to 24% when using five monitors. On the SplitStream application, this overhead is higher as it spans from 6.8% to 30% when using respectively two and five monitors. Yet, we consider this overhead as reasonable. Indeed, in the worst of our experiments (i.e, in the SplitStream application using five monitors), for 24 hours logging, nodes need to devote 4.4GB of storage for enforcing accountability in presence of selfish nodes, which is reasonable.

In the third experiment, we measure the impact of the audit period on the overhead of FullReview compared to PeerReview. The audit period was ranging from 1s to 30s. We set the number of nodes to 50, with 2 monitors per node and 5 relays for the Onion routing application. Each experiment last 5 minutes. Results, presented in Table I, show that even with a high frequency of audit (i.e. every second), FullReview generates only 6.7% more traffic and logs are 8.2% larger than PeerReview in the worst case. To summarize, FullReview adds a small overhead to Peer-Review in terms of generated traffic and log size. This overhead is mainly due to the new log entries inserted by FullReview to detect selfish nodes. Similarly to PeerReview, the cost of Full-Review increases with the number of monitors per node and with the frequency of the audits. Overall, accounting for the increasing resources (storage and network bandwidth) at the disposal of a large public (Terabytes of storage and Megabits of network bandwidth), the cost of enforcing accountability in presence of selfish nodes becomes a realistic option.

E. Scalability of FullReview

In this section we show that SplitStream-FullReview and Onion routing-FullReview scale up to at least 1000 nodes.

Figure 15 presents the network traffic and the log growing rate of SplitStream and Onion routing, for both PeerReview and FullReview, as a function of the number of nodes in the system. Each value has been measured via a simulation that lasts 100s. Moreover, the system has been configured with 5 monitors per nodes. As one could expect from the results of Figure 14, using less monitors provides better performance. In addition, the audit period was set to 10s. Finally, Onion routing was configured with 40 relays and was sending onions at a rate of 16kb/s.

From this figure we can draw the following conclusions. First of all, for both SplitStream and Onion routing, the network traffic and log growing rate of FullReview is within a constant factor of PeerReview. For instance, with SplitStream, the log growing rate (resp. network traffic) of FullReview is equal to 1.4x (resp. 1.3x) the one of PeerReview. This is due to the fact that FullReview adds a constant number of operations on the ones performed by PeerReview. Second, we can observe that FullReview scales up to 1000 nodes, as the network traffic and log size remain fairly stable despite the increase of the number of nodes. The reason is that each node always interacts with the same number of nodes on average, whatever the overall number of nodes in the system (i.e. its partners w.r.t. to the application and a fixed number of monitors).

VII. CONCLUSION

This paper addresses the problem of accountable distributed systems in presence of selfish nodes. We have shown that PeerReview, the only software generic solution to enforce accountability, does not tolerate selfish nodes. To tackle this problem we propose the FullReview protocol. This protocol uses game theory techniques by embedding incentives that force selfish nodes to stick to the protocol. We have evaluated FullReview on a cluster of physical machines and using simulation with two applications: SplitStream, an efficient multicast protocol, and Onion routing, the most widely used anonymous communication protocol. Our evaluation makes the following points. First, contrarily to PeerReview, FullReview effectively tolerates selfish nodes. Second, FullReview has a low additional overhead compared to PeerReview. Finally, FullReview scales up to 1000 nodes.

  __,. __ __.,_ __ .,.._ _ __, ____ ---" rout i ng w/ 5 relays ---><---:'/,' On i on rout i ng w/ 40 relays ---':.f:o---�----�-----

Fig. 1 :

 1 Fig. 1: Impact of seliish nodes in PeerReviewed SpliLSLream and Onion routing protocols.

  Sending/receiving as liule as pos sible monitoring messages to/from other nodes. 2) (Computation) Performing as little as possible monitoring-related computations for other nodes.

  on.::: in• (i) : i's rnoni Lured nodes

Fig. 2 :

 2 Fig. 2: Simple accoumabilily architecture.

  i) rdkcl com.• cl communication Ko pallerns wrl P aml M protocols/ YP.� Do all t l 1P. computations perfonrn:�c1 hy i '\l,,'l t Lo J\."l appear corrccl'? Yes Dues lug(i) correspumb lo a rnrrecl l' Xl' CULion o[ P'! Yes t I• cnn'!'CT Ko Ko i is ta11l1y

Fig. 4 :

 4 Fig. 4: Example oJ a secure log.

Fig. 5 :

 5 Fig. 5: Ful!Review audit protocol.

\

  •I:( llfl : ( h<lllE'n£E' rvl: I\ :1•l 1 nll_ n11.( 11m,;, J--iig. 6: Augmenting the P protocol. J--iig. 7: Sending audit requests.

�

  \1:IN : rrndil l' CQ ).1 : 0UT : ml.di[ rc:�p J--iig. 8: Dealing with audit requests.

Fig. 9 :

 9 Fig. 9: FullReview handling or omission failures

Fig. 12 :

 12 Fig. 12: [G5K] Percentage of received messages in SplitStream and Onion routing as a function of the percentage of selfish nodes.

Fig. 14 :

 14 Fig. 14: [G5K] Average network traffic and log growing rate per node of SplitStream (SS) and Onion routing (OR) w.r.t. the number of monitors.

Fig. 15 :

 15 Fig.15:[SIM] Average network traffic and log growing rate of SplitStream and Onion routing w.r.t. the number of nodes in the system.

TABLE I :

 I [G5K] Overhead of FullReview compared to Peer-Review, for both SplitStream (SS) and Onion routing (OR), with an audit period ranging from 1s to 30s.

Due to the lack of space, this proof is available in the companion technical report[START_REF] Diarra | Practical accountability in presence of rational nodes[END_REF]

PccrRcvicw code: http://pccrrcvicw. mpi-sws.rupg.de/.

ACKNOWLEDGMENTS

We thank the anonymous reviewers for the insightful comments that helped improving this paper. Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr). The presented work was developed within the EEXCESS project funded by the EU Seventh Framework Program, grant agreement number 600601.