Search

In this work, we consider hard real-time applications scheduled upon heterogeneous multiprocessor platforms. The originality of this study is to consider multi-mode real-time applications (software aspects) and reconfigurable-heterogeneous hardware platforms (composed of CPUs, GPUs, FPGAs...). Our approach is based on a multi-mode protocol, for mode-dependent tasks upon reconfigurable hardware. The goal is to handle predictable switches between different task sets and different hardware settings. The novelty here is the dynamic hardware and software reconfigurability. First, we propose a formal model of the applications and reconfigurable hardware platforms. We then propose and prove correct a mode change protocol. We propose in particular a validity test for the verification of the timing constraints of the application --- including the time allowed to complete a mode change. We also perform a complete evaluation. We study the theoretical complexity of the protocol, use a simulation to evaluate the efficiency of our solution, and finally propose a competitive analysis of our protocol to prove that it is 2-competitive.

We present an identity-based encryption (IBE) scheme in composite-order bilinear groups with essentially optimal parameters: the ciphertext overhead and the secret key are one group element each and decryption requires only one pairing. Our scheme achieves adaptive security and anonymity under standard decisional subgroup assumptions as used in Lewko and Waters (TCC ’10). Our construction relies on a novel extension to the Deja Q framework of Chase and Meiklejohn (Eurocrypt ’14).

The Service Oriented Architecture (Soa) paradigm supports the assembly of atomic services to create applications that implement complex business processes. Since ''real-life'' processes can be very complex, composition mechanisms inspired by the Separation of Concerns paradigm (e.g. features, aspects) are good candidates to support the definition and the upcoming evolutions of large systems. We propose Adore, ''an Activity meta-moDel supOrting oRchestration Evolution'' to address this issue. The Adore meta-model allows process designers to express in the same formalism business processes and fragments of processes. Such fragments define additional activities that aim to be integrated into other processes and adequately support their evolution. The underlying logical foundations of Adore allow the definition of interference detection rules as logical predicate, as well as the definition of consistency properties on Adore models. Consequently, the Adore framework supports process designers while they design and then apply evolutions on large processes, managing the detection of interferences among fragments and ensuring that the composed processes are consistent and do not depend on the order of the composition.

Analytic proof calculi are introduced for box and diamond fragments of basic modal fuzzy logics that combine the Kripke semantics of modal logic K with the many-valued semantics of G\"odel logic. The calculi are used to establish completeness and complexity results for these fragments.

In this paper, we introduce a new partial consistency for constraint networks which is called Structural Consistency of level w and is denoted w-SC consistency. This consistency is based on a new approach. While conventional consistencies generally rely on local properties extended to the entire network, this new partial consistency considers global consistency on subproblems. These subproblems are defined by partial constraint graphs whose tree-width is bounded by a constant w. We introduce a filtering algorithm which achieves w-SC consistency. We also analyze w-SC filtering w.r.t. other classical local consistencies to show that this consistency is generally incomparable although this consistency can be regarded as a special case of inverse consistency. Finally, we present experimental results to assess the usefulness of this approach. We show that w-SC is a significantly more powerful level of filtering and more effective w.r.t. the runtime than SAC. We also show that w-SC is a complementary approach to AC or SAC. So we can offer a combination of filterings, whose power is greater than w-SC or SAC.

Since the pioneer works of composer Tom Johnson, many questions arise about block designs. The aim of this paper is to propose some new graphical representations suitable for composers and analysts, and to study the relationship between pcsets and small t-designs. After a short introduction on the combinatorial aspects of t-designs, we emphasize the musical perspectives open by these mathematical objects.

The paper investigates information sharing communities. The environment is characterized by the anonymity of the contributors and users, as on the Web. It is argued that a community may be worth forming because it facilitates the interpretation and understanding of the posted information. The admission within a community and the stability of multiple communities are examined when individuals differ in their tastes., Le papier étudie la formation de communautés partageant des informations dans un environnement qui est caractérisé par l'anonymat des utilisateurs et contributeurs à l'instar du Web. L'analyse est basée sur la valeur de l'information au sens de Blackwell (1953). Nous examinons le choix des critères d'admission dans une communauté et la stabilité des communautés dans un modèle de divergence de goûts.

