Abdulkader Benchi

Frédéric Guidec

Pascale Launay

JOMS: a Java Message Service Provider for Disconnected MANETs

Keywords: Java Message Service, JMS provider, Message Oriented Middleware, disconnected MANET

A disconnected mobile ad hoc network (or D-MANET) is a wireless network, which because of the sparse distribution of mobile hosts appears at best as a partially or intermittently connected network. Designing and implementing distributed applications capable of running in such a challenged environment is not a trivial task. Middleware systems such as Java Message Service (JMS) have made application development easy and cost-effective in traditional wired networks. It can be expected that middleware systems designed specifically for D-MANETs bring similar benefits. In this paper, we introduce JOMS (Java Opportunistic Message Service), a JMS provider for D-MANETs with which pre-existing and new JMS-based applications can be deployed simply in D-MANETs.

I. INTRODUCTION

In a mobile ad hoc network (or MANET), mobile devices can communicate with one another using direct wireless transmissions. Because the range of these transmissions is often quite short, a number of protocols (such as OLSR, AODV, DYMO, DSR...) have been developed during the last two decades in order to support multi-hop forwarding in MANETs. Yet most of these protocols rely on the assumption that the network remains connected, that is, a temporaneous end-toend path exists at any time between any pair of hosts in the network. Unfortunately this assumption does not hold in many MANETs that are, at best, only partially or intermittently connected.

Figure 1 illustrates a typical disconnected MANET (or D-MANET). This network appears as a collection of distinct "islands" (or connected parts of the network) rather than as a single, connected network. Hosts can communicate within each island, but no temporaneous communication is possible between different islands. The concept of delay/disruptiontolerant networking makes it possible to bridge the gap between islands, though, using mobile hosts as message carriers as they move in the network [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. A message can thus be stored temporarily on a host, and be carried for a while by this host before being forwarded to another host when circumstances permit. In Figure 1, a smartphone or laptop carried by a user moving -deliberately or by chance-from island 1 to island 2 can serve as a carrier for messages addressed to hosts located in island 2. Based on this "store, carry and forward" model, connectivity disruptions can be tolerated. Yet this approach yields long transmission delays because it depends on theusually non-predicted-mobility of hosts. The term opportunistic networking is usually used in the literature to denote this kind of networking where nonpredicted radio contacts between mobile hosts are used by these hosts to exchange messages, and thus contribute to the propagation of messages network-wide. A number of opportunistic networking protocols have been developed for D-MANETs during the last few years [START_REF] Nguyen | Routing in Opportunistic Networks[END_REF]. Yet developing distributed applications capable of running based on these protocols is not a trivial task: the dynamic nature of D-MANETs, long transmission delays, occasional transmission failures all constitute serious challenges developers must face. As a general rule, when designing an application for D-MANETs the peer-to-peer model should be preferred over the client-server one, because in most circumstances no host can be considered as being stable and accessible enough to play the role of a server for all other hosts.

In traditional networking environments the concept of middleware gained popularity as a solution to ease the development of distributed applications. It can be expected that middleware systems designed specifically for D-MANETs should bring developers similar benefits. According to Hurwitz [START_REF] Hurwitz | Sorting out middleware[END_REF] there are four main types of middleware: transactional, procedural, message-oriented and object-oriented middleware. The asynchronous message-passing feature of message-oriented middleware makes it an appropriate model for D-MANETs, for the long transmission delays imposed by the "store, carry and forward" scheme can be easily tolerated through asynchronous messaging.

In the remainder of this paper we present JOMS (Java Opportunistic Message Service), a message-oriented middleware system we designed and deployed for D-MANETs. JOMS is actually a provider for the standard Java Message Service (JMS), so the developers of JMS applications can use JOMS just like they use any other JMS provider.

This paper is structured in the following way: an overview of the JMS specification is provided in Section II. Section III presents the general architecture and principles of our system JOMS, and details about the implementation of this system are provided in Section IV. Related work is discussed in Section V. Section VI concludes this paper, and describes our plans for future work.

II. JAVA MESSAGE SERVICE (JMS)

The Java Message Service (JMS) is a Message-oriented Middleware (MoM) standard that allows application components based on the Java 2 Platform Enterprise Edition (J2EE) to create, send, receive, and read messages. Since it is a MoM standard, it supports distributed communication in a looselycoupled, reliable, and asynchronous manner [START_REF] Hapner | Java message service, version 1[END_REF]. In general, MoM enables a loosely-coupled type of distributed communication. A client sends (produces) a message to another client, which can then try to retrieve (consume) it asynchronously. The producer and the consumer do not have to be available at the same time in order to communicate. In fact, the producer does not need to know anything about the consumer, nor does the consumer need to know anything about the producer. This brings a major benefit to MoM, where the producer and the consumer need to know only what message format and what channel to use in order to communicate.

The JMS API defines a common set of interfaces including the associated semantics that allows programs written in Java to communicate. The JMS specification does not define how messages are transported within a particular implementation, known as a JMS provider. Because of the lack of unified implementation, each major vendor proposes its own JMS provider along with the associated management tools. Each JMS provider supplies the user with an appropriate transport technology for a particular deployment environment.

The JMS API defines two communication models: pointto-point and publish-subscribe. The point-to-point model is built around the concept of queues. A queue sender sends a message to a specific queue, from which a queue receiver can receive it asynchronously. This model provides a oneto-one communication model. In other words, a given queue may have multiple senders and multiple receivers, but each message sent by a sender to this queue is consumed by one receiver. This means that some mechanism is required to decide which receiver candidate will be the actual receiver of a given message.

The publish-subscribe model is based on the use of topics that can be subscribed to by topic subscribers. Messages are published to a topic by topic publishers and are then received in an asynchronous mode by all the corresponding topic subscribers. Each message may thus be consumed by multiple subscribers. This model complements the point-topoint model in that it provides a one-to-many communication model.

JMS supports two delivery semantics, through the so-called persistent and non-persistent delivery modes. A non-persistent message should be delivered in a best-effort mode. Conversely, a persistent message must be delivered in a guaranteed mode. The JMS specification does not define how messages are transported. It is up to the JMS provider to define how these two types of delivery semantics are implemented.

III. JAVA OPPORTUNISTIC MESSAGE SERVICE (JOMS)

JMS was primarily designed for systems where clients connect to central servers via traditional networks and this has remained its typical usage scenario. In most implementations of JMS, message producers send messages to a server that stores these messages and forwards (delivers) them later to the consumers. As explained in Section I a server-based model is hardly compatible with the characteristics of D-MANETs. No host can act as a reliable server for all other hosts. A serverless JMS implementation must thus be developed in order to provide JMS services in D-MANETs.

JOMS, or Java Opportunistic Message Service, is a JMS provider that was designed along that line. Its architecture is composed of two basic modules: a communication middleware system and the JMS provider per se.

A. Communication layer

Building any application for D-MANETs requires some communication middleware system with which mobile hosts can collaborate in a peer-to-peer manner to ensure message transportation. JOMS relies on a communication middleware system called DoDWAN (Document Dissemination in mobile Wireless Ad hoc Networks). This system was designed in our laboratory in order to support content-based information dissemination in D-MANETs [START_REF] Haillot | A protocol for content-based communication in disconnected mobile ad hoc networks[END_REF].

Messages in DoDWAN are composed of two parts: a descriptor and a payload. The payload is simply perceived as a byte array. The descriptor is a collection of attributes expressed as (name, value) tuples, as illustrated in Fig. 2. These attributes can be defined freely by the developers of application services built on top on DoDWAN. The only exceptions to this rule are a message identifier and a deadline, that must systematically appear in any descriptor. The identifier must be unique, for it allows DoDWAN to differentiate messages while detecting duplicate copies of the same message. The deadline is meant to specify how long a message should be allowed to disseminate in the network, and therefore how long copies of this message should be stored by mobile hosts in their local cache.

DoDWAN provides application services with a publish/subscribe API. When a message is published by a local application service, it is simply put in the local cache maintained by DoDWAN. Afterwards each radio contact with another host will be an opportunity for DoDWAN to transfer a copy of the message to that host.

id= "ff789" destination_id= "ChatRoom1" destination_type= "topic" date= "Mon Oct 17 20:54:03 CET 2011" deadline= "Fri Nov 18 20:54:03 CET 2011" delivery_mode= "PERSISTENT" priority= "4" language= "English" locked= "true" In order to receive messages an application service must subscribe with DoDWAN and provide a selection pattern that characterizes the kind of messages it would like to receive. A selection pattern is expressed just like a message descriptor, except that the value field of each attribute contains a regular expression. Fig. 3 shows a selection pattern, which would for example match the message descriptor shown in Fig. 2.

The selection patterns specified by all local application services running on the same host define this host's interest profile. DoDWAN uses this profile to determine which messages should be exchanged whenever a radio contact is established between two hosts. The interaction scheme implemented in DoDWAN takes inspiration from the Autonomous Gossiping (A/G) algorithm [START_REF] Datta | Autonomous gossiping: a selforganizing epidemic algorithm for selective information dissemination in mobile ad hoc networks[END_REF], which itself defines a selective version of the epidemic routing model proposed in [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF]. Each host periodically broadcasts an announcement in order to inform its neighbors (if any) about its identity and interest profile. By sending such an announcement periodically, a node informs its neighbors about its presence and about the kinds of messages it is interested in. Conversely, by receiving similar announcements a host discovers its neighbors, and learns about their own interest profiles. By matching its neighbor's profiles against the descriptors of the messages it maintains in its cache, a host can select descriptors of messages that might be of interest to at least one of its current neighbors. It can thus build a catalog containing these descriptors, and incorporate this catalog in its next announcement. Upon receiving such a catalog, each host matches the descriptors it contains against its own interest profile in order to identify messages that match this profile and that are not already present in its local cache. If such messages are identified, then a request for these messages is sent to the announcer, which complies by sending the missing messages on the radio channel. Finally, when a host receives a message it has requested, this message is put in the local cache so it can later be proposed to other hosts met while moving in the network. As a general rule, a host that subscribes to receive a particular kind of message is expected to serve as a mobile carrier for this kind of message. Yet a host can also be configured so as to serve as an altruistic carrier for messages that present no interest to the application services it runs locally. This behavior is optional, though, and it must be enabled explicitly by an administrator of the DoDWAN platform.

Mobile hosts running DoDWAN only interact by exchanging control and data messages encapsulated in UDP datagrams, which can themselves be transported either in IPv4 or IPv6 packets. When a message is published on a host, its descriptor and its payload are both compressed in order to reduce the bandwidth required for their transmission. Large messages are additionally segmented so that each fragment can fit in a single UDP datagram. Fragments of a large message all contain a copy of the original message's compressed descriptor, so they can propagate independently in the network and be reassembled only on destination hosts, where the payload is eventually uncompressed.

Interactions between neighbor hosts rely on an opportunistic scheme rather than on a strict transactional scheme. No session -and especially no TCP session-is ever established between neighbor hosts because of the high level of connectivity disruptions expected between these hosts. Each host only maintains soft-state information about its neighbors. Thus, whenever a host broadcasts an announcement, for example, some of its neighbors may fail to receive this announcement, without ever compromising either the sender or any potential receiver. Likewise, whenever a host requests a message and fails to obtain this message, it simply waits until it can get another chance to grab this message (either from the same neighbor, or from a different one).

B. JMS provider

A JMS provider supports the publish-subscribe and the point-to-point styles of messaging. This Section describes the message model of JOMS and the way it supports the two models of communication.

1) Message model: according to the JMS specification [START_REF] Hapner | Java message service, version 1[END_REF], a JMS message has three parts: a header, properties, and a body. The JMS message header contains fields used by both clients and providers to control messages. The properties are extra header fields that act as a set of rules describing the message content. They are used by clients to filter messages via message selectors. It is worth noting that selection criteria cannot reference the message body, that carries the message content.

A DoDWAN message has two parts: a descriptor and a payload. Since JOMS is based on DoDWAN, it adopts this message model by mapping the JMS message's fields to the DoDWAN message. An example of a JOMS message is shown in Fig. 2. The JMS message's body is carried in a DoDWAN message as its payload, and considered as a simple byte array. The message descriptor is used by DoDWAN to manage the message dissemination and delivery, by selecting carriers or recipients whose interest profile match the descriptor. The JMS message's header and properties are mapped to the DoDWAN message's descriptor, as their content is needed by JOMS to process the messages delivery. MessageID and Destination are standard JMS header fields used to identify and route the message. The message identifier is needed by DoDWAN to differentiate messages and avoid the dissemination of duplicate copies of the same message. The destination name is used by JOMS to route the message to its recipients having this criterion in their interest profile. We will explain later how these profiles are defined in JOMS to allow publish-subscribe and point-to-point communications. As those communication styles are quite different and implemented in JOMS using distinct models, an extra property, the destination type, is added to the JMS initial message. The JMS Expiration field is mapped to the DoDWAN message and called deadline. This field, optional according to the JMS specification, is mandatory while using DoDWAN, as it is used to avoid the overloading of radio channels and hosts' caches with out-ofdate messages. Its value is set to a default value by JOMS if the JMS expiration field's value is zero. According to the JMS specification, the DeliveryMode and Priority properties express the expected degree of reliability and priority for transmitting messages. Given the disconnected nature of the environments targeted by JOMS, it is not possible to ensure reliability as defined by JMS. JOMS uses these properties to increase the delivery probability for the most important messages by modifying the DoDWAN's cache management policy in order to give them more chances to be opportunistically disseminated. Messages with a persistent delivery mode are favoured over non-persistent ones, and then the priority property is taken into account. All extra fields composing the JMS message's properties part are carried by the DoDWAN message's descriptor as they can act as a message selection criterion for DoDWAN while implementing the JMS selector mechanism.

2) Publish-subscribe model: this model is very close to the publish-subscribe API provided by DoDWAN. Usually, JMS providers implement this communication pattern using a server-based model: the publications and subscriptions to a given topic are managed by a central entity. However, the implementation of publish-subscribe communications using a server-less model is quite obvious and well suited: messages published to a given topic are disseminated over the network; thus, any application service interested in this topic is given the opportunity to receive its messages. DoDWAN supports content-based dissemination, rather than destinationbased routing of messages. Therefore, JOMS tags a message published to a given topic with the topic name, and then publishes it using DoDWAN; DoDWAN manages the message dissemination and the message delivery to all interested hosts. JOMS expresses applications' interest in receiving messages published to a given topic (topic subscribers) by adding the topic's name in their interest profile. Moreover, JMS selectors, allowing topic subscribers to filter the messages they receive, are added to the applications' interest profile; thus, the message filtering is processed at the communication middleware level.

The JOMS message shown in Fig. 2, for example, is pub-destination_id= "MailBox1@00b0d086bbf7" destination_type= "queue" Figure 4. Example of a queue manager's interest profile lished to the topic "ChatRoom1". This read-only text message, labeled "ff789", has the priority 4 and is to be delivered in persistent mode. It has been published at "Mon Oct 17 20:54:03 CET 2011" and will die at "Fri Nov 18 20:54:03 CET 2011". The message selector "language= English" is a set of keywords characterizing this message.

In D-MANETs, disconnections are the norm rather than the exception. As a result, the implementation of the JMS nondurable subscriptions concept, where messages are delivered only to active subscribers, is unsuitable and has no meaning for this environment. We deal with this problem by introducing a way to configure JOMS behaviour for non-durable subscriptions. By setting or unsetting some property, JOMS considers all non-durable subscriptions as durable ones, or refuses nondurable subscriptions and reports attempts to use them by throwing an exception.

3) Point-to-point model: this model is built around the concept of queue which has a central role in transmitting the messages from a queue sender to one and only one queue receiver. In fixed platforms, queues are maintained on a server which plays this central role in selecting the receiver of a message if there are multiple recipients associated with it. The main problem now is how to achieve this semantic of JMS queues in a D-MANET environment, where a server-based implementation is inappropriate, and where the consensus problem has not been however solved [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]. The approach to solve this problem is the so-called quasi-central queue approach: when an application creates a queue, its host will act as a queue manager (QM) for this queue. Thus, JOMS forwards to this QM all applications' requests to be receivers for this queue and all the messages sent to this queue. Then, it is up to the QM to decide to which receiver is to be handed the message, and to forward it using DoDWAN. Even if this QM is turned off or becomes unreachable, DoDWAN gives it a chance to receive later all the missing requests and messages by caching them on many other hosts. Thus, this queue acts as a central decision-making but not as a central store. This approach has the benefit that no consensus algorithm is required, thus making it more suitable for D-MANETs.

For the sake of illustration, a QM's profile is shown in Fig. 4. This profile matches all messages sent to the queue "MailBox1@00b0d086bbf7", which descriptors contain this property in the same way as the message shown in Fig. 2. Now, when an application wants to be a receiver for this queue, JOMS sends a request to the QM as shown in Fig. 5. The QM will use the reply_id property in order to address messages to that application, that has this property in its interest profile.

It is worth noting that each queue manager applies a selection policy in order to choose one receiver for each destination_id= "MailBox1@00b0d086bbf7" destination_type= "queue" jms_general= "queue_receiver" src= "86f8f700dad0" reply_id= "host_1@86f8f700dad0" language= "English" Figure 5. Example of a request to be a queue receiver Host 1 // Publish a message named "firstMSG" with payload "Hello" // and selector "language=English" to "ChatRoom1" % pub -t ChatRoom1 -id firstMSG -p Hello -ssl language=English The Message has been published

Host 2 // Subscribe to the topic "ChatRoom1" to receive messages // with properties "language=English or French" % sub -t ChatRoom1 -ssl language=English|French Waiting .... You have received a new message with the content: Hello Figure 6. Simple scenario message. For each message, the queue manager chooses a receiver that matches the message properties in a fair way. The JOMS's administrator can override this policy in order to have a more appropriate one regarding his requirements.

IV. IMPLEMENTATION DETAILS

The originality of our work lies in the fact that JOMS 1 and DoDWAN 2 have been fully implemented in Java and are now distributed under the terms of the GNU General Public License.

To date DoDWAN has been deployed and tested extensively using dozens of hand-held devices (such as laptops and smartphones) featuring Wi-Fi interfaces. It has also been used in a military tactical network involving VHF battlefield radios with built-in and proved robust and reliable in such harsh conditions [START_REF] Haillot | Disruption-tolerant content-driven information dissemination in partially connected military tactical radio networks[END_REF]. The scalability and stability of the algorithms DoDWAN relies on have been verified in simulations, using scenarios involving hundreds of mobile hosts [START_REF] Haillot | A protocol for content-based communication in disconnected mobile ad hoc networks[END_REF].

JOMS implements Sun Microsystems' Java Message Service API 1.1 specification on top of DoDWAN. An interactive command-line (console) is distributed with JOMS. The console is a tool that makes it easy and straightforward to test the performance of JOMS in real conditions. It provides the user with the most common JMS commands, i.e., destination-object management, publish/subscribe and send/receive commands. Using the console, JOMS has been tested using dozens of hand-held devices. For the sake of illustration, the following scenario demonstrates how to use the console. Assume that two hosts use JOMS. Fig. 6 shows commands executed on these two hosts along with the returned results.

JOMS is distributed with a number of example programs that demonstrate how to write simple applications. It is worth taking into consideration that nearly all JMS applications can be deployed perfectly over JOMS, even without changing their 1 http://www-valoria.univ-ubs.fr/CASA/JOMS 2 http://www-valoria.univ-ubs.fr/CASA/DoDWAN source code. This is an expected result of implementing a standard specification such as JMS. Application developers should take into consideration the characteristics of the networks supported by JOMS, where reliability, messages ordering and transmission delays cannot be guaranteed.

V. RELATED WORK

A number of JMS providers have been developed in the last few years in order to support JMS in MANETs.

EMMA (Epidemic Messaging Middleware for Ad hoc networks [START_REF] Musolesi | EMMA: Epidemic messaging middleware for ad hoc networks[END_REF]) is an adaptation of JMS that targets MANETs presenting connectivity disruptions. EMMA assumes the availability of a so-called synchronous protocol, which can be used to reach mobile hosts that belong to the same cloud -or islandas the sender. An asynchronous epidemic routing protocol is used to disseminate messages towards remote clouds. EMMA manages queues in a manner that is quite similar to that of JOMS: each queue is maintained by a single holder, which advertises this object periodically with a set lifetime, and which can accept subscriptions from other hosts. EMMA and JOMS however differ in the way they deal with topics. In EMMA topics are managed just like queues, with a single holder per topic. In JOMS topic subscriptions can be set locally on any host. Messages published in a topic propagate in the network by being stored, carried and forwarded by all hosts that have subscribed to this topic. Other hosts can additionally contribute to the dissemination of such messages, provided they have been configured so as to behave as altruistic carriers. Another difference between EMMA and JOMS is that in EMMA the gossiping mechanism between neighbor hosts is done in such a way that all messages are considered, so very large lists of message identifiers can be exchanged between neighbor hosts. In JOMS this gossiping is content-basedand thus more frugal-since neighbor hosts only exchange messages based on their respective interest profiles.

Extended JMS -or E-JMS-is another JMS provider, that uses an application-level multicast routing protocol that provides publish/subscribe semantics by mapping JMS topics to multicast addresses [START_REF] Vollset | Jms on mobile ad hoc networks[END_REF]. Since this protocol cannot disseminate messages beyond a single connected fragment of the network, E-JMS is hardly usable in D-MANETs. It could probably be adapted, though, using a disruption-tolerant version of the multicast routing protocol. Another problem is that the authors signal persistence as possible future work for developing consensus algorithms. We argue that such assumptions restrict MANET asynchronicity and limit the usability of E-JMS in D-MANETs.

EMMA and E-JMS both define their own communication protocols. In contrast JOMS presents a two-layer architecture: the upper layer is concerned with queue and topic management and utilisation, while the lower layer supports opportunistic communication. For the lower layer JOMS currently relies on DoDWAN, a middleware system we designed to support content-based information dissemination in D-MANETs [START_REF] Haillot | A protocol for content-based communication in disconnected mobile ad hoc networks[END_REF]. Yet JOMS could theoretically be implemented above any other communication system, provided this system can operate satisfactorily in D-MANETs.

Although many communication protocols for D-MANETs have been proposed during the last decade, most of these protocols have only been described in papers as abstract algorithms, and tested using pseudo-code in simulators. Only a handful of these protocols have been actually implemented in middleware systems (and can thus be used in real conditions), and only a couple of these systems are openly distributed and are thus accessible to developers.

DTN2 is the name for a reference implementation of protocols designed by the Delay-Tolerant Networking Research Group (DTNRG), a research group chartered as part of the Internet Research Task Force (IRTF). The DTN architecture operates as an overlay network, forwarding contiguous data blocks named bundles in a store and forward manner towards nodes identified by an EID (Endpoint Identifiers) [START_REF] Cerf | Delay-tolerant networking architecture[END_REF]. Several convergence layers are defined, so bundles can for example be transported between two nodes using TCP sessions, UDP datagrams, plain files, or any other convenient transport protocol. The DTN2 reference implementation is available and can easily be deployed on standard workstations or laptops. However, this system has not primarily been designed to target highly dynamic D-MANETs presenting short, unpredictable radio contacts between mobile hosts, so it is still unclear to us if it could run satisfactorily in such conditions.

Haggle is a content-centric architecture for opportunistic communication among mobile users (or devices) [START_REF] Nordström | A search-based network architecture for mobile devices[END_REF]. In fact Haggle and DoDWAN obviously share many common points. In both systems the information dissemination scheme is content-driven rather than destination-driven, and each mobile host can be characterised by an interest profile that determines the kinds of messages it is primarily interested in. A mobile host can additionally behave as an benevolent carrier for messages it is not interested in, although interesting messages are always favoured over less-interesting ones. DoDWAN and Haggle however differ significantly in the way interest profiles are dealt with. In Haggle the interest profile is disseminated network-wide, which may yield significant overheads in a large network involving hundreds or thousands of mobile devices. When the profile hence disseminated matches some data on another user's device, that device tries to push the matching data to the owner of the profile through a selected subset of its neighbors. In contrast DoDWAN does not attempt to disseminate profiles network-wide, but only up to a given horizon -defined as a maximum number of hops-around each host. Besides messages are not pushed by DoDWAN towards each potentially interested host, but a catalog of available messages (built according to their interest profiles) is proposed to all neighbors, and each neighbor can then request -or pullthe messages it is really interested in.

Another major difference between both systems is that Haggle was written in C and C++ (with language wrappers available for C# and Java) while DoDWAN was written directly in Java. DoDWAN is therefore highly portable, and readily interoperable with Java-based services such as JOMS.

VI. CONCLUSION

In this paper we have presented JOMS (Java Opportunistic Message Service), a JMS provider we designed and implemented specifically for disconnected mobile ad hoc networks (D-MANETs). With JOMS pre-existing and new JMS applications can be deployed easily over D-MANETs, so the developers can simply focus on writing standard JMS applications which will be simply deployed over D-MANETs using JOMS.

JOMS is distributed under the terms of the GNU General Public License. It is currently compliant with version 1.1 of the JMS specification, which dates back to 2002. The next version of the JMS specification, namely JMS 2.0, should be issued at the end of 2012. JOMS shall be modified or extended so as to comply with this new specification. In future work we plan to add a directory service to JOMS so clients will be able to automatically discover queues and topics. We also plan to leverage on JOMS in order to implement other distributed programming abstractions for D-MANETs, such as tuple spaces and future objects.

Figure 1 .

 1 Figure 1. Example of a disconnected mobile ad hoc network

Figure 2 .

 2 Figure 2. Example of a message descriptor

Figure 3 .

 3 Figure 3. Example of a selection pattern


Paul Lajoie-Mazenc
email: paul.lajoie-mazenc@irisa.fr

Système de réputation distribué préservant la vie privée

I. INTRODUCTION

Dans les grands réseaux, la grande majorité des interactions sont effectuées entre des inconnus, ce qui pose problème lorsque les membres du réseau placent dans ces interactions une certaine valeur, monétaire ou autre. Dans le cas du commerce électronique par exemple, un acheteur n'a aucune idée de l'état réel du bien vendu, qui peut être un produit d'occasion au lieu d'un produit neuf ou être plus abîmé qu'annoncé. Parallèlement, le vendeur ne peut pas être certain qu'il sera payé après avoir expédié le bien. De ce fait, l'acheteur et le vendeur aimeraient tous deux savoir avant de s'engager définitivement s'ils peuvent faire confiance à l'autre et si le risque qu'ils encourent est grand.

Pour répondre à ce problème, il est possible d'utiliser un système de réputation. Un système de réputation permet à ses utilisateurs d'estimer la réputation des autres utilisateurs afin de les aider à décider si oui ou non ils peuvent leur faire confiance et s'il est prudent de conclure une transaction. La réputation (ou score de réputation) d'un membre d'un réseau est généralement représentée par un objet mathématique (un nombre dans {-1, 0, 1} dans le cas du système de commerce électronique de eBay ou une fonction bayesienne dans [START_REF] Whitby | Filtering out unfair ratings in bayesian reputation systems[END_REF] par exemple) qui donne une représentation synthétique des différents avis ou témoignages des clients ayant déjà eu une interaction avec le fournisseur.

Resnick et al. [START_REF] Resnick | Reputation systems[END_REF] expliquent qu'un système de réputation doit au moins respecter les trois contraintes suivantes : 1) Les durées de vie des identifiants des utilisateurs et des objets doivent être assez longues pour leur permettre de se construire une réputation ;

2) Les informations sur les comportements des utilisateurs et les états des objets doivent pouvoir être collectées, agrégées et distribuées de façon à ce qu'elles soient visibles par tous les utilisateurs concernés ;

3) Ces informations doivent guider les actions futures des utilisateurs.

Dans ce travail, nous considérons le cas d'un réseau dans lequel des fournisseurs de services fournissent des services aux autres membres du réseaux que nous appelons les clients. Nous proposons un système de réputation permettant aux clients Paul Lajoie-Mazenc est actuellement en stage de Master 2 dans les équipes INRIA conjointes CIDre/CIDER encadré par E. Anceaume, G.Guette, N.Prigent et V. Viet Triem Tong.

de décider s'ils peuvent en toute confiance interagir avec un fournisseur de service. Ce système de réputation est distribué afin qu'il n'existe pas de point unique de défaillance sur lequel un attaquant pourrait focaliser ses efforts. De plus, pour des raisons de vie privée notre proposition garantit l'anonymat des clients : il est impossible de lier l'identité d'un agent avec les interactions qu'il a eu avec différents fournisseurs de service ni avec les différents témoignages qu'il a pu émettre.

Dans la Section II, nous précisons la terminologie employée et définissons formellement les termes utilisés. La Section III fait un état des lieux concernant les systèmes de réputation préservant la vie privée. La Section IV présente le fonctionnement du système de réputation proposé. La section V décrit le protocole suivi lorsqu'un client désire interagir avec un fournisseur de service. Nous montrons dans la Section VI quelles attaques sont atténuées grâce à l'utilisation de ce protocole. La Section VII explique en quoi notre système respecte la vie privée des clients. Finalement, nous concluons dans la Section VIII et proposons les principaux travaux futurs.

II. TERMINOLOGIE ET DÉFINITIONS

Les fonctionnalités d'un système de réputation peuvent être classées en trois catégories : la collecte de témoignages, le calcul du score de réputation, l'utilisation de ce score.

Un témoignage est un ensemble de données permettant d'évaluer une transaction. Il comporte l'opinion d'un client à propos d'un fournisseur de service, fondé sur ses interactions passées avec lui et l'opinion du fournisseur de service sur les transactions auxquelles il a participé avec ce même client.

Afin de garantir leur anonymat, les clients agiront sous le couvert de pseudonymes. Les témoignages seront stockés sur des agents bien identifiés fournissant un service de boîte aux lettres. Nous préciserons ces deux notions en Section IV.

Définition 1 (Contenu d'un témoignage). Afin d'obtenir un score de réputation pertinent, le témoignage d'un agent utilisant un pseudonyme p sur un fournisseur de service F S doit porter plusieurs informations :

-la note donnée par p sur le comportement de F S ; -la note donnée par F S sur le comportement de p ; -une estampille pour rendre compte de la date à laquelle la transaction a lieu ; -la valeur de la transaction pour accorder plus d'importance aux transactions importantes.

Les différents témoignages concernant un fournisseur de service F S sont agrégés par chaque nouveau client désirant se forger une opinion sur F S. Plus précisément, ces témoignages sont agrégés pour calculer un score de réputation dont la pertinence dépend à la fois de la quantité des témoignages collectés et de leur qualité. Un témoignage est dit de qualité si chacun des deux avis portés reflète les comportements des deux agents concernés.

Le comportement d'un agent (client ou fournisseur de service) se divise en deux parties : la conformité et l'honnêteté. Nous considérons ici que les attaquants sont des agents du système (clients, fournisseurs de service ou boîtes aux lettres). Un attaquant peut vouloir médire sur un autre agent en apportant des témoignages de mauvaise qualité, ou bien en sélectionnant ou augmentant le nombre des témoignages défavorables concernant cet autre agent. Ces attaques par médisance peuvent être amplifiées si l'attaquant peut se créer de nombreuses identitées. A l'inverse, l'attaquant peut aussi vouloir filtrer l'ensemble des témoignages le concernant pour augmenter la proportion de témoignages favorables et ainsi augmenter sa réputation. Ces attaques par filtrage peuvent être menées de deux manières différentes. L'attaquant peut effectuer une attaque dite de l'homme au milieu. Lorsqu'un client demande la réputation d'un fournisseur de service, l'attaquant intercepte la réponse de la boîte aux lettres et expurge les témoignages négatifs de la réponse avant de la faire suivre vers son destinataire naturel. L'impact est alors local, seul le client ayant demandé la réputation du fournisseur obtient une fausse information. L'attaquant peut aussi réussir à se faire désigner comme sa propre boîte aux lettres afin de ne stocker que les témoignages qui lui sont favorables. Dans ce cas, l'impact est global car les témoignages fournis par cette boîte aux lettres seront incomplets. Comme nous le verrons en Section V ces attaques sont mitigées par notre protocole. Par ailleurs, nous expliquerons pourquoi notre système de réputation protège la vie privée des clients.

Définition 4 (Protection de la vie privée des clients). La vie privée d'un client est préservée si les trois conditions suivantes sont satisfaites.

pseudonymat un client est connu uniquement via des pseudonymes ; -non-tracabilité des identités un client ne peut être relié à tout ou partie de ses pseudonymes ; -non-tracabilité des pseudonymes deux pseudonymes ne peuvent pas être reliés.

III. ETAT DE L'ART

Carrara et Hogben [START_REF] Carrara | Reputation-based systems : a security analysis[END_REF] présentent de nombreux exemples d'utilisations de systèmes de réputation, en commençant par des systèmes de commerce électronique tels que eBay [4], un site web d'enchères électronique, PGP (Pretty Good Privacy), un logiciel de signature cryptographique permettant l'établissement de chaînes de signature de confiance, ou encore le réseau pair à pair Gnutella. Dans eBay, un vendeur propose un objet à la vente. Les acheteurs potentiels vont enchérir afin de remporter cet objet. Après chaque transaction, le vendeur et l'acheteur peuvent se noter l'un l'autre avec un retour positif, négatif ou neutre (c'est-à-dire +1, -1 ou 0) tout en laissant des commentaires associés à cette transaction. Une fois ces témoignages (notes et commentaires) envoyés à un serveur eBay, le score de chaque utilisateur est calculé en sommant tous les retours. Dans ce premier exemple, le score de réputation est la somme des notes obtenues. Celle-ci a pour but d'aider les acheteurs potentiels à se faire une idée du comportement passé du vendeur. Dans ce système, les témoignages des acheteurs et des vendeurs sont accessibles (lisibles) par l'autre partie une fois déposés sur le serveur. Carrara et Hogben affirment qu'il existe une forte corrélation entre les retours des acheteurs et du vendeur : un acheteur sera tenté de ne pas déposer de note ou commentaire négatif afin ne pas se voir lui même attribuer une note ou un commentaire négatif (et réciproquement).

Ce premier système de réputation est un système centralisé puisque toutes les évaluations sont stockées par les serveurs de eBay. Ce système est intéressant car il propose un pseudonymat des différents clients du système : une personne utilise un pseudonyme pour s'authentifier sur le système, et il n'est pas possible de relier les différents pseudonymes d'une même personne. Néanmoins, ce système permet de tracer les actions effectuées par un même pseudonyme : une recherche simple permet de connaître l'historique des achats et des ventes avec leurs évaluations. Par ailleurs, la gestion de ce pseudonymat n'est pas automatique puisque l'obtention de n pseudonymes passe par la création de n comptes Ebay. Ces différents pseudonymes auront alors des scores de réputation différents (un score étant relié à un pseudonyme) ce qui fausse la portée d'un score de réputation. Il serait souhaitable que toutes les évaluations d'une même personne soient prises en compte dans le calcul du score de réputation de tous ses différents pseudonymes et que l'historique d'un pseudonyme soit difficile à connaître.

Pour répondre à ce problème, Androulaki et al. [START_REF] Androulaki | Reputation systems for anonymous networks[END_REF] ont proposé une architecture de commerce électronique assurant l'anonymat des clients et des vendeurs. Cette architecture est une fois encore centralisée car elle repose essentiellement sur un agent particulier : une banque connaissant l'identité de chacun des agents du système et leur attribuant des jetons. Ces jetons constituent la monnaie d'échange pour les transactions entre les vendeurs et les clients et représentent le score de réputation : plus un agent possède de jetons, meilleur est son score. Les agents (clients et vendeurs) discutent entre eux via des pseudonymes et n'utilisent leur identité réelle que pour communiquer avec la banque. Le contenu des transactions entre les agents et la banque étant protégé par des moyens cryptographiques (signature en aveugle et chiffrement asymétrique), l'anonymat des agents est garanti.

Nous proposons ici une architecture de commerce électronique permettant d'assurer l'anonymat des clients. Contrairement aux travaux présentés ci-dessus, notre architecture est entièrement distribuée. À notre connaissance, en dehors de cette proposition, il n'existe aucun système de réputation distribué préservant l'anonymat des agents.

IV. FONCTIONNEMENT DU SYSTÈME DE RÉPUTATION

A. Organisation du réseau

Le système de réputation que nous proposons repose sur un réseau pair à pair structuré en anneau [START_REF] Stoica | Chord : A scalable peer-to-peer lookup service for internet applications[END_REF] qui permet aux clients de trouver rapidement les fournisseurs de service et leurs boîtes aux lettres (BaL) ainsi que de communiquer avec eux. Afin de garantir la disponibilité des témoignages, des grappes de boîtes aux lettres sont utilisées comme proposé initialement par Ravoaja et al. [START_REF] Ravoaja | Storm : A secure overlay for p2p reputation management[END_REF].

La figure 1 présente l'exemple d'un tel réseau où AD est l'autorité de démarrage responsable de l'insertion des noeuds dans le réseau et F S 1 . . . F S 6 sont six fournisseurs de service. La figure présente aussi les boîtes aux lettres (BaL(F S 2 , j) pour j ∈ {1, 2, 3}) de F S 2 organisées en grappes. Comme expliqué à la Section II, notre système repose sur l'utilisation de boîtes aux lettres pour regrouper les témoignages concernant un même fournisseur de service. Les témoignages concernant le fournisseur de service F S sont stockés sur les boîtes aux lettres associées à F S.

Afin d'empêcher les attaques visant à augmenter artificiellement le nombre de témoignages (bourrage d'urnes), dès qu'une boîte aux lettres reçoit un nouveau témoignage concernant les deux mêmes participants (pseudonyme et fournisseur de service), l'ancien témoignage est remplacé. Ainsi, à tout instant, et pour chaque paire d'agents ayant interagi, une boîte aux lettres ne contient donc qu'une seule paire de témoignages entre ces agents.

B. Calcul des scores de réputation

Nous utilisons la méthode bayésienne décrite par Whitby et al. [START_REF] Whitby | Filtering out unfair ratings in bayesian reputation systems[END_REF] reposant sur le système de beta-réputation proposé par Ismail et Jøsang [START_REF] Jøsang | The beta reputation system[END_REF] pour calculer la réputation d'un fournisseur. Cette méthode suppose que le comportement d'un agent suit une loi de probabilité bêta dont on ne connaît pas les paramètres. Sa fonction de calcul de score présente deux propriétés intéressantes. La première autorise des retours non-binaires alors que la seconde permet de « vieillir » les témoignages, c'est-à-dire de donner plus d'importance aux témoignages récents. Ces propriétés sont atteintes de la manière suivante : un témoignage n'est plus un retour positif ou négatif, mais est un vecteur :

ρ = ρ + ρ -, ρ + , ρ -∈ [0, 1] | ρ + + ρ -= 1,
où ρ + représente la partie positive du témoignage et ρ -sa partie négative. Le vieillissement d'un témoignage se fait en introduisant une « fonction de vieillissement » f (t). Si t ρ représente le temps écoulé depuis l'émission du témoignage ρ, positif -ou nul si le témoignage vient d'être émis -, le nouveau témoignage sera :

ρ t = ρ × f (t ρ ).
Enfin, lorsqu'un client A veut utiliser les services du réseau, il doit initier une communication avec l'autorité de démarrage et payer le coût d'inscription, que celui-ci soit monétaire ou calculatoire. L'autorité de démarrage fournit alors n pseudonymes permettant à A de rester anonyme et que nous notons p(A, 1), . . . , p(A, n). Enfin, A prend place dans le réseau, sous la forme des n pseudonymes. Si jamais un agent désire obtenir plus de pseudonymes, il lui suffit de contacter à nouveau l'autorité de démarrage.

V. PROTOCOLE D'INTERACTION

Dans cette section, nous détaillons le protocole permettant à un agent A possédant les pseudonymes p(A, i), i ∈ I d'interagir avec un fournisseur de service F S, associé aux boîtes aux lettres BaL(F S, j) pour j ∈ J (cf. figure 2). Nous supposons que les boîtes aux lettres sont honnêtes.

Le protocole se découpe en trois parties. La première permet à A d'obtenir le score de réputation de F S. Notons que le protocole s'arrête dès la fin de la première partie si A n'est pas satisfait de la valeur du score de réputation de F S. La seconde partie du protocole établit la communication permettant la transaction entre A et F S. Enfin, la troisième partie décrit comment A et F S déposent leur témoignage sur les boîtes aux lettres. service F S avec lesquelles il communiquera. Il réduit ainsi le nombre de messages envoyés en ne choisissant qu'une fraction des boîtes aux lettres disponibles. Si les boîtes aux lettres choisies se révèlent indisponibles alors l'agent peut en utiliser d'autres. Notons que dans la suite, on supposera qu'il existe parmi les m boites aux lettres un quorum de boîtes aux lettres disponible jusqu'à la fin de la transaction. Une fois ce choix effectué, A établit un tunnel TLS [START_REF] Dierks | The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246[END_REF] avec chacune des boîtes aux lettres qu'il a choisi. Ces tunnels garantissent l'authentifi-cation des boîtes aux lettres, la confidentialité et l'intégrité des données échangées. Une fois ces tunnels disponibles, le client demande à chacune des boîtes aux lettres les témoignages correspondants au fournisseur de service F S. Les boites aux lettres fournissent tous les témoignages, dans la limite d'un par pseudonyme (le plus frais s'il y en avait plusieurs). Notons que A n'a besoin de connaître ni le pseudonyme ayant déposé le témoignage, ni l'identifiant de la transaction, ces informations sont donc purgées des témoignages par les boîtes aux lettres.

Une fois les témoignages expurgés récupérés, A agglomère les différentes notes et calcule le score de réputation de F S selon la méthode de calcul décrite précédemment. A choisit ensuite s'il désire ou non continuer l'interaction.

Partie 2 : Interaction entre F S et p(A, i). Si A choisit d'interagir avec F S, il établit un tunnel TLS avec lui pour bénéficier comme précédemment d'un canal de communication sécurisé. Il l'informe ensuite des m boîtes aux lettres qu'il a choisi en lui envoyant J m pour que les deux participants puissent communiquer avec ces mêmes boîtes aux lettres. p(A, i) choisit un identifiant de transaction τ -par exemple en calculant une empreinte de (p||F S||timestamp) 1 où timestamp représente le moment auquel cet échange a lieu-et le transmet à F S qui lui renvoie le même identifiant, signé avec sa clé privée. p(A, i) informe ensuite les m boîtes aux lettres de l'interaction en leur envoyant cette signature. F S fait de même de son côté. Les boîtes aux lettres en accusent réception dès qu'elles ont reçu les deux exemplaires. Cela permet d'assurer aux deux participants que l'autre s'est lui aussi engagé à poursuivre l'interaction.

S'ensuit la transaction entre le client sous le pseudonyme p(A, i), et le fournisseur de service F S. Nous ne faisons aucune hypothèse sur la nature ou le déroulement de cette transaction.

Partie 3 : dépots des témoignages de F S et p(A, i) sur les boîtes aux lettres de J m Une fois la transaction terminée, les participants déposent leurs témoignages sur toutes les boîtes aux lettres de J m en utilisant les tunnels de communication crées en première partie du protocole. Les boîtes aux lettres les informent quand les deux témoignages sont récupérés. Si après un certain temps T , les boîtes aux lettres n'ont reçu qu'un seul des deux témoignages, elles considèrent le témoignage manquant comme étant neutre vis à vis de la transaction. Si le témoignage manquant est celui du client alors elles le considèrent comme un avis positif à propos de F S. Si le témoignage manquant est celui de F S alors elle le considère comme un avis négatif à propos de la transaction. Après ce temps T les témoignages sont rendus disponibles à tous.

VI. ATTAQUES ATTÉNUÉES

Avant toute interaction avec la boîte aux lettres (resp. le fournisseur de service), le client établit un tunnel TLS qui garantit l'authentification de la boîte aux lettres (resp. celle du fournisseur de service) et permet d'effectuer des échanges confidentiels et intègres. Ainsi, toute usurpation d'identité ou tentative de rejeu de messages par un attaquant potentiel est empêchée.

Une boîte aux lettres peut envoyer des témoignages obsolètes ou fallacieux. L'utilisation de grappes de boîtes aux lettres permet d'atténuer l'effet de ce type attaque. Intuitivement, si le nombre de boîtes aux lettres sélectionnées est suffisamment grand, le client peut détecter avec une forte probabilité les boîtes aux lettres malveillantes. Nous projetons de prouver cette propriété dans un travail futur.

Un des deux participants peut également essayer de réfuter une transaction afin d'augmenter son score ou de diminuer 1. || est l'opérateur de concaténation. celui de l'autre. Si p(A, i) interagit avec un fournisseur F S bienveillant mais ne veut pas augmenter la réputation de F S, il peut se déconnecter volontairement du réseau une fois la transaction effectuée mais avant d'avoir déposé son témoignage. La boîte aux lettres aura reçu son engagement sur la transaction -{τ } Kpriv(F S) -et, après un certain temps T passé à l'attendre, la boîte aux lettres attribue d'ellemême un témoignage positif pour F S. Un client est ainsi incité à témoigner lorsqu'une transaction s'est mal déroulée. De même, si F S se déconnecte après s'être mal comporté sans émettre de témoignage, la boîte aux lettres attribue un témoignage négatif sur la transaction, incitant ainsi F S à témoigner. L'avantage de cette méthode est qu'elle pallie toutes les tentatives de réfutation. Par contre, les déconnexions (involontaires) du réseau sont également détectées comme des tentatives de réfutation.

VII. RESPECT DE LA VIE PRIVÉE

D'après la définition 4, la vie privée d'un client est préservée si trois conditions sont respectées : le pseudonymat, la nontraçabilité des identités et la non-traçabilité des pseudonymes.

Un client utilise son identité réelle uniquement lorsqu'il rejoint le réseau : en effet, il n'a pas encore de pseudonymes et communique avec l'autorité de démarrage afin d'en obtenir. Afin d'assurer l'authentification de cette autorité et une confidentialité des messages échangés, le client et l'autorité de démarrage peuvent également utiliser un tunnel TLS pour toutes leurs communications. Ainsi, seule l'autorité connaît les identités des agents. Nous supposons que cette entité est suffisamment protégée pour qu'on puisse formuler l'hypothèse de fiabilité de l'autorité de démarrage.

Hypothèse (Fiabilité de l'autorité de démarrage). Nous supposons que l'autorité de démarrage est fiable et que les liens identité-pseudonymes qu'elle stocke sont confidentiels.

Cette même hypothèse nous permet de garantir que seule l'autorité de démarrage est à même de faire un lien entre une identité et des pseudonymes puisque pendant chaque interaction avec un fournisseur, un client utilise uniquement ses pseudonymes lors de ses communications avec un fournisseur de service ou une boîte aux lettres.

La propriété la plus intéressante est la non-traçabilité des pseudonymes. En effet, celle-ci garantit que l'on ne peut pas savoir si deux pseudonymes différents appartiennent à la même identité ou pas. Il existe de nombreuses attaques par inférence, où l'on s'intéresse à des comportements révélateurs. Un exemple significatif est celui présenté par Barbaro et Zeller [START_REF] Barbaro | A face is exposed for AOL searcher no. 4417749[END_REF] : en 2006, après le dévoilement par AOL de données de recherches des utilisateurs sur son moteur de recherche, certaines personnes furent retrouvées. Notamment, Thelma Arnold, grâce à quelques unes de ses recherches révélatrices : recherches généalogiques, de commerces de proximité, etc.

Nous supposons que de telles attaques peuvent être menées dans notre système de réputation, en comparant les différents éléments des témoignages : date et heure des transactions, valeur des transactions, portée des notes. Cependant, seules les boîtes aux lettres et les fournisseurs de service connaissent une partie de l'historique des pseudonymes. Une boîte aux lettres dispose de différents témoignages portés par un même pseudonyme sur le fournisseur de service avec lesquels le pseudonyme a interagit. Un fournisseur peut établir qu'un même pseudonyme a interagit plusieurs fois avec lui. Par contre, lorsqu'un client demande les témoignages concernant un fournisseur de service, il aura seulement les notes des différents client puisque les pseudonymes sont expurgés des témoignages rendus publics. Afin de pouvoir mener efficacement de telles attaques, il faut qu'un attaquant connaisse les historiques de nombreux fournisseurs -soit en formant une collusion à grande échelle, soit en inondant le réseau de boîtes aux lettres ou de fournisseurs de service sous son contrôleafin de pouvoir comparer les différents paramètres. Pour l'instant nous formulons l'hypothèse que les conditions nécessaires à la mise en place d'une attaque par inférence visant à relier plusieurs pseudonymes rendent ces types d'attaques presque impossibles. Dans la suite de ce travail nous affinerons cette hypothèse en calculant les paramètres nécessaires permettant de résister à une telle attaque.

VIII. CONCLUSION ET TRAVAIL FUTUR

Nous avons proposé dans cet article un système de réputation distribué respectant la vie privée des utilisateurs et robuste aux attaques. Sous l'hypothèse que l'autorité de démarrage n'est pas corrompue, notre système de réputation garantit le respect de la vie privée des clients, des applications construites au-dessus de notre système, en combinant à la fois des outils cryptographiques standards et la distribution des traitements sur un ensemble d'agents, appelés boites aux lettres.

Pour poursuivre ce travail, nous pensons tout d'abord formaliser la preuve que le protocole garantit l'anonymat des clients de l'architecture. Nous nous attacherons ensuite à montrer formellement que l'architecture proposée est résistante à d'autres attaques. Par exemple, nous montrerons qu'un client peut toujours obtenir un témoignage précis dès que le nombre de témoignages stockés est assez grand et que les témoignages de mauvaise qualité restent limités. Nous aimerions aussi mettre en évidence la possibilité d'obtenir un score de réputation pertinent tant que la proportion de boîtes aux lettres malicieuses est inférieure à une certaine borne.

RÉFÉRENCES

FIGURE 1 :

 1 FIGURE 1: Forme générale du réseau : structure en anneau des agents et grappes de boîtes aux lettres

Partie 1 :

 1 Calcul de la réputation de F S par un agent A. L'agent A utilisant le pseudonyme p(A, i) choisit aléatoirement un ensemble J m de m boîtes aux lettres du fournisseur de p(A, i) BaL(F S, j) F S Choix de J m ⊂ J de cardinal m Initialisation tunnel TLS témoignages + arbre ? témoignages + arbre calcul du score Calcul de la réputation de F S Calcul de la réputation de F S ∀j ∈ Jm Initialisation tunnel TLS J m Choix de τ τ {τ } Kpriv(F S) ∀j ∈ J m , {τ } Kpriv(F S) ∀j ∈ J m , {τ } Kpriv(F S) OK OK Transaction Interaction p(A, i) -F S Interaction p(A, i) -Dépôt des témoignages ∀j ∈ Jm

FIGURE 2 :

 2 FIGURE 2: Interaction entre un utilisateur A sous le pseudonyme p(A, i), un fournisseur de service F S et ses boîtes aux lettres BaL(F S, j)


Steve Dodier-Lazaro

Quentin Avril
email: quentin.avril@gmail.com

Valérie Gouranton
email: valerie.gouranton@irisa.fr

SODA: A Scalability-Oriented Distributed & Anticipative Model for Collision Detection in Physically-based Simulations

Keywords: collision detection, physically-based simulation, distributed systems, scalability, optimistic computing

In this paper, we propose a distributed and anticipative model for collision detection and propose a lead for distributed collision handling, two key components of physically-based simulations of virtual environments. This model is designed to improve the scalability of interactive deterministic simulations on distributed systems such as PC clusters. Our main contribution consists of loosening synchronism constraints in the collision detection and response pipeline to allow the simulation to run in a decentralized, distributed fashion. To do so, we setup a spatial subdivision grid, and assign a subset of the simulation space to each processor, made of contiguous cells from this grid. These processors synchronize only with their direct neighbors in the grid, and only when an object moves from one's area to another. We rely on the rarity of such synchronizations to allow anticipative computing that will also work towards improving scalability. When synchronizations occur, we propose an arrangement of collision checks and rollback algorithms that help reduce the processing cost of synchronized areas' bodies. We show potential for distributed load balancing strategies based on the exchange of grid cells, and explain how anticipative computing may, in cases of short computational peaks, improve user experience by avoiding frame-rate drop-downs.

INTRODUCTION

Virtual reality [VR] researchers and industry users have growing needs for the physically realistic simulation of large virtual environments. These include detecting collision between simulated bodies. Collision detection [CD] consists of finding if, where and when several objects may collide in a 3D virtual environment [START_REF] Ericson | Real-time Collision Detection[END_REF]. It is a prerequisite of collision response [CR] that will provide the proper forces or impulses to be applied on the bodies by means of Constraint Solving [CS].

Considerable research effort has been put in collision handling in general, and many algorithms and frameworks exist for sequential and parallel collision detection and constraint solving. Current parallel collision detection or handling systems are based on the traversal and update of tree structures [START_REF] Tang | Multi-core collision detection between deformable models[END_REF][START_REF] Thomaszewski | Parallel techniques for physically based simulation on multi-core processor architectures[END_REF], the use of GPUs for massively parallel processing [START_REF] Kim | HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs[END_REF][START_REF] Pabst | Fast and scalable cpu/gpu collision detection for rigid and deformable surfaces[END_REF], or fine-grained scheduling strategies [START_REF] Hermann | Interactive physical simulation on multicore architectures[END_REF].

Coupled with powerful computers, these algorithms already allow real-time large-scale simulation of increasingly complex bodies. Besides, theoretical grounds exist on the distribution of a virtual environment simulation [START_REF] Fujimoto | Parallel and distributed simulation[END_REF], and we are now in a time where PC clusters are affordable for most research centers and large companies, and are already used for animation and rendering in VR systems [START_REF] Raffin | Pc clusters for virtual reality[END_REF].

Nevertheless, little work has been done towards collision handling on distributed systems. Current research addresses collision detection between bodies in high-latency networks [START_REF] Chen | A protocol for distributed collision detection[END_REF], rather than the fully distributed scheduling of a collision pipeline. [START_REF] Morgan | Scalable collision detection for massively multiplayer online games[END_REF] distributed collision handling in the past, but also with a focus on avatars controlled by multiple users rather than handling collisions distributedly without duplicates. We argue this would benefit the performance of applications like distributed simulation of virtual cities, or massively multiplayer online games with more persistent and realistic physics.

Contributions: We present SODA, a model for collision detection on distributed systems with anticipative computation. SODA aims for interactive physically-based simulation on PC clusters. We propose loosely-synchronized and anticipative simulation by dividing space into areas called worlds. Each world is sequentially simulated on a stand-alone core (or multi-core node). We allow anticipative computation (i.e. simulating steps ahead of the current clock of other worlds) when no data dependency prevents it. We outline methods for synchronizing collision detection and constraint solving when a dependency exists, and we propose rollback algorithms that reduce the cost of synchronizing a simulation step between worlds when that step had been anticipatively computed. Finally, we explain how anticipation can help improve user experience by avoiding sharp decreases of frame-rate when computationally expensive collisions occur.

Organization: In Section 2, we review some parallel and distributed CD and particle simulation algorithms, and explain our positioning. In Section 3, we describe our distributed and anticipative virtual environment simulation model. Section 4 presents observations made on a case study of collision detection. They may guide implementation choices for spatial subdivision granularity and distributed CS design. They also outline the benefits of anticipation. Finally, we conclude and propose leads for future research in Section 5.

RELATED WORK

In this section, we present state-of-the-art CPU-based parallel collision handling systems. We do not investigate GPUs, used as massively parallel side processors in both CD and CS, as they are not relevant to our intent in SODA: assessing the feasibility of distributed rather than centralized parallel collision detection.

We also outline the difference between existing distributed CD methods and SODA, and introduce distributed particle simulation algorithms. Finally, we enumate the assumptions our model is based on.

Parallel Collision Handling

Parallel and distributed systems are nowadays targets of choice for virtual reality applications with significant computing needs, and there is flourishing literature on parallel collision handling. Yet, no distributed approach has been proposed for consistent, deterministic CD. Many researchers have instead sought to take better advantage of particular architectures such as combinations of CPUs and GPUs [START_REF] Hermann | Multi-GPU and multi-CPU parallelization for interactive physics simulations[END_REF][START_REF] Kim | HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs[END_REF][START_REF] Pabst | Fast and scalable cpu/gpu collision detection for rigid and deformable surfaces[END_REF]. The papers we present focus on lowering synchronization and load balancing costs in a multi-CPU context, and are the closest in philosophy with SODA. [START_REF] Hermann | Interactive physical simulation on multicore architectures[END_REF] explored the construction of a task dependency graph for the collision handling pipeline based on previous collisions, which allowed them to schedule tasks among available processors and eliminated the need for synchronization between each pipeline stage. The graph is replayed among several time frames to limit the overhead of load balancing. They reached close to optimal scalability for particle simulation, but not for simulations containing heterogeneous complex objects. [START_REF] Tang | Multi-core collision detection between deformable models[END_REF] proposed incremental parallel BVTT traversal, measuring the workload per BVTT branch to distribute the load between processors in collision detection. They decompose BVTT traversal as a pipeline mostly made of parallel steps, albeit with synchronization between each stage. They achieved a speedup up to 6 fold on an eight core CPU, after which performance stopped increasing linearly. Besides, tree-based spatial subdivisions need to be regularly updated, which is difficult in a distributed way.

Finally, [START_REF] Kim | Pccd: Parallel continuous collision detection[END_REF] reached 7.3 speedup on 8 CPUs over a single core, with their PCCD algorithm which is based on dynamic task decomposition and assignment. They reach such scalability by getting rid of as many data dependencies and synchronizations as possible in their pipeline. They presented the best scalability in the CD literature. For comparison, Hermann et al.'s physics simulation pipeline has a slightly lower scalability when simulating heterogeneous rigid bodies on sixteen cores.

Distributed Collision Detection

Typical peer-to-peer applications include multiplayer games, featuring a virtual environment in which avatars may collide. These avatars are controlled on different computers, which need to exchange information in order to process collisions and keep the state of the environment consistent. Deterministic CD is not realistic in this high-latency network context because packets may be lost or take hundreds of milliseconds to reach all hosts.

Various strategies emerged for CD with remote bodies, usually variants of Dead Reckoning [DR] which predicts the motion of remote avatars until they update their real position [START_REF] Fujimoto | Parallel and distributed simulation[END_REF]. For instance, Motion-Lock (Chen and Verbrugge, 2010) predicts collisions and starts agreement with remote hosts before the collisions occur, rather than once remote hosts communicated updated body positions.

In SODA however, it is the simulation that is distributed on several cores and not the sources of user interaction. We are interested in precise, deterministic CD. SODA could be used for complex physically-realistic virtual city simulations with one or several agents. In contrast, previous work focuses on virtual worlds where each node can process all physics constraints on its own.

Distributed Particle Simulation

Particle simulation researchers have common research questions with the collision detection community: they need to detect and process collisions between thousands of objects in a simulated environment. However, particles are typically represented as points or spheres, rather than thousands-of-polygons bodies. This allows the use of much simpler CD algorithms, and significantly simpler load balancing metrics. Therefore, particle simulation systems are usually run on clusters aggregating hundreds of cores. [START_REF] Li | Speculative and distributed simulation of manyparticle collision systems[END_REF] proposed an event-driven particle collision system with a priority queue of events to be processed for each particle. Speculative computations are performed on particles waiting for a prior event to be processed. These speculative computations are kept if the states of particles they are performed on have not been affected by prior events in the queue. They also proposed a dynamic adjustment of the amount of speculative computation to perform depending on how many of these are invalidated, in order to save storage and computation costs. [START_REF] Miller | Event-driven molecular dynamics in parallel[END_REF] proposed a spatial subdivision based on a uniform grid, where each CPU manages an area of contiguous, square-shaped cells to best exploit spatial coherence. They add border traversal events to their system to know when synchronization between two areas is necessary. Finally, they perform dynamic load balancing by splitting an overloaded area, merging two underloaded areas, and assigning one of the splitted sub-areas to the orphan core.

Work Hypotheses

Scalability is limited in a parallel computing system by the lack of task decomposition that prevents from using all available nodes, or by recurrent synchronizations. The former problem may be solved by decompositing tasks further, and scheduling them according to their dependencies. This has been largely done in CD and CR.

The latter may be managed with optimistic computing: if the slowest node's tasks cannot be split any further, other nodes will anticipate their workload to obtain speed improvements onto next computation steps. However this will bring benefits only if the slowest node is not always the same.

We argue that this condition may be verified in a range of VR applications (e.g. those with constantly moving bodies such as factory automated assembly lines, or virtual cities with moving crowds). A distributed (inherently anticipative) system may improve performance for such applications.

Asanovic et al. [START_REF] Asanovic | The landscape of parallel computing research: A view from berkeley[END_REF] advise researchers to design systems that scale well on any number of cores. In practice, simulations imply temporal coherence and hence synchronization at some point, which means they cannot scale infinitely. Likewise, benefits from optimistic computing are theoretically bounded [START_REF] Miller | Event-driven molecular dynamics in parallel[END_REF], on top of additional memory cost [START_REF] Fujimoto | Parallel and distributed simulation[END_REF].

Knowing this, improving the performance of some tasks of the collision handling pipeline (such as using GPUs to dramatically improve CD or CS) will bring benefits, but pushing further scalability limits of the global pipeline by removing unnecessary synchronizations may bring other, complementary benefits.

THE SODA MODEL

In this section, we describe how space is distributed and synchronization occurs in SODA. We also present our approaches to I/O management, and a sketch of distributed load balancing algorithm.

We propose to loosen synchronization constraints between the main components of collision handling pipelines, by dividing the simulation space and allowing the computation of different simulation steps in either of these areas. In contrast, current frameworks never start a simulation step's CD before CS and time integration have been entirely performed for the previous step.

In SODA, each node processes a subset (referred to as a world) of the simulation space, defined by adjacent cells in a spatial subdivision uniform 3D grid (named territory). Each world communicates exclusively with those managing areas adjacent to his own (called neighbors, and the planes between distinct areas are called borders).

Worlds synchronize with neighbors when a body overlap the border between their territories. Only the CS stage on the simulation island of the bordercrossing body needs to be performed concurrently by worlds. However, they also exchange data during CD to identify common simulation islands.

Each world saves the results of simulation steps into a buffer. A process then reads entries corresponding to the slowest world's clock, to allow output to users. User input can be managed by modifying the world containing bodies with which the user interacts. Rollback algorithms can be used to integrate user actions in the world's buffer entries.

In this paper, we do not investigate issues linked to user interaction or to predictability of body motion which may impact offline computation of data structures or scheduling strategies. In SODA, initial territories are modified with time by load balancing.

Territories and Borders

Territory Definition

We define spatial subdivision in the form of a uniform 3D grid, which has the following advantages in a distributed context:

• cells can be described with just coordinates and a world identifier, allozing compact exchange of cell data between worlds

• storing the topology of the subdivision is very cost-efficient (no need to store shapes)

• unlike tree-like subdivisions, they do not require to update their shape on body motion (but may have to on body deformation)

Worlds manage a territory made of adjacent grid cells so as to best exploit temporal coherence [START_REF] Lin | Collision detection between geometric models: a survey[END_REF]. Hence, bodies switching between cells will most often remain in the same world. This avoids creating data dependencies between worlds when a body moves from one to another.

Another advantage of this territory definition is that worlds need to hold in memory just the grid of their territory and direct surroundings (to keep track of which cells belong to which neighbors).

The problem of optimal cell size is well-known and does not have an ideal solution (Le [START_REF] Grand | Broad-phase collision detection with cuda[END_REF]. The size of grid cells depends in SODA upon a single criterion: cells should be strictly larger than the biggest simulated body in order to ensure that collisions only occur between bodies from adjacent cells. The use of hierarchical grids is left for further research, to support bodies with heterogeneous dimensions or deformable shapes.

Border Traversal Detection

Collisions may occur between bodies from different worlds, as illustrated in Figure 1. If they are left unmanaged, then some contact responses will not be applied and the simulation will no longer be deterministic. To allow anticipation within a world, we need to be able to detect which bodies overlap a border.

To do so, borders between two territories are represented by static physics bodies and SODA's detection collision algorithm is used to discover border traversals, although no collision response is applied with border bodies. The synchronization mechanism is explained in Section 3.2.2.

Cost of the Detection: Assuming territories are made of a single cell, every body will have to be tested for collision with the 6 borders of its containing cell. In the worst case, all bodies will be next to their cell's corner and collide with 3 borders. Hence they may overlap with up to 7 distinct worlds, which brings up to 9 more borders with which they may be colliding. The sum of additional collision checks to perform, fifteen per body, remains of linear complexity.

In practice, territories are larger and fewer cells contain borders. Besides, overlapping tests with an axis-aligned plane are often faster than collision checks between two complex bodies, further limiting the cost of border detection.

Autonomous Worlds

Worlds and Transform Buffers

Worlds in SODA are physics engines that run sequentially on a node. They are responsible for detecting and processing collisions in a subset of the simulation space. Each engine uses its own local clock and performs simulation steps independently from others. The results of a simulation step are made available to others as a time-stamped list of transforms (i.e. motions, rotations and velocities of bodies) for each body simulated in the world's territory. The lists are saved to a circular buffer, which can be read to retrieve the positions of bodies at each step.

The use of a circular transform buffer offers a trade-off between the desired robustness of the application and the memory size needed to store the buffers. A large buffer enables the precomputation of several seconds of simulations, which can help absorb the performance impact of a computational peak due to many simultaneous collisions. Yet, the size of the

3D Engine

Figure 2: Global architecture of SODA. Worlds i, j and k's buffers are read by the interface, which is used by the 3D engine's process to update positions.

buffer must be bounded depending on the amount of memory available on the system where SODA runs. Besides, the more important the anticipation is, the more likely it is to be invalidated by further synchronizations, up to a point where anticipation becomes pointless [START_REF] Miller | Event-driven molecular dynamics in parallel[END_REF].

A buffer interface is in charge of reading and deleting buffer entries, at the same timestamp for all worlds. It updates body representations within a 3D engine, to allow output to users, and also to make sure no entry within a buffer is deleted before all worlds have simulated the corresponding timestamp (since it may be modified by unexpected synchronization).

Synchronization With Neighbors

Determinism is guaranteed in traditional parallel collision handling frameworks by not performing anticipation: all constraints from a simulation step are solved before the next step starts. Instead, we want to guarantee it by taking into account data dependencies between worlds at different times.

Consequently, any body that overlaps a border between two worlds will cause these worlds to synchronize their physics pipeline. When two worlds are synchronized, they will exchange information about border-crossing bodies, and make sure to take into account collisions between foreign border-crossing bodies and their own ones. Simulation islands are then computed from collision information.

If a body overlaps a border and exists in two islands on different worlds, the islands will be merged before computing a response in parallel. Otherwise, islands that exist within a single world (a fortiori those that don't contain bodies on border cell) are solved locally on a world's node.

Algorithm 1 presents our new collision handling pipeline. First, CD is performed between local bodies, then with the world's borders. In case of synchronization (border traversal or external query), worlds will exchange their lists of crossing bodies, and detect collisions between these new bodies and theirs.

Simulation islands can then be computed and merged with foreign ones when they contain a foreign body. The local ones may be solved locally and the mixed ones in parallel between involved worlds.

Nothing prevents from starting local CS before foreign collisions are detected. Synchronization messages can be read asynchronously by their recipient, and a world ahead of another one for any stage of the pipeline could use the rollback algorithms presented after to avoid processor idling caused by synchronization.

Modifying Anticipated Entries

A direct consequence of synchronization between two worlds w 1 and w 2 is that the world that is ahead of the other has to modify some of its anticipated computations: they were performed ignoring a data dependency from the slower world and some collisions need to be integrated.

In order to limit the incurred losses, we propose a CD rollback based on the spatial subdivision grid used for territories. We integrate changes caused by the synchronization into previously computed buffer entries, using algorithm 2: Rollback and Propagate.

The worst use case of SODA, performance wise, is a simulation where all bodies are constantly interconnected. This will force constant synchronization between all worlds and prohibit anticipation. We yet have to evaluate the overhead caused by the use of SODA in such a setup, but SODA is likely to be outperformed by finer-grained parallel solutions for this kind of simulations. We expect to be able to improve performance in the future by finding other ways of performing anticipative computations.

The rollback algorithm will improve performance over direct invalidation of a full entry whenever not a territory contains several simulation islands. Indeed, we already use a spatial subdivision broad-phase to allow cheap border traversal detection. The cost of this broad-phase lies in the actual overlap tests between bodies and not in the browsing of the subdivision cells. Hence, the rollback algorithm will not be significantly costlier than a broad-phase with ordered cell browsing, and will be more efficient as soon as some bodies are not in a chain of contacts with the ones that cross a border. Figure 3 shows a fictive example of rollback applied to a buffer entry. Only the bodies in the darker cells will have their transforms re- computed, and because they do not collide with bodies from surrounding cells, the rest of the entry will be preserved.

Rollback may also be developed for CS, by saving result matrices of commonly used iterative solvers, and by later modifying them by adding extra constraints. Because the matrix will be close to convergence for almost all values (except for the non-null lines and rows of the new constraints), it may converge with less iterations than from starting over. This technique is already used to decompose systems and solve them in parallel on GPUs [START_REF] Tonge | Mass splitting for jitter-free parallel rigid body simulation[END_REF].

However, it provides benefits only from direct rollback of the first step where synchronization occured. Typically, many values will be (slightly) af- CS part of the pipeline benefits from our border detection, in case of mistake during anticipated computations. Figure 4 shows that SODA will never detect false collisions when a foreign body's motion is not known for a given simulation step. Instead, it will ignore the (potential) foreign body until the rollback algorithm is called. This means that no false constraint has been injected in the constraint equation system (as would happen with estimations of remote body position), and this is primordial to allowing the reuse of past computed matrices. In SODA, false positives may only occur indirectly, when a rollback removes a border traversal that also caused a collision.

Input/Output and Simulation Setup

Rendering

Interactive applications need real-time rendering, regardless of simulation progress. In SODA, a 3D engine stores its own clock and 3D representation of bodies, and updates them before each rendering pass with a buffer interface (as illustrated by Figure 2). This interface is queried with the clock value of the step to render, and then asks all worlds if they have a buffer entry for this value. If not, the interface uses the lowest clock value available among all worlds. Then, it actually queries entries and updates the 3D engine's body information accordingly. It also returns the engine the clock value that was used, so that rendering occurs in real time when worlds cope with the workload, and in slow motion otherwise.

The cost of reading transforms is linear in number of bodies and no worlds are created or removed during the simulation. On large clusters where buffer reading may not scale, it is thus possible to distribute the querying and reading of entries onto several cores that will concurrently access the 3D engine's internal memory. They can negotiate the clock value to use and the worlds each one of them should monitor.

p i 39% p j 54% p k 64% p h 82% p l 73% p m 73% p i 24% p j 32% p k 81% p h 92% p l 89% p m 73% p i 54% pj 54% pk 64% p h 69% p l 73% p m 73%

User input

Users may interact with an application by adding, removing, or modifying the behavior of a body. Either way, the modifications that occurred will cause the invalidation of anticipated simulation steps in a world. The rollback algorithm can be used to manage these changes. The overhead of integrating user interactions in anticipated computations cannot be avoided but is lesser than that of full invalidation.

Load Balancing

To validate our model, we must be able to balance load between nodes in a distributed fashion as well. In this section we just show that there are ways of designing distributed load balancing for SODA. For instance, this may be performed between two worlds by asking for and by giving parts of their territory. When a cell is transferred from a world to another, its bodies are then simulated by the recipient world, increasing the runtime of its collision handling pipeline, and reducing the load of the sender world. A rough sketch of the load balancing process is illustrated by Figure 5.

There are several challenges to address for efficient load balancing: using lightweight, accurate and distributed load estimation metrics; choosing which grid cells should be given, and to which neighbors; keeping territories shaped as spheres or cubes to preserve benefits from temporal coherence [START_REF] Miller | Event-driven molecular dynamics in parallel[END_REF]; performing loose load balancing to limit its cost and rely more on anticipation.

Load Metrics

Simple metrics, such as the average time to perform one pass of collision handling, can be combined with the advance of a world over its neighbors, which indicates how much it can afford to handle collisions more slowly. We could also use the density of the territory, as it represents the risk that a computational peak occurs. The problem of computing an average load, or of estimating one's load, in a distributed context can be expressed as a consensus problem and is widely studied. A summary of current challenges and advances can be found in the PhD thesis of [START_REF] Cosenza | Efficient distributed load balancing for parallel algorithms[END_REF], with examples in ray-tracing and simulation.

Example of Load Balancing Algorithm

Every world may compute, using the metrics, a global load estimation, as well as an estimation for each of its cells. It may then ask its neighbors for their own last load estimation. If the world is significantly more loaded, it will compute a load score to reach, representing its overload compared to neighbors. Then, it will search among its neighbors which are most likely to benefit from receiving additional territory (e.g. depending on their own load, territory size, number of neighbors) and rank them by load score to give. It will then choose among its cells which are the most interesting for that neighbor and distribute them until it reached the load score previously set, switching to a new neighbor if necessary. As in [START_REF] Miller | Event-driven molecular dynamics in parallel[END_REF], the algorithm should make sure to keep territories in one piece and to minimize their perimeters.

CASE STUDY

In this section, we present statistics from simulations performed on our ongoing implementation. We observe the behavior of synchronizations in our implementation to choose the most suitable granularity of space distribution among worlds. We also illustrate the interest of anticipation in terms of resistance to frame-rate drop-downs.

The implementation uses open-source software (the Bullet Physics engine v2.79 and the Ogre 3D engine v1.7). At the time of writing this paper, distributed CD was implemented but CS had not yet been adapted to manage foreign bodies' constraints within a world. We did not seek to evaluate raw performance as our implementation conflicts with many of the optimizations present in the engine we used. We focus only on the feasibility of a distributed physics pipeline and on reducing the amount of synchronizations to an acceptable level.

Distribution of Synchronizations

The following experiment was performed on a system with two Intel Xeon X5680 processors, for a total of 12 CPUs. The system has 48GB RAM, and runs Linux 3.2. We wrote a parallel shared-memory implementation, each world running in a thread of the same process. This choice was made as no PC cluster with more cores was available.

We explored the potential for distribution with our current definition of territories and borders. To do so, we ran a simulation with twelve worlds and a growing number of bodies (hence a growing density), homogeneously and randomly distributed in the space. The space was 24000 km 3 , and the simulated bodies were cubes of 100 cm 3 . We ran each simulation five times for ten seconds (at 60 FPS) and aggregated results for each time steps.

Although it may seem a school case for traditional CD algorithms, the homogeneity of the positioning means that it is impossible for worlds to map their territories to "collision hot spots". Because there are very few worlds for such a large space, borders between worlds are very large and inevitably overlapped by at least one cube.

Figure 6 shows worlds classified by the size of their synchronization group, on average. It is obvious that such a coarse granularity has no chance of bringing performance improvements over parallel approaches: it would need to scale for thousands of bodies rather than a few hundreds.

We classified groups for better readability, depending on what kind of scalability groups of their size would obtain with state-of-the-art algorithms from the CD litterature. For instance, groups below four worlds would obtain full scalability while those above eight would start being limited. The idea is to visualize the groups that have a critical size and that will decrease the overall scalability of the simulation.

Our second experiment seeked to evaluate the improvements we would obtain from using more worlds. We ran on the same system a similar simulation with five hundred bodies (where the previous simulation was almost fully synchronized), and a varying number of worlds. As Figure 7 suggests, synchronizations become rarer with as few as five to ten bodies per world.

From this perspective, we recommand that distributed collision handling be run on many-core ar- Current parallel CD algorithms make use of GPUs, which are a form of many-core architecture, but we argue that current state of GPGPU languages is limiting potential for anticipation and asynchronous computing because it allows the use of GPUs only as passive devices which need a CPU to send data and launch kernels. However, we may see the emergence of new classes of distributed algorithms, similar or not to SODA, when GPGPU languages and frameworks start offering more flexibility.

Anticipation Benefits

We evaluate the benefits of anticipations in SODA with a function taking two parameters: a percentage of overload for a process, and the size of a buffer in which anticipated entries are stored. It should inform on the number of simulation steps that can be computed and used (including those in the buffer) before a process will start being too late to cope with the rendering frame rate.

In implementations, such a function could be used to evaluate the cost-efficiency of anticipation (comparing the size requirement of a buffer and its ability to provide resilience to frame-rate drop-downs), or the emergency of load balancing for discrete CD systems. Indeed, load balancing can be delayed when the additional workload is limited and does not represent a high risk of lateness for a given process.

We designed an experimental case study, running at 60 FPS with a single world running on a Intel Xeon W3540 CPU (2.93GHz). We simulated 40 cubes perfectly overlapping, and put them back to their original position after each simulation step, so that they would keep overlapping (though we did not reset acceleration). We used a 2-body broad-phase algorithm, which has exponential complexity. Hence, we evaluated increases in work load in terms of number of checks to perform when adding bodies. This number of cubes was enough for the collision handling pipeline of our prototype to fill the transform buffer, yet adding more cubes would cause the world to miss the 60 FPS target. After a warm-up phase of one second to fill buffers, we added enough cubes to reach a wanted threshold of additional cost, and calculated the time it would take for the world not to be able to provide an entry on due time to the rendering process. Results are shown in Figure 8 and indicate that there is a clear interest to allow anticipation rather than to simpler coupling of collision handling and rendering. Even with a 150% load increase, the world had up to a second (sixty steps) to react and trigger load balancing.

In practice, we expect that load balancing algorithms with direct access to anticipation benefits functions for a variety of buffer sizes would be able to adapt the aggressiveness and granularity of their load balancing using the number of anticipated entries they store in their buffers. In a distributed context where processors can be added to match the computational needs of an application, resilience to frame-rate dropdowns is a desired property that may let processes perform load balancing only when it is necessary and focus on useful computation instead.

Conclusion

In this paper, we have presented SODA, the first collision handling model designed for low-latency distributed systems. SODA is designed for high scalability on systems with tens to hundreds of CPUs, using decentralization and anticipation to reach this goal. We showed how collision handling can be performed in a distributed way among several processes, without constant clock synchronization between processes. We proposed a novel rollback algorithm to improve the efficiency of anticipative computation.

We showed that there is potential for load balancing in SODA. We showed the limitations of our broad-grained approach, with synchronizations still too frequent for proper distributed computation without a significant number of concurrent worlds, which we will have to address by finding finer-grained task decompositions. Finally, we evaluated in a case study the expected ability of anticipation to mitigate framerate drop-downs that may harm user experience.

In the future, we intend to develop specific constraint solvers for distributed contexts, in order to improve rollback and to solve constraints in parallel with least communication between two cores. We also want to integrate the motion of objects into load balancing decisions, and to use the static environment for initial territory setup. Finally, we want to explore the efficiency of SODA for specific applications such as indoor crowd simulation or complex factory environment simulations, with predictable flows of motions.

Figure 1 :

 1 Figure 1: A 2D simulation with three worlds. On the right, a border traversal forces the top worlds to synchronize.

Figure 4 :

 4 Figure4: DR-like strategies may detect false positive that will prevent CS rollback, whereas SODA will avoid them.

Figure 5 :

 5 Figure 5: Example of two underloaded worlds, p i and p j , being given territory by their overloaded neighbors (percentages represent load estimations).

Figure 6 :

 6 Figure 6: Evolution of the number of worlds per sizes of synchronization groups, depending on the density of the simulation.

Figure 8 :

 8 Figure 8: Example of anticipation benefits function for a world run on a Xeon W3540 with a buffer of 48 anticipated entries.

  Figure 7: Evolution of the number of worlds in each connected-group size class, depending on the number of cores chitectures with very fine-grained distribution of the space. Miller and Luding used such a small granularity while Li et al. chose to simulate bodies directly rather than territories regrouping few bodies. Besides, there are incentives for chosing simulation islands as a unit of task decomposition, for the CS stage of the collision handling pipeline.

	96	Worlds per
		group size
	0	12 20		32 40	48	56	64	96 Worlds
		1-4	4-8	9-12		13-20	21-36	37+

Acknowledgments

We address our thanks to Bruno Arnaldi and the anonymous reviewers their feedback, Alexandra Covaci for her help in processing experiments data and Loeiz Glondu for our insightful discussions on linear constraint solvers. This work was partly supported by the French Research National Agency project named Corvette (ANR-10-CONTINT-CORD-012).