Hala Skaf-Molli

Charbel Rahhal
email: charbel.rahal@loria.fr

Pascal Molli
email: molli@loria.fr

Peer-to-peer Semantic Wikis

Wikis have demonstrated how it is possible to convert a community of strangers into a community of collaborators. Semantic wikis have opened an interesting way to mix web 2.0 advantages with the semantic web approach. P2P wikis have illustrated how wikis can be deployed on P2P wikis and take advantages of its intrinsic qualities: fault-tolerance, scalability and infrastructure cost sharing. In this paper, we present the first P2P semantic wiki that combines advantages of semantic wikis and P2P wikis. Building a P2P semantic wiki is challenging. It requires building an optimistic replication algorithm that is compatible with P2P constraints, ensures an acceptable level of consistency and generic enough to handle semantic wiki pages. The contribution of this paper is the definition of a clear model for building P2P semantic wikis. We define the data model, operations on this model, intentions of these operations, algorithms to ensure consistency and finally we implement the SWOOKI prototype based on these algorithms.

Introduction

Wikis are the most popular tools of Web 2.0, they provide an easy to share and contribute to global knowledge. The encyclopedia Wikipedia is a famous example of a wiki system. In spite of their fast success, wiki systems have some drawbacks. They suffer from search and navigation [START_REF] Vôlkel | Semantic wikipedia[END_REF], it is not easy to find information in wikis [START_REF] Buffa | Sweetwiki: A semantic wiki[END_REF]. They have also scalability, availability and performance problems [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF][START_REF] Morris | DistriWiki: a distributed peer-to-peer wiki network[END_REF] and they do not support offline works and atomic changes [START_REF] Du | Dtwiki: a disconnection and intermittency tolerant wiki[END_REF]. To overcome these limitations, wiki systems have evolved in two different ways: semantic wikis and peer-to-peer wikis.

Semantic Wikis Semantic wikis are a new generation of collaborative editing tools.They allow users to add semantic annotations in the wiki pages. Users collaborate not only for writing the wiki pages but also for writing semantic annotations. Usually, this is done by annotating the links between wikis pages. Links in semantic wikis are typed. For instance, a link between the wiki pages "France" and "Paris" may be annotated by "capital". Semantic wikis provide a better structuring of wikis by providing a means to navigate and search based on annotations. These annotations express relationships between wikis pages, they are usually written in a formal syntax so they are processed automatically by machines and they are exploited by semantic queries. Semantic wikis try to preserve the benefits of classicals wikis such as, simplicity in creating and editing of wikis pages. Many semantic wikis are being developed such [START_REF] Vôlkel | Semantic wikipedia[END_REF]Semantic MediaWiki], [START_REF] Schaffert | Ikewiki: A semantic wiki for collaborative knowledge management[END_REF]IkeWiki] and [START_REF] Buffa | Sweetwiki: A semantic wiki[END_REF]SweetWiki].

P2P wikis Wikis on a peer-to-peer network attempt to reconcile the benefits of mass collaboration and the intrinsic qualities of peer-to-peer network such as scalability, fault-tolerance, better performance and resistance to censorship [START_REF] Androutsellis-Theotokis | A Survey of Peer-to-Peer Content Distribution Technologies[END_REF]. There are currently many research proposals to build P2P wikis such [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF]Wooki] and [8, git-wiki] [4, DistriWiki], [START_REF] Du | Dtwiki: a disconnection and intermittency tolerant wiki[END_REF]DtWiki], [START_REF] Patrick Mukherjee | Piki -a peer-to-peer based wiki engine[END_REF]Piki] and [START_REF] Kang | The hash history approach for reconciling mutual inconsistency[END_REF]Repliwiki]. The basic idea is to replicate wiki pages on the peers of a P2P network and the main problem is to ensure the consistency of copies.

In this paper, we propose to build the first peer-to-peer semantic wiki, called SWOOKI. SWOOKI combines advantages of P2P wikis and Semantic wikis. The main problem for building such a system is to maintain consistency of replicated semantic wiki pages. We propose an algorithm that ensures the CCI consistency (CCI stands for Causality, Convergence and Intention Preservation [START_REF] Sun | Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems[END_REF]) for the replicated semantic wiki pages. In the state of art, traditional wikis systems that ensure CCI consistency do not manage currently this data type.

Building a P2P semantic wiki based on the CCI model is challenging. The fundamental problem is to provide an optimistic replication algorithm that (1) is compatible with P2P constraints, [START_REF] Buffa | Sweetwiki: A semantic wiki[END_REF] ensures the CCI model and ( 3) is generic enough to manage semantic wiki pages. In this paper, we define formally the semantic wiki page data type, we specify its operations and we define the intentions of these operations. We extend the WOOT [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF] algorithm to take into account semantic annotations and finally we build SWOOKI the first P2P semantic wiki based on this algorithm.

The paper is organized as follow. Section 3 presents some related works. Section 4 details the general approach for building a P2P semantic wiki. It defines a data model and editing operations. Section 5 defines the causality and intentions of operations used to edit semantic data. Section 6 develops the integration algorithm. Section 7 gives an overview of the architecture. The last section concludes the paper and points to future works.

Use cases for P2P semantic wikis

We have identified three interesting use cases for P2P semantic wikis. We aim to develop a peer to peer semantic wiki that support these use cases.

Mass Collaboration . In this case, a P2P semantic wiki system is deployed as a Usenet network [START_REF] Spencer | Managing Usenet[END_REF]. For instance, thousands of semantic wiki servers can be deployed within organizations or universities. Any user can connect to any semantic wiki server. This deployment allows :

to handle a large number of users by dividing the load on the whole network. Semantic queries can be performed locally on each semantic wiki server. to tolerate many faults. A crash of one semantic wiki server does not stop the service.

to share the cost of the infrastructure. Wikis are set up and maintained by different organizations. Therefore, it is not necessary to collect funds just to maintain the infrastructure. For instance, Wikipedia foundation has to collect 150000 $ every three months just to maintain the Wikipedia infrastructure. to resist to censorship. An organization controls only one semantic wiki server and not all data. Off-line work and transactional changes Adding off-line capabilities to web applications is currently a major issue. For instance, the development of Google gears [START_REF] Kang | The hash history approach for reconciling mutual inconsistency[END_REF] and Firefox3 offline capabilities demonstrate the need of the off-line work. Wikis are web applications and the need for off-line wiki editing is real. Current technologies for adding off-line capabilities to web applications focus on Ajax applications. However, the off-line mode of these web applications does not provide all features available in the on-line mode. This can be an obstacle for a wiki system. For instance, the off-line mode of the wiki allows navigation but it does not allow editing. A P2P semantic wiki tolerates naturally off-line work by means of an integrated merge algorithm. With such system, it is possible to travel with a complete wiki system on a laptop, make changes off-line and re-synchronize with the P2P network as soon as an Internet connection is available. The off-line mode enables also transactional changes. Users can work disconnected if they lack internet connection or if they decide to disconnect directly from the user interface. While disconnected, a user can change many semantic wiki pages in order to produce a consistent change. The P2P semantic wiki ensures that the execution of concurrent transactions on different peers lead to a consistent state of the semantic wiki pages. Ad-hoc Collaborative Editing this scenario is derived from the previous one. Imagine several off-line wiki users have a meeting. Unfortunately, there is no Internet connection available in the meeting room. Therefore, they decide to set up an ad-hoc network within the meeting room. A P2P semantic wiki is able to propagate changes within the ad-hoc network and allows collaborative editing just for these off-line users. Of course, when the meeting is finished and users return to their organizations, their semantic wiki systems will re-synchronize with the whole P2P network.

The use cases presented above illustrate the importance of optimistic replication algorithms. In order to build a P2P Semantic wiki, there is a need for an algorithm that handles linear text and semantic annotations embedded in this text and ensures the CCI consistency.

The fundamental problem for building a P2P semantic wiki is to provide an optimistic replication algorithm that (1) supports collaborative editing, (2) manages a semantic wiki data type, (3) ensures the CCI model and ( 4) is compatible with P2P Constraints.

In the following, we show the state of the art of data replication in semantic web and collaborative systems

Replication in Semantic Web

Many researches have been done in P2P semantic web [START_REF] Nejdl | Edutella: a p2p networking infrastructure based on rdf[END_REF][START_REF] Morbidoni | Rdfsync: efficient remote synchronization of rdf models[END_REF][START_REF] Cai | Rdfpeers: a scalable distributed rdf repository based on a structured peer-to-peer network[END_REF][START_REF] Chirita | Publish/subscribe for rdf-based p2p networks[END_REF][START_REF]Semantic Web And Peer-to-peer[END_REF]. These works focus on sharing, querying and synchronizing RDF resources rather than collaborative editing of RDF resources. Sharing is different from collaboration. In sharing, some peers publish data while others can only read these data and concurrent updates are not managed. In P2P semantic wikis, some peers publish data, others can read and write these data and a synchronization algorithm integrates concurrent updates while maintaining consistency of these data. Existing synchronization algorithms of RDF resources such RDFSync [START_REF] Morbidoni | Rdfsync: efficient remote synchronization of rdf models[END_REF] and RDFPeers [START_REF] Cai | Rdfpeers: a scalable distributed rdf repository based on a structured peer-to-peer network[END_REF] are used in the sharing context. Hence, they are not adapted for P2P semantic wikis.In summary, P2P Semantic Web researches focus on knowledge sharing and querying. No algorithm has been designed for collaborative editing of RDF graphs. Consequently, the existing algorithms do not take into account concurrent updates on RDF graphs.

Replication in Collaborative systems

