Samuel Cruz-Lara

Nadia Bellalem

Lotfi Bellalem

Tarik Osswald

Immersive 3D Environments and Multilinguality: Some Non-Intrusive and Dynamic e-learning-oriented Scenarios based on Textual Information

Keywords: Multilinguality, Virtual Worlds, Standardization, Non-Intrusive and Dynamic Scenarios, Language Learning

Virtual Worlds may become primary tools for learning many aspects of history, for acquiring new skills, for job assessment, and for many of our most cost-effective and productive forms of collaboration (Metaverse Roadmap Report, 2007). We will present some non-intrusive and dynamic e-learning based scenarios related to multilin-gual textual information within an immersive 3D environment. We refer to these scenarios as non-intrusive because they do not interrupt the user's activities within the immersive 3D en-vironment. Rather, they enrich his/her individual experience. Obviously, these scenarios need to be dynamic, because user interaction occurs mostly in real-time. In addition, these non-intrusive and dynamic e-learning-oriented scenarios exemplify how a standardized framework for textual multilingual support associated with an immersive 3D environment, may consid-erably change the way people usually deal with multilingual information and with language learning on the Internet. We would like to illustrate that, in the context of immersive 3D envi-ronments, dealing with multilinguality is more than just localization and real-time automatic translations. Finally, the analysis of these non-intrusive and dynamic e-learning based scenarios lead us to propose a general architecture allowing immersive 3D environments to deal with multilinguality in the most general and dynamic way possible.

Linguistic information plays an essential role in the management of information, as it bears most of the descriptive content associated with more visual information. Depending on the context, it may be seen as the primary content (text illustrated by pictures or videos), as documentary content for multimedia information, or as one among several possible information components in specific contexts such as interactive multimedia applications. Linguistic information can also appear in various formats: spoken data in an audio or video sequence, implicit data appearing on an image (caption, tags, etc.) or textual information that may be further presented to the user graphically or via a text to speech processor.

In this context dealing with multilinguality is crucial to being able to adapt the content to specific users' targets. It has to take into account situations in which the linguistic information contained in a multimedia sequence is already conceived in such a way that it can be adapted on the fly to the linguistic needs of the user. It also has to take into account situations in which the content should be adapted by additional processes before it is presented to the user.

The extremely fast evolution of the technological development in the sector of Communication and Information Technologies, and in particular, in the field of natural language processing, makes the question of standardization particularly acute. The issues related to this stan-dardization are of industrial, economic and cultural nature.

The scope of activities in localization and translation memory (TM), as well as any type of online multilingual customization (subtitling, iTV, karaoke) is very large, and numerous independent groups are working on these aspects, such as LISA, OASIS, W3C, ISO, etc. Under the guidance of the above-mentioned groups, many formats have been developed. Some of the major formats of specific interest for localization and translation memories are TMX (LISA/OSCAR), XLIFF and OAXAL (OASIS), ITS (W3C). There are many identical requirements for all the formats, irrespective of the differences in final output.

Second Life, in common with other virtual world applications, has opened up the potential for users and learners, teachers and trainers, policy makers and decision makers to collaborate easily in immersive 3D environments. Through their presence as an avatar in the immersive space, the user can readily feel a sense of control within the environments and more easily engage with the experiences as they unfold.

In this paper, we would like to illustrate that within immersive 3D environnments dealing with multilinguality involves more than just localization and translation issues.

The paper is structured as follows: firstly, we define some important concepts such as Multilin-guality, Globalization, Localization, Internationalization, and Automatic Translation; secondly, we explain why normalization and standardization are key-issues in the framework of mulitilin-guality, and we introduce the Multi Lingual Information Framework -MLIF [ISO CD 24616]; thirdly, we introduce several non-intrusive and dynamic e-learning scenarios that allow us to illustrate how multilinguality may be approached within immersive 3D environments. Finally, from the analysis of these scenarios, we propose a general architecture allowing immersive 3D environments to deal with multilinguality in the most general and dynamic way.

Multilinguality

This section provides some important definitions in the frame of multilinguality, such as localization, internationalization and automatic translation. It should be noted that the scenarios described in Section 4 mainly focus on automatic translation.

Globalization: Localization and Internationalization

As the LISA association explains, globalization can best be thought of as a cycle rather than a single process, as shown in Figure 1.

Figure 1: The Globalization process

In this view, the two primary technical processes that comprise globalization -international-ization and localization -are seen as part of a global whole:

• Internationalization encompasses the planning and preparation stages for a product in which support for global market is built in by design. This process means that all cul-tural assumptions are removed and any country-or language-specific content is stored externally to the product so that it can be easily adapted.

• Localization refers to the actual adaptation of the product for a specific market. It in-cludes translation, adaptation of graphics, adoption of local currencies, use of proper forms for dates, addresses, and phone numbers, and many other details, including phys-ical structures of products in some cases. If these details were not anticipated in the internationalization phase, they must be fixed during localization, adding time and ex-pense to the project. In extreme cases, products that were not internationalized may not even be localizable.

Automatic translation

Automatic or Machine translation (MT) is a sub-field of computational linguistics that inves-tigates the use of computer software to translate text or speech from one natural language to another. At its basic level, MT performs simple substitutions of words in one natural language for words in another. Using corpus techniques, more complex translations may be attempted, allowing for better handling of differences in linguistic typology, phrase recognition, and translation of idioms, as well as the isolation of anomalies. Current MT software often allows for customization by domain or profession (such as weather reports) -improving output by limiting the scope of allowable substitutions. This technique is particularly effective in domains where formal or formulaic language is used. It follows then that machine translation of government and legal documents more readily produces usable output than conversation or less standardized text 2 .

Standardization Introduction

Nowadays, an increasing number of standards are frequently being used within most scientific and technical domains. Translation and localization activities simply cannot remain isolated from this important and novel situation. The advantages of normalization are currently fully recognized by most professional translators. Using standards means working with a high level of quality, performance, and reliability within a very important market that is becoming more and more global and thus more and more challenging. Indeed, the standards combine simplicity and economy by reducing the planning and production costs, and by unifying several kinds of terminology (i.e. validated vocabulary) and several kinds of products. At the national and international levels, standards stimulate cooperation between different communities of trade while ensuring interoperability within information exchanges and reliability of all generated results by using standardized methods and procedures; this is why normative information has become fundamental.

The scope of research and development within the localization and translation memory process development is very large.

Within this context, several industrial standards have been developed, including TMX, XLIFF and OLIF. However, when we closely examine these different multilingual textual information representation standards or formats by subject field, we find that they have many overlapping features. All the formats aim at being user-friendly, easy-to-learn, and at reusing existing data or knowledge bases. All these formats work well in the specific field they are designed for, but they lack the synergy that would make them interoperable when using one type of information in a slightly different context. Modelization corresponds to the need to describe and compare existing interchange formats in terms of their informational coverage and the conditions of interoperability between these formats. One of the issues here is to explain how a uniform way of documenting such data takes into account the heterogeneity of both the formats and the descriptors.

We also seek to answer the demand for more flexibility in the definition of interchange formats so that any new project may define its own data organization without losing interoperability with existing standards or practices. Such an attempt should lead to more general principles and methods for analyzing existing multilingual databases and mapping them onto any chosen multilingual interchange format.

Normalization: a key issue for translation