In 1997, B. Selman and H. Kautz proposed a series of 10 challenges. One of them concerned the design of a practical stochastic local search procedure for proving unsatisfiability (Challenge 5). Today, more than 10 years later, only few attempts were led to address this challenge, in spite of the great number of incomplete methods for proving satisfiability. In this paper, we propose a two steps algorithm for proving unsatisfiability of CNF formulas\footnote{supported by ANR UNLOC project n\ensuremath{^\circ} BLAN08-1\_328904}. The first step consists in detecting $\ssi$-gates greedily. At the same time, a polynomial algorithm is used to eventually prove the unsatisfiability of the extracted set of equivalency-gates. We show that this method outperforms the existing ones on some classes of instances. This method is then extended to other logical functions (and-gates and or-gates).

Synchronous products of (max, +) automata are introduced as multi-event (max,+) automata (which correspond to a class of timed automata with serveral clocks) and their behaviour is studied. A formula for the behavior of synchronous product is obtained.

National audience; Cet article s'inscrit dans le cadre de l'étude des systèmes complexes via la modélisation et la simulation informatique. Nous pensons qu'il est parfois nécessaire de faire interagir plusieurs modèles pour simuler un phénomène. Dans le cas des technologies des réseaux dynamiques (réseaux P2P, réseaux mobiles Ad Hoc), le comportement des usagers et le fonctionnement des réseaux s'influencent mutuellement. Nous proposons une approche de modélisation et un outil de simulation couplant un modèle d'utilisateurs - basé sur le paradigme multi-agents - et un modèle de réseaux dynamiques. Nous discutons, au travers d'un cas d'étude particulier, des avantages, des problématiques soulevées et des limitations d'une telle approche. Nous montrons que cette démarche de modélisation apporte un niveau de précision et une flexibilité élevés.

National audience; Les circuits reconfigurables FPGA ont désormais une capacité telle qu'ils peuvent être utilisés à des tâches d'accélération de calcul en virgule flottante. La littérature (et depuis peu les constructeurs) proposent des opérateurs pour les quatre opérations. L'étape suivante est de proposer des opérateurs pour les fonctions élémentaires les plus utilisées. Parmi celles-ci, nous proposons des architectures dédiées pour l'évaluation des fonctions exponentielles, logarithme, sinus et cosinus, et étudions les compromis possibles. Pour chacune de ces fonctions, un seul de ces opérateurs surpasse d'un facteur dix les processeurs généralistes en terme de débit, tout en occupant une fraction des ressources matérielles du FPGA. Tous ces opérateurs sont disponibles librement sur http://www.ens-lyon.fr/LIP/Arenaire/.

National audience; Les architectures orientées services (AOS) se sont imposées pour la construction d'applications web grâce à l'élaboration de standards ouverts et compatibles avec les technologies web existantes. Le nombre de services sur le web grandit chaque jour et les développeurs d'applications sont souvent confrontés au problème de choisir parmi les services disponibles. Cet article présente un modèle de classement de services fondé sur des scores d'importance qui reflètent pour chaque service son activité et sa contribution à la qualité d'autres services. Nous décrivons également un algorithme distribué pour le calcul de ces scores exploitant les connexions déjà existantes entre services. Le modèle et les algorithmes ont été validés par simulation.

The numerical simulation of air flow in a building or a house is certainly a very challenging field of engineering applications. The objectives differ from one application to the other, ranging from the optimization of air conditioning systems in buildings to the study of the propagation of harmful products via the air conditioning system. In this paper, we address the problem of coupling the Navier-Stokes equations for incompressible fluids and a temperature equation. To solve this problem in 3d, we use an anisotropic mesh adaptation strategy. The meshes are generated by a local remeshing techniques based on an anisotropic version of Delaunay kernel. The method is fairly general and applies to other cases as well. We illustrate this problem with an example showing the heating of the last floor of a furnished house.

In most works on negotiation dialogues, agents are supposed to be ideally honest. However, there are many situations where such a behaviour cannot always be expected from the agents (e.g. advertising, political negotiation, etc.). The aim of this paper is to reconsider the role of deceitful arguments in argumentation frameworks. We propose a logical tool for representing and handling deceitful arguments in a dialogue between two formal agents having to face their respective knowledge and trying to convince each other. X-logics, a nonmonotonic extension of classical propositional logics, is used as the background formalism for representing the reasoning of the agents on arguments. Starting from a previous work dedicated to the generation of new arguments, we propose to define the notion of lie as a new kind of possible agent's answer. Finally, we describe the way an agent may trick and how the other agent may detect it