Data replication in collaborative P2P systems mainly relies on optimistic replication. Existing approaches can not be applied to the P2P semantic wikis context. For instance, the Bayou system [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF] is suitable for deploying a collaborative application on a decentralized network. Unfortunately, in order to ensure the convergence of copies, Bayou has to arrange eventually operations in the same order. To achieve this, it relies on a primary site that will enforce a global continuous order on a growing prefix of history. Using such a primary site is not compatible with P2P network constraints. Other systems such as Usenet [START_REF] Spencer | Managing Usenet[END_REF] apply the Thomas write rule [START_REF] Johnson | RFC677: The maintenance of duplicate databases[END_REF] to ensure eventual consistency. They ensure that, when the systems are idle i.e all operations have been sent and received by all sites, all copies are identical. Unfortunately, if there is two concurrent write operations on the same data unit, then the rule of "the last writer wins" is applied and in this case, this means that the modifications of a user are lost. Collaborative editing cannot be easily achieved if the system can loose some changes just to ensure eventual consistency.

Many algorithms have been developed by the Operational Transformation community [START_REF] Sun | Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems[END_REF] such as SOCT2, GOTO, COT etc. They are designed to verify the CCI model. But only few of them support P2P constraints such as MOT2 [START_REF] Cart | Asynchronous reconciliation based on operational transformation for P2P collaborative environments[END_REF]. However MOT2 algorithm suffers from a high communication complexity [START_REF] Ignat | A Comparison of Optimistic Approaches to Collaborative Editing of Wiki Pages[END_REF] and no transformation functions for a semantic wiki page are available.

Some existing P2P wikis such as giki or git-wiki use distributed version control systems (DVCS) to manage data. Wiki pages are stored as text files. DVCS manage them as code files. They ensure causal consistency. This implies that concurrent write operations can be seen in a different order on different machines. In this case, if two sites observe 2 write operations in different order then copies on both sites can diverge. DVCS systems are aware of this problem and delegate the problem to external merge algorithms for managing concurrent operations. However, as existing merge algorithms are not intrinsically deterministic, commutative and associative so convergence cannot be ensured in all cases. Wooki [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF] is the only available P2P wiki that ensures the CCI consistency. Wooki relies on the WOOT [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF] algorithm to ensure the CCI consistency for wiki pages. However, WOOT cannot be applied directly to a P2P semantic wiki. WOOT is designed to synchronize linear structures, it can not synchronize a mix of text and RDF graphs. We propose to extend the WOOT algorithm to handle collaborative writing on replicated RDF data model.

A P2P semantic wiki is a P2P network of autonomous semantic wiki servers (called also peers or nodes) that can dynamically join and leave the network. Every peer hosts a copy of all semantic wiki pages and an RDF store for the semantic data. Every peer can autonomously offer all the services of a semantic wiki server. When a peer updates its local copy of data, it generates a corresponding operation. This operation is processed in four steps: it is executed immediately against the local replica of the peer, broadcasted through the P2P network to all other peers, received by the other peer and integrated to their local replica. If needed, the integration process merges this modification with concurrent ones, generated either locally or received from a remote server.

The system is correct if it ensures the CCI (Causality, Convergence and Intention Preservation) consistency model [START_REF] Sun | Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems[END_REF].

-Causality preservation: operations ordered by a precedence relation will be executed in same order on every peer.

-Convergence: When the system is idle, all copies are identical.

-Intention and Intention preservation: The intention of an operation is the effects observed on the state when the operation was generated. The effects of executing an operation at all sites are the same as the intention of the operation. The effect of executing an operation does not change the effects of independent (not causally dependent) operations.

Data Model

The data model is an extension of Wooki [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF] data model to take in consideration semantic data. Every semantic wiki peer is assigned a global unique identifier named N odeID. These identifiers are totally ordered. As in any wiki system, the basic element is a semantic wiki page and every semantic wiki page is assigned a unique identifier P ageID, which is the name of the page. The name is set at the creation of the page. If several servers create concurrently pages with the same name, their content will be directly merged by the synchronization algorithm. Notice that a U RI can be used to unambiguously identify the concept described in the page. The U RI must be global and location independent in order to ensure load balancing. For simplicity, in this paper, we use a string as page identifier. Definition 2. A semantic wiki line L is a four-tuple < LineID, content, degree, visibility > where -LineID is the line identifier, it is a pair of (N odeID, logicalclock) where N odeID is the identifier of the semantic wiki server and logicalclock is a logical clock of that server. Every semantic wiki server maintains a logical clock, this clock is incremented when an operation is generated. Lines identifiers are totally ordered so if LineID 1 and LineID 2 are two different lines with the values (N odeID 1 , LineID 1 ) and (N odeID 2 , LineID 2 ) then LineID 1 < LineID 2 if and only if (1) N odeID 1 < N odeID 2 or (2) N odeID 1 = N odeID 2 and LineID 1 < LineID 2 .

Pages storage model

content is a string representing text and the semantic data embedded in the line.

degree is an integer used by the synchronization algorithm, the degree of a line is fixed when the line is generated, it represents a kind of loose hierarchical relation between lines. Lines with a lower degree are more likely generated earlier than lines with a higher degree. By definition the degree of L E and L B is zero.

visibility is a boolean representing if the line is visible or not. Lines are never really deleted they are just marked as invisible.

For instance, suppose there are two lines in a semantic wiki page about "France" , "France" is the identifier of the page. §

France is located in [locatedIn :: Europe] The capital of France is [hasCapital:: Paris ] ¦ ¥ Now, suppose these two lines are generated on the server with N odeID = 1 in the above order and there are no invisible lines, so the semantic wiki page will be internally stored as:

§ LB ((1,1), France is located in [locatedIn :: Europe], 1, true) ((1,2), The capital of France is [hasCapital:: Paris ], 2, true) LE ¦ ¥
Text and semantic data are stored in separate persistent storages. Text can be stored in files and semantic data can be stored in RDF repositories, as described in the next section.

Semantic data storage model RDF is the standard data model for encoding semantic data. In P2P semantic wikis, every peer has a local RDF repository that contains a set of RDF statements extracted from its wikis pages. A statement is defined as a triple (Subject, Predicate, Object) where the subject is the name of the page and the predicates (or properties) and the objects are related to that concept.

For instance, the local RDF repository of the above server contains : R = {("France", "locate-dIn", "Europe"), ("France", "hasCapital", "Paris") }. As for the page identifier, a global U RI can be assigned to predicates and objects of a concept, for simplicity, we use a string.

We define two operations on the RDF repositories:

-insertRDF(R,t): adds a statement t to the local RDF repository R.

-deleteRDF(R,t): deletes a statement t from the local RDF repository R. These operations are not manipulated directly by the end user, they are called implicitly by the editing operations as shown later.

Editing operations

A user of a P2P semantic wiki does not edit directly the data model. Instead, she uses traditional wiki editing operations, when she opens a semantic wiki page, she sees a view of the model. In this view, only visible lines are displayed. As in a traditional semantic wiki, she makes modifications i.e. adds new lines or deletes existing ones and she saves the page(s).

To detect user operations, a diff algorithm is used to compute the difference between the initial requested page and the saved one. Then these operations are transformed into model editing operations. A delete of the line number n is transformed into a delete of the n th visible line and an insert at the position n is transformed into insert between the (n -1) th and the n th visible lines. These operations are integrated locally and then broadcasted to the other servers to be integrated.

There are two editing operations for editing the wiki text: insert and delete. An update is considered as a delete of old value followed by an insert of a new value. There are no special operations for editing semantic data. Since semantic data are embedded in the text, the RDF repositories are updated as a side effect of text replication and synchronization.

1. Insert(P ageID, line, l P , l N ) where P ageID is the identifier of the page of the inserted line. line is the line to be inserted. It is a tuple containing < LineID, content, degree, visibility >. l P and l N are respectively the identifiers of the lines that precedes and follows the inserted line.

During the insert operation, the semantic data embedded in the line are extracted, RDF statements are built with the page name as a subject and then they are added to the local RDF repository thanks to the function insertRDF (R, t).

2. The delete(P ageID, LineID) operation sets the visibility of the line identified by LineID of the page P ageID to false. The line is not deleted physically, it is just marked as deleted. The identifiers of deleted lines must be kept as a tombstones. During the delete operation, the set of the RDF statements contained in the deleted line are deleted from the local RDF repository thanks to the deleteRDF (R, t).

Correction Model

This section defines causal relationships and intentions of the editing operations for our P2P semantic wiki data model.

Causality preservation

The causality property ensures that operations ordered by a precedence relation will be executed in the same order on every server. In WOOT, the precedence relation relies on the semantic causal dependency. This dependency is explicitly declared as preconditions of the operations. Therefore, operations are executed on a state where they are legal i.e. preconditions are verified. In the following, we define causality for editing operations that manipulate text and RDF data model. Definition 3. insert Preconditions Let P age be the page identified by P ageID, let the operation op=Insert(P ageID, newline, p , n), newline =< LineID, c, d, v> generated at a server N odeID, R is its local RDF repository. The line newline can be inserted in the page P age if its previous and next lines are already present in the data model of the page P age.

∃i ∃j LineID(P age[i]) = p ∧ LineID(P age[j]) = n Definition 4. Preconditions of delete operation Let P age be the page identified by P ageID, let op = Delete(P ageID, dl) generated at a server N odeID with local RDF repository R, the line identified by dl can be deleted (marked as invisible), if its dl exists in the page.

∃i LineID(P age[i]) = dl When a server receives an operation, the operation is integrated immediately if its pre-conditions are evaluated to true else the operation is added to a waiting queue, it is integrated later when its pre-conditions become true. r r ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee

Intentions and Intentions preservation