The translator is the most important element of the translation process: thanks to their expe-rience, their knowledge and the automatic translation services they may use, they ensure that the translated document is accurate with respect to the original one [3]. A good translation does not only need linguistic awareness but it also needs a good knowledge of the technical or scientific field of the documents that have to be translated. Most texts are addressed to specialists and ignorance of the specialized expressions can justifiably cause rejection by the reader. In the same way, English technical terms -whose equivalents nevertheless exist in the target language -are often used untranslated (as is the case in French, for example). Obviously, technical translations are not limited to data processing or computer science translations. Technical translators must have, in addition to their knowledge, a high-quality set of documents. Even the more knowledgeable must continuously seek advice from technical documents (i.e. journals, specialized dictionaries, magazines, data bases, etc.). These technical documents constitute a set of essential tools that allow a translator or a translation service to analyze the information located on the covered subject. So they must evolve constantly by acquiring new information and new experiences, because this way they will obtain additional linguistic and non-linguistic knowledge related to their domains [4].

Given that they are high-level models for technical specifications (i.e. symbols, definitions, codes, figures, methodology, etc), standards constitute a fundamental tool for translation, because they will provide abundant, exact, and above all, interoperable and reliable information. Unfortunately, several fieldsand especially translation -have numerous and often non-compatible standards. This requires a parallel activity of normalization of these standards in order to ensure, at least, a minimal degree of compatibility.

This activity constitutes the main issue of the "Documentation on standards" or the "Structured set of standards" [5]. As the texts, objects of translation, have a great diversity of subjects, the documentary activities applied to the standards can also guide and direct the translator in the search for standards relative to a given field. The production of standards is sometimes so prolific that it makes it quite difficult to understand exactly what method or procedure has to be used.

The documentary techniques bring essential assistance. The services of information and dissemination of the national and international organizations of standardization give easy access to all this information. The standards issued by the organizations of standardization (i.e. ISO, W3C and LISA) are becoming more and more accepted by the translation services and the translators to achieve a high-level quality in their services and their products. Standardization thus becomes a synonym of quality for the customers who desire the best possible results. In addition, standards also represent an essential tool for translators and translation services, as they aim at creating normalized terminological and methodological linguistic resources, in order to improve the national and international exchanges as well as cooperation within all possible fields. It is also necessary to point out the important efforts of standardization of ISO and W3C in the field of information technologies, especially those related to the computerized processing of multilingual data and the Internet.

Standardization is present during the whole process of translation. So, the access to the norma-tive information represents a stage impossible to circumvent within the activity of translators and translation services. Within this task (i.e. standardization) human translators are as-sisted not only by resource centers in charge of disseminating the information of the standards worked out by the national and international organizations, but also by other specialized pri-vate agencies (i.e. PRODOC 3 ) whose main objective is to advise the customers with regards to standards. In the same way, the Internet allows access to thousands of web sites (i.e. termi-nology trade, databases, etc.) that provide important information related to using standards, as well as access to several interesting research projects in progress whose objectives are the development of standards and recommendations in the field of the "industry of language".

MLIF: The Multi Lingual Information Framework (MLIF)

MLIF provides a generic platform for modeling and managing multilingual information in vari-ous domains: localization, translation, multimedia, document management, digital library, and information or business modeling applications. MLIF provides a metamodel and a set of generic data categories for various application domains. MLIF also provides strategies for the inter-operability and/or linking of models including (but not limited to): XLIFF, TMX, OAXAL, SMILText and ITS.

What is a metamodel?

A metamodel does not describe one specific format, but acts as a high level mechanism based on the following elementary notions: structure, information and methodology. A metamodel can be defined as a generic structure shared by all other formats and which breaks out the organization of a specific standard into basic components. A metamodel should be a generic mechanism for representing content within a specific context.

Actually, a metamodel summarizes the organization of data. The structuring elements of the metamodel are called "components" and they may be "decorated" with information units. A metamodel should also comprise a flexible specification platform for elementary units. This specification platform should be coupled to a reference set of descriptors that should be used to parameterize specific applications dealing with content.

What is a data category?

A metamodel contains several information units related to a given format, which we refer to as "Data Categories". A selection of data categories can be derived as a subset of a Data Category Registry (DCR) [ISO 12620]. The DCR defines a set of data categories accepted by an ISO committee. The overall goal of the DCR is not to impose a specific set of data categories, but rather to ensure that the semantics of these data categories is well defined and understood. A data category is the generic term that references a concept. There is one and only one identifier for a data category in a DCR. All data categories are represented by a unique set of descriptors. For example, the data category /languageIdentifier/ indicates the name of a language which is described by 2 [ISO 639-1] or 3 [ISO 639-2] digits. A Data category Selection (DCS) is needed in order to define, in combination with a metamodel, the various constraints that apply to a given domain-specific information structure or interchange format. A DCS and a metamodel can represent the organization of an individual application, and the organization of a specific domain.

Specifying the Multi Lingual Information Framework

Linguistic structures exist in a wide variety of formats ranging from highly organized data (e.g. translation memory) to loosely structured information.

The representation of multilingual data is based on the expression of multiple views representing various levels of linguistic information, usually pointing to primary data (e.g. part of speech tagging) and sometimes to one another (e.g. references or annotations).

The following model identifies a class of document structures that could be used to cover a wide range of multilingual formats, and provides a framework that can be applied using XML.

All multilingual standards have a rather similar hierarchical structure but they have, for example, different terms and methods of storing metadata relevant to them. MLIF is being designed in order to provide a generic structure that can establish a basic foundation for all these stan-dards. From this high-level representation we are able to generate, for example, any specific XML-based format. We can thus ensure the interoperability between several standards and their committed applications. Figure 2 describes the MLIF metamodel. • GI (Global Information) Represents technical and administrative information applying to the entire multilingual data collection.

• GroupC (Grouping Component) Represents a sub-collection of multilingual data having a common origin or purpose within a given project.

• MultiC (Multilingual Component) Groups together all variants of a given textual content.

• MonoC (Monolingual Component) Part of a multilingual component (MultiC) containing information related to one language

• HistoC (History Component) This generic component allows tracing of modifications in the component it is anchored to (i.e. versioning).

• SegC (Segmentation Component) A recursive component allowing any level of segmenta-tion for textual information.

Any format compliant with this standard may use the MLIF metamodel in two possible ways:

• By fully implementing the MLIF metamodel starting at the level of the <MLDC> com-ponent;

• By specifically embedding MLIF compliant information within another model, by implementing one of the lower level MLIF component, namely <GroupC>, <MultiC> or <MonoC>.

Relation with other standards

As with TMF used for terminology, MLIF introduces a metamodel in combination with chosen data categories as a means of ensuring interoperability between several multilingual applications and corpora.

MLIF deals with multilingual corpora, multilingual fragments, and the translation relations between them. In each domain where MLIF can be used, we may consider a specific granularity of segmentation and description, built on MAF, SynAF and TMF, for morphological description, syntactical annotation or terminological description respectively. Supporting the construction and the interoperability of localization and "Translation Memories" TM resources, MLIF also deals with the description of a metamodel for multilingual content. MLIF does not propose a closed list of description features. Rather, it provides a list of data categories, which is much easier to update and extend. This list represents a point of reference for multilingual information in the context of various application scenarios.

However, MLIF will not only describes elementary linguistic segments (i.e. sentence, syntac-tical component, word, part of speech, etc.), but it may also be used to represent document structure (i.e. title, abstract, paragraph, section, etc.). In addition, MLIF allows using external and internal links (i.e. annotations and references).

The MLIF is being designed with the objective of providing a common platform for all the existing tools developed by the groups listed in the introduction section. It promotes the use of a common framework for the future development of several different formats: TMX, XLIFF, etc. MLIF can be considered as a parent for all these formats, since all of them deal with multilingual data expressed in the form of segments or text units. They can all be stored, manipulated and translated in a similar manner.

E-learning scenarios: the Language Academy

We would like to present now some non-intrusive and dynamic e-learning based scenarios on multilingual textual information within an immersive 3D environment. We refer to these sce-narios as non-intrusive because they do not interrupt the user activities within the immersive 3D environment. Rather, they enrich his/her individual experience. Obviously, these scenarios need to be dynamic, because user interaction occurs mostly in real-time situations. We would like to illustrate that, in the context of immersive 3D environments, dealing with multilinguality is more than just localization and real-time automatic translations.