International audience; In an earlier context, we have proposed a metadata model for service description. It describes service by three levels of properties: static properties (like its provider, its location and so on), behavior and interface. We have used ontologies in order to index and store the properties provided by this model. We have developed and implement tools which constitute a trader based on ontologies to discover a service by querying its three levels of description from ontologies. Based on the metadata model that we have proposed, we propose in this paper, an approach which allows the client to compose and to combine services by using our trader. This approach defines three models of composition : static, semi_dynamique and dynamique. These models allow the client to benefit from the functionalities of more than one service and to combine them at run-time and at compile-time to get novel services which provide novel functionalities.

Nowadays, materialized views are increasingly being supported by a variety of commercial DBMS to speed up query response time. This technique is also very useful in dataware-housing for optimizing OLAP queries. However, most existing view selection methods are of static nature. Moreover, none of these methods have considered the problem of dematerializing the previously materialized views. This paper deals with the problem of dynamic view selection and the pending issue of removing materialized views in order to replace the less beneficial views with more beneficial views. More precisely, we have designed and implemented a view selection method, including a polynomial algorithm, to decide which views to materialize according to statistic metadata.

Ce document est une introduction rapide au domaine du contrôle des sytèmes temporisés

Many real-time systems must simultaneously handle hard real-time constraints and Quality of Service constraints. Thus, a performance criterion must be optimized for some tasks while meeting all deadlines for hard real-time tasks. For that purpose, we present a generic Branch & Bound method dedicated to hard real-time fixed-priority schedulers. Our approach is based on a generic algorithm that defines common functions to any performance criteria. Only few functions need to be specialized to deal with a specific criterion. We then present such a specialization for minimizing the weighted average response time of tasks.

In 1974, E.W. Dijkstra defined self-stabilization as the property for a distributed sys- tem to recover by itself a correct behavior in a finite number of steps, starting from any initial state. Thus, self-stabilization is a simple and efficient way to tolerate transient faults or fail- ures. This paper surveys works that propose self-stabilizing solutions to problems arising in Computer Networks, such as routing and transport layers, or network control protocols. We also review techniques to design self-stabilizing protocols, and mechanisms that reduce the sta- bilization time when the number of hitting faults is small. MOTS-CLES :autostabilisation, reseaux, protocoles, routage, communications point a point, con- trole reparti, transformation automatique.

International audience; Information visualization needs benchmarks to carry on. A benchmark is aimed at comparing information visualization techniques or systems. A benchmark is made of a dataset, a list of tasks mostly based on finding facts about the dataset, and a list of interesting or important findings about the datasets (the nuggets to find). For the second year, we are organizing the InfoVis Contest aimed at collecting results for benchmarks. We describe here the main lessons we learned.

We study here a CSP decomposition method introduced in [P. Jegou (1990)] and called cyclic-clustering. While [P. Jegou (1990)] only presents the principles of the method, This work explains how this method can be made operational by exploiting good properties have triangulated induced subgraphs. After, we give formal results, which show that cyclic-clustering proposes a time-space trade-off w.r.t. theoretical complexities. Finally, we present some preliminary experiments, which show that cyclic-clustering may be efficient in practice.

National audience; We present in this paper a new code generator, called O'Jacaré, to interoperate between Java and Objective Caml through their object model. O'Jacaré defines a basic IDL (Interface Definition Language) for classes and interfaces description to communicate from Objective Caml to Java. For communications from Java to Objective Caml we add a callback mechanism. The implementation is based on each language low-level interfaces (Java Native Interface for Java and external for Objective Caml) and uses an extended version of the camljava library. O'Jacaré generates all needed wrapper classes and enables static typechecking in both worlds. Although the IDL is an intersection from these two object models, O'Jacaré allows to combine all features from both.

International audience; This work addresses the analysis and validation of CHP specifications for asynchronous circuits, using property verification tools. CHP semantics, initially given in terms of Petri Nets, are reformulated as labeled transition systems. Circuit specifications are translated into an intermediate format (IF) based on communicating extended finite state machines. They are then validated using the IF environment, which provides model checking and bi-simulation tools. The direct translation must be optimized to delay state explosion. Performance studies are reported.

Cet article soutient le point de vue que les Environnements Informatises d'Apprentissage Humain (EIAH) ne considerent pas assez l'enseignant comme un utilisateur potentiel distinct de l'apprenant. Aussi, le neologisme “preceptoriel” est introduit pour decrire des EIAH ayant une approche centree sur le professeur.