The intention of an operation is the visible effect observed when a change is generated at one peer, the intention preservation means that the intention of the operation will be observable on all peers, in spite of any sequence of concurrent operations.

We can have a naive definition of intention for insert and delete:

-The intention of an insert operation op= Insert(P ageID, newline, p , n) when generated at site N odeID, where newline =< nid, c, d, v> is defined as: [START_REF] Vôlkel | Semantic wikipedia[END_REF] The content is inserted between the previous and the next lines and (2) the semantic data in the line content are added to the RDF repository of the server.

-The intention of a delete operation op= delete(pid, l) when generated at site S is defined as : (1) the line content of the operation is set to invisible and (2) the semantic data in the line content are deleted from the RDF repository of the server. Unfortunately, it is not possible to preserve the previous intention definitions. We illustrate a scenario of violation of these intentions in figure 1. Assume that three P2P semantic wiki servers, peer 1 , peer 2 and peer 3 share a semantic wiki page about "France". Every server has its copy of shared data and has its own persistence storage repository. At the beginning, the local text and the RDF repositories are empty. At peer 1 , user 1 inserts the line "France is located [located In::Europe]" at the position 1 in her copy of the "France" page. Concurrently, at peer 2 user 2 inserts a new line "France is a country in [located In::Europe]" in her local copy of "France" page at the same position and finally at peer 3 user 3 deletes the line added by user 1 .

When op 2 is integrated at peer 1 , the semantic annotation is present two times in the text and just one time in the RDF repository. In fact, the RDF repository cannot store twice the same triple. When op 3 is finally integrated on peer 1 , it deletes the corresponding line and the semantic entry in the RDF repository. In this state, the text and the RDF repository are inconsistent.

Concurrently, peer 3 has integrated the sequence [op 1 ;op 3 ;op 2 ]. This sequence leads to a state different than the state on peer 1 . Copies are not identical, convergence is violated.

Intentions presented above cannot be preserved because the effect of executing op 3 changes the effect of op 2 which is independent, of op 3 i.e. op 3 deletes the statement inserted by op 2 , but op 3 has not seen op 2 at generation time.

Model for Intention preservation

It is not possible to preserve intentions if the RDF store is defined as a set of statements. However, if we transform the RDF store into multi-set of statements, it becomes possible to define intentions that can be preserved. Definition 5. RDF repository is the storage container for RDF statements, each container is a multi-set of RDF statements. Each RDF repository is defined as a pair (T, m) where T is a set of RDF statements and m is the multiplicity function m : T → N where N = 1, 2...... For instance, the multi-set R = { ("France", "LocatedIn", "Europe"),("France", "LocatedIn", "Europe"),("France", "hasCapital", "Paris") } can presented by R = { ("France", "LocatedIn", "Europe" ) 2 , ( "France", "hasCapital", "Paris" ) 1 } where 2 is the number of occurrence of the first statement and 1 is this of the second one. Definition 6. Intention of insert operation Let S be a P2P semantic wiki server, R is its local RDF repository and P age is a semantic wiki page. The intention of an insert operation op= Insert(P ageID, newline, p , n) when generated at site S, where newline =< nid, c, d, v> and T is the set (or multi-set) of RDF statements in the inserted line, is defined as: [START_REF] Vôlkel | Semantic wikipedia[END_REF] The content is inserted between the previous and the next lines and the semantic data in the line content are added to R.

∃i ∧ ∃ i P < i LineID(P age[i P ]) = p (1)

∧ ∃ i ≤ i N LineID(P age[i N ]) = n (2)
∧ P age [i] = newline (3)
∧ ∀j < i P age [j] = P age[j] (4)

∧ ∀j ≥ i P age [j] = P age[j -1] (5) ∧ R ← R T (6)
Where P age and R are the new values of the page and the RDF repository respectively after the application of the insert operation at the server S and is the union operator of multi-sets. If a statement in T already exists in R so its multiplicity is incremented else it is added to R with multiplicity one. Definition 7. Intention of delete operation Let S be a P2P semantic wiki server, R is the local RDF repository and P age is a semantic wiki page. The intention of a delete operation op= delete(P ageID, ld) where T is the set (or multi-set) of RDF statements in the deleted line, is defined as: (1) the line ld is set to invisible and (2) the number of occurrence of the semantic data embedded in ld is decreased by one, if this occurrence is equal to zero which means these semantic data are no more referenced in the page then they are physically deleted from the R.

∃i ∧ P ageID(P age

[i]) = ld (7)
∧ visibility(P age

[i]) ← f alse (8) ∧ R ← R -T (9)
Where P age and R are the new values of the page and the RDF repository respectively after the application of the delete operation at the server S and -is the difference of multi-sets. If statement(s) in T exists already in R so its multiplicity is decremented and deleted from the repository if it is equal to zero. France is located in [locatedIn::Europe] France is a country in [locatedIn::Europe]

{(F rance, locatedIn, Europe) 2 } France is located in [locatedIn::Europe] {(F rance, locatedIn, Europe) 1 } op3 = delete(1)
r r ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee

Text op3 op2

France is a country in [locatedIn::Europe]

{(F rance, locatedIn, Europe) 1 }
France is a country in [locatedIn::Europe] {(F rance, locatedIn, Europe) 1 }

Fig. 2. Convergence after integrating concurrent modifications

Let us consider again the scenario of the figure 1. When op 2 is integrated on peer 1 , the multiplicity of the statement ("F rance", "locatedIn", "Europe") is incremented to 2. When op 3 is integrated on peer 1 , the multiplicity of the corresponding statement is decreased and the consistency between text and RDF repository is ensured. We can observe that P eer 1 and P eer 3 now converge and that intentions are preserved.

Algorithms

As any wiki server, a P2P semantic server defines a Save operation which describes what happens when a semantic wiki page is saved. In addition, it defines Receive and Integrate operations. The first describes what happens upon receiving a remote operation and the second integrates the operation locally.

Save operation

During saving a wiki page, a Dif f algorithm computes the difference between the saved and the previous version of the page and generates a patch. A patch is the set of delete and insert operations on the page (Op = Insert(P ageID, line, l P , l N ) or Op = Delete(P ageID, LineID)). These operations are integrated locally and then broadcasted to other sites in order to be executed as shown below. ¦ ¥ At this level of description, we just make the hypothesis that Broadcast(P ) will eventually deliver the patch P to all sites. More details are given in section 7.

Delivery Operation

When an operation is received its preconditions are checked. If they are not satisfied, the operation is added to the waiting log of the server, else according to the type of the operations some steps are executed.

Integrate operation

The integration of an operation is processed in two steps: (1) text integration and (2) RDF statements integration. § To integrate an insert operation op = insert( P ageID, line, l P , l N ), the line has to be placed among all the lines between l P and l N , some of these lines can be previously deleted or inserted concurrently and the inserted semantic data are integrated. § Sesame Engine. We use Sesame 2.0 [START_REF] Broekstra | Sesame: A generic architecture for storing and querying rdf and rdf schema[END_REF] as RDF repository. Sesame is controlled by the SWOOKI manager for storing and retrieving RDF triples . We used a facility of the Sesame interface to represent RDF triples as multi-set. This component allows also generating dynamic content for wiki pages using queries embedded in the wiki pages. It provides also a feature to export RDF graphs.

Diffusion Manager. In order to ensure the CCI model, we made the hypothesis that all operations eventually reach all sites of the unstructured P2P network. The diffusion manager is in charge to maintain the membership of the unstructured network and to implement a reliable broadcast. Membership and reliable broadcast of operations are ensured by an implementation of the Lpbcast algorithm [START_REF] Eugster | Lightweight Probabilistic Broadcast[END_REF]. This algorithm ensures that all connected sites receive messages and that there is no partition in the P2P network. Of course, disconnected sites cannot be reached. So we added an anti-entropy mechanism based on [START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF]. The anti-entropy algorithm selects randomly a neighbor in the local table of neighbors and sends a digest of its own received messages. The receiver returns missing messages to the caller. Using the anti-entropy implies that each server keeps received messages in a log, as this log can grow infinitely, the log is purged as detailed in [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF].

Discussion

Every SWOOKI server provides all the services of a semantic wiki server. We analyze our system with respect to the following criteria, more detailed analyzing results about the implemented algorithms can be found in [START_REF] Eugster | Lightweight Probabilistic Broadcast[END_REF] and [START_REF] Ignat | A Comparison of Optimistic Approaches to Collaborative Editing of Wiki Pages[END_REF].

Availability, fault tolerance and load balancing Data are available on every peer so they are accessible even when some peers are unavailable. The global naming of the wiki pages (concepts) and their associated properties and objects and the respect of the CCI model ensure to have the same data at any node. So if a server is unavailable or slow, it is possible to access to another server.

Performance We analyze the performance with respect to messages necessary to execute query, propagate modification and synchronize data.

-Query execution: Every semantic wiki server can execute every semantic query locally without generating network traffic for resolving it.

-Messages delivery: As our algorithm generates no traffic for ensuring CCI consistency, the traffic cost for our system is the traffic cost of Lpbcast [START_REF] Eugster | Lightweight Probabilistic Broadcast[END_REF] and the traffic cost of the anti-entropy classical algorithm. As logs of messages can be purged safely, the traffic cost, even for anti-entropy, is bounded. The volume of changes generated by the Wikipedia in French is less than 100Mb per month between September 06 and May 081 . In 2008, the total size of Wikipedia in French was less than 2,5Gb.