The General Scenario

Pierre is a French student, who speaks English fluently but recently moved to the Netherlands. Therefore, he decides to learn Dutch through various ways. The following scenarios represent Pierre's evolution phases for virtual world usage in order to learn Dutch.

Pierre alone, at home

This scenario represents the already existing solutions in the language learning domain.

At the beginning, Pierre learned the grammatical ground knowledge using book learning methods or through group or private Dutch lessons given by a teacher. After acquiring strong ground knowledge, Pierre decides to go further and to learn this new tongue by watching Dutch movies with French or English subtitles.

His media player with multilingual support enables him to pause anytime in order to obtain the Dutch translation of the displayed subtitles. He can also have the audio part corresponding to one subtitle played back, or he can ask for some definitions and synonyms for a single word -using specific web services 4 -by searching in his web browser. If the Dutch subtitles are not available, a translation web service may generate them from the French or English ones.

It would be interesting to be able to click directly on the subtitles (in order to get synonyms, definitions or translations) without needing to use a web browser and in order to sensibly improve the interactivity. This functionality is not currently available but is conditionally conceivable.

Pierre can also get information about the Dutch culture, thanks to on-line resources like Wikipedia, for example. This possibility is particularly useful for understanding some subtle scenes.

Nevertheless, this learning method has several weaknesses:

• Pierre only gets information without having any opportunity to use his knowledge for speaking or writing. Therefore, it is a one-way learning.

• The resources (movies and subtitles) may be limited, on the one hand by their costs, and on the other hand, by Pierre's cinematographic tastes.

That is why Pierre will take the plunge and look into virtual worlds, in order to discover more interactive and more immersive learning methods.

Pierre alone, in a virtual world

Pierre now discovers the virtual worlds. He hears about the very accurate modeling of the historic museum of Amsterdam and decides to teleport there in order to take a virtual tour.

At his arrival, Pierre is offered a flying carpet to take him through the museum. The flying carpet is actually a robot which communicates through the chat interface in the virtual world (see Figure 3). It can talk and understand what Pierre says. Pierre will now virtually visit the museum, riding and directing the flying carpet.

At first, Pierre asks the carpet in Dutch to have a brief guided tour. The sentence written by Pierre is analyzed and then the carpet flies through some museum key-places. At each place, the carpet gives Pierre a description of the place where he is or a description of some works.

Pierre can also ask the carpet to fly to a given place. Then, the carpet computes the shortest way to go there. It is a means of conveyance which is more efficient than walking and which enables Pierre to use his Dutch knowledge in order to express himself. During Pierre's visit, the server memorized the works about which Pierre asked for information. At the end, Pierre is offered a quiz which has been established according to the concerned works, which is written in Dutch too.

Through the museum visit, Pierre can start expressing himself in Dutch and learn a lot about Dutch culture. These two elements are essential for language learning.

Pierre participating in a group to learn Dutch, in a virtual world

Pierre is now on an island in the virtual world, where conferences are held in Dutch. In particular, there are many documentary movies about the Netherlands, directly presented in the virtual world by their respective directors. Many people from several countries who wish to learn Dutch meet on this island in order to improve their skills.

In fact, the directors are native Dutch speakers and they can talk in the virtual world using VoIP technology. On the server, a software application analyzes the voice information and transcribes it into text format for the avatars who are attending the conference. Doing so, the avatars may at once read the speech and listen to it, so that they can easily understand and assimilate the Dutch language.

Moreover, once the speech is transcribed into text, it may be translated by an online tool into each avatar's tongue. As a consequence, one speech may be listened to in Dutch and read in various languages. As before, it is possible to click on one word to get synonyms, definitions or translations.

The attendees at one conference may also ask questions to the speaker if they virtually put up their hands. They may do it in different ways: through the chat-based communication system or directly with VoIP. In order to practice, they often prefer expressing themselves in Dutch.

Moreover, the same transcription and translation system as before is available to the speaker (the movie director), so that he can understand questions asked in other languages than Dutch. Figure 4 5 shows how such a conference may be seen by Pierre.

Figure 4: Virtual conference with voice transcription and translation Finally, once again in order to facilitate language learning, the Dutch text may be analyzed by a grammar parser. Doing so, a user may for example configure their display so that all the verbs are displayed in a red font color.

Pierre with Dutch people, in a virtual world

Pierre has now improved his Dutch level a lot. He knows the Dutch culture much better and has heard many native Dutch people talking. Nevertheless, his skills are not perfect yet and he now wishes to talk in real time with Dutch people. That is why he teleports to one of the most popular virtual islands in the Netherlands.

He can now talk through the chat interface with native Dutch people. The virtual world makes the situation less alarming than in the real world so that Pierre feels more comfortable during the talks.

He does not feel as nervous as he usually is in real life, particularly when talking in a foreign language. The virtual world also makes the chat-based talk more immersive than the usual chat interfaces, as it offers the users a common environmental context.

Pierre is going to meet Dutch people, and suggests that they watch a movie together in a virtual cinema. Pierre may display on his screen the subtitles in a selected language whereas his virtual friends do not need them. He can also talk about his impressions concerning the movie or about the cultural differences. In that case, the displayed subtitles are clickable.

5 Image from Wikimedia Commons (http://commons.wikimedia.org/), text from Wikipedia (http://www. wikipedia.org) But Pierre's Dutch knowledge is still not good enough to understand everything he hears or reads and he still needs to click on some words in order to get synonyms, translations or definitions in real time. Sometimes, he also enables the syntax coloration, for example in order to highlight the verbs displayed in the chat window of his local user interface (see Figure 5). Every time Pierre clicks on one word, the system memorizes the searched information. Doing so, Pierre can delay dealing with the words and expressions which where a bit difficult to him. This is particularly useful if Pierre has not had time to consult the information right away. This functionality leaves Pierre more time to get focused on the talk in the virtual world. The sentences containing the searched words or expressions are also kept in memory, so that Pierre can retrace his searches back to the original context and have a usage example for each word.

Required system components

In this part, we are going to explain the different technologies required for each scenario pre-sented in Section 4. Some components are transversal to the described scenarios and implement their own mechanisms, and some other components have already been defined before. To make things easier to follow, we will first make a list of the required system components and then associate them with each scenario in Section 6. Figure 6 shows the relationship between all the system components that we are going to explain further.

A multimedia player

The needed multimedia player should support video files with synchronized textual subti-tles, in various languages.

As each word or sentence in the subtitles should be clickable, the corresponding lexical units have to be representable in the text files containing the subtitles.

The player links the subtitles with the corresponding audio part (using their corresponding time signature), so that the user can ask to hear the audio part corresponding to a given subtitle. This player can display and control subtitle streams in order to be able to change the subtitle language while the video is running.

That is why the subtitles should be linked together in order to be able to switch from a language to another. This functionality is enabled by MLIF.

As a consequence, it is necessary to have a data structure which represents both time informa-tion and language equivalences.

A web service linked to external resources

This service uses external resources which already exist on the web and allows one to work easily with upto-date information.

It relies on services like WordNet (definitions, synonyms), Reverso (word, sentence or paragraph translations) or Wikipedia (cultural information). The way those services are structured should make the needed information easy to extract. The web service should also be able to provide information which would not only be indexed to nouns, but also to cultural singularities.

A virtual guide robot

We are now talking about a robot having the appearance of a flying carpet, which moves in a marked network according to the visitor's orders.

The markers (nodes of the graph representing the network) need to have names in various languages, including Dutch in our example. The markers have to be linked together in order to represent the graph edges.

The robot program communicates with a web service which includes a dynamic and multilingual grammar parser (depending on the marker names), in order to make accurate syntax and semantic analysis.

The implemented grammar manages several kinds of orders: moves and information inquiries.

The least-cost path computing, the management of the links between markers, the marker names in various languages, the information display and the syntax and semantic analysis are relocated on a PHP/MySQL server working as a web service in order to make the processing faster. That means that the virtual world should also be able to send HTTP requests.

As for the information inquiry (date, type, author), the text data describing the works located in the virtual world should be structured in such a way that the required information may be extracted easily.

To do so, the virtual world textual data has to be formalized. The resources to fill in the descriptions might also be taken from online encyclopedias if the relevant information is standardized too.

It should also be possible to obtain information about one work by clicking on it. This information may be displayed directly in a web browser but also in the graphical virtual assistant (see Section 5.5). The information elements may be sorted according to the inquiries of the visitor and that is why they should also be standardized.

The data describing the works is stored on a remote server which is accessible through the web service.

A voice recognition application

This module allows the transcription of talks into text, which is then displayed to the listeners through the chat interface window or the graphical assistant. Matching voice and text allows several kinds of learning:

• Phonetics: to be able to identify the sounds of a tongue (perception and discrimination);

• Lexical: to learn the word spellings;

• Morphosyntax: agreement of adjectives, nouns, past participles (depending on the lan-guage);

• Semantic: understanding words according to their context.

In order to get a better voice recognition rate, the conferences will be thematic and tools like Viavoice, Dragon Naturally Speaking and Freespeech will be used depending on each one's speciality.

A graphical virtual assistant

This graphical assistant, dedicated to language learning, is an interface which is integrated to the virtual world. This interface is available for each user who would like to use the functionalities of the Language Academy. It encompasses the following modules:

• A movie recorder (in order to watch the virtual conferences again);

• A web browser or alike, to display the information relative to the works in a museum, the results of a search when clicking on one word and the search history (storage with MLIF format in the database);

• A voice recognition module -which may be an external stand-alone component-in order to transcribe into text the talks of the speakers (scenario 4.4) and of the Dutch people Pierre talks to (scenario 4.5).

An interactive chat interface

The chat interface of the virtual world has to be flexible enough in order for the user to be able to configure syntax coloring and to click one word if he wants to. Syntax coloring can be made, as the user wishes, in the chat window and/or in the graphical assistant.

All of the obtained text data is clickable, in order to get information about the selected words or groups of words. Besides, a clicked word may be put back into its context (the sentence). Therefore, the granularity of the textual information (paragraphs, sentences, words, etc.) must be included in the standard.

Since the chat-based talks have a time signature, it is also important to be able to match time information to each text element.

Discussion

Relationship between system components and scenarios

Figure 7 shows the system components involved in each scenario. A checked box means that the corresponding scenario involves the corresponding system component.

Theoretical and technical limits

The functionalities of scenarios 4.4 and 4.5 mainly rely on a very good voice recognition quality. The current systems are mostly based on the use of linguistic corpora in order to improve the recognition quality. It means that, within scenario 4.4, every conference should be associated to one available corpus. But this is not so easy to do in scenario 4.5, as the talk themes can't be defined in advance. Moreover, the translation of the transcripted talk into another language mainly depends on the voice recognition quality. The loss of accuracy caused by text automatic translation should also be taken into account. Therefore, depending on the vocabulary and expressions used, the results of the transcription and translation functionality may be more or less accurate. However, those limitations are not theoretical limitations. The research for this kind of application is advancing and that is why we think we can get better results in the coming years.

Finally, all the scenarios are based on a certain representation of multilingual textual informa-tion. Therefore, the emergence of new multilingual textual information standards is necessary. The MLIF standard proposal has been developed in a similar vein in order to standardize the multilingual textual information representation and fully satisfies the needs of the scenarios presented in Section 4.

Conclusion

We have proposed some non-intrusive and dynamic e-learning based scenarios related to multilingual textual information within an immersive 3D environment. We have shown that in the context of immersive 3D environments, dealing with multilinguality is not only localization and real-time automatic translations. Immersive 3D environments may really change the per-ception that users may have of multilingual issues, in particular, in the field of language learning. The analysis of these scenarios leads us to propose a general architecture allowing immersive 3D environments that are able to deal with multilinguality in the most general and dynamic possible way. It should be noted that several scenarios have already been implemented (at least partially) in Second Life, and in Open Sim. All this work is being performed in the framework of the ITEA2 Project METAVERSE1 (ITEA2 07016).

These scenarios have also led us to propose a list of minimal multilingual requirements to ISO's MPEG-V working group. The requirements that must be fulfilled are:

• Multilinguality: textual information must be managed, accessed, and represented by taking into account multilingual aspects. Here, some key technologies and standards are: Unicode, XML, etc.

• Multilingual links: it must be possible to set up links between documents using different languages. This will allow u s to represent localization and translation issues. Here, some key technologies and standards are TMX, XLIFF, MLIF, OAXAL, and ITS.

• Linguistic granularity: it must be possible to represent textual information at several levels: paragraphs, sentences, words, syllables, part-of-speech, etc. Here, some key tech-nologies and standards are those of ISO's TC37/SC4 "Linguistic Resources Management".

• Time issues: it must be possible to associate time to multilingual textual information. A classical example in this domain is illustrated by captions or sub-titles related to video frames.

Here, some key technologies and standards are W3C's SMILText and Timed-Text, SRT, etc.

Figure 2 :

 2 Figure 2: MLIF metamodel with related Data Categories

Figure 3 :

 3 Figure 3: The flying carpet in Second Life

Figure 5 :

 5 Figure 5: Red font colour for the verbs displayed in the chat interface

Figure 6 :

 6 Figure 6: Relationship between the system components

Figure 7 :

 7 Figure 7: Relationship between system components and scenarios

Definition from http://www.wikipedia.org

http://www.prodoc.de

If he wants to, Pierre can ask, in Dutch, for more accurate information about the works he discovers. The carpet then extracts the date, the author or the story of the work from the available data stored on a web server.4 Online databases like WordNet (http://wordnet.princeton.edu/) or ConceptNet (http://conceptnet. media.mit.edu/)


Didier Hoareau

Yves Mahéo

Constraint-Based Deployment of Distributed Components in a Dynamic Network

Hierarchical software components offer interesting characteristics for the development of complex applications. However, supporting the deployment of such applications is difficult, especially on challenging distributed platforms. This paper addresses the distribution and the deployment of hierarchical components on heterogeneous dynamic networks. Such networks may include fixed and mobile resource-constrained devices and are characterized by the volatility of their hosts and connections, which may lead to their fragmentation. The distribution scheme and the associated mechanisms we propose allow a component to provide its services in an ubiquitous way and to operate in a degraded mode. The deployment of hierarchical components is described: we present an ADL extension for specifying a context-aware deployment and we detail a hierarchicallycontrolled deployment designed for dynamic networks. This deployment is performed in a propagative way and is driven by constraints put on the resources of the target hosts.

Introduction

Distributed platforms are no longer restricted to stable networks of workstations. One of the archetype of a distributed platform is now a network that may comprise stable and powerful workstations but also a number of mobile and resource-constrained devices. Although this kind of distributed platform is increasingly common, it remains a challenging target for building, deploying an maintaining distributed applications. Specific techniques must be applied to cope with the heterogeneity of the hosts and links as well as with the dynamism of the network. What we call dynamic networks are especially a difficult target, as hosts may become unaccessible because of their mobility or their volatility. As a consequence, one cannot rely on models and algorithms designed for fully connected networks. A dynamic network is rather described as a partitioned network, viewed as a collection of independent islands. An island is equivalent to a connected graph of hosts that can communicate together, while no communication is possible between two islands. In addition, the configuration of the islands may change dynamically.

Figure 1 shows an example of such a dynamic network. It is composed of a number of hosts a user has access to and on which a distributed application is meant to be accessible. This set of hosts includes fixed and mobile machines. Connectivity is not ensured between all the hosts. Indeed, at home, the user's connection to Internet is Fig. 1. Example of a dynamic network, possibly partitioned in three islands sporadic and some of the devices are mobile (as such, they may become out of reach) and/or volatile (a PDA may for example be switched off frequently).

The applications that are to be executed on dynamic networks can be inherently complex. This complexity is even increased by the need to produce code that can adapt to the changes of the execution environment. Since a few years, the use of software components proved to be useful for developing complex distributed applications and many component models and their associated technologies are now available. In the component-based approach, the application is designed as an assembly of reusable components that can be bound in a versatile manner, possibly dynamically. Some of the proposed models are known as hierarchical models. They offer the possibility of creating high level components by composing components of lower abstraction level, which represents a software construction principle that is natural and expressive. In such models, a component -that is then called a composite component-can be itself an assembly of components, recursive inclusion ending with primitive components that encapsulate computing code.

Using a hierarchical component-based approach for building an application that targets a dynamic network seems an attractive solution. Yet, several problems remain that are not dealt with available component models and component execution supports. In particular, the two following aspects have to be dealt with: [START_REF] Roussain | Cooperative Component-Based Software Deployment in Wireless Ad Hoc Networks[END_REF] how to deploy a hierarchical component in a dynamic network while ensuring that this deployment respects the architecture of the application and adapts itself to the resource constraints imposed by the target platform? (2) how to allow a distributed execution of the components, i.e. to allow interactions between components in a not-always-connected environment? This paper describes a distribution scheme of hierarchical components and its associated deployment process that target dynamic networks. Because of the very constrained environment in which the application is to be deployed, we can hardly envisage a permanent access to the services offered by the application or an optimal utilization of the resources. The emphasis is put on finding a distribution scheme and some deployment mechanisms that achieve a minimal availability while taking account of the environment.

Outline of our approach

The distribution scheme we propose is related to the hierarchical structure of the application. This scheme is based on the replication of composite components. Indeed, we allow a composite to be accessible on a set of hosts, although each primitive component is localized on a single host. Besides, we also allow a component to operate in a degraded mode in order to account for network disconnections without making the entire application unusable. The notion of active interface is added to the component model. Our runtime support detects network disconnections and deactivates some components' interfaces accordingly. Introspection on the state (active or inactive) of an interface is possible so as to allow the development of adaptive components.

The deployment of a component covers several parts of the life-cycle of a component. In this paper we focus on the last phases of the deployment, covering the instantiation of the component (that creates an executable instance from a component code), its configuration (that establishes the bindings to its interfaces) and its activation (that allows the other components to invoke its interfaces). The presented techniques should be complemented with component delivery mechanisms such as those described in [START_REF] Roussain | Cooperative Component-Based Software Deployment in Wireless Ad Hoc Networks[END_REF].

The deployment of the hierarchy of components is specified in a constraint-based declarative way. The architecture descriptors of the components are augmented with deployment descriptors in which constraints on the resources required by components and on their possible location can be specified.

When the deployment is triggered, all the constraints listed in the deployment descriptor may not be satisfied immediately. The dynamism of the network makes the situation even more difficult as it may occur that the set of hosts that would satisfy globally the deployment constraints are never connected together at the same time, precluding any deployment. Instantiation of some components and their activation is however possible as we allow the components to operate in a degraded mode through the dynamic management of interfaces' activation. The deployment process we implement is thus a propagative process : the instantiation and the activation of a component are performed as soon as some resources that meet its needs are discovered. We propose an algorithm that supports this propagative deployment. The scalability of the process is ensured by the distributed and hierarchical organisation of the control. Moreover, we implement a distributed consensus that guarantees that the location constraints are satisfied even in the context of a partitioned network.

The paper is organised as follows. First, the model of hierarchical component we work on is presented and we explain how a hierarchy of components is distributed over a network. The concept of activation at the interface level is briefly exposed. In section 3 we give some details on the form of the deployment descriptor that complements the architecture description. Section 4 presents the overall propagative deployment process and details the distributed instantiation algorithm that forms the basis of the distributed deployment. Section 5 briefly describes the status of the development of our prototype. Finally, we cite the related works before concluding.

Distributed Hierarchical Components

We describe in this section what we understand by distributed hierarchical components, through the description of the basic features of our component model and of the way we have chosen for distributing the components over a network of hosts. Further details can be found in [START_REF] Hoareau | Distribution of a Hierarchical Component in a Non-Connected Environment[END_REF].

Hierarchical Component Model

In this paper, we consider a widely applicable hierarchical component model in which a composite component represents a more or less complex structure of interconnected components that can be used as a simple component with well-defined required and provided interfaces. Recursion stops with primitive components that correspond to computing units. Components are interconnected through bindings that each represents a link between a required interface and a provided interface. For practical reasons, we have chosen to base our development on the Fractal component model [START_REF] Bruneton | An Open Component Model and its Support in Java[END_REF] and more precisely on its reference Java implementation Julia. However, the concepts developed in this paper could easily be applied to other hierarchical component models such as Koala [START_REF] Van Ommering | Koala, a Component Model for Consumer Electronics Product Software[END_REF], Darwin [START_REF] Magee | Specifying Distributed Software Architectures[END_REF] or Sofa [START_REF] Plasil | SOFA/DCUP: Architecture for Component Trading and Dynamic Updating[END_REF].

The notion of composite component is often used at design time and is found in so-called architecture description languages (ADL) [START_REF] Medvidovic | A classification and comparison framework for software architecture description languages[END_REF]. In the applicative framework we have chosen, it is however interesting to also be able to manipulate a composite at execution time in order to ease dynamic adaptation. Therefore the composite is reified at runtime namely by a membrane object that stores the interfaces of the component and its configuration (the list of its subcomponents and the bindings between these subcomponents).

Distribution Model

As mentioned in the introduction, we wish to deploy a hierarchy of components on a distributed platform that is characterized namely by its heterogeneity and the volatility of its hosts. The application components are distributed on a set of hosts. The way this placement is performed is detailed in section 4. We focus here on the description of the mechanisms allowing a distributed execution of hierarchical components.

In our approach, the architecture of a component is coupled to its placement and this relationship is dealt with differently for composite components than for primitive components. As far as distribution is concerned, a primitive component executes on one host whereas a composite can be physically replicated on a set of different hosts. The main goal of composite replication is that the component's interfaces become directly accessible on several hosts. A composite component can then be seen as providing a ubiquitous service.

A single host is associated with a primitive component whereas a set of hosts is associated with a composite component. This set must be a subset of the set of hosts associated with the including component. By default, the placement set of a composite component is inherited from the including component.

At execution time, each instance of a composite component maintains locally information about the configuration of its subcomponents. Hence, a distributed composite component c distributed over a set of hosts respects the following properties:

-The provided and required interfaces of c are accessible on all the hosts h i of .

-Let c be a composite component that contains a primitive subcomponent p. There exists a single host h i on which p executes. For every host h j ∈ ( j i), there exits c j , an instance of c on h j . Each c j holds a remote reference to p (in a proxy).

Example

We give in this section an example of an application made of hierarchical components and we detail how it can be distributed on a given set of hosts.

Figure 2 depicts the architecture of a photo application that allows the user to search for a number of photos in a repository and to build a diaporama with the selected photos. The top-level composite component (PhotoApp) includes a generic component devoted to document searching (DocumentSearch). This component is also a composite component (taken off the shelf); it is composed of a DocumentFinder and a DocumentBuffer. The primitive DocumentFinder component provides an interface for issuing more or less complex requests based on the names of documents, on their subjects or some other meta-information, and for selecting the corresponding documents from a given set of documents (a repository). The selected documents are passed to a Document-Buffer. Apart from an interface for adding new documents, the primitive Document-Buffer component provides an interface for sorting and extracting documents. This provided interface and the one of DocumentFinder are accessible as provided interfaces of the DocumentSearch component. Finally, the DocumentSearch component is bound to a PhotoRepository component that constitutes the specialized document repository and a DiapoMaker component which allows the selected photos to be assembled in a parameterizable diaporama. Consider that the photo application is meant to be usable from any of the five machines owned by the user (hosts h 1 to h 5 ), in a dynamic network similar to the one depicted in figure 1. Hence, the target set of hosts associated with the PhotoApp component is {h 1 , h 2 , h 3 , h 4 , h 5 }. A subset of these hosts is dedicated to the distributed execution of the composite component DocumentSearch, say {h 1 , h 2 , h 3 }, h 4 and h 5 being excluded for licence reasons for example. Moreover, some constraints on the required resources result in the following placement of the primitive components (see section 4 for details): DocumentFinder on h 1 , DocumentBuffer on h 2 , PhotoRepository on h 4 and DiapoMaker on h 5 .

At runtime the membranes of the composite components are maintained on each of their target hosts. A membrane contains the interfaces of the component as well as the description of its architecture (subcomponents and bindings). The instances of components (primitive or composite) that are not present are represented by proxies. Note that for a primitive component, the proxy is linked to the distant (single) instance of this primitive whereas for a composite component, the proxy is linked to one distant instance of the (partially replicated) membrane.

Figure 3 summarizes the placement of the components and shows the runtime entities (architectural information and instances) maintained on h 1 and h 4 for our PhotoApp example.

Support for disconnections

The replication of a composite component eases the access to the services it implements as it makes possible to use its provided interfaces on each host. However, because of network disconnections, from a given site, access to a remote component can be interrupted. Consequently, a method invocation in this case may raise some kind of a network exception. This problem is not specific to our approach but appears as soon as remote references are used, that may point to unaccessible components at any time. In a context of hierarchical components, the technique that consists in deactivating a component as soon as one of its required interface is unbound is very penalizing as a single disconnection will end up by ricochet with the deactivation of the top-level component, that is the deactivation of the entire application. In the dynamic environments we target, where disconnections are frequent, the application is likely to be rarely usable.

We address this problem in the following two ways:

-We introduce the notions of active and non active interfaces. We maintain the state (active or not) of an interface according to the accessibility of the component's instance it is bound to. Moreover, we add a control interface to components to allow introspection on the state of its provided and required interfaces. -We allow the execution of a component even if some of its interfaces are not active.

On the PhotoApp example, if a disconnection occurs between h 1 and h 4 , the Pho-toRepository component is no longer accessible from h 1 . The disconnection is detected by a dedicated monitor, and consequently, the required interface of the DocumentSearch component is deactivated. This triggers the deactivation of the corresponding required interface of the DocumentFinder and then of its provided interface. However, the second interface of DocumentSearch (the one bound to DiapoMaker) can remain active as the DocumentSearch component is still accessible. Globally the application is still usable, although in a degraded mode, as diaporamas can still be built from the document buffer.

Notice that this approach has an obvious impact on the programming style required when developing components, as the state of an interface should be tested before invoking methods on this interface. Indeed, the uncertainty of the accesses to needed (or required) services -inherent to the targeted dynamic platforms-enforces adaptable code. The provision for tools to introspect on the availability of the interfaces is a minimal answer that should be complemented by other facilities for describing or applying, for example, adaptation strategies. This involves research at language level and middleware level that is out the scope of the presented work.

Deployment Specification

When considering the deployment of distributed components, the key issue is to build a mapping between the component instances and the hosts of the target platform. This task implies to have some knowledge not only about the identity of the hosts involved in the deployment phase, but about the characteristics of each of them as well. Moreover, for a hierarchical component-based application, every component instance at each level of the hierarchy has to be handled.

At design-time, the designer is unlikely to know where to deploy each component regarding resource availability. This motivates the need to differ this task at runtime. We propose to add a deployment aspect to an existing architecture description language (such as [START_REF]xacme: Acme extensions to xarch[END_REF][START_REF] Dashofy | An infrastructure for the rapid development of xml-based architecture description languages[END_REF]).This will allow the description of the resource properties that must be satisfied by a machine for hosting a specific component.

We propose an extension to ADLs that makes possible the description of the target platform in a declarative way. The language we propose is purely declarative and descriptive and has a similar objective to the language described in [START_REF] Dearle | A framework for constraint-based deployment and autonomic management of distributed applications[END_REF]. It is not mandatory to give an explicit name or address of a target machine: the placement of components are mainly driven by constraints on the resources the target host(s) should satisfy. The choice of the machine that will host a component will be made automatically at runtime (during the deployment).

The description of the resources that the target platform must satisfy is defined in a deployment descriptor in which references to component instances (defined in the architecture descriptor) can be made. For each component, a deployment context is defined. Such a context lists all the constraints that a hosting machine has to satisfy. If these constraints are associated with a primitive component, one host will be authorized to instantiate this component whereas several hosts may be selected for hosting the membrane of a composite component, in accordance with our distribution model.

There are two types of constraints that can be defined in a deployment context: resource constraints (ResCst) and location constraints (LocCst). ResCsts allow hardware and software needs to be represented. Each of these constraints defines a domain value for a resource type that the target host(s) should satisfy. LocCsts are useful to drive the placement choice of a component if it occurs that more than one host is applicant.

<component name=" DocumentSearch" > <component name=" DocumentFinder" > <deployment-c o n t e x t > < resource-c o n s t r a i n t > 5 <cpu f r e q = " 1 . 2 " u n i t ="GHz" operator =" min " / > </ resourcec o n s t r a i n t >

10

< l o c a t i o nc o n s t r a i n t > < t a r g e t varname=" x " / > </ l o c a t i o nc o n s t r a i n t > </ deployment-c o n t e x t > </ component> 15 <component name=" DocumentBuffer " > <deployment-c o n t e x t > <resource -c o n s t r a i n t > <memory f r e e ="200" 20 u n i t ="MB" operator =" min " / > </ resourcec o n s t r a i n t > < l o c a t i o nc o n s t r a i n t > < t a r g e t varname=" y " / > 25 </ l o c a t i o nc o n s t r a i n t > </ deployment-c o n t e x t > </ component> <deployment-c o n t e x t > 30 < l o c a t i o nc o n s t r a i n t > <operator name=" a l l d i f f " > <arg varname=" t h i s . DocumentFinder . x " / > <arg varname=" t h i s . DocumentBuffer . y " / > </ operator 35 </ l o c a t i o nc o n s t r a i n t > <deployment-c o n t e x t > </ component> (a) <component name=" PhotoApp" > <component name=" DiapoMaker " > <deployment-c o n t e x t > 40 <cpu f r e q = " 1 . 5 " u n i t ="GHz" operator =" min " / > <memory f r e e ="50" d i r e c t o r y = " / home / " u n i t ="MB" 45 operator =" min " / > </ resourcec o n s t r a i n t > </ deployment-c o n t e x t > </ component> 50 <component name=" PhotoRepository " > <deployment-c o n t e x t > <resource -c o n s t r a i n t > <memory f r e e = " 1 " u n i t ="GB" d i r e c t o r y = " / home / " 55 operator =" min " / > </ resourcec o n s t r a i n t > </ deployment-c o n t e x t > </ component> 60 <component name=" DocumentSearch" > < l o c a t i o n c o n s t r a i n t > <operator name=" exclude " > <arg value =" e g i l s a y " / > <arg value =" p a r v a t i " / > 65 </ operator > </ l o c a t i o n c o n s t r a i n t > </ component> <deployment-c o n t e x t > 70 < l o c a t i o n c o n s t r a i n t > < t a r g e t hostname =" ambika " / > < t a r g e t hostname =" d a k i n i " / > < t a r g e t hostname =" mafate " / > < t a r g e t hostname =" e g i l s a y " / > 75 < t a r g e t hostname =" p a r v a t i " / > <deployment-c o n t e x t > </ component> For every component, adding an XML tag corresponding to a resource type (e.g. cpu, memory) specifies a constraint on this resource the target host has to verify.

Location constraints are declared within the location-constraint element. The target element defines the set of hosts among which our runtime support will have to choose. Hosts can be represented in two ways: (1) by their hostname if their identity are known before the deployment or (2) by a variable. Such a variable can be used at the composite level to control the placement of components. This feature is achieved by the use of the operator element. This element allows relations between variables to be expressed. For example, in descriptor (a), the DocumentFinder component is said to be deployed on host x and DocumentBuffer on host y. Constraining DocumentFinder and Document-Buffer to be on two distinct hosts is achieved by using the alldiff operator that declares x to be different from y. For a primitive component, at most one variable can be declared (because a primitive component will be placed on an unique host). Several variables can be used for a composite component, which is physically distributed over several hosts.

When composing the application, it is possible to use only variables. Then, the definition of the target platform is made at the first level of the hierarchy (for the component PhotoApp on the example) by adding the list of the machines that will be involved in the deployment (lines 71-75 on Figure 4). During the deployment, as it is detailed in next section, this set of machines, together with the location constraints will be inherited by the sub-components.

Deployment Process

Overview of the Propagative Deployment

Because of the dynamism of the network on which we deploy our applications, it is not possible to base a deployment on a full connection of the different hosts. We are interested in a deployment that will allow an application to be activated progressively, that is, part of its provided services can be put at disposal even if some machines that are required for the "not yet" installed components, are not available. As soon as these machines become connected, the deployment will go along. Moreover, resource changes on any host may yield the deployment of components although is was not possible before. The deployment we present in this paper is thus asynchronous as it may not be possible to deploy every component immediately.

Once the architecture descriptor and the deployment descriptor have been defined, the deployment phase we consider in this article consists in choosing a target host for every component of the architecture. This selection has to be made according to the deployment context associated with every component. Indeed, the selected machine has to satisfy all the resource constraints and this machine must not contradict the location constraints. In the case of a primitive component, a single host has to be selected among several applying machines. For a composite component, the number of applicants can be greater than the set of machines over which this composite component has to be distributed. Controlling the selection of the target hosts is essential to guarantee the consistency of the application. Indeed, in a dynamic network where islands of machines may appear, we must avoid inconsistent decisions in two different islands. For example, we have to ensure that two distinct machines from two islands will not be selected for the hosting of the same primitive component.

In the following we present the general propagative deployment algorithm in two steps. First, we consider a fully connected environment. This will help us to focus on the resolution of the constraints expressed in the deployment descriptor and to describe a possible distribution of the instantiation tasks (thus the selection of target hosts) within a hierarchical architecture. Then we present the complete propagative deployment in a dynamic network where the main difficult aspect is to ensure a unique decision regarding component instantiation.

Deployment in a Connected Network

We consider in this section a fully connected network composed of a finite set of machines. Each machine is identified and no disconnection may occur. The propagative deployment in such a network consists in diffusing the architecture descriptor and the deployment descriptor to all the machines that are listed at the top level of the application (with the XML target element).

Then, once a machine has received these descriptors, a recursive process is launched in order to select the components that can be hosted on this machine. The main steps of this process for a machine m i , for a component C are the following:

1. machine m i checks if it satisfies the location constraints associated with C. This corresponds to verifying if m i belongs to the set of the target hosts (see XML target element). If the m i is not concerned by the deployment (instantiation) of component C, the process returns for this component, else, 2. machine m i has to launch probes corresponding to the resource constraints of C (e.g. CPUProbe, MemoryProbe). If at least one probe returns a value violating a resource constraint (e.g. not enough free memory available), the process returns, else, 3. machine m i declares itself as an applicant host for component C and a collective decision has to be made. Indeed, more than one host may apply and if C is a composite component, it may have subcomponents with location constraint such as x y 4. once a choice has been made, all the applicants are informed of the value of the free variables and of the fact that they are authorized (or not) to instantiate component C. The process stops for hosts that are not authorized. For the others, 5. if C is a composite component, the process is performed recursively for all the subcomponents of C

In a connected network, there is no difficulty to make the collective decision described in point 3. We could for example choose before the deployment a machine S whose role is to decide a host among applicants. In this case, when a host h satisfies all the constraints attached to a component and thus becomes applicant, h announces itself to S and waits for a decision. However we prefer the approach of [START_REF] Quéma | Asynchronous, hierarchical and scalable deployment of component-based applications[END_REF] where a deployment controller, which is in charge of well-defined tasks of the deployment, is defined for each composite component of the hierarchy. The main reason for such a distribution of the deployment controllers is scalability. Indeed, with this approach, parts of the application can be deployed independently according to its topology. Thus, we define a machine S i per composite component of the hierarchy. This machine is responsible for the decision-making of its direct sub-architecture, i.e. it must choose among applicants those who don't contradict the location constraints. Applicants must be informed of the results. Thus, after a decision, each representative S i sends to the applying hosts a new deployment descriptor which is updated with the new location information, i.e. the actual name of the machine hosting a specific component is added to the location constraints. Indeed, before the deployment, no explicit machine name is given and variables can be used to indicate applicant machines. For example, if the machines ambika and dakini are respectively attributed to components DocumentFinder and DocumentBuffer, the following lines are added to descriptor (a): / / r e p l a c e l i n e 1 1 by : / / r e p l a c e l i n e 2 3 by : < t a r g e t varname =" x " v a l u e =" ambika " / > < t a r g e t varname =" y " v a l u e =" d a k i n i " / >

As a consequence of the decision, some components can be instantiated. In the case of composite components, the deployment process (local evaluation, applicant announcement, decision-making) goes along recursively.

However, it may be possible that a representative machine could not find any placement solution (because no combination of applicants fullfills all the location constraints). In order to propose to the representative a new possible placement, a machine that newly satisfies some resource constraints (for uninstalled components) declares itself as applicant.

Deployment in a Dynamic Network

The previous section, with the assumption of a fully connected network, has highlighted two main ideas of the propagative deployment: (1) each host does the evaluation of the constraints attached to the components and (2) the decision making is distributed over several machines, each of them representing a composite component of the application.

In a dynamic network all the machines may not be connected at the same time. In this kind of network, islands may exist and communication paths between machines may disappear. In such an environment, a deployment based on a full connection of the different machines at the same time is not conceivable. We may want to start the deployment (i.e. the instantiation of parts of the components and thus to put parts of the services offered by the application at disposal) while some machines may be disconnected or inaccessible. The component model presented previously (see section 2) allows an application to run in a degraded mode but the main difficulty here is to deal with the unicity of the instantiation of the-possibly statefull-components, which is difficult to ensure in a dynamic network. Indeed, we must avoid conflicting decision to be made in the different islands that may exist in such an environment. On one hand, a machine that represents a composite component, cannot be selected before the deployment, as in a fully connected network, since this machine may not be connected. On the other hand, if we let each of the machines that host the same replicated composite component make a decision, we cannot guarantee that in two different islands contradictory instantiations may not be performed. We tackle this difficulty by considering the consensus problem: a set of machine has to decide on a same value regarding the representative of composite components.

We use the results of [START_REF] Mostéfaoui | Condition-based consensus solvability: a hierarchy of conditions and efficient protocols[END_REF], in which the requirements of the consensus problem are relaxed. The authors have identified conditions for which there exists an asynchronous protocol that solves the consensus problem despite the occurrence of t process crashes. We define the consensus to select, for each composite that is replicated on several machines, a representative host that will make future decisions on where the direct subcomponents have to be instantiated.

Algorithm

The main steps of the algorithm described in the previous section are not modified. The only change concerns the designation of a representative host for each node of the hierarchy. We use the algorithm of [START_REF] Mostéfaoui | Condition-based consensus solvability: a hierarchy of conditions and efficient protocols[END_REF] to elect such a representative and to build a common view of the placement of the components.

The consensus algorithm requires that a majority of machines can be reached among the target hosts of the composite component. This majority is not the same depending on the composite component. For example, the photo application is distributed over {h 1 , h 2 , h 3 , h 4 , h 5 }, as a consequence, the majority is reached when at least three of these machines are in the same island. Whereas for the composite DocumentSearch component, which is distributed over {h 1 , h 2 , h 3 }, the consensus is possible when an island, composed of at least {h 1 , h 2 }, {h 1 , h 3 } or {h 2 , h 3 }, is formed.

The consensus-based algorithm consists in:

1. ensuring that the selection of a host for a representative composite component is possible if an island is composed of a majority of machines, 2. selecting a machine S i for the future instantiation decisions for each composite component of the hierarchy 3. updating the deployment descriptor with the identifier of the selected machine.

Points 1 and 3 guarantee that if a new island composed of a majority of machines is created, there is at least one machine that possesses the most recent version of the deployment descriptor. Thus no contradictory decision can be made in this island.

The consensus may not terminate (e.g. the number of hosts within an island may not be sufficient). In order to prevent this situation, we allow a newly connected machine to participate in this consensus. This is achieved by periodically broadcasting a message asking if a consensus is still in progress. In that case the newly connected machine collects the data that have already been exchanged between the other machines and proposes a value that can make the consensus evolve.

Once a representative composite component is chosen, due to the dynamism of the network, this composite may be in a non-majority island during a more or less amount of time. In this case, if an instantiation decision is made, it cannot decide any more whereas it may exists an other island in which a consensus can be reached. Thus, if such a decision has to be made and a majority of machines composes the islands, a new representative machine is selected and the deployment descriptor is updated. No conflict will arise later, i.e. when the older representative belongs to a new majority islands. Indeed in such an island, it exists at least one machine that possesses the most recent version of the deployment descriptor, thus during the consensus, the older representative will learn the existence of the new one.

Implementation Status

The propagative deployment presented in this paper is based on a constraint basedlanguage for the description of the placement of components according to resource requirements. Our current prototype has been implemented using Julia, a Java implementation of the Fractal component model [START_REF] Bruneton | An Open Component Model and its Support in Java[END_REF]. The features of the ADLs described in section 3 have been implemented as new modules into the Fractal Architecture Description Language. Deployment descriptors can be specified graphically through an extension of FractalGUI.

In order to evaluate the constraints defined in the deployment descriptor, we have to collect information about resources on every host. We use D-Raje [START_REF] Mahéo | A Java Middleware Platform for Resource-Aware Distributed Applications[END_REF] -a framework developed in our team, dedicated to the observation of distributed system resources in Java-to define specific probes related to resource constraints. D-Raje is also used to model and to monitor the state of physical links between hosts. A disconnection can then be captured with the result that bindings between components are withdrawn and the corresponding interfaces are deactivated. Further details can be found in [START_REF] Hoareau | Distribution of a Hierarchical Component in a Non-Connected Environment[END_REF].

We are currently implementing a distributed test platform in order to tune our consensus algorithm considering parameters such as the numbers of hosts and the frequency of disconnections.

Related work

The main aspects developed in this paper are related to a distribution scheme for hierarchical components on dynamic networks and to a resource-aware and propagative deployment.

Many works have taken into account a context-aware deployment, that is, the placement of components onto hosts according to some resource requirements. A formal statement of the deployment is given in [START_REF] Mikic-Rakic | Software architectural support for disconnected operation in highly distributed environments[END_REF] and a set of algorithms that improve mobile system's availability is presented. In [START_REF] Li | A platform architecture to support the deployment of distributed applications[END_REF] the authors propose a deployment configuration language (DCL) in which properties on the target hosts can be expressed. The deployment considered in this work extends the Corba Component Model, which is a flat component model. In [START_REF] Dearle | A framework for constraint-based deployment and autonomic management of distributed applications[END_REF], the authors present the Deladas language that also allows constraints to be defined on hosts and components. A constraint solver is used to generate a valid configuration of the placements of components and reconfiguration of the placement is possible when a constraint becomes inconsistent. But this centralized resolution is not suited to the kind of dynamic network we target. Moreover, the current version of Deladas does not consider resource requirements. These abovementioned works aim at finding an optimum for the placement problem of components. This aspect is not one of our objectives. Indeed, due to the dynamism of the environment, it is hardly feasible to define a quiescent state that will allow our consensus algorithm to decide on an optimal placement. Moreover, the solutions proposed are centralized.

In [START_REF] Mikic-Rakic | Architecture-level support for software component deployment in resource constrained environments[END_REF] a decentralized redeployment is presented. The configuration to be deployed is available on every host involved in the deployment. A local decision can then be made according to the local subsystem configuration state. However the choice of the components' location is made before the deployment process. The works presented in [START_REF] Quéma | Asynchronous, hierarchical and scalable deployment of component-based applications[END_REF] on the deployment of hierarchical component-based applications is probably the closest to ours'. The authors describe an asynchronous deployment and use the hierarchical structure of the application in order to distribute deployment tasks. In the solution developed by the authors, a deployment controller is statically chosen and defined in the deployment descriptor. In our approach we could not decide at design-time which machine will host such a controller. The approach proposed by the authors focuses on functional constraints and thus resource requirements have not been taken into account.

Conclusion

This paper has presented a support for deploying and executing an application built with hierarchical components on an heterogeneous and dynamic network. The main contribution of this work is that it attempts to take into account a challenging distributed target platform characterized by the heterogeneity and the volatility of the hosts, volatility that may result in the fragmentation of the network.

A distribution method has been proposed for hierarchical components. Composite components are made accessible on a set of hosts whereas each primitive component is localized on a single host. Besides, via the notion of active interface, we allow a component to operate in a degraded mode in order to account for network disconnections without making the entire application unusable.

We have presented a purely descriptive language for specifying deployment descriptors that allow for a context-aware deployment. This language is meant to extend some existing ADL. A deployment descriptor allows the description of the resource needs of a component and some placement constraints.

The deployment process we have defined is a propagative one. The instantiation and the activation of a component is performed as soon as some resources that meet its needs are discovered. This early activation is possible as some of its interfaces can remain inactive (the component then executes in a degraded mode).We have designed an algorithm that supports this propagative deployment in a dynamic network. The scalability of the process is ensured by the distributed and hierarchical organisation of the control. Moreover, we have presented a distributed consensus that guarantees that the location constraints are satisfied even in the context of a partitioned network.

The main direction of our future work consists in taking into account the possible modifications on the resources' availability after some component instantiations have been made. Indeed, even if we can respect for example a memory constraint on the instantiation of a given primitive component, the memory conditions may change that invalidates the choice afterwards. The mechanisms we have implemented in our deployment algorithm could be adapted for solving this problem, provided the component can be safely stopped. An autonomic deployment could thus be defined.

Fig. 2 .

 2 PhotoApp DocumentSearch

Fig. 4 .

 4 Fig. 4. Deployment descriptor