Search

International audience; Public data availability in cloud-hosted databases raises interests in systems providing multi-cloud querying capabilities. Since data access in this context induces monetary costs, we suggest a method to compute SLAs for multi-cloud queries. It consists in decomposing queries into a directed graph of maximal sub-queries per provider, and finding a financially cheapest execution plan. This method yields SLAs with monetary costs lower than a download-all approach, granted that inter-provider data transfers are minimised.

The Modelica mathematical modeling language, based on Differential Algebraic Equations (DAE), brings several specific issues that do not exist with modeling languages based on Ordinary Differential Equations. The main problem is the determination of the differentiation index and latent equations. Prior to generating simulation code and calling solvers, the compilation of a Modelica model requires a structural analysis step, which reduces the differentiation index to a level acceptable by numerical solvers. The Modelica language allows hybrid models with multiple modes, mode-dependent dynamics and state-dependent mode switching. These Multimode DAE (mDAE) systems are much harder to deal with. The main difficulties are (i) the combinatorial explosion of the number of modes, and (ii) the correct handling of mode switchings. The focus of this report is on the first issue, namely : How can one perform a structural analysis of an mDAE in all possible modes, without enumerating these modes? A structural analysis algorithmfor mDAE systems is presented, based on an implicit representation of the varying structure of an mDAE. It generalizes J. Pryce’s structural analysis method to the multimode case and uses Binary Decision Diagrams (BDD) to represent the mode-dependent structure of an mDAE. The algorithm determines, as a function of the mode, the set of latent equations, the leading variables and the state vector. This is then used to compute a mode-dependent block-triangular decomposition ofthe system, that can be used to generate simulation code with a mode-dependent scheduling of the blocks of equations.This report is an extended version of the homonym paper, published in the proceedings of the HSCC’20 conference.; Le langage de modélisation mathématique Modelica, basé sur les systèmes d'équations algebro-différentielles (Differential Algebraic Equations, ou DAE), présente des difficultés qui n’apparaissent pas dans la modélisation à base d'éequations différentielles ordinaires.Le problème principal consiste à déterminer l’indice de différentiation et les équations latentes d’un système. Lors de la compilation d’un modèle Modelica, un prérequis `à la génération de code de simulation et `a l’appel de solveurs est une étape d’analyse structurelle, qui réduit l’indice de différentiation à un niveau acceptable par les solveurs numériques.Le langage Modelica permet l’écriture de modèles hybrides, ou multimodes, dont la dynamique dépend du mode, et où les changements de mode sont conditionnés par les variables d’état. Ces DAE multimodes (mDAE) sont considérablement plus difficiles `a traiter, les obstacles principaux étant (i) l’explosion combinatoire du nombre de modes, et (ii) la prise en charge des changements de mode.Ce rapport se focalise sur le premier point: Comment effectuer l’analyse structurelle d’une mDAE en prenant en compte tous ses modes, mais sans énumérer ces derniers ? Un algorithme d’analyse structurelle de systèmes de mDAE est proposé; il s’appuie sur une représentationimplicite de la structure variable de la mDAE considéŕée. La méthode présentée généralise celle de Pryce au cas multimode, et utilise des Diagrammes de Décision Binaire (Binary Decision Diagrams, ou BDD) pour représenter la structure variable d’une mDAE. L’algorithme détermine l’ensemble des équations latentes, les variables de tête et le vecteur d’état, en tant que fonctions du mode. Ces informations permettent ensuite de décomposer le système en une forme triangulaire par blocs dépendant du mode. Cette dernière peut, par la suite, être utilisée pour générer du code de simulation efficace, en prenant en compte un ordonnancement des blocs d’équations qui dépend du mode. Ce rapport est une version étendue de l’article homonyme, publié dans les actes de la conférence HSCC’20.

The Modelica mathematical modeling language, based on Differential Algebraic Equations (DAE), brings several specific issues that do not exist with modeling languages based on Ordinary Differential Equations. The main problem is the determination of the differentiation index and latent equations. Prior to generating simulation code and calling solvers, the compilation of a Modelica model requires a structural analysis step, which reduces the differentiation index to a level acceptable by numerical solvers. The Modelica language allows hybrid models with multiple modes, mode-dependent dynamics and state-dependent mode switching. These Multimode DAE (mDAE) systems are much harder to deal with. The main difficulties are (i) the combinatorial explosion of the number of modes, and (ii) the correct handling of mode switchings. The focus of this report is on the first issue, namely : How can one perform a structural analysis of an mDAE in all possible modes, without enumerating these modes? A structural analysis algorithmfor mDAE systems is presented, based on an implicit representation of the varying structure of an mDAE. It generalizes J. Pryce’s structural analysis method to the multimode case and uses Binary Decision Diagrams (BDD) to represent the mode-dependent structure of an mDAE. The algorithm determines, as a function of the mode, the set of latent equations, the leading variables and the state vector. This is then used to compute a mode-dependent block-triangular decomposition ofthe system, that can be used to generate simulation code with a mode-dependent scheduling of the blocks of equations.This report is an extended version of the homonym paper, published in the proceedings of the HSCC’20 conference.; Le langage de modélisation mathématique Modelica, basé sur les systèmes d'équations algebro-différentielles (Differential Algebraic Equations, ou DAE), présente des difficultés qui n’apparaissent pas dans la modélisation à base d'éequations différentielles ordinaires.Le problème principal consiste à déterminer l’indice de différentiation et les équations latentes d’un système. Lors de la compilation d’un modèle Modelica, un prérequis `à la génération de code de simulation et `a l’appel de solveurs est une étape d’analyse structurelle, qui réduit l’indice de différentiation à un niveau acceptable par les solveurs numériques.Le langage Modelica permet l’écriture de modèles hybrides, ou multimodes, dont la dynamique dépend du mode, et où les changements de mode sont conditionnés par les variables d’état. Ces DAE multimodes (mDAE) sont considérablement plus difficiles `a traiter, les obstacles principaux étant (i) l’explosion combinatoire du nombre de modes, et (ii) la prise en charge des changements de mode.Ce rapport se focalise sur le premier point: Comment effectuer l’analyse structurelle d’une mDAE en prenant en compte tous ses modes, mais sans énumérer ces derniers ? Un algorithme d’analyse structurelle de systèmes de mDAE est proposé; il s’appuie sur une représentationimplicite de la structure variable de la mDAE considéŕée. La méthode présentée généralise celle de Pryce au cas multimode, et utilise des Diagrammes de Décision Binaire (Binary Decision Diagrams, ou BDD) pour représenter la structure variable d’une mDAE. L’algorithme détermine l’ensemble des équations latentes, les variables de tête et le vecteur d’état, en tant que fonctions du mode. Ces informations permettent ensuite de décomposer le système en une forme triangulaire par blocs dépendant du mode. Cette dernière peut, par la suite, être utilisée pour générer du code de simulation efficace, en prenant en compte un ordonnancement des blocs d’équations qui dépend du mode. Ce rapport est une version étendue de l’article homonyme, publié dans les actes de la conférence HSCC’20.

This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ' , no process delivers first a set of messages including m ' and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent., Comment: arXiv admin note: substantial text overlap with arXiv:1702.08176

This technical report is a bibliographic study, an analysis and a synthesis of needs. This work is realized as part of a thesis about the subject"Constraint Logic Programming's application to the Timetable problems", within the department of Constraint Logic Programming (PLA :"Programmation en Logique et Applications") and the CNET's division SLC of Lannion-A. The subsidies come on the one hand from the Brittany's local committee, on the other hand from the national center of telecommunications studies (CNET).The Timetable problem is difficult and can give many days of work to one or two persons. A Timetable is very important due to the fact that it deals with the good management of time for different people who have their own activities. In big institutions (secondary schools, colleges of tlniversity ; CNET ...), many difficulties arise : big volume of data, fuzzy criterion of optimization, combinatorial problem, very varied constraints, inopportune changes. Then, many applications have grown either from mathematic models assisted by graph theory, or from other techniques such as operational research or artificial intelligence.This paper draws the requirements to solve this problem and proposes a model of resolution by the approach of Constraint Logic Programming.; Cette note technique est le résultat d'une étude bibliographique, d'une analyse et d'une synthèse des besoins, réalisées dans le cadre d'une thèse dont le sujet est "Application de la Programmation en Logique avec Contraintes aux problèmes d'Emploi du Temps", au sein de l'équipe Programmation en Logique avec Contraintes (PLA) dans la division SLC au CNET-Lannion A. Cette thèse est subventionnée d'une part par le Conseil Régional de Bretagne et d'autre part par le CNET.Le problème d'Emploi du Temps est un problème difficile qui peut donner plusieurs jours de travail à une ou deux personnes. L'importance d'un Emploi du Temps est évidente puisqu'il s'agit de gérer le temps de différentes personnes possédant leurs propres activités et ceci d'une manière satisfaisante pour chacune d'elle. Dans de grands établissements (lycées, grandes écoles ;CNET ; IRET ; ...), on se trouve confronté à de multiples difficultés : volume important d'informations, critère d'optimisation flou, combinatoire, contraintes très diverses, changements intempestifs. De ce fait, plusieurs recherches et essais de résolutions se sont développés, que ce soit par des modélisations mathématiques aidées de la théorie des graphes ou que ce soit par d'autres techniques issues de la Recherche Opérationnelle ou de l’IntelligenceArtificielle.Ce document conclut en dégageant les besoins pour informatiser et résoudre ce problème et propose une modélisation de résolution fondée sur I'approche Programmation en Logique avec Contraintes.

This technical report is a bibliographic study, an analysis and a synthesis of needs. This work is realized as part of a thesis about the subject"Constraint Logic Programming's application to the Timetable problems", within the department of Constraint Logic Programming (PLA :"Programmation en Logique et Applications") and the CNET's division SLC of Lannion-A. The subsidies come on the one hand from the Brittany's local committee, on the other hand from the national center of telecommunications studies (CNET).The Timetable problem is difficult and can give many days of work to one or two persons. A Timetable is very important due to the fact that it deals with the good management of time for different people who have their own activities. In big institutions (secondary schools, colleges of tlniversity ; CNET ...), many difficulties arise : big volume of data, fuzzy criterion of optimization, combinatorial problem, very varied constraints, inopportune changes. Then, many applications have grown either from mathematic models assisted by graph theory, or from other techniques such as operational research or artificial intelligence.This paper draws the requirements to solve this problem and proposes a model of resolution by the approach of Constraint Logic Programming.; Cette note technique est le résultat d'une étude bibliographique, d'une analyse et d'une synthèse des besoins, réalisées dans le cadre d'une thèse dont le sujet est "Application de la Programmation en Logique avec Contraintes aux problèmes d'Emploi du Temps", au sein de l'équipe Programmation en Logique avec Contraintes (PLA) dans la division SLC au CNET-Lannion A. Cette thèse est subventionnée d'une part par le Conseil Régional de Bretagne et d'autre part par le CNET.Le problème d'Emploi du Temps est un problème difficile qui peut donner plusieurs jours de travail à une ou deux personnes. L'importance d'un Emploi du Temps est évidente puisqu'il s'agit de gérer le temps de différentes personnes possédant leurs propres activités et ceci d'une manière satisfaisante pour chacune d'elle. Dans de grands établissements (lycées, grandes écoles ;CNET ; IRET ; ...), on se trouve confronté à de multiples difficultés : volume important d'informations, critère d'optimisation flou, combinatoire, contraintes très diverses, changements intempestifs. De ce fait, plusieurs recherches et essais de résolutions se sont développés, que ce soit par des modélisations mathématiques aidées de la théorie des graphes ou que ce soit par d'autres techniques issues de la Recherche Opérationnelle ou de l’IntelligenceArtificielle.Ce document conclut en dégageant les besoins pour informatiser et résoudre ce problème et propose une modélisation de résolution fondée sur I'approche Programmation en Logique avec Contraintes.