-Data synchronization: The complexity of the integration of n operations is O(n * l 2 ) [START_REF] Ignat | A Comparison of Optimistic Approaches to Collaborative Editing of Wiki Pages[END_REF], where l is the number of lines that have been inserted in the wiki page. In fact, as deleted lines are just marked as deleted and there is no garbage collecting algorithm compatible with P2P constraints, the size of the wiki page is growing infinitely. However, traditional wikis such as Wikipedia keeps all changes in log history and never delete them. Consequently, in the context of a wiki, our solution seems acceptable.

Scalability SWOOKI scales with respect to the number of peers. The number of peers is not a parameter of the complexity in time and space of our algorithm.

However, It does not support solution for scalability with the size of data, the storage capacity is limited by the storage capacity of each node. For achieving this scalability, a solution based on partial replication is better. But in this case, offline editing and transactional changes are much more difficult to obtain.

Offline-work and transactional changes Users can work disconnected if they have no Internet connection or if they decide to disconnect directly from the user interface. While disconnected, a user can change many semantic wiki pages in order to produce a consistent change. By this way she generates a transaction. All changes performed in disconnected mode are kept in the diffusion manager component. As our optimistic replication algorithm forces all operations to commute (according to the CCI consistency) then, the concurrent execution of several transactions is always equivalent to a serial one. Thus, a consistent state is produced in all cases.

Cost sharing The deployment of SWOOKI network is very similar to the deployment of the Usenet P2P network. A trusted peer of any organization can join the network, take a snapshot of replicated data and start answering wiki requests. The proposed architecture can be easily deployed on the Internet across different organizations. In the contrast to the Wikipedia infrastructure that requires a central site with costly hardware and high bandwidth, the cost of the underlying infrastructure of our system can be shared by many different organizations.

Conclusion, Open Issues and Perspectives

Peer-to-peer semantic wikis combines both advantages of semantic wikis and P2P wikis. The fundamental problem is to develop an optimistic replication algorithm that ensures an adequate level of consistency, supports P2P constraints and manages semantic wiki page data type. In this paper, we proposed such an algorithm. By combining P2P wikis and semantic wikis, we are able to deliver a new work mode for people working on ontologies: transactional changes. This work mode is useful to help people to produce consistent changes in semantic wikis. Often, managing a semantic wiki requires to change a set of semantic wiki pages. These changes can take a long time and if intermediate state results are visible, it can be confusing for other users and it can corrupt the result of semantic requests. We believe that this working mode is crucial if we want to use semantic wikis for collaborative ontologies building. However, this approach has many open issues and perspectives:

-Security issues are an important aspect. Replication makes security management more difficult. Often in wikis, security is represented as page attributes. If wiki pages are replicated, it means that security policies are replicated. In this case, it is possible to produce concurrent changes on security policy itself. If we re-centralize security management, we loose the benefits of replication. This problem can be solved by applying the approach proposed in this paper. To manage security policy: define the security policy data type, its operations, the intentions of these operations and update the replication algorithm with these new operations.

-An alternative way for managing security issues is to deploy a P2P semantic wiki on the web of trust. Instead on relying on Lpbcast to build an unstructured P2P network, users can organize themselves in the topology of a network based on trusted relationships. Consequently, the resulting system is a P2P semantic wiki based on a social network that promotes privacy.

-We explored also the combination of an unconstrained semantic wiki with a P2P wiki system based on total replication. We motivated this choice by pointing out to the need of transactional changes. However, even if it is more difficult, it is possible to achieve the same objective with a P2P wiki based on partial replication and consequently take advantage of partial replication benefits such as reduced traffic, infinite storage and cheap join procedure.

Definition 1 .

 1 A semantic wiki page P age is an ordered sequence of lines L B L 1 , L 2 , . . . L n L E where L B and L E are special lines. L B indicates the beginning of the page and L E indicates the ending of the page.

= 3 op2=

 3 Insert(1, "France is located.." ) 3 Insert(1, "France is a country... " ) o o $ $ France is located in [locatedIn::Europe] {(France, locatedIn, Europe)} France is a country in [locatedIn::Europe] {(France, locatedIn, Europe)} op2 op1 France is located in [locatedIn::Europe] France is a country in [locatedIn::Europe] {(France, locatedIn, Europe)} France is located in [locatedIn::Europe] {(France, locatedIn, Europe)} op3 = delete(1)

Fig. 1 .

 1 Fig. 1. Semantic inconsistency after integrating concurrent modifications

3 op2=

 3 op1 = Insert(1, "France is located.." ) 3 Insert(1, "France is a country... " ) o o $ $ France is located in [locatedIn::Europe] {(France, locatedIn, Europe,1)} France is a country in [locatedIn::Europe] {(France, locatedIn, Europe,1)} op2 op1

§ 1 3 for each op ∈ P do 4 Receive(op) 5 endfor 6

 13456 Upon Save(page, oldPage) :-2 let P ← Diff(page, oldPage) Broadcast(P)

§ 7 10 IntegrateIns 20 return

 71020 Upon Receive(op) :-8 if isExecutable(op) then 9 if type(op) = insert then The waiting log is visited after the integration and the operations that satisfy their preconditions are removed from the log and integrated. § 16 isExecutable(op) :-17 if type(op) = del then 18 return containsL(PageID,LineID) and isVisible(LineID) 19 else ContainsL(PageID,lP ) 21 and ContainsL(PageID, lN ) 22 endif ¦ ¥ The function ContainsL(P ageID, id) tests the existence of the line in the page, it returns true if this is the case. The function isV isible(LineID) tests the visibility of the line.

  To integrate a delete operation, the visibility flag of the line is set to false whatever is its content. § 26 IntegrateDelT(LineID) :-27 Page[LineID]. visibility ← false ¦ ¥ To integrate RDF statements, a counter is used to implement a multi-set RDF repository. A counter is attached to every RDF triple, the value of the counter corresponds to the number of occurrence of the triple in the repository. § 28 IntegrateDelRDF(LineID) :-29 let S ← ExtractRDF(LineID) 30 if S = ∅ then 31 for each triple ∈ S do 32 triple .counter--During the delete operation, the counter of the deleted statements is decreased, if the counter is zero the statements are physically deleted from the repository.

37Fig. 3 .

 3 Fig. 3. SWOOKI Architecture

Fig. 4 .

 4 Fig. 4. User Interafce of SWOOKI

http://stats.wikimedia.org/EN/TablesDatabaseEdits.htm

¥ This algorithm selects the sub-sequence S' of lines between the previous and the next lines, in case of an empty result, the line is inserted before the next line. Else, the sub-sequence S' is filtered by keeping only lines with the minimum degree of S'. The remaining lines are sorted according to the line identifiers order relation < id [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF], therefore, line will be integrated in its place according < id among remaining lines, the procedure is called recursively to place line among lines with higher degree in S'.

To integrate the semantic data, the RDF statements of the inserted line are extracted and added to the local RDF repository. If the statements exist already in the repository, their counter is incremented, otherwise, they are inserted into the RDF repository with a counter value equals to one as shown below. §

Synthesis

Causality as defined in section 5.1 is ensured by the Receive algorithm.

Convergence for text is already ensured by the WOOT algorithm [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF]. Convergence for semantic data is trivially ensured by the multi-set extension of the RDF repository.

The intention preservation for a text is demonstrated in [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF]. Here, we are concerned with the intention of semantic data as defined in 5.2. The intention of an insert operation is trivially preserved by the algorithm IntegrateInsRDF. Since a possible way to implement a multi-set is to associate a counter to every element. In the same way, the algorithm IntegrateDelRDF preserves the intention of the delete operation. The basic idea behind all these algorithms is to reach convergence and preserve intentions whatever is the order of reception of operations. This implies that these algorithms "force" commutativity of operations. If operations are commuting then all concurrent executions are equivalent to a serial one. In our system, users can start a transaction just by switching to the offline mode and end a transaction by switching to online mode. We chose this way to interact with users in order to keep the system simple. If a user produces a consistent change, as all operations of any transaction are commuting and ensure the same effects, then all concurrent execution of transactions generate a correct state.

Implementation and discussion

We have implemented the first peer-to-peer semantic wiki called SWOOKI based on algorithms presented in section 6. The SWOOKI prototype has been implemented in Java as servlets in a Tomcat Server and demonstrated in [START_REF] Rahhal | Swooki: A peer-to-peer semantic wiki[END_REF]. This prototype is available with a GPL license on sourceforge at http://sourceforge.net/projects/wooki and it is also available online at: http: //wooki.loria.fr/wooki1.

SWOOKI Architecture

A SWOOKI server is composed of the following components (see figure 3):

User Interface. The SWOOKI UI component (shown in figure 4) is basically a regular wiki editor. It allows users to edit a view of a page by getting the page from the SWOOKI manager. Users can disconnect their peer to work in an off-line mode (feature1) and they can add new neighbors in their list to work with (feature2). In addition, the UI allows users to see the history of a page, to search for pages having some annotation (feature3), to execute semantic queries (feature4), and to export the semantic annotations of the wiki pages in an RDF format (feature5).

SWOOKI Manager. The SWOOKI manager is responsible for the generation and the integration of the editing patches. It implements the SWOOKI algorithm. Its main method is


Lecointre Luc

Kudriakov Sergey

Studer Etienne

Vicquelin Ronan

Tenaud Christian

Hydrogen/Air flame acceleration: advanced numerical modeling and criteria for detonation

come   L'archive ouverte pluridisciplinaire

Hydrogen/Air flame acceleration: advanced numerical modeling and criteria for detonation.

Luc Lecointre (CEA), Sergey Kudriakov (CEA), Etienne Studer (CEA), Ronan Vicquelin (EM2C) and Christian Tenaud (EM2C)

The acceleration and transition from deflagration to detonation of hydrogen/air flames are critical for hydrogen safety in chemical and nuclear industries. It is, therefore, important to define criteria for flame acceleration and transition to detonation (DDT). This study investigates the relevance of existing criteria for the transition in the configuration of reflected shock detonation. A high-order numerical solver has been developed to predict such configurations based on splitting methods, using numerical schemes adapted to each operator. In particular, the resolution of the compressible Euler equations is performed with a high-resolution Lax-Wendroff scheme built from the Roe approximate Riemann solver, with a shock-capturing method satisfying monotonicity preservation constraints. As a wide range of spatial scales is involved, multiresolution tools are applied to adapt the mesh locally. Immersed boundary methods have also been integrated to allow non-trivial geometric configurations while maintaining a structured mesh.

We illustrate the numerical approach on several configurations that deal with phenomena occurring in hydrogen flame acceleration and detonation. We mainly focus on reflected shock detonation in shock tubes and analyze adequate criteria for DDT prediction.


Charbel Rahhal
email: charbel.rahal@loria.fr

Stéphane Weiss
email: weiss@loria.fr

Hala Skaf-Molli

Pascal Urso
email: urso@loria.fr

Pascal Molli
email: molli@loria.fr

Undo in Peer-to-peer Semantic Wikis

The undo mechanism is an essential feature in collaborative editing systems. Most popular semantic wikis support a revert feature, some provide an undo feature to remove any modification at any time. However this undo feature does not always succeed. Supporting the undo mechanism for P2P semantic wikis has never been tackled. In this paper, we present an undo approach for Swooki the first P2P semantic wiki. We identify the problems to resolve in order to achieve such mechanism for P2P semantic wikis. We give the definition of the undo and the properties that must ensure. This approach allows both a revert and a permanent successful undo.

Introduction

Wiki systems are the most popular collaborative editing systems. Thanks to a simple syntax, users can build complex text documents, including tables, pictures or videos. As collaborative editors, wiki systems provide an undo mechanism. This mechanism is integrated in two forms, either through a revert which allows to return to an old version, or through an undo allowing to remove any modification from the current version [START_REF] Sun | Operational transformation in real-time group editors: Issues, algorithms, and achievements[END_REF].

In spite of their success, wiki systems have some limitations such as:

Centralization Most of existing wikis are centralized: this implies a high cost to ensure scalability, censorship issues, data availability and durability issues especially in case of failure; Low structuring Wiki systems are low-structured, they suffer in the navigation and the search, i.e. it is hard to navigate and to find relevant information in wikis [START_REF] Buffa | Sweetwiki: A semantic wiki[END_REF]. Wiki content is only human readable and it is not accessible and readable by machines, hence, it cannot be reused in external applications.

To overcome these limitations, two orthogonal solutions are proposed : P2P wiki systems and semantic wiki systems.

P2P wiki systems [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF][START_REF] Morris | Distriwiki: : a distributed peer-to-peer wiki network[END_REF] are based on a decentralized architecture and optimistic replication [START_REF] Saito | Optimistic replication[END_REF] mechanism to improve scalability and data availability. As traditional wiki systems, they suffer from low structuring.

Semantic wiki systems [START_REF] Vôlkel | Semantic wikipedia[END_REF][START_REF] Schaffert | Ikewiki: A semantic wiki for collaborative knowledge management[END_REF][START_REF] Buffa | Sweetwiki: A semantic wiki[END_REF] allow users to incorporate some computer readable information in wiki pages. Such information can be used to improve navigation and search. However, they suffer from centralization limitations.

Swooki [START_REF] Skaf-Molli | Peer-to-peer semantic wikis[END_REF] aims at conciliating both directions, it combines the advantages of P2P systems and semantic wikis. Swooki is a semantic wiki inspired from Semantic MediaWiki [START_REF] Vôlkel | Semantic wikipedia[END_REF]. Moreover, Swooki supports massive collaboration, fault tolerance, off-line work mode and ad hoc collaboration thanks to its P2P structure and to the replication of semantic wiki pages on different sites. Unfortunately, this approach does not offer any undo mechanism.

In the literature, several collaborative editing systems offer an undo mechanism. Existing semantic wikis are centralized, therefore their undo mechanism is not adequate for the P2P environment. On the contrary, some undo frameworks were devised for distributed collaborative systems, however they do not support semantic wiki data type. The data type maintained in semantic wikis is the wiki pages and the semantic annotations storage. Our goal is to design an undo mechanism that is compatible with P2P constraints, that supports the semantic wiki data type and that ensures the consistency between the wiki pages and the semantic storage.

In this paper, we propose an undo mechanism for Swooki. We define the property that this mechanism must ensure. This mechanism supports both undo and revert features. We develop the undo component and the needed algorithms and extensions to instantiate this undo mechanism in Swooki.

The paper is organized as follows. In section 2, we motivate the need for the undo mechanism. Section 3 presents existing approaches for the integration of the undo mechanism in collaborative editing systems. Section 4 presents Swooki. An overview of the undo in Swooki approach is given in section 5. Section 6 describes the implementation of the approach. The last section concludes the paper.

Motivation

Similarly to classical collaborative editors, P2P semantic wikis require supporting the undo feature for many reasons:

-Undo is a user required feature. Indeed, users can use the undo feature as a powerful way to recover from their proper errors. -In collaborative editors, when two or more users modify the same data, the system proposes a document based on all modifications. This merge algorithm is a best-effort and is not able to produce the result expected by users. The undo feature is useful to recover from unexpected result. -We consider a P2P semantic wiki as an open system where anyone can join and leave. Since anyone can join, malicious users can also join. As a result, the undo feature can be used to remove the impact of vandalism acts.

In all these cases, the expected result matches the undo definition [START_REF] Sun | Undo as concurrent inverse in group editors[END_REF]: "Undoing a modification makes the system return to the state it would have reached if such modification was never produced."

To achieve such a goal, the revert feature seems to be adequate: we can remove the whole content and add a previously created one. Unfortunately, the revert feature does not allow to undo any modification. Indeed, concurrent operations can be received in different orders. For instance, starting from an initial version V 0 (see Figure 1). A user1 on Site1 inserts a second line, though he generates a new version V 1 including the M 1 modification. Another user2 on Site2 inserts concurrently a second line, he generates a new version V 2 including the M 2 modification. Unfortunately, he made a mistake about the value of the car top speed. The integration of the M 1 and M 2 modifications on both sites results into a version V 3 including both of them. In order to correct the mistake, each site has different alternatives. Site1, which has integrated first M 1 , can restore the versions V 1 or V 0 . V 1 is the expected result since it contains all the modifications except the erroneous one. On the contrary, Site2 which has received first M 2 , can return to V 0 or V 2 . V 2 contains the erroneous modification while V 0 does not contain M 1 . As a result, Site2 is not able to cancel only the erroneous modification using a revert function without a lost of the Site1 modification.

Site1 Site2

The

M 1 u u k k k k k k k k k k k k k k k k k k k k k k k k k k V1 V2
The Another common idea is to undo changes by doing the inverse modification. Unfortunately, this does not achieve the undo definition. Figure 2 illustrates this case.

Starting from version V 3 the result of the previous example, a user3 on Site3 generates a malicious modification M 4 by deleting the whole document. M 4 deletes all the document lines. Concurrently, user1 on Site1 deletes the third line that contains the error. The inverse modification of M 4 inserts the three lines. As a consequence, when user1 on Site1 undoes M 4 , it reinserts the three lines

s s h h h h h h h h h h h h h h h

Related work

This section gives an overview about the undo mechanism in different collaborative editors.

Undo in semantic wikis

Semantic wikis such AceWiki [START_REF] Kuhn | Acewiki: Collaborative ontology management in controlled natural language[END_REF], Rise [START_REF] Decker | Self-organized Reuse of Software Engineering Knowledge Supported by Semantic Wikis[END_REF] and WikiSar [START_REF] Aumueller | Towards a semantic wiki experience -desktop integration and interactivity in wiksar[END_REF] do not support neither versioning for wiki pages nor versioning for metadata, hence they do not support an undo mechanism. Makna [START_REF] Karsten Dello | Makna, free university of berlin[END_REF] is a wiki based tool for distributed knowledge engineering. It extends the JSPWiki wiki engine with generic, easy to use ontology-driven components for collaboratively authoring, querying and browsing Semantic Web information. Makna supports versioning for pages and metadata within the pages, thus the revert feature is provided. However, it does not support the undo feature.

IkeWiki [START_REF] Schaffert | Ikewiki: A semantic wiki for collaborative knowledge management[END_REF] is a semantic wiki with features to support collaborative knowledge engineering, different levels of formalization ranging from informal texts to formal ontologies, and it has a sophisticated, interactive user interface. IkeWiki supports also a revert feature to restore an old version. IkeWiki does not support a feature to undo modifications applied on a page version. In addition, the annotations about the wiki pages are outside the content of these pages. Tracking the annotations changes is not provided, an insert or a delete of annotations can not be detected.

SweetWiki [START_REF] Buffa | Sweetwiki: A semantic wiki[END_REF] is a semantic wiki based on the CORESE engine. It supports WYSIWYG edition of pages and annotations, and use the CORESE engine and the SeWeSe library for all semantic operations : navigation, search and others. Pages are annotated using tags which are outside the content of the pages. SweetWiki does not support a versioning support for the formalized content, i.e. changes in the tags on pages is not tracked. SweetWiki supports a revert feature without an undo one.

Rhizome [START_REF] Souzis | Building a semantic wiki[END_REF] supports a modified version of WikiML (ZML) that uses special formatting conventions to make semantic properties directly explicit in the page content. Pages are saved in RDF and another editor can be used to edit the RDF directly. Rhizome provides a native versioning of content and metadata. It provides only a revert feature without an undo one.

Semantic MediaWiki (SMW) [START_REF] Vôlkel | Semantic wikipedia[END_REF] is an extension of MediaWiki that helps to search, organize, tag, browse, evaluate, and share the wiki content. SMW adds semantic annotations in the wiki pages in order to bring the power of the Semantic Web into the wiki. SMW inherits all the features of MediaWiki including revert and undo. While the revert always succeeds in restoring an old version, in some cases the undo can fail1 . For instance, suppose that a modification M in a paragraph was followed by other modifications in the same paragraph. In this case, the undo of M can not work.

OntoWiki [START_REF] Auer | Ontowiki -A tool for social, semantic collaboration[END_REF] and Powl [START_REF] Auer | Proceedings of the 1st Workshop on Scripting for the Semantic Web (SFSW'05)[END_REF] are web based applications designed to collaboratively build ontologies and create instances. Every change on any element such as knowledge model, concept, property or instance is logged. So they enable users to track, review and selectively roll-back changes. Consequently, they can offer both the revert and the undo features. Unfortunately, their undo mechanism is designed only for ontological elements and not for text.

Undo in different collaborative editors

Most of undo approaches were devised in the Operational Transformation [START_REF] Ellis | Concurrency control in groupware systems[END_REF] (OT) framework.

In [START_REF] Prakash | A framework for undoing actions in collaborative systems[END_REF], the authors propose to select which operation to undo. They also add the notion of conflict. If a conflict occurs, the undo is aborted. Therefore, this framework does not allow undoing any operation.

In [START_REF] Ressel | Reducing the problems of group undo[END_REF], the authors propose a solution to undo operations in the inverse chronological order, i.e. from the last operation to the first one without skipping one. Therefore this approach does not allow undoing any operation.

The GOTO-ANYUNDO approach [START_REF] Sun | Undo as concurrent inverse in group editors[END_REF] is the first approach that allows any user to undo any operation at any time. This approach is designed for real-time editing and uses state vectors [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF]. Since state vectors size is proportional to the number of site, this approach cannot be used in a P2P environment.

The COT approach [START_REF] Sun | Operation Context and Context-based Operational Transformation[END_REF] is an OT system designed for real-time editing which introduces the notion of "context vector". A context vector is associated to each operation and represents the operations executed before its generation. As state vectors, the cost of context vectors is compatible with real-time editing, however, they are not suitable in a P2P environment.

Distributed version control systems (DVCS) as Git2 are P2P collaborative systems mainly used for source code editing. They compute a new patch to remove the effect of a previous one and treat it as a new patch. However, DVCS lack of a formal framework, indeed, there is no property to validate DVCS correctness.

The UNO [START_REF] Weiss | An undo framework for p2p collaborative editing[END_REF] framework proposed an undo for P2P collaborative editing based on the Operational Transformation approach. The main idea of this approach is to devise new operation for counterbalancing previously made operations. This framework cannot be used directly to provide an undo feature in Swooki. However, we propose an undo mechanism inspired by this framework capable of undoing any modification at any time, i.e. supporting both a revert and an undo features.

Swooki System

Swooki [START_REF] Rahhal | Swooki: A peer-to-peer semantic wiki[END_REF][START_REF] Skaf-Molli | Peer-to-peer semantic wikis[END_REF][START_REF] Rahhal | Swooki: A peer-to-peer semantic wiki[END_REF] is the first P2P semantic wiki, it combines the advantages of P2P wikis and semantic wikis. Swooki is a P2P network of a set of autonomous semantic wiki servers (called also peers, nodes or sites) that can dynamically join and leave the network.

Every peer hosts a copy of all wiki pages where these pages embed semantic data and an RDF store. Every peer can autonomously offer all the services of a semantic wiki server. Swooki supports massive collaboration, improves data availability and has a high performance thanks to its total replication of shared data. It allows to query and access data locally without any data transfer. In addition, it enables off-line works and transactional changes.

As in any wiki system, the basic element is a wiki page and every wiki page is assigned a unique identifier P ageID, which is the name of the page. The name is set at the creation of the page. If several servers create concurrently pages with the same name, their content will be directly merged by the synchronization algorithm.

A semantic wiki page P age is an ordered sequence of semantic wiki lines. A semantic wiki line L is a four-tuple < LineID, content, degree, visibility > where LineID is a unique line identifier, content is a string representing text and the semantic data embedded in the line. degree is an integer used by the synchronization algorithm. visibility is a boolean representing whether the line is visible or not. Lines are not deleted physically, they are just invisible in the view of the semantic wiki page.

A Swooki peer is composed of the following components (see figure 3): User Interface. The Swooki UI component is basically a regular wiki editor. It allows users to edit a view of a page by getting the page from the Swooki manager. Users can disconnect their peer to work in an off-line mode and they can add new neighbors in their list to work with. In addition, the UI allows users to see the history of a page, to execute semantic queries and to export the semantic annotations of the wiki pages in an RDF format.

Swooki Manager. The Swooki manager is responsible for the generation and the integration of the editing patches. A patch is the set of delete and insert operations on the semantic wiki page (Op = Insert(P ageID, line, l P , l N ) or Op =Delete(P ageID, LineID)). It implements the Swooki algorithm. Requesting and modifying a page or resolving a semantic query in the RDF repository pass through this manager.

Sesame Engine. The RDF repository used in Swooki is Sesame 2.0 [START_REF] Broekstra | Sesame: A generic architecture for storing and querying rdf and rdf schema[END_REF]. Sesame is controlled by the Swooki manager for storing and retrieving RDF triples. We used a facility of Sesame to represent RDF triples as multi-set. This component allows also generating dynamic content for wiki pages using queries embedded in the wiki pages. It provides also a feature to execute semantic queries and to export RDF graphs.

Diffusion Manager. The diffusion manager maintains the membership of the unstructured network and implements a reliable broadcast. This component is described in [START_REF] Skaf-Molli | Peer-to-peer semantic wikis[END_REF][START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF].

The integration of the undo mechanism in Swooki requires the addition of the undo component, with slightly extensions of some existing elements. The undo mechanism is designed to allow users to remove or reinsert the effect of some changes in the wiki pages and consequently to update their semantic annotations in the RDF repository. A detailed overview of the proposition is given in the following section.

Proposition

We developed the undo component for Swooki to provide users a feature to handle vandalism, to correct errors and to improve easily undesired result of an automatic merge done by Swooki.

Undo component

In this section, we describe the behavior of the undo component which is responsible of handling undo actions.

When a user wants to undo a modification, i.e. a patch, the document must return to a state in which the modification was never performed according to the undo definition 2. This definition implies two cases:

the patch is already undone and the document must not be changed, the patch must be disabled and its effect must be removed.

Moreover, since the action of undoing a patch is also a modification of the document, users must be able to undo an undo modification, also called redo.

Similarly, according to the undo definition, if a patch is already redone, the action of "redo" has no effect, otherwise, we must re-apply its effect.

As a result, the system must know if a patch is enabled or not. Moreover, the system has to know how many times a patch has been undone or redone as illustrated in figure 4.

Assume that two sites, called Site1 and Site2, have received the same patch P 1. Concurrently, both sites decide to undo this patch. Consequently, Site1 generates a modification M 1 while Site2 generates M 2 . Then, Site2 chooses to redo the patch P1. Finally, each site receives each other modifications. Site1 has received both "undo" modifications and then the "redo". If the system just knows that P1 is undone, the "redo" will reapply P1. Unfortunately, this example violates the definition. Indeed, if the modification M 2 was never produced, the only remaining modification is M 1 , then the P1 must remain undone.

Site1

Site2

P 1 P 1 M1 = undo(P 1) % % L L L L L L L L L L L L L L L L L L L L L M2 = undo(P 1) t t i i i i i i i i i i i i i i M2 = undo(P 1) M3 = redo(P 1) t t i i i i i i i i i i i i i i M3 = redo(P 1) M1 = undo(P 1)

Fig. 4. Concurrent undo and redo messages

For instance, a patch with a patchDegree equals to three implies that the patch has been redone three times and that it has an effect in the semantic wiki page model. Actually, patches are never deleted from the patchGraph, however their effect is removed from the wiki page model as if they did not exist.

As a result, we propose to extend the patchGraph as defined in Swooki by associating a patchDegree to each patch in that graph. This patchGraph becomes a set of <patch, patchDegree> where the patchDegree indicates whether the patch has an effect or not in the current state of the wiki page. We arbitrary choose to affect a degree of 1 at the patch reception, to decrease by one the degree at the execution of an undo and increase it by one for a redo. Then, a patch is undone if its degree is strictly inferior to 1.

Consequently, in Figure 4, Site1 will compute a degree of 0 and will not restore P1.

Finally, we translate the description of the undo component above into the following algorithm: Now, the system can compute whether or not a patch has to be reapplied or undone. Next, we will explain how to remove or reapply a patch.

IntegrateUndo(patchId): patch <-

Removing and reapplying a patch

Since we keep deleted lines as tombstone in Swooki, we propose to reuse them instead of inserting new lines in case of redo. We call deletion the transformation of a line into a tombstone and, reinsertion the inverse of deletion.

Moreover, using the inverse operations as shown in Figure 2 is not sufficient for removing the effect of a patch. This is mainly due to concurrency: the line "It has a [topSpeed:=49km/h]." is deleted twice (by M 3 and M 4 ) and "reinserted" once by "Inverse(M 4 )". Similarly to the previous example, we propose to count the number of deletion/reinsertion to overcome this issue.

In Swooki, a line in the wiki page model is never deleted, it is only set to invisible in the wiki page view. The visibility of a line is determined through a boolean visibility field. We change the line visibility as defined in Swooki into a visibility degree in order to let the system detect whether a line is visible or not after multiple undo and redo of patches. In our case, a line is visible if it is visibility degree is positive. A delete of a line turns its visibility degree to zero, however an undo or a redo action decreases or increases it respectively by one.

Since we have changed the data model, we have to redefine the operation to modify it. In Swooki, the integration of an operation is processed in two steps:

(1) text integration and (2) RDF statements integration. To integrate an insert operation op = insert( P ageID, line, l P , l N ), the line has to be placed among all the lines between l P and l N . Finding the right position where the line should be inserted is done through the Woot algorithm (for more details see [START_REF] Oster | Tombstone transformation functions for ensuring consistency in collaborative editing systems[END_REF]).

Once the right position is found, we insert the line in the page with a degree of 1 and insert hypothetical metadata into the RDF store: Due to concurrency, a line can have a degree greater than 1. Therefore, the execution of a delete consists in decreasing the degree of that line. If the line becomes invisible, i.e. its degree is now 0, we have to update the RDF store using the method "IntegrateInsRDF". Similarly, the reinsertion of a line increases its degree. If the line is now visible, we update the RDF store. or reapply its effect:

EnablePatch(patch): for (op:opsPatch) do lineId <-op.getLineID() switch(type(op)) insert : ReinsertLine(lineId ) delete : DelLine(lineId)

}

In Figure 2, since the line is deleted twice, its degree is -1. As a consequence, when Site1 undoes M 4 the line degree is increased by one and the line remains invisible.

Messages

As usual modifications, the undo/redo action must be propagated to all other sites. Therefore, we need to extend the diffusion manager to take account of undo/redo messages.

We define three kind of messages:

Do message: In case of a do message (i.e. containing only insert or delete operations), the patch is added in the patchGraph with a patchDegree equals to one. All the operations of that patch are integrated depending on their type. Undo message: In case of an undo message, the patch on which the undo message will be applied is extracted from the patchGraph; Redo message: Similarly for a redo message, the patch is extracted from the patchGraph.

When a message is received, we test if it is executable. A do message is executable if all its operations satisfy their preconditions as defined in [START_REF] Oster | Data consistency for P2P collaborative editing[END_REF], however an undo or a redo message is executable if the patch on which it is applied exists in the patchGraph. When a message is not executable, it is added in a message waiting queue. The message information mInf o of an executable patch is added in the page history. A message is integrated depending on its type.

Implementation

The undo or redo of changes can take place either by visiting the history or the patch graph of a page. The figure 5 shows the history where different messages are integrated on the wiki page. A line in the history is equivalent to the message information. It indicates the identifier of the patch, the peer that generated the patch, the type of the message and a user comment when it exists. The undo action of a patch has a grey background. In order to undo a set of patches, a user can click the checkbox that precedes each one of them and then press the undo preview button. The result of this preview is a temporary version of the page which undoes these patches. If he is satisfied, he can apply these changes by saving the undo preview. Another option provided in the history is to revert the current version of the wiki page. Users can choose to return to a state of a page undoing all the changes integrated after the chosen patch. This is can be achieved by selecting the patch and clicking on the revert preview. Similarly, if he is satisfied the user can save the revert preview and his changes will be applied. The undo of each patch inserts a new line in the history. The history allows also providing more information about each patch by a click on show details link at the end of each line. Each undo action in the history generates a new message of type undo. This message is sent through Swooki diffusion manager to the other peers in order to be integrated. The integration of that message locally or on the other peers is done as defined in section 5. 6). The patch graph is viewed as an oriented graph of patches. Each patch is a node in the graph and the arrows represent the dependence between these patches. A node relating one or more nodes implies that this patch was generated on a state integrating these patches. Each node is labeled with the patch identifier and the patch degree. A black node is a disabled patch that has no effect in the wiki page. A right click on a node allows to show the information about the patch, to undo or redo a patch or to preview a version of the wiki page. The patch graph is visualized through an applet built using JGraphT java libraries to build the graph model and JGraph to render the graph layout. It is based on a recursive algorithm crossing the patch graph [START_REF] Alshattnawi | Concurrency awareness in a p2p wiki system[END_REF]. The patch graph provides information about the patches dependency, hence the concurrency between them.

Conclusion

In this paper, we propose an undo mechanism for Swooki. This mechanism allows users to undo any modification at any time, i.e. to remove any modification as if it was never produced. It provides both an undo and a revert features. We developed the undo component, the appropriate algorithms and extended some parts of Swooki to provide an undo mechanism in Swooki. The undo component is Fig. 6. Undo from the patch graph responsible for the generation and the integration of undo and redo actions. The propagation of these actions lies on Swooki diffusion manager. Swooki extension ensures the convergence of the wiki pages and the RDF stores on all peers. This convergence is independent from concurrent modifications, the order of integration of the undo or redo actions and the fact that users can edit in an off-line mode i.e. join or leave at anytime.

We identified the problems to resolve in order to achieve such mechanism for P2P semantic wikis. While the revert feature may be sufficient for centralized semantic wikis, this is not the case for P2P semantic wikis aiming at removing any modification at any time.

Our solution is general, it is based: (1) on enabling and disabling patches in the patch graph and (2) on the generation and the integration of undo and redo actions. It can be adopted in any P2P semantic wiki.

As future work, we intend to carry out user studies to evaluate the improvement of the quality of the wiki pages and the knowledge in the RDF stores using our approach and how this mechanism facilitates the task of the users compared to Swooki without the undo mechanism.

Fig. 3 .

 3 Fig. 3. Swooki architecture extended with the undo component

  DelLine(LineID) :line <-Page[op.LineID] line . visibilityDegree -if line . visibilityDegree = 0 then IntegrateDelRDF(line.content) endif

  ReinsertLine(LineID) :line <-Page[op.LineID] line . visibilityDegree ++ if line . visibilityDegree = 1 thenIntegrateInsRDF(line.content) endifFinally, we can now remove the effect of a patch:DisablePatch(patch):for (op:opsPatch) do lineId <-op.getLineID() switch(type(op)) insert : DelLine(lineId) delete : ReinsertLine(lineId )

Fig. 5 .

 5 Fig. 5. Undo from the history

  Ferrari FXX is a [type::race car].

	V0	V0
		The Ferrari FXX is a [type::race car].
	M 1	M 2
	The Ferrari FXX is a [type::race car].	The Ferrari FXX is a [type::race car].
	It can reach [topSpeed:=349km/h]. S S M 2 S S S S S S S S S S S S S S ) ) S S S S S S S S S S It has a [topSpeed:=49km/h].

http://en.wikipedia.org/wiki/Wikipedia:Undo#Undo

http://git.or.cz/


Michel Dabas

François Blary

Gianluca Catanzariti

Exemplaire auteur

INTRODUCTION

Geophysical prospecting, even if now used routinely for managing cultural heritage questions in open areas, suffers in currently urbanized environment from various difficulties which makes its use non-trivial. A certain number of constraints in the urban environment are generally well known: presence of mechanical vibrations, electromagnetic noise, presence of infrastructures, furniture, pedestrians, cars above the surface, presence of underground modern services (water, gas, electricity, fibers, etc.), and most obviously, presence of above ground structures which tend to fragment into small pieces the areas that can be measured. Others like the very high heterogeneity of the subsoil (rubble and a highly complex multiphase stratigraphy) remains the biggest challenge for the geophysicists and ultimately for archaeologists during the interpretation process. The very good results obtained over abandoned roman towns for example are due to the conjunction of facts that are seldom encountered in today's city centres: low depth of structures (< 1 m); existence of some destruction phase that has cleared up the rubbles and made apparent walls or their negative counterpart; existence of a single phase of construction of the urban layout. The situation of today's cities is closer to the one of "tells" in middle-east countries. If the first archaeo-geophysical surveys in cities were very 'punctual' and were often limited to the study of religious buildings or parks, in recent years the appearance of new methods such as the electrostatic method (also called CCR -Capacitively Coupled Resistivity) or motorized ground radar (GPR) allow the investigation of very large areas. Two examples are developed: the research conducted in Alexandria twenty five years ago and a newer one not yet published, carried out in 2018-2019 in Brussels.

CASE STUDY #1: Alexandria, Egypt

This case study represents the first large experiment done in a modern city. Following an idea of J.-Y. Lempereur in 1995, we (Albert Hesse et al. 2002) were looking for traces of the old causeway (Heptastadium, a causeway of 1155m long) described by Strabon and others (Aristée, Plutarque, Sénèque) between the old town of Alexandria and the island of Pharos in Egypt. This causeway is sometimes described as an embankment (χωμα) that could form a bridge (with piles?) and an aqueduct which connects the old town to the island of Pharos. There was before our work only one hypothetical route that was proposed by Mahmoud Bey Al-Falaki last century and situated halfway between the two banks of today isthmus. But looking at topographic features (orientation and width of the old roads, parcels in the 1930 cadaster, altitudes and the distribution of sewers), Albert Hesse proposed another route closer to the west bank of the isthmus. This hypothesis focused all the geophysical work in this region and four methods were used in 1997 (Seismic refraction, EMI, GPR and Electrostatic imaging) mainly along six modern roads (approximately 100 m apart) crossing the hypothetical trace of the Heptastadium. We will not discuss into details (cf. Hesse et al., 2002) the results of these geophysical profiles in a very difficult environment (very low resistivities due to the presence of salted water, decompacted sediments, high industrial noise). Seismic refraction and GPR were not successful but Electrostatic data and to a lesser extent conductivity data (EMI) made possible the delimitation of resistive bodies at a depth of roughly 4 meters. Nevertheless, it is clear, as was expected since the beginning of this work, that the Heptastadium does not constitute a perfect linear geophysical anomaly (Fig. 1). But on the other hand, the two methods show that there exists in the studied sector a slight eminence aligned in the right direction and composed of resistant materials contrasting with more loose alluvium on the sides, validating the hypothesis of some 'openings' across the Heptastadium for communications between the western and the eastern harbor. These geomorphological issues together with micro-topographical issues were important for strengthening the hypothesis of a causeway in the western part of the isthmus.

CASE STUDY #2: Brussels, Belgium

The program "Voir sous les pavés" ("Seeing under cobblestones") launched in 2018 for the study of the Grand'Place in Brussels, under the direction of François Blary (ULB) and Michel Dabas (CNRS-ENS), aimed to detect and map the archaeological structures under this square and nearby street without performing excavations. It corresponds in the case of Brussels to a set of large-scale integrated non-destructive surveys that prefigure what could be undertaken in other downtown areas. This project is actually part of a larger project launched in 2017: the BAS (Brussels Archaeological Project). It aims at finding the traces of the Brussels of the Middle Ages of which nothing remains on the surface. This research focuses on the study of all accessible underground structures and in particular cellars within the oldest area of Brussels known as "Pentagon". Grand'Place occupies the central position of this Pentagon.

Methodology

The current appearance of the Grand'Place is close to that of 1695, after the bombardment by the French. Before 1695, little is known: the square was probably much smaller, texts mention buildings but their location are unknown. One or more fountains existed and are depicted in some drawings. Also more ephemeral structures have existed: Gas street lamps, places for Christmas trees, market place, and podium for public executions. All these remains could eventually be detected by geophysics… Only a single very small archaeological excavation has occurred near the Town Hall and some occasional discoveries like a water well or a cave are known. Before the surveys took place, it was possible to get a high definition (5 cm) aerial ortho-image and a map of the different utilities. But no georeferencing of these utilities existed and one of the purposes of the survey was also to map all utilities under the main square and the streets around. Four classes of methods were used simultaneously in the Grand'Place: ground penetrating radar (GPR), electrostatic method (also named CCR-Capacitively Coupled Resistivity-), Vertical Electrical Sounding (VES), and micro-topography (Fig. 2). The biggest challenge was to get authorizations to survey this UNESCO-square full of tourists, with security issues (2016 suicide bombings in Brussels), with heavy car traffic during the early morning when shops are stocked, and with a high tavern activity in the afternoon and at night … Several 3D-multi-channel radars (Stream X and C) were set up (Gianfranco Morelli, Geostudi Astier) to find a compromise between depth of investigation, spatial resolution and measurement speed. Simultaneously, a new prototype of electrostatic resistivity-meter "MP3" specifically developed for this project was implemented (S. Flageul and M. Dabas). It allows the measurement of electrical resistivity simultaneously for three depths of investigation down to 2meters. Positioning was done by a robotic total station and proves to be very effective in such a situation (compared to GNSS) even if it has to be moved several times during the survey of surrounding streets, and has to be guarded all day by an operator. It was used for all geophysical methods and consequently all data set were spatially coherent, saving lot of efforts during post-processing phases. The post-processing of these data made it possible to calculate a digital model of the soil surface (DSM) with a post-registration into the Belgian cartographic system (Lambert72) using some GPS control points. The relatively simple processing and interpretation of the CCR data in a GIS has to be opposed to the very complex processing and interpretation of 3D-radar data: radar maps in the form of time-slices, using a representation of the amplitude (phase) or the magnitude (envelope), taking into account -or not -the topography were tested.

Results

Resistivity (Fig. 3) was very successful and able to detect several resistive structures that can be interpreted as the rest of old dwellings, and despite the signature of some utilities, generally depicted as conductive elongated anomalies, distinctive walls of houses were detected all over the Grand'Place. These anomalies were detected with the most superficial quadrupole (a=0,5 m), meaning that these anomalies are superficial. They are best seen with the 1 m dipole and have been confirmed with the different maps corresponding to the two orientations of the dipoles. The highest gradient corresponding to probably a massive building can be seen in the south-east corner (Fig. 5). The density of resistive anomalies is less in the western part of the Grand'Place. We think that this does not necessarily imply a lower density of constructions in this area, but perhaps deeper or more erased structures. The phase of destruction and reconstruction of the XVII c. Grand'Place was clearly picked up especially in the South-Eastern part: the widening of the place to the East has resulted in a realignment of the houses that resulted in the destruction of the former front of the houses (pushed approx.10m to the North-East). Among the know utilities, only one was clearly picked-up within the CCR data and corresponds to the trench associated to a water pipe. The other utilities were too small to be imaged by resistivity but were picked-up by GPR.

GPR results, despite many maps corresponding to the different frequencies used, to different processes, and even to different polarizations, were hard to interpret. Unfortunately Radar penetration even at 200 MHz was low (1 m approximately); we have often encountered this situation and it is a drawback when using GPR in downtown areas. For Brussels, this can be explained by the low electrical resistivity measured both by CCR and confirmed by a single Vertical Electrical Sounding between the cobblestones. Nevertheless, the GPR results demonstrated, beside a very high number of unknown utilities, the existence of the basement of two fountains and probably three water wells (Fig. 4) which were not picked-up in the CCR data. The spatial resolution of GPR was necessary to detect these small-scale anomalies (compared to resistivity imaging). As an example of known structures, the place of the basement of the Christmas tree and the one of former water wells were discovered in the time-slice GPR maps (but were not known before our survey). Surprisingly, signature of the dwellings and walls discovered with resistivity imaging was not so clear in GPR maps. Only GPR amplitude time-slices (and not envelope) thanks to a difference in texture was able to delineate these limits and we should admit that the confrontation with ER maps was mandatory to secure our interpretation. We should admit that, without the information gained with old drawings and paintings, we will probably have missed some of the archaeological structures. We believe that the good achievement of this project is due to the integration of the archaeologists at every stage of the process. And of course, the archaeological interpretation of geophysical data from Grand'Place is a challenge which is not yet finished. All results will be published in a book, in a public leaflet and through a web-GIS.

CONCLUSIONS

Through these two examples, we have shown how we have tried to answer the three main questions dealing with geophysics in urban spaces: how is it possible to undertake a multidisciplinary research in large urbanized settings; how we have managed the acquisition, processing and integration of al large amount of data; and finally, how can we have interpreted and disseminated the results of such urban-scale projects?

In both examples, it was mandatory to use several classes of geophysical methods simultaneously to solve the archaeological questions: presence of the Heptastadium in Alexandria, presence of medieval buildings in Brussels. But also, the ancillary role of microtopography was highlighted for both studies. The role of the electrostatic method (CCR) as a quick mapping technics was demonstrated even if the geometry of such system prevents from using it easely for large depth of investigations (>3m). Processing of CCR data is also very easy compared to GPR data. The high horizontal and vertical resolution of GPR data is nevertheless unavoidable in order to resolve small scale anomalies, define sharp limits of structures and ultimately interpret structures at a stratigraphic level. Processing of data and integration of all types of data is also very important and is still a challenging part of this work. Our interpretation heavily relies on these processing workflows that can -and should-evolve during the interpretation process. Our experience shows that without extra information like old plans and drawings, our geophysical interpretation may remain very poor. Finally, we can ask ourselves what exactly is the role of geophysical information obtained in such contexts? Is it only useful for archaeologists, or can we imagine a more integrated approach with geotechnical engineers, network managers, urban planners? Can it be used blindly as in the case of an archaeological diagnosis or does it have to answer specific questions? Even if it is still an open question, our experience and certainly the Rome transformed project are throwing new bridges for our connaissance.

  et al., L'Heptastade d'Alexandrie, Etudes alexandrines 6-2002, 191-273. List of Figure Caption:

Figure 1 (

 1 Figure 1 (from top to bottom, clockwise): Position of the geophysical surveys in Alexandria (white square); Electrical Profiling using independent electrostatic quadripoles in Wenner configuration (a=6 m) along one of the streets (credit: A. Hesse); Map of apparent electrical resistivities obtained by krigging the data along the 6 profiles (Hesse et al., 2002); Superposition of microtopography and Google Earth showing in yellow the proposed causeway for the Heptastadium (credit: A. Hesse, M. Dabas).

Figure 2 :

 2 Figure 2: MP3 prototype for measuring apparent resistivity, operators (A. Tabbagh and S. Flageul) are within a 'moving' safety zone delimited by yellowtape; Robotic total Station operated by B. van Nieuwenhoeve; GPR (StreamC 600 MHz and StreamX 200 MHz, IDS GeoRadar Corporation) G. Morelli and G. Catanzariti; Vertical electrical Sounding between the cobblestones in the Townhall (A. Tabbagh).

Figure 3 :

 3 Figure 3: Map of apparent electrical resistivities (22 to 103 Ohm.m) obtained with channel 2 (DOI: 1 m) of the MP3 prototype (charge coupled resistivitymeter) overlaid on 5 cm resolution orthoimagery (June 2016, source: cirb.brussels, Open licence) and utilities (in white). Processing and source: M. Dabas, www.chronocarto.eu [06/2021].

Figure 4 :

 4 Figure 4: 200 MHz GPR amplitude time-slice centered on 0.22 m overlaid on ortho-imagery (June 2016, source: cirb.brussels, Open licence) and utilities (in blue). Processing and source: G. Catanzariti, www.chronocarto.eu [06/2021].

Figure 5 :

 5 Figure 5: First joint interpretation of resistivity maps and GPR time-lapse maps. Processing and source: F. Blary [03/2019].