Semi-Customizable Gestural Commands Approach and its Evaluation

Rennes, France a : {pei-yu.li, eric.anquetil}@irisa.fr b : ney.renau-ferrer@irisa.fr c : eric.jamet@uhb.fr

Abstract-Pen-based interfaces allow users to interact with the help of a stylus and/or fingers. Thanks to a recognition system, users can execute commands by drawing gestures. Because of the complexity of the software, the set of gesture commands can be very large. Consequently, it becomes difficult for the users to remember all the commands. In this paper we introduce "Semicustomizable gestural commands". The idea is to take into account the commands usage frequency: to facilitate the memorization of the most used commands we leave users the freedom/liberty to define their associated gestures (by) themselves. The remaining gesture commands will be automatically generated on the base of the defined gestures according to their hierarchical categorization. Several comparative tests demonstrate that this new approach improved the progressive memorization of the gestural commands.

Gesture commands; usage; incremental learning (key words)

I. INTRODUCTION

Pen-based interfaces allow users to draw strokes to run a command. These gesture commands offer an efficient and intuitive Human-Machine communication which is more and more researched nowadays [START_REF] Bailly | Wave Menus: Improving the Novice Mode of Hierarchical Marking Menus[END_REF][2][3][4] [START_REF] Kurtenbach | The limits of expert performance using hierarchic marking menus[END_REF] [START_REF] Li | Evaluation of Continuous Marking Menus for Learning Cursive Pen-based Commands[END_REF][9] [START_REF] Zhao | Simple vs. Compound Mark Hierarchical Marking Menus[END_REF]. For instance, we can associate a "C"-shaped gesture to Copy, a "V"-shaped gesture to Paste. In real software, the definition and the memorization of gestures associated to every command becomes a real challenge. Today the graphic gesture recognizers are stronger and more competitive; some of them can adapt and learn incrementally the user style [START_REF] Almaksour | Improving premise structure in evolving Takagi-Sugeno neuro-fuzzy classifiers[END_REF] [START_REF] Almaksour | Personalizable Pen-Based Interface Using Lifelong Learning[END_REF]. The problem comes from the side of the user, who needs to learn all the gesture commands. Even if we try to associate intuitive and significant gestures to commands when it is possible, or to leave user the freedom to define the gestures by himself, this work becomes tedious when the number of gesture commands becomes important. To solve this problem, Kunterbach proposed the "Marking Menus" [START_REF] Kurtenbach | The design and evaluation of marking menus[END_REF]. The main idea is to help user's memorization by manipulating menus which lead to final gestures corresponding to commands. The Marking Menus allow two kind of utilization: novice mode where the user will be guided by menus to run a command; and expert mode where the user has already learned the gesture and no menu will be displayed, so his gesture will be sent to a recognizer to be identified.

Since Marking Menus have met a big success, a lot of variants have been proposed. Above all, Hierarchical Marking Menus [START_REF] Kurtenbach | The limits of expert performance using hierarchic marking menus[END_REF] allow more levels in menus so that the gesture set increases, but at the same time, it is more difficult for the recognizer. To keep a reasonable accuracy, Zhao et al. [9][10]proposed Zone and Polygon Menus where the user should draw several straight strokes to execute one command. Consequently, the set of induced gestures is constrained and cannot include the natural drawing habits, i.e. cursive gestures. Another interesting approach is Octopocus [START_REF] Bau | Octopocus: A Dynamique Guide for Learning Gesture-based Command Sets[END_REF]. It introduces fluid and cursive gestures with a one-level menu. The induced gestures are diverse, contrary to other approaches who allow only polygonal lines which are neither natural, nor fluid. In novice mode, it guides users throughout the drawing of strokes with a colorful dynamic menu. This menu gives continuous feedback to the user. However, Octopocus allows only one level for the menu and the set of gestures is predefined and not customizable by the user. Moreover, there is no logic between each gesture and its associated command.

In our previous work, we first proposed the Continuous Marking Menus (CMM) [START_REF] Delaye | Continuous Marking Menus for learning Cursive Pen-based Gestures[END_REF] to improve the expressiveness of marking menus and to admit a vocabulary of cursive, fluent handwritten gestures. After some tests to evaluate this concept [START_REF] Li | Evaluation of Continuous Marking Menus for Learning Cursive Pen-based Commands[END_REF], we did prove that CMM helps the learning of gestures, when the original "help" displayed on the side of the software was not so helpful. Nevertheless, after the experiments, some users have been frustrated because they could not personalize some gesture commands. Based on these critics, we are convinced that it is important to give users a freedom degree to customize their gesture and it is also important to reduce the constraints on drawing the gesture as much as possible. Consequently, we focus on the new objective to answer these principal properties:

-leave the gesture form as natural as possible; -allow user to choose gestures associated to frequent commands; -keep a semantic meaning and a hierarchy which can help the memorization; -Use some advantages of Marking Menus to ease the learning. The results of this analysis are presented in this paper: we design the concept of "Semi-Customizable Gestural Commands (SCGC)" approach. The SCGC's originality is to consider the usage frequency of commands to ease the learning of commands gestures. At the same time, we leave user the freedom to define his gestures for the predominant commands, and the remaining gestures are automatically generated based on the gesture of the predominant command. The objective is to get natural and cursive gestures which are easy for the user to learn and memorize at the same time.

The rest of the paper is organized as follows. We introduce at first the SCGC approach. Then we expose the incremental gesture recognizer [START_REF] Almaksour | Improving premise structure in evolving Takagi-Sugeno neuro-fuzzy classifiers[END_REF][13] we have used to conduct experiments. Finally we present a complete experimentation which involves more than twenty users in three comparative tests to evaluate the impact of SCGC approach in terms of learning and memorization of the gestures by the users. We also report, in parallel with what the user learnt, the result of the incremental learning of the gesture recognizer used in these experiments.

II. SEMI-CUSTOMIZABLE GESTURE COMMANDS

According to the users' feedback in our previous works, we estimate that it is really important to keep users defining some gestures themselves to help their memorization (particularly for the most frequent commands). Moreover, in real software, all commands do not have the same use frequency. For instance, the "copy" command is used more often than the "print" command. In general, user wants to memorize the most used commands at first. The more we use a command, the faster we learn it. This is why we introduce a new kind of commands: the Semi-Customizable Gesture Commands (SCGC). The SCGC approach leaves the user the freedom to design gestures for their most used commands, and then generates all the derived gesture commands automatically. It avoids the user the tedious task of defining all the gestures. To make the generated gestures meaningful, we group the commands by family, like Marking Menus. More precisely, we ask the user to define the gesture for one predominant command per family, and the gestures for the other members will be automatically generated.

To implement automatic generation of gesture commands, all the gestural commands are modeled by spline to formalize the prototypes of the gestures. All derived gestures are then generated by a continuous deformation of the predominant prototype. The next sections present the different steps to formalize the drawing of the gestural commands.

A. Polygonal approximation

The first step consists in a polygonal approximation of the drawing of the gestural commands. We use the polygonal approximation algorithm defined in [START_REF] Perez | Optimum polygonal approximation of digitized curves[END_REF]. Given a collection of N points and a constant M, this algorithm can find the M points which form a polygon that follows the best curve defined by the N points collection. The quality of the polygonal approximation is quantified by an error indicator. We can find the optimal polygonal approximation according to this indicator. For instance, in Figure 1, the black curve is the original stroke drawn by user. The step 1 corresponds to polygonal approximation. These points are polygons corners which are automatically extracted with the polygonal approximation algorithm. Here we have M=6.

B. Canonical spline

The M points extracted by the polygonal approximation are used as control points to define a canonical spline to represent the original drawing.

A canonical spline is a cubic polynomial who aims to imitate the original curve by defining several control points to regularize the drawing [START_REF] Petzold | Canonical Splines in WPF and Silverlight[END_REF]. Unlike the Bézier curve, the canonical spline passes through all its control points. The implemented canonical spline algorithm is based on [START_REF] Petzold | Canonical Splines in WPF and Silverlight[END_REF] . In Figure 1, the second step corresponds to a canonical spline definition.

C. Automatic gesture generation

The generation for gesture commands is based on a continuous deformation of the gesture's end.

Let's note the M control points of the gesture that the user defined: p 1 , …, p M . For the other members of the same family, we keep the same beginning, i.e.: p 1 , …, p M-1 . We move simply the last control point to generate new gestures. Thanks to the properties of splines, the newly generated curves will stay fluid and cursive.

Figure 2 illustrates the principles of the automatic generation of all the alternative commands of a same family. The black stroke presents the canonical curve of the original curve drawn by user. For a family who has three commands, we take the coordinates of the last two points: p M-1 and p M . We generate the new coordinates of p M ' (new last control point for one new command) and p M '' (new last control point for the other command), respectively:

|p M-1 p M |= | p M-1 p M '| = | p M-1 p M ''| and ∠p M p M-1 p M ' = ∠p M. p M-1 p M '' = ∠p M '' p M-1 p M '.
The control point collection for the two new commands of the family are (p 1 , p 2 , …, p M-1 , p M ') and (p 1 , p 2 , …, p M-1 , p M '') respectively.

Figure 3 illustrates a real use case. In step 1, after getting the original curve of the user, a canonical spline is generated with M=6. In step 2, the other two gesture commands of the same family are generated automatically.

III. RECOGNIZER

In SCGC approach, for gesture recognition, we adopt a pattern recognition approach adapted to this application. The recognizer needs to be able to learn with very few training samples because the set of gestures will be different for each user. Input gestures are described by a reduced set of 15 features, and classification is executed by an incremental lightweight Fuzzy Inference System that requires few training samples [START_REF] Almaksour | Improving premise structure in evolving Takagi-Sugeno neuro-fuzzy classifiers[END_REF] [START_REF] Almaksour | Personalizable Pen-Based Interface Using Lifelong Learning[END_REF].

A. Feature extraction

Input gestures are first linearly rescaled so their maximal dimension is 64, in order to make the recognition of gesture scale-independent. The pen trajectory is then resampled so that the spatial distance between points is always equal to 8, to avoid sensitivity with respect to speed variations in the writing. We finally extract a set of 15 features, combining dynamic (time-based) and visual (image-based) features, so as to handle different properties of the patterns. Some retained features are inspired from Rubine's features [START_REF] Rubine | Specifying gestures by example[END_REF]: trajectory length, initial angle, first point to last point vector. The position of the first point and the last point of the trajectory with respect to the gesture's bounding box is also described. As visual descriptors, we extract zoning features from a regular 3x3 grid partition of the bounding box.

This diversity of features is essential for some tests (see section 4) where the recognition of "unpredictable" userdefined gestures is needed. While no optimization is possible, given this "open-world" problem, it is hoped that the chosen feature set can properly distinguish between a sufficiently large set of classes defined by the same user.

B. Fuzzy inference system

Most of classical feature-based recognition methods (neural networks, statistical recognizers, Support Vector Machines…) involve a training phase that is executed offline. In our situation, however, the training phase has to be run online, since the gestures chosen by the user have to be learned by the classifier. Another constraint is the few available training samples, since the user should not need to perform more than 3 samples per gesture. For these reasons, we chose to use an Incremental Fuzzy Inference System, a competitive discriminative classifier that requires very few training samples and computing resource. This system is designed to be integrated into applications which need customization aspect. Actually, the system can be used as an evolving recognizer, with lifelong learning and handling of new classes of gestures (see more details in [START_REF] Almaksour | Improving premise structure in evolving Takagi-Sugeno neuro-fuzzy classifiers[END_REF][13]). The reduced size of the feature set (only 15 features) is also essential to obtain better classification performance with only few training samples.

IV. EXPERIMENTS To evaluate our SCGC approach, we made several experiments. On first step, we made some pre-tests to see users' reaction for this new approach on a tablet. After having observed some difficulties on manipulation, we adapted our approach to make the learning even much easier as described in section 4.1. On second step, we fixed the objectives of these experiments: we wanted to evaluate SCGC in a real piece of software's context (ecological frame). It means that we would like to see user's attitude without telling them that it is a test. We wanted to see how gestures are learnt unconsciously by users. We did not want them to feel obliged to memorize the gestures which is different from a lot of tests made before [START_REF] Bailly | Wave Menus: Improving the Novice Mode of Hierarchical Marking Menus[END_REF][2][9] [START_REF] Zhao | Simple vs. Compound Mark Hierarchical Marking Menus[END_REF]. So we made three different comparative tests: test1 where the user chose all his gestures; test2 (SCGC approach) where the user chose the root gesture and the relative gestures were automatically generated; and test3 (SCGC without personalization) where root gestures are pre-defined.

A. SCGC adaptation

We made some pre-tests to collect users' observations on SCGC. We realized that it is difficult for a user to remember the relative direction of a spline's end in one family. To overcome this difficulty, we fix the spline's end in three absolute directions: down, right and left. So instead of defining gesture for the predominant command in a family, the user defines a root gesture for the family. Figure 4 illustrates this change (more examples in Figure 6).

B. Presentation of the application

The application context of the tests we performed took the shape of a pen-based picture editor program with which users can perform various actions using graphic gestures. The aim is to obtain an ecological frame, allowing the user to be confronted with a real case of gestural commands' use. Moreover, whereas the test protocols involved the user only being asked to draw a series of commands into a box, a real use of a concrete application does not allow placing the user in an "artificial" learning situation. The ecological frame we used allows deceiving the user by making him think that the purpose of the test is not to memorize the commands but to test the use of graphic commands applied to picture manipulation. The goal is to obtain user learning rates in a passive learning context.

C. Experimental protocol

Users are distributed in 3 groups; each group corresponds to a different kind of experimentation. Users from group 1 were asked to choose a gesture for each of the 21 commands. For group 2, we used the SCGC approach where users only have to choose a root gesture for the 7 families of commands, and then the system automatically generates the 21 corresponding gestures. Finally for group 3, the 7 root gestures and the corresponding 21 gestures were forced onthe users. For each group, users were asked to draw each gesture 3 times in an initialization phase. We present a variety of gestures from users from group 1 for 3 different commands in Table 1.

Experimentation itself is divided into 2 use phases and 2 test phases. Use phases are made of 34 questions, each of them corresponding to a command. Moreover, some commands were asked more often than others. 6 of them were asked 3 times by use phase, 4 were asked twice and 8 were asked once. The remaining 3 commands were asked during use phases. During the use phases, user had access to a help window with a table of all the gestures (Figure 6).

During the test phase user had to achieve once each of the 21 gestures in a random order. During test phase, user could not display the help windows. To summarize, the protocol follows the pattern: When a gesture is made, it is sent to the recognizer. If the gesture is correctly recognized, the visual effect of the command applies so the user can be informed that he has successfully performed his gesture, and then another question is asked. On the other hand, if the answer of the recognizer is different from the gesture that was asked, we must know if the recognizer failed or if the user performed a wrong gesture. So, in this situation, a window will pop up to show the user the asked gesture and the gesture he drew. In this window, the user has to state whether or not he has performed the right gesture. If he drew the good gesture, the visual effect applies and the test goes one. However if he drew a wrong gesture, he will then have to try again. When a gesture is correctly recognized, the classifier uses it to strengthen its learning for this class. When the classifier is mistaken there are two possibilities: if the user states that he has done the good gesture, then it's used to strengthen the gesture that was asked, instead of the gesture which has been recognized. If the user states that he did a wrong gesture, and then nothing happens, the user has to draw it again.

D. Results

We present here the results of 23 users divided into the 3 groups: 1) User learning curve: Figure 8 shows the average score for each group. This score represents the percentage of gestures correctly realized by the users during each testing phase. The dotted curve corresponds to the group 1, the dashed one to the group 2 and the solid curve shows the score for the group 3.

We can see that the average score of the group 1 for test phase 1 is the higher (83%). This is most likely due to the fact that users can here choose for each command a familiar gesture. Also, users in this group have the possibility to choose gestures that have a very strong semantic link with the commands (examples include drawing a square for the command "classic frame", a heart for "valentine frame" or an @ for "send by email"). Consequently, many gestures are already "known" by the user since the very beginning of the test. On the other hand, not all commands can be associated to a "semantic" gesture. Moreover, memorizing 21 different gestures remains a hard task. As we can see, final scores of group 1 will finally be weaker than the scores of group 2. We can notice that group 1 presents the worst learning progression rate with 0.6%, while in group 2, the users progressed at a 19% rate and in group 3, 33%. Now let us take a look at the results concerning group 2 and 3. Those two groups use the same system of gestures generation from a root family gesture. Group 2 corresponds to the SCGC approach where the users can choose their root gestures while in group 3, they are imposed. As we can see, even if the scores of group 2 are lower at the beginning, they finally exceed those of group 1 with a score of 93%. This shows that even if users cannot customize their gestures as much as they would like in order to make the task easier, only having to memorize 7 gestures and the 3 variations is a much easier task than memorizing 21 gestures, even if customized gestures seem to be better known at first. Group 3 is a perfect illustration of this principle. Of course this group presents the lowest scores from the beginning to the end. This is easily explainable by the fact that all gestures and root gestures are unknown for the user. However the use of the family organized gestures with our method of gestures generation allow this test to present a high progression rate of 33.7%.

2) Classifier's learning curve: At the same time, to learn how the user behaved in front of these tests, we also wanted to see the incremental classifier's behavior. We then took the gestures obtained during the two test phases as a test database (without the three commands which were not asked to draw during the use phases). This test database is used to evaluate the classifier's performance at the end of the initialization phase, at the end of use phase 1 and at the end of use phase 2. So we obtained three control points to see the incremental learning of the classifier. We obtained the learning curve of the classifier reported in Figure 7. The control point 1 begins at a different place for these curves because users can choose not to repeat 3 times all gestures during the initialization phase. The difference at point 2 or point 3 is due to questions asked more than once when the user did not draw the good gesture. On the mean curve, we can find that after the initialization phase, the recognizer has a 25.2% error rate on the test database. It has a 13.4% error rate after use phase 1. Finally it has a 11.3% error rate after use phase 2. We conclude that even with few gesture samples (7 to 11 for each command), the incremental recognizer has learned progressively the gestures from the users, which explains the decrease on the error rate.

V. CONCLUSION

In this paper we present the new SCGC approach to make fluid and natural gesture commands easy to memorize and to learn for the user. The reported experiments demonstrate that a user has better memorization with the SCGC approach than by defining all the gestures himself. We conclude that the learning progression of the user is faster with the SCGC approach. We analyzed the users' learning curve and the classifier's learning curve at the same time: we show that the fuzzy incremental recognizer is really accurate on this kind of software scalable. All the material of the reported experiments (database) will be soon available on our research team's website (http://www.irisa.fr/intuidoc/).

LI

  PeiYu a Renau-Ferrer Ney b Anquetil Eric a Jamet Eric c a : IRISA/INSA Rennes b,c : University Rennes 2

Figure 1 .Figure 2 .

 12 Figure 1. Prototype creation.

Figure 3 .

 3 Figure 3. Gesture generation for a family.

  a. Initialization: user draws each gesture 3 times b. Use phase1: user answers the 34 questions c. Test phase1: user draws the 21 gestures d. Use phase2: user answers the 34 questions e. Test phase2: user draws the 21 gestures

  9 in group 1, 7 in group 2, 7 in group 3. The group 1 dataset contains 1017 gestures divided into 189 classes (21 per user) with 7 to 11 examples per class. The group 2 dataset contains 861 gestures divided into 147 classes (21 per user) with 7 to 11 examples per class. The group 3 dataset contains 861 gestures divided into 21 classes with 49 to 77 examples per class (7 to 11 per user).

Figure 4 .

 4 Figure 4. New SCGC for a gesture family.

Figure 6 .

 6 Figure 6. "help" window with the gesture set.

Figure 5 .

 5 Figure 5. Test's picture.

Figure 8 .

 8 Figure 8. Percentages of gestures correctly known by the user for the 2 test phases.

Figure 7 .

 7 Figure 7. Classifier's learning curve.

Table 1 .

 1 Example of users' gestures.

	Display
	icons
	Display
	normal
	Personal
	folder

ACKNOWLEDGMENT

During this experiment, we received a lot of help from the platform LOUSTIC. We would like to express our thanks to Caroff Olympe and Uhde Alarith who organized the test séances. We would like also to give our thanks to Manuel Bouillon who helped us a lot on classifier's learning curve.


Ahmad Ahmad-Kassem
email: ahmad.ahmad_kassem@inria.fr

Eric Bellemon
email: eric.bellemon@gmail.com

Stéphane Grumbach
email: stephane.grumbach@inria.fr

Seamless Distribution of Data Centric Applications through Declarative Overlays

Keywords: peer-to-peer overlays, declarative networking, multiplayer online games réseaux pair à pair, protocoles déclaratifs, jeux multijoueurs en ligne

We present an approach based on peer-to-peer overlays which allows to distribute seamlessly data centric applications defined by queries over a centralized database. We consider applications in which the users have access to views, which contain horizontal fragments of the data of interest to them. The peer-to-peer overlays are defined by simple declarative programs in the Netlog language. The communication relies on implicit addresses, which can be evaluated on the fly, and ensure persistence of data in messages. We demonstrate the technique on a multiplayer online game, written in SQL, with players who connect to a mobile ad hoc network through their portable devices. The overlay is defined by a combination of an ad hoc routing protocol, DSDV, together with a DHT. The application runs on the QuestMonitor platform, which allows to monitor the communication between peers, the evolution of the local data stores, as well as the execution of the declarative code.

Introduction

Peer-to-peer systems have been widely used to alleviate the burden of servers, by transferring to peers in a network tasks that do not require a centralization of the information. Their architecture can be more or less structured, with nodes playing identical or different functions, and with or without interaction with a centralized server. They have been very successful in various fields such as file sharing (e.g. Napster, Gnutella), and communication networks (e.g. skype). A wide range of applications are now emerging over peer-to-peer systems, such as social networking [START_REF] Buchegger | Peerson: P2p social networking: early experiences and insights[END_REF][START_REF] Au Yeung | Decentralization: The future of online social networking[END_REF], multiplayer games [START_REF] Knutsson | Peer-to-peer support for massively multiplayer games[END_REF][START_REF] Hampel | A peer-to-peer architecture for massive multiplayer online games[END_REF], mobile messaging [START_REF] Persson | Exms: an animated and avatar-based messaging system for expressive peer communication[END_REF], video broadcasting [START_REF] Liu | Opportunities and challenges of peer-to-peer internet video broadcast[END_REF], etc.

Most of these applications are essentially data centric, they rely on exchange of data between peers, and could be expressed by queries over a database. In this paper, we demonstrate how such applications programmed as a collection of queries over a database, can be ported seamlessly, that is without changing the queries, from a client-server architecture, to a peer-to-peer architecture with the appropriate overlay. Moreover, following the trend open by the declarative networking [START_REF] Loo | Implementing declarative overlays[END_REF][START_REF] Loo | Declarative networking: language, execution and optimization[END_REF], we show that the overlay can be defined using declarative data centric programs, thus resulting in a fully data centric modeling of the peer-to-peer application.

Let us consider for instance online multiplayer games, which constitute a very promising application for peer-to-peer systems. This type of application relies on a scenery from a virtual world, which constitute static data with graphical properties that are out of the scope of this work. Games also involve mutable objects, whose properties can be updated, and avatars representing the players, that can change their attributes. Most of the actions of such games can be captured in a purely data centric perspective, even if like for other applications, additional characteristics are important, such as trust and security issues [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF], as well as real time aspects, essential for communication systems [START_REF] Chopra | Peer-to-peer overlays for real-time communication: Security issues and solutions[END_REF].

In all these applications, the clients can access data of interest to them, which can generally be defined by views over some horizontal fragments of the data structures. The clients can perform actions, which consist in querying or updating these views (e.g. moving an avatar means updating its position), while the system can perform more general actions such as queries and updates over the whole data. We show that under some restrictions under the views and queries allowed, the application can be ported seamlessly over overlay networks and executed efficiently.

Numerous techniques have been developed to support peer-to-peer overlays, such as Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], or Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF] for instance. As distributed algorithms in general, they require high programming skills, and their correction is very difficult to guarantee. High level programming abstraction, such as data centric programming languages constitute a very promising model in this context [START_REF] Hellerstein | The declarative imperative: experiences and conjectures in distributed logic[END_REF]. They are more declarative, so facilitate programming, they parallelize well, so facilitate the execution, they manipulate explicitly data structures, so facilitate verification of their properties.

The use of rule-based languages, à la Datalog [START_REF] Bancilhon | Naive evaluation of recursively defined relations[END_REF][START_REF] Bancilhon | Magic sets and other strange ways to implement logic programs (extended abstract)[END_REF][START_REF] Vieille | Recursive axioms in deductive databases: The query/subquery approach[END_REF][START_REF] Ramakrishnan | A survey of research on deductive database systems[END_REF], developed in the field of databases in the 1980's, for distributed applications, was initially proposed in UC Berkeley [START_REF] Loo | Declarative routing: extensible routing with declarative queries[END_REF][START_REF] Loo | Declarative networking: language, execution and optimization[END_REF], under the name "declarative networking". It was shown that such languages augmented with communication primitives, allowed to express communication protocols or P2P systems with code about two orders of magnitude shorter than imperative programs, and with reasonable execution models.

We used the rule-based language, Netlog [START_REF] Grumbach | Netlog, a rule-based language for distributed programming[END_REF], which extends Datalog with aggregation and non-deterministic constructs as well as communication primitives, in the spirit of the declarative networking approach. It has a sound distributed fixpoint semantics, which takes explicitly into account the in-node behavior as well as the communication between nodes. Netlog runs on the Netquest Virtual Machine, which is coupled with an embedded Data Management System, DMS, which stores all the data as well as the bytecode of the Netlog programs. The bytecode is obtained by a compilation from Netlog into an SQL dialect. The Virtual machine makes calls to the DMS to evaluate the bytecode of the Netlog programs, which result in updates of the database, and production of messages. Implicit addresses have been added to the Netquest machine, to handle messages to peers that perform server duties. They ensure the persistence of the data even in case of changes in the network due to a node failure or departure.

The Netquest machine has been shown to be portable over small devices, as long as they support an embedded DMS [START_REF] Bauderon | Programming imote networks made easy[END_REF]. It runs as well on the QuestMonitor platform [START_REF] Bellemon | Questmonitor: A visualization platform for declarative network protocols[END_REF], which allows to monitor the communication between peers, the evolution of the local data stores, as well as the execution of the declarative code. Moreover, proof techniques have been developed in Coq to certify Netlog programs [START_REF] Deng | A framework for verifying data-centric protocols[END_REF].

We describe the technique over an example of a multiplayer online game, which can be defined by sequences of queries over a central database, presented in Section 2. Each player has access to views giving the data pertaining either to its avatar in the game (simple views), or to the region where it is involved (geographic views). We consider a game where a player participates to an auction by making a bid, while the system at the expiration of the auction, changes the owner of the object, and updates the bank accounts of both the seller and the buyer according to the price.

So far as the network is concerned, we make the following assumptions on the application. We assume that players participate to the game over a network to which they connect through devices in some short range communication mean (e.g. bluetooth). The players thus form an ad hoc mobile network. They can physically enter or leave the network, as well as move from one place to another, without being disconnected from the application. The players form a pure peerto-peer system, with nodes playing identical roles, and no centralized server. The overlay network is formed by a distributed hash table, DHT, which is used to distribute both data and computation initially performed by the server.

We assume that each table has (at least) an index attribute. The values of index attributes are mapped to hash keys using a hash function. The corresponding horizontal fragments of the relations are stored on the node which has the largest Id smaller than the hash key. Some restrictions are imposed on the queries to ensure smooth distribution through the peer-to-peer system, making full use of the DHT. Queries should in particular have at least one where argument on an index attribute. Moreover join should be performed on index attributes as well. Under such restrictions, we show that the distribution can be done smoothly using the DHT protocols.

For the game application, we propose a DHT constructed over a routing table defined and maintained by a DSDV like protocol [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers[END_REF]. DSDV is a table-driven routing protocol based on the Bellman-Ford algorithm, well adapted to ad hoc networks. We have considered other routing protocols as well such as OLSR [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF], AODV, for on-demand routing, well adapted to a network with many changes, [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF], or VRR [START_REF] Caesar | Virtual ring routing: network routing inspired by dhts[END_REF] based on a ring, which are useful under other network conditions.

The main contribution of the paper is to show that the whole specification of such applications can be made in a fully data centric approach, relying on simple centralized queries for the application, and data centric programs written in Netlog for the DHT protocols. We show in particular in Section 4 that a few dozen of rules are sufficient to express the DHT for mobile ad hoc networks.

Our experiments with the game are presented in Section 5. The scenario, with a node joining the network, participating to the game, moving physically while playing, and leaving the network before the distributed server handles the updates in the game, shows the robustness of the proposed protocols in Netlog. Our experiments show that the movement of one node does not affect the game, all data are preserved, and the duties ensured by the leaving nodes are distributed to other nodes.

The paper is organized as follows. In the next section, we explain the motivation through the multiplayer games, and show the distribution over an overlay. In Section 3, we present the Netlog language together with the virtual machine to evaluate Netlog programs. Section 4 is devoted to fundamental protocols supporting the overlay. In Section 5, we illustrate over the example, the protocols to distribute the applications specified as centralized queries, and test these protocols over the QuestMonitor system.

Motivation

We consider applications which can be described as sequences of database updates performed by clients over a centralized server. The server stores all the data from all clients, while the clients can access and modify only some part of these data, which can be defined by views over the whole data. In this section, we consider such an example to illustrate our technique.

On-line multi-player games over virtual worlds, such as Second Life, World of Warcraft, etc. constitute fundamental applications of this type. Currently, most massively multiplayer games are implemented on a client-server architecture, with a server which handles both client accounts and game states. Various types of clusters are used, for scalability purposes, to support massive numbers, millions, of players at the same time.

If we leave apart the graphical interface in which players evolve, the basic actions they perform can be modeled easily as database updates. Clients generally participate to the game through an avatar. The game relies on some stable "landscape", which can be seen by the clients, using their views over the global data. Most games support mutable virtual objects, which can be changed (created, destroyed, exchanged, etc.) by the players during the course of the game.

The server knows at every moment the connected clients, as well as the updates they make on the data (e.g. creating, deleting or moving avatars, exchanging virtual objects, etc.). We illustrate over an example how each of the basic actions of the payers can be described with a set of queries over the centralized database of the server.

The list of avatars of players is stored in the table Owner, which contains an authentication key for each avatar. We consider a simple game in which avatars exchange, sell or buy objects through an auction market. Each avatar owns bank accounts (table Bank), can register itself into a market (table Market), buy or sell their objects (table Objects), into an auction market (table Auction). Samples of the tables used in the example are shown below. Each client has a local view of these data, which concerns their avatar, say α. We distinguish between simple views, such as the bank accounts or the objects that belong to the avatar α, defined with a where condition of type Object.Avatar=α; and geographic views, where an avatar can get all the fragment of for instance the market on which it occurs. The local view of table, Table, is denoted VTable. Views have the same structure as the corresponding table, without the Avatar attribute in the case of simple views.

We distinguish between two types of actions: client action and system action. The only actions clients can perform is to query or update their local views. Note that some attributes might be system defined (e.g. Account, Balance). An avatar, for example, cannot retrieve the account balance of another avatar neither change the balance of its bank account. When an avatar updates data in a view, the update is sent to the server to be performed. Systems actions consist of queries over the global schema and are triggered and performed by the server. We show below the main actions of the auction game which are defined by simple queries.

1. See the auctions on the market where I am (geographical view) In their seminal paper, Knutsson et al. [START_REF] Knutsson | Peer-to-peer support for massively multiplayer games[END_REF] showed how such a multiplayer game could be developed over a P2P architecture using the Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF] overlay network. We show how more generally any application described by queries and views as presented above can be distributed seamlessly over an overlay.

INSERT INTO VAuction SELECT A u c t i o n . Name , A u c t i o n . OId , A u c t i o n . P r i c e , A u c t i o n . S e l l e r FROM A u c t i o n , A u c t i o n AS A u c t i o n 2 , Owner WHERE A u c t i o n . Name = A u c t i o n 2 .
We consider a network constituted by peers that communicate in a peer to peer fashion (over the Internet, device to device, etc.). They can join and leave the network at any time and participate to the applications with the other connected peers. Collectively they support the tasks of the centralized server, by storing fragments of the data on peers, and by routing the queries (views, client actions, system actions) to the peers in charge. There is no centralized server, and the peers play the same role.

The application is defined over some schema, which will be used in the distributed environment exactly like in the centralized one. Each relation has at least one special attribute called index attribute (underlined in the tables of our example), such as Avatar in table Owner, and Id in table Object. Attributes of the tables are either client-defined (e.g. Name, Price in table Object), or system defined (e.g. Balance in Bank).

The views are expressed as select queries over a single table of the schema. There are two types of views, simple views and geographic views. Simple views are expressed as select queries with a where argument over the index attribute which should be some Id of the client (e.g. the avatar in the game). Geographic views are expressed as select queries with a similar where condition, but allowing a self equijoin over the geographic attribute of the table. The client queries are queries over the views available on the client. System queries are queries over the global schema. Joins are limited to index attributes.

The data are fragmented and distributed as follows using a DHT. The values of the index attribute are mapped to a random uniformly distributed set of circular ID's, used to form the Distributed Hash Table . We assume for simplicity that the node Id's are uniformly distributed, and that the hash values are over the same domain as the node Id's. A circular order is defined over this domain. Each node α is responsible for storing the fragment of each relation corresponding to the tuples whose index value is such that α is the largest node Id smaller than the index value of the tuple.

Several mechanisms can be used to ensure the replication of the data so that nodes can leave the network without perturbing the application. In the sequel we use replication and synchronization methods to ensure the persistence of the data under nodes movement.

3 The Netlog language for distributed protocols Netlog programs consist of sets of recursive rules of the form head :body, where the head is derived when the body is satisfied. The programs are installed on each node of a network, where they run concurrently. The computation is distributed and the nodes exchange information. The facts deduced from the rules can be either stored on the node on which the rules run, or sent to other nodes.

We present the language through some fundamental examples of programs for network organization, routing, and sensor network monitoring.

In the following Program tree, we consider the construction of a spanning tree. The results are distributed so that each node stores the knowledge of its parent in the tree.

Program Tree

onST (self ) : -Root(self ).

(1) ↓ ST (⋄y, self ) : -Link(self, y), onST (y), ¬onST (self ).

(2) onST (self ) : -Link(self, y), onST (y), ¬onST (self ).

(

) 3
The variable self is interpreted by the node address. The store/push operator, " ", in front of rules, determines where the results are assigned. The effect of "↓" is to store the results of the rule on the node where it runs; "↑", to push them to its neighbors; and " ", to both store and push them.

The negation is interpreted by local closed world assumption (a fact is not true on a node if it is not stored on that node). The choice operator ⋄ chooses non-deterministically a parent among the possible choices.

Assume that Root(ρ) holds on a root node ρ exclusively. When a node α is on the spanning tree, it broadcasts onST (α) to its neighbors by Rules (1) and (3). The fact ST (α, β), which is deduced by node β, is stored exclusively on node β, and saved as parent the node α, by Rule (2).

Program Sensor monitoring

↑ Req(self ) : -T emperature(self, t), t > m_threshold.

(4) ↑ Rep(self, @x, t) : -Req(x), T emperature(self, t).

(5) ↓ T emperature(x, t) : -Rep(x, self, t), ¬T emperature(x, _).

(6) ↓ T pAvg(x, avg(t)) : -T emperature(x, t).

(

) 7
The program Sensor monitoring uses to monitor the temperature on sensors. The temperature of the sensors are stored in the relation T emperature with attributes nodeId and temperature. The location instruction "@" in the head of rules represents the destination. Rule (5) unicasts its results, using the location instruction "@", on the second variable of the head, instead of pushing them to all neighbors. The constant m_threshold in Rule ( 4) is a metadata defined in the header of the program, and the underscore used in Rule (6) denotes "any value".

When the temperature of a sensor, say α, is greater than the defined threshold, it sends a request to all neighbors to retrieve their temperature in Rule (4). Neighbor sensors, upon receiving the request in Rule ( 5) , unicast their current temperature to α, which in its turn saves the temperature of their neighbors upon receiving their answers in Rule [START_REF] Caesar | Virtual ring routing: network routing inspired by dhts[END_REF]. Finally, sensor α, using the aggregation avg in Rule [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF], computes the average temperature of all its neighbors and stores it in the relation T pAvg.

The Netquest Virtual Machine executes the Netlog bytecode and manipulates data and messages. It is working as a daemon in the device, and applications can use it to communicate with other devices on the network. The virtual machine is portable and can be installed in small devices with embedded DMS. A previous implementation was done in iMote sensors [START_REF] Bauderon | Programming imote networks made easy[END_REF].

The Netquest Virtual Machine is composed of six components:

• Device Wrapper for QuestMonitor: provides an abstraction layer of the network. It receives and sends data over the network, and does the address translation between Netlog internal addresses and the network addresses.

• Data Management System (DMS): provides an access to the data. This module evaluates the bytecode, manipulates data (insertion, update and deletion) and produces messages.

• Router: receives and sends Netquest messages through the device wrapper. It chooses the best route to reach each destination. The strategy to select the route can be easily defined in Netlog.

• Engine: executes the Netlog programs. When a node receives a new message, the engine loads the rules matching the facts of the message and evaluates them through the DMS.

• Timer Manager (TM): manages time event of the system. Netlog programs can create and manipulate timers. These timers are managed and fired by this module.

• Application API: this module is an interface between the virtual machine and applications. An external application can use the Netlog Virtual Machine to send and receive messages over the network.

The generated bytecode is a SQL dialect. A query is built for each operator (store, push and deletion) in a rule.

Consider for instance the following rule which contains the three operators. The @ symbol in the body of the rule followed by the variable a denotes the location specifier, where the evaluation of the rule is taken place (on node a). The symbol "!" denotes the deletion of the facts used in the evaluation of the rules. This rule is evaluated when the engine receives a Hello message. It is translated into three SQL queries corresponding to each operator.

The first query is the result for the operator push, the second for the operator store and the third for the deletion.

All the keyword beginning by m_ (e.g. m_self ) are replaced by the engine during the evaluation of the rule. The negation of Link is translated with the sub-query into the section not exists. Nodes communicate by messages which have the following format: < dest, payload >, where payload is the content of the message (a set of facts), and dest = (exdest, imdest), where exdest is an explicit destination (e.g. node Id), and imdest is an implicit destination, that is a query whose answer is of type node Id.

When a message is received by a device, the device wrapper transfers it to the router. The message is read by the router and the payload is sent to the engine if the device belongs to the destination, otherwise it is forwarded to the destination. If the explicit destination is known to the node, the implicit destination is ignored. Otherwise, the query of the implicit destination is fired on the local store of the node, and the result is used as new explicit destination. As we will see, the implicit destinations reveal very useful to handle the destination obtained by the DHT, which can have left the network, and can be recomputed on the fly.

The engine loads rules from Netlog programs matching the facts contained in the payload and then evaluate these rules using the DMS. The DMS can update or delete data and create messages to be sent. These new messages are sent to the network through the device wrapper.

The Netlog Engine does not execute directly the bytecode. It orchestrates the tasks to be done to treat messages and facts. When receiving facts, a new round starts and a first stage is executed. In this stage, the engine loads and executes rules triggered by these facts. If there are derived facts produced by the engine, a new stage is executed recursively again with these new facts. A round is finished when there are no new derived facts. At the end of a round, produced messages are sent to other nodes in unicast or broadcast mode.

Declarative overlays

Netlog is well adapted to the development of networking protocols. In this section, we show how the basic protocols which are used to distribute the server tasks over a DHT can be written. We first present a routing protocol, which defines the routes in the network. Then a ring, that is a circular order, is defined over the node Ids. Each node then constructs the segment of keys it is responsible for. Finally, the replication of the fragments to ensure persistence of the game in the event of failure of a node is defined.

The program DSDV, presented below, is a simplified version of the DSDV protocol [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers[END_REF], which constructs and maintains proactively all possible routes in ad hoc networks. We chose DSDV to support mobile clients participating to a multiplayer game in a device to device network. The routes are stored in relation Route with attributes dest, nextHop, nbHops, destSN and expirationT ime, where destSN is used for sequence numbers.

The program is composed of four modules. Each module can be triggered by an incoming fact or by a timer. For example, the module ini, composed of Rule [START_REF] Chopra | Peer-to-peer overlays for real-time communication: Security issues and solutions[END_REF], is triggered by the timer ini, while the module U pdRoute is composed of Rules ( 11), ( 12) and ( 13) and triggered by the fact HelloRoute. When a module is triggered, all the rules of this module are evaluated in parallel.

Each node initially creates a route to itself when the program starts with Rule (8), triggered by the timer ini, which is fired only once. Periodically, using the timer hello, each node in Rule ( 9) broadcasts all its route information to its neighbors, and increases the value of the sequence number destSN , of the route to itself, using Rule [START_REF] Grumbach | Netlog, a rule-based language for distributed programming[END_REF].

The route information are sent using facts of the form HelloRoute. A node updates its routing table according to the received route information from its neighbors as follows: (i) a new route is stored Rule [START_REF] Hampel | A peer-to-peer architecture for massive multiplayer online games[END_REF] if there is no route to the same destination in the local route table, (ii) the old route is deleted and replaced with a new one, if the new route has a larger destination sequence number, Rule [START_REF] Hellerstein | The declarative imperative: experiences and conjectures in distributed logic[END_REF], or the new route has the same sequence number as the old one but has a smaller number of hops, Rule [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF]. Each node sets for each route a timeout m_timeout, in Rules ( 11), ( 12) and ( 13) upon saving it in the routing table. In Rule [START_REF] Knutsson | Peer-to-peer support for massively multiplayer games[END_REF], each node periodically using the timer checkRoute deletes all expired routes.

Program DSDV module(ini) ↓ Route(self, self, 0, 1, 0) : -T imeEvent( ′ ini ′ ). (8) module(hello)
↑ HelloRoute(self, x, n, s) : -T imeEvent( ′ hello ′ ), Route(x, y, n, s, _). ( 9)

↓ Route(self, self, 0, s, 0) : - T imeEvent( ′ hello ′ ), !Route(self, self, 0, s ′ , 0), s := s ′ + 1. (10) module(UpdRoute)
↓ Route(x, ⋄y, n, s, t) : -HelloRoute(y, x, n ′ , s), ¬Route(x, _, _, _, ),

n := n ′ + 1, t := m_time + m_timeout. (11) ↓ Route(x, ⋄y, n, s, t) : - HelloRoute(y, x, n ′ , s), n :
= n ′ + 1, s ′ < s, !Route(x, y ′ , n ′′ , s ′ ), t := m_time + m_timeout. (12) ↓ Route(x, ⋄y, n, s, t) : - HelloRoute(y, x, n ′ , s), n :
= n ′ +1, n ′′ > n ′ + 1, !Route(x, y ′ , n ′′ , s), t := m_time + m_timeout. (13) module(checkRoute)
:

- !T imeEvent( ′ checkRoute ′ ), !Route(_, _ , _, t), t < m_time, t <> 0. (14)
The next figure shows an example of dynamic network in which node 9 is moving between nodes. We monitor and display the content of the routing table of node 9. The left figure and related table represent the network and the content of the table of node 9 before changing the position while the right figure and related table represent node 9 after changing its position. The route between source node 9 and the destination node 1 is colored in red. As we notice, all routes are up to date, with the DSDV protocol, and there is always a route between all the nodes. The following program, RING, defines a circular order on the node Ids (with the smallest node Id, immediate successor of the biggest one), used in the DHT. The index values of each relation are mapped to hash values. Each node is responsible for an interval of these values, according to the value of its identifier, and their predecessor and successor in the ring.

Since we consider mobile ad hoc networks, the next program relies on the previous routing protocol, ensuring that each node has routes to all nodes in the network, which are maintained over time. Any participating node may be part of the DHT and hold data related to the application. The program uses the relations Intvl with two attributes to save the predecessor and the successor of each node, similar for NIntvl to calculate the new interval. The relation Extreme with two attributes saves the nodes with minimum and maximum Id in the network.

Program RING module(ini) ↓ Intvl(self, self ) : -T imeEvent( ′ ini ′ ). (15
: -Intvl(op, os), hv := hash(x), hv < self, !Owner(x, y, _), !N Intvl(np, ns), np > op.

↑ Recover(@np, x, y, z) : -Intvl(op, _), !N Intvl(np, _), hv < self, Owner(x, y, z), hv := hash(x), np < op.

module(updateOwner)

↓ Owner(x, y, z) : -!OwnerU pd(self, x, y, z).

: -!OwnerU pd(self, x, y, z), !Owner(r, s, m) hv := hash(r), hv < self.

↓ Owner(x, y, z) : -Recover(self, x, y, z).

(

) 27
The program is composed of three main modules. Periodically using the timer upd in module updatecopy, each node, using Rules ( 21) and ( 22), sends a backup to be saved on its successor s for all entries that have index values in the interval [self, s[. Rule [START_REF] Persson | Exms: an animated and avatar-based messaging system for expressive peer communication[END_REF] is used to manage the last node and together with Rule [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF] to prevent each node to save on its successor the backup of its predecessor.

The module updatemove with rules ( 23) and ( 24) is used to manage the backup copy in the successor upon the detection of any change in the predecessor. Indeed, if the new predecessor is greater than the old one, all entries that have index values less than self are deleted, Rule [START_REF] Ramakrishnan | A survey of research on deductive database systems[END_REF]. However, if old predecessor less than old one, that means the old predecessor leaves the network, and so all entries that have keys less then self should be sent to new predecessor, Rule [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF].

The backup and recover copy are sent using facts of the form OwnerU pd(nodeId, avatar, authentication, owner) and Recover(nodeId, avatar, authentication, owner). In the module updateOwner, the successor saves a backup copy upon receiving the fact OwnerU pd(self, x, y, z) in Rule [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF] and at the same time deletes the old copy, Rule [START_REF] Vieille | Recursive axioms in deductive databases: The query/subquery approach[END_REF], while new predecessor saves a recover copy upon receiving the fact Recover(self, x, y, z) in Rule (27).

In the next example, we monitor the impact of the departure of node 7 from the network. Node 7 is in charge of fragments of relations whose index attribute is mapped to a value in the interval [6, 8[. The values of the index attributes Toto and Loulou are mapped by the hashing function respectively to 7, and 3. Node 7 is therefore responsible for the fragment of relation Owner with Avatar Toto as seen on the first Owner Table below. When node 7 disappears, its predecessor 6 takes the duty, and hosts the fragment, as shown on the second owner table. The figure shows the new Ring over the network after the departure of node 7.

• Replication and synchronization: The change in the ring also triggers the replication and synchronization protocols. The predecessor and the successor of node α in the ring send to node α all entries (data about the distributed table) that have index values in the interval [pred α , succ α [. The new node is now responsible of some fragments of the distributed database.

The process begins as follows when a new node, node 7, joins the game, which is already running between players. The communication between nodes is represented in red in the following figure .   After the authentication and the propagation of the route, node 7 calculates its interval and saves as predecessor node 6 and successor node 8. It then receives all entries of the distributed table that have index values in its interval [6, 8[ from both its predecessor and its successor.

Suppose now that node 6 has data with index values in the interval ]7, 8]. The predecessor of the index values is the node responsible. Thus, node 6 communicates with node 7 to save the corresponding data, and then saves a backup in its successor node 8.

After node 7 has entered the game, it has to retrieve all the information about its avatar (list of owned objects, bank account, etc.) as well as its geographic views (such as the list of auctions on markets where it registers). It uses the index attributes to communicate with nodes that are responsible of the fragments of interest to it. When the node has retrieved all the information about its avatar, and has registered to a market, it is able to bid at an auction. It updates its local view of the table Auction and then sends an update (client action 3 in Section 2) to the node responsible of the market. When this node receives the update query, it updates the table Auction and the backup copy in its successor (using the replication protocol).

The node can move in the physical space, and so change position in the network. Thanks to the DSDV program, it is always reachable, but the DHT ring is not modified.

Every message sent by a node is composed of an explicit and an implicit destination. The explicit destination is the node responsible of the index values and the implicit destination is a query over relation Intvl that can compute a new destination if the explicit destination becomes unreachable.

The DSDV program updates its routes every three seconds. If a node α sends a message to a disconnected node β, a hop in the path between α and β will eventually be missing and the implicit destination to find a new explicit destination will be evaluated. The new destination is the node newly responsible of the index value. Thus, data in the message is not lost.

Suppose now that the node disconnects before the end of the auction. The DSDV program detects that the node is no more in the network and the route to this node expires and is deleted.

When the route is deleted, the ring, as well as the duplication and replication of the data fragments are updated as seen in Section 4.

When the auction expires, the node responsible of the market where the auction is stored has to execute some system actions. These actions are SQL queries on the distributed tables. They consist of a transaction of SQL queries: (i) update the bank account of the seller and the buyer; (ii) update the owner of the object; and (iii) delete the auction from table Auction To update the bank accounts, the node responsible of the auction, say λ, does a join between the fragments of two tables Auction and Market, which are on the same node because they have the same index attribute, in order to retrieve the account of the avatar. Then, after hashing the account of each avatar, it sends two messages with explicit and implicit destination to nodes responsible (say β, γ for the seller and the buyer respectively) in order to update their balance.

Given the restrictions on the queries, messages are never broadcasted, but unicasted thanks to the index attribute of the DHT table. An important feature of our approach, supported by the Nequest machine, is the use of a pair of explicit/implicit destination at the same time, to handle the possibility that the destination node leaves the network.

To update the object, node λ hashes the object OId from its local table Auction and sends a message with explicit and implicit destinations to the node responsible, say θ. Upon receiving the message, node θ updates the entry related to object OId.

Finally, to delete the auction, node λ directly removes the entry of the auction on the local fragment of the auction table, and updates the replicated version and synchronizes with the protocol Replication and Synchronization.

In the simple game we have considered, the join is done on one single node. More complex distributed joins can be handled as well by the present approach, but require additional protocols to carry on the distribution.

Conclusion

Data centric languages facilitate the writing of distributed programs, resulting in much shorter and more declarative code. We have shown that networking protocols could be written as simple, very concise, programs consisting of a few dozen of Netlog rules. We described the rules coding for a DHT in a mobile ad hoc network relying on a DSDV like routing protocol. We then showed that applications coded as queries in a client-server framework could be ported seamlessly, that is without modifying the initial queries, to the distributed environment. The distributed system based on the DHT ensures the tasks of the centralized server in a fully distributed manner, by relying in the peers which handle horizontal fragments of the relations, and communicate with other peers to solve queries. We considered the promising example of multiplayer online games, which can be fully described in a data centric fashion, and showed how it can be seamlessly distributed. The experiments we made on the QuestMonitor platform, with games of over 50 players, demonstrated the robustness of the approach.

We plan to further investigate the protocols supporting peer-to-peer applications and the distribution of the server tasks, by considering other DHTs, as well as additional issues, such as security and real time which are critical. We also plan to verify formally the DHT, and extends our results to ensure the persistence of the game under more stringent conditions, such as the movements of several nodes at a time. It has been shown that the data centric approach facilitates the verification of the programs. Simple Netlog protocols have already been verified [START_REF] Deng | A framework for verifying data-centric protocols[END_REF] using the Coq proof assistant.

  Name AND A u c t i o n 2 . S e l l e r = Owner . A v a t a r AND Owner . C l i e n t = s e l f ; 2. Propose a new auction (client action) INSERT INTO VAuction SELECT ' Catown ' , Owner . A v a t a r , Owner . A v a t a r , O b j e c t . Id , 1 WHERE Owner . C l i e n t = s e l f AND V O b j e c t . I d = I d ; 3. Make a bid (client action) UPDATE VAuction SET VAuction . Buyer =Owner . A v a t a r , VAuction . P r i c e = ' 150 ' WHERE VAuction . Name= ' Catown ' AND VAuction . S e l l e r = ' T o t o ' AND VAuction . OId = 1 AND Owner . C l i e n t = s e l f ; 4. Cancel a bid (client action) DELETE FROM VAuction WHERE VAuction . Name= ' Catown ' AND VAuction . S e l l e r = Owner . A v a t a r AND VAuction . OId = 1 AND Owner . C l i e n t = s e l f ; 5. Conclude an auction when the auction has expired (system action) UPDATE Bank SET Bank . B a l a n c e = Bank . B a l a n c e -150 WHERE Bank . A c c o u n t = ' AB87532 ' ; UPDATE Bank SET Bank . B a l a n c e = Bank . B a l a n c e + 150 WHERE Bank . A c c o u n t = ' AB123985642 ' ; DELETE FROM A u c t i o n WHERE A u c t i o n . Name= ' Catown ' AND A u c t i o n . S e l l e r = ' T o t o ' AND A u c t i o n . OId = 1 ; UPDATE O b j e c t SET O b j e c t . A v a t a r = ' L o u l o u ' , O b j e c t . P r i c e =150 WHERE O b j e c t . I d = 1 ;

  Link(a, b) : -!Hello(b, @a), ¬Link(a, b).

SELECT

  H e l l o . a , H e l l o . b FROM H e l l o WHERE H e l l o . a= ' m _ s e l f ' AND NOT EXISTS ( SELECT L i n k . a , L i n k . b FROM L i n k WHERE L i n k . a= H e l l o . a AND L i n k . b= H e l l o . b ) ; INSERT INTO L i n k SELECT H e l l o . a , H e l l o . b FROM H e l l o WHERE H e l l o . a= ' m _ s e l f ' AND NOT EXISTS ( SELECT L i n k . a , L i n k . b FROM L i n k WHERE L i n k . a= H e l l o . a AND L i n k . b= H e l l o . b ) ; UPDATE H e l l o SET H e l l o . d e l e t e d =1 WHERE H e l l o . a= ' m _ s e l f ' AND NOT EXISTS ( SELECT L i n k . a , L i n k . b FROM L i n k WHERE L i n k . a= H e l l o . a AND L i n k . b= H e l l o . b ) ;

  ) module(extreme) ↓ Extreme(min(d), max(d)) : -T imeEvent( ′ chN gb ′ ), Route(d, _). (16)module(interval) ↓ N Intvl(max(d1), min(d)) : -!Extreme(_, _), Route(d, _), d > self, Route(d1, _), d1 < self. (17) ↓ N Intvl(y, min(d)) : -!Extreme(self, y), Route(d, _), d > self. (18) ↓ N Intvl(max(d), x) : -!Extreme(x, self ), Route(d, _), d < self.(19)module(updateInt)↓ Intvl(np, ns) : -!Intvl(_, _), !N Intvl(np, ns).

Acknowledgment

The authors would like to thank Ben Leong for suggesting us to consider fully distributed multiplayer games, as well as Christophe Bobineau, Christine Collet, Fuda Ma, and Stéphane Ubéda, for fruitful discussions.

This work has been supported by the Agence Nationale de la Recherche, under grant ANR-09-BLAN-0131-01.

The program is composed of four main modules. Each node in the network initially sets its successor and predecessor to its node Id when the program starts with rule [START_REF] Liu | Opportunities and challenges of peer-to-peer internet video broadcast[END_REF], triggered by the timer ini only once. Then, periodically using the timer chN gb in Rule [START_REF] Loo | Declarative networking: language, execution and optimization[END_REF], extreme nodes are specified by using the routing table which has a route to all destination. The third step consists at finding the interval of each node. Rule [START_REF] Loo | Implementing declarative overlays[END_REF] defines new intervals of intermediate nodes by checking the routing table and finding the new predecessor and successor, while Rule ( 18) and ( 19) are used to calculate the interval of extreme nodes. The minimum node, in Rule [START_REF] Loo | Declarative routing: extensible routing with declarative queries[END_REF], sets its predecessor to the last node and finds its successor, and the maximum node in Rule [START_REF] Au Yeung | Decentralization: The future of online social networking[END_REF] sets its successor to the first node and finds its predecessor. Finally, in Rule [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers[END_REF], each node updates its interval upon receiving a new interval.

The virtual ring can be seen on the next figure. The edges in black are the network edges, while red edges form the virtual ring. For reliability purposes, we assume that all data are replicated on two nodes, thus allowing any node to leave the network with no perturbation to the game. We assume that each node, say α, is responsible for the interval of values between its predecessor and successor node in the loop, [pred α , succ α [. The program REPLICATION ensures the replication of the data on the two nodes responsible for a fragment. It is shown here on the relation Owner, which has three attributes Avatar, Auth and Client, where Avatar is the index attribute.

Program REPLICATION module(updatecopy)

↑ OwnerU pd(@s, x, y, z) : -T imeEvent( ′ upd ′ ), hv := hash(x), hv ≥ self, Intvl(p, s), Owner(x, y, z), hv < s.

↑ OwnerU pd(@s, x, y, z) : -T imeEvent( ′ upd ′ ), hv := hash(x), hv ≥ self, Intvl(p, s), Owner(x, y, z), s < self. The program SYNCHRONIZATION, performs the synchronization of the tables which have more than one index, such as the table Auction of the example, and whose data are therefore duplicated in as many pairs of copies as there are indexes. (This program is omitted in this draft for space reason).

Similar replication and synchronization programs are defined for all the tables of the application. The use of these programs is shown in the next section.

A Distributed Server for a multiplayer game

We have implemented the auction game in Netlog over the QuestMonitor system, and made experiments on dynamic networks of several dozen peers participating to the game. We describe below the execution of a simple scenario, where a node joins the network to participate to the game. After retrieving all the information about its avatar, it does a bid on an auction and finally disconnects from the network. At the expiration of the auction, the avatar owns the object, although the peer to whom the avatar belongs has already left the game.

To join the game, a node, say α, goes through four important steps:

• Authentication: Node α sends an authentication message to its neighbors. When the neighbors receive an authentication request, they verify if the authentication key of the avatar is correct, by sending the query to the node which stores the corresponding fragment of the Owner table. If the authentication succeeds, the routing algorithm is allowed to start.

• Route propagation: If node α is allowed to join the game, neighbors propagate their routes to node α and accept incoming route from it. The detailed workflow of DSDV is described in Section 4.

• Insertion in the ring: Node α has to insert itself into the DHT ring. The Ring protocol described in Section 4 is used to make it responsible for the interval [pred α , succ α [ of index values, and to update accordingly the nodes pred α and succ α .