Search

State-machine replication (SMR) is a software technique for tolerating failures and for providing high availability in large-scale systems, through the use of commodity hardware. A replicated state-machine comprises a number of replicas, each of which runs an agreement protocol, with the goal of ensuring a consistent state across all of the replicas. In hostile environments, such as the Internet, Byzantine fault tolerant state-machine replication (BFT) is an important technique for providing robust services. During the past decade, we have seen an emergence of various BFT protocols. In order to be adopted, besides providing correctness, a BFT must provide good performance as well. Consequently, all of the new protocols focus on improving performance under various conditions. However, a closer look at the performance of state-of-the-art BFT protocols reveals that even in best-case execution scenarios, they still remain far behind their theoretical maximum. Based on exhaustive evaluation and monitoring of existing BFT protocols, we highlight a few impediments to their scalability. These obstructions include the use of IP multicast, the presence of bottlenecks due to asymmetric replica processing, and an unbalanced network bandwidth utilization. The goal of this thesis is to evaluate the actual impact of these scalability impediments, and to offer a solution for a high-throughput BFT protocol in the case in which the network itself is the bottleneck. To that end, we have developed Ring, a new BFT protocol which circumvents the aforementioned impediments. As its name suggests, Ring uses the ring communication topology, in the fault-free case. In the ring topology, each replica only performs point-to-point communications with two other replicas, namely its neighbors on the ring. Moreover, all of the replicas equally accept requests from clients and perform symmetric processing. Our performance evaluation shows that, with the network as the bottleneck, Ring outperforms all other, state-of-the-art BFT protocols. Ring achieves 118 Mbps on the Fast Ethernet – a 24% improvement in throughput over previous protocols. Finally, we conducted an extensive practical and analytic evaluation of Ring. In order to analyse benefits (and drawbacks) of Ring (and other protocols) under different settings, without resorting to costly experimentation, we developed an analytical performance model. Our performance model is based on queueing theory, and relies only on a handful of protocolagnostic measurements of the environment.

Cet article soutient que l’accélération des rythmes de vie dans la période contemporaine est exacerbée par la mise en place de nouvelles pratiques temporelles reliées à l’émergence de ce que nous appelons le capitalisme algorithmique. Il examine le rapport théorique et historique entre le temps de loisir et le marché et problématise l’arrimage des temps vécus aux temporalités marchandes. La définition historique du temps de loisir comme temps « extraéconomique », exempt des soucis de reproduction matérielle, est aujourd’hui rendue désuète par les restructurations néolibérales, puis algorithmiques, du capitalisme et de la valorisation des temps d’attention. L’article examine ces questions à partir d’un engagement critique avec la théorie de l’accélération sociale, les études du temps social et l’économie politique hétérodoxe., This paper argues that the acceleration of life rhythms in the contemporary period is exacerbated by new temporal practices related to what we call algorithmic capitalism. We focus on a historical and theoretical analysis of the relationship between leisure time and the market, and the anchoring of lived times to market imperatives. The historical definition of leisure as an “extra-economic” practice, remote from any economic concerns, is now made obsolete by the neoliberal, and then algorithmic, restructuration of capitalism, and especially the valorization of attention time. The article examines these questions, mobilizing and critically engaging with the theory of social acceleration, time studies, and heterodox political economy.

International audience; Ce texte s’interroge sur les risques d’abus de position dominante qui peuvent être observés dans le domaine des plateformes d’intermédiation électronique. Il met en évidence les risques d’abus d’éviction au détriment des marchands utilisateurs des plateformes mais également d’abus d’exploitation vis-à-vis de ceux-ci et des consommateurs. Il s’attache également aux phénomènes de dépendance économique qui peuvent en résulter. Il s’agit alors de s’interroger sur la capacité des outils fournis par les règles de concurrence à répondre à ces risques et d’évaluer dans quelle mesure des mesures de nature réglementaires seraient possibles ou souhaitables

National audience; This paper proposes a method that analyzes data representing trajectories of moving objects. The method is based on extracting frequent patterns and introduces different types of patterns, for example, latent, emergent, etc. A set of algorithms are introduced to pre-process the data, to extract the frequent patterns and detect the behaviors. These types are used to generate a city map tagged by behaviors. The classification of a given trajectory consists in its projection on this spatial zone. This leads to a multi-label classification which depends on the spatio-temporal granularity. Finally, we discuss the application of our method on real-world data representing taxi trajectories.; Cet article propose une méthode qui analyse des données représentant des trajectoires d'objets mobiles. La méthode se base sur les motifs fréquents et introduit différentes types de motifs, par exemple, les motifs latents, émergents, etc. Un ensemble d'algorithmes sont alors introduits pour pré-traiter les données, extraire les motifs fréquents et détecter les types des motifs. Ces motifs géolocalisés sont ensuite utilisés pour tagger une zone spatiale déterminée. La classification d'une trajectoire consiste alors en sa projection sur la zone spatiale ce qui conduit nécessairement à une classification multi-labels dépendant de la granularité spatio-temporelle. Pour finir, nous discutons de l'application de notre méthode sur des données réelles représentant des trajectoires de taxis.

Numerous bacteria and viruses use cells from another species to ensure their proliferation. This mode of reproduction implies the pathogen must escape the host immune system and reprogram its metabolism to sustain its own needs. These changes are often detrimental to the host cell and cause pathologies or death. The intracellular bacteria which use this mode of operation have been the focus of many studies aiming to understand their "hijacking" mechanisms. Recent advances in genomics have largely stimulated research in this field by offering the possibility to decipher the sequence of genes expressed during infection. Several intracellular bacteria secrete "effector" proteins into the host cytoplasm which interact with its proteins and affect its genetic expression program. Recently, studies in Legionella pneumophila, an experimental model for intracellular bacteria, have shown it was able to alter the epigenetic state of its host. Such modifications allow rapid physiological changes and are intimately linked to the spatial organisation of the genome. 3D genome organisation plays an important part in many biological processes, for example by modulating gene expression through long range interactions in the sequence. Throughout this work, we develop computational tools to explore and measure spatial changes occuring in the genome, and exploit them to investigate the changes taking place during infection by intracellular bacteria. We use the model species Legionella pneumophila and Salmonella enterica to explore structural changes taking place in the host chromosomes and their link with genetic expression., De nombreuses bactéries intracellulaires (BI) et virus utilisent les cellules d'autres espèces pour assurer leur prolifération. Ce mode de reproduction implique que le pathogène doit échapper au système immunitaire de son hôte et reprogrammer son métabolisme pour subvenir à ses propres besoins. Les BI utilisant ce mode de fonctionnement et font l'objet d'études qui visent à comprendre leurs mécanismes de "piratages". Les récents progrès en génomique ont stimulé la recherche dans ce domaine en offrant la possibilité de déchiffrer la séquence des gènes exprimés durant l'infection. De nombreuses BI sécrètent des "effecteurs" dans le cytoplasme de leur hôte qui vont interagir avec ses protéines et affecter son programme d'expression génétique. Récemment des études dans Legionella pneumophila, un modèle expérimental pour les BI, ont démontré qu'elle était capable d'altérer la régulation épigénétique de son hôte. Ce genre de modifications permet des changements physiologiques rapides et est intimement lié à l'organisation spatiale du génome. L'organisation 3D du génome joue un rôle important dans de nombreux processus biologiques, par exemple en modulant l'expression génétique par la formation d'interaction entre des éléments éloignés. A travers ce travail, nous développons des outils computationels pour explorer et mesurer les changements spatiaux du génome, et nous les exploitons pour étudier les changements qui ont lieu pendant l'infection par des BI. Nous utilisons en particulier les modèles Salmonella enterica et L. pneumophila pour explorer les changements de structure qui surviennent dans les chromosomes de leurs hôtes et leurs liens avec l'expression génétique.

Nowadays, there are many methods used to detect the background of an image, with different complexity and different results. Usage varies depending on the application and the necessities. This Project consists in academic software to perform differentiation or segmentation of elements belonging to the background of an image, in order to identify the new objects that appear in the scene. Those objects can be objects that are in constant movement (people, cars, etc.) or objects that reminds in the future (abandoned objects, parked cars, etc.) . In general, background is defined as the objects in the scene that reminds static for long period of time. The environments of these scenes can be classified as internal or external. Each one of them presents substantially different characteristics and some problems that must be resolved. The algorithms implemented in this project will be tested in two types of environment to evaluate their effectiveness and to draw conclusions. We have studied quite different methods, not only in terms of results but also in terms of computational cost and complexity of the algorithms. Automatically arrange from low to high computational cost, the studied algorithms are Frame Difference, Approximate Median Filter, Running Gaussian Average and Mixture of Gaussians finally. In this academic software, the main goal is the easy interaction of the user with the different parameters of each method and the visualization of the effects in the estimation of the background and the foreground. In this memory, is explained briefly the digital image and some aspects of the acquisition of the images are included. The nomenclature used in literature analysis related with this thematic and the different models that have worked are analyzed is also presented. In addition, proceeds to deal in more detail the background removal of an image, the main problems that arise and the specific techniques used. Finally, a review of existing algorithms and their implementation is done.

La Bienveillance des machines n'est ni l'ouvrage d'un technophile, ni d'un technophobe. Pourtant, les machines, les robots, les algorithmes (d'intelligence artificielle) et les réseaux y occupent une place prépondérante. Il ne s'agit pas d'étudier les aspects politiques, économiques ou encore techniques qui s'y rapportent, même si ces dimensions sont légitimement représentées, mais de déplacer la question des rapports que l'humain entretient aux machines à un niveau ontologique. L'objectif de cet ouvrage est d'étudier ce que l'auteur nomme « syndromes technologiques » à travers une thèse originale : « les technologies contemporaines induisent différentes transformations de nos subjectivités. » Ces syndromes permettent d'aborder différentes notions allant de la confiance que l'utilisateur·trice accorde aux informations données par les machines jusqu'à celle de la surveillance dont nous faisons l'objet afin de démontrer, premièrement, le changement de nature de la machine et l'apparition d'un règne machinique (au même titre que le règne animal ou végétal) et, deuxièmement, la variation de notre forme de vie (au sens de Wittgenstein) pour mettre en évidence la transformation du sujet en sujet digital., La Bienveillance des machines is neither the work of a technophile nor of a technophobe. However, machines, robots, algorithms (of artificial intelligence) and networks occupy a preponderant place in it. It is not a question of studying the political, economic or technical aspects that are related to them, even if these dimensions are legitimately represented, but of shifting the question of the relationship that humans have with machines to an ontological level. The book studies what the author calls "technological syndromes" through an original thesis: "contemporary technologies induce different transformations of our subjectivities." These syndromes allow to approach different notions -- from the trust that the user grants to the information given by the machines to the one of the surveillance of which we are the object -- in order to demonstrate, firstly, the change of nature of the machine and the appearance of a machinic reign (in the same way as the animal or vegetal reign) and, secondly, the variation of our form of life (in the sense of Wittgenstein) to highlight the transformation of the subject into a digital subject.

Ce projet de semestre a pour objectif d'optimiser la conception d'un transducteur piézoélectrique ultrasonique, utilisé dans le domaine biomédical comme outil chirurgical, à l'aide d'une classe spécifique d'algorithmes appelés algorithmes génétiques.

International audience; L'accroissement des données disponibles sur les caractéristiques et les comportements des consommateurs ainsi que le renforcement des capacités de traitement de ces dernières par des algorithmes ouvrent la voie audéveloppement de stratégies de discrimination tarifaire de troisième degré avec une granularité extrêmement fine. Si les effets de cette discrimination de quasi-premier degré sur le surplus total sont ambigus, ils induisent aussi un transfert de bien-être entre agents économiques. Cet article analyse la possibilité de mettre en œuvre de telles stratégies dans l'économie numérique et envisage lespossibles réponses venant des règles de concurrence ou des consommateurs eux-mêmes.

Le dernier ouvrage de Dominique Cardon présente la version rédigée du cours en Culture numérique que le sociologue assure depuis plusieurs années auprès du collège universitaire de SciencesPo. Dans ces pages, on peut reconnaître la démarche théorique du chercheur aussi bien que l’effort pédagogique de l’enseignant qui assume une responsabilité assez délicate : nous offrir une synthèse critique, accessible, exhaustive et efficace, de la culture numérique à l’état actuel des choses. Au carrefour de deux exigences spéculaires, celle de coder et celle de décoder, le sociologue organise ici une totalité de savoirs et de connaissances interdisciplinaires, naviguant entre informatique et philosophie, sociologie et théorie économique, sciences politiques et analyses de marché. Au centre de son analyse, les nouvelles configurations de l’espace public, les formes de la démocratie internet, l’influence des algorithmes et des moteurs de recherche, le digital labor, le problème de la surveillance. Notre compte rendu, sans aucune prétention d’exhaustivité, revient sur les principales étapes de cette véritable exploration de la culture numérique, qui s’adresse avant tout aux novices tout en constituant un instrument utile de synthèse et de suggestions bibliographiques pour les chercheurs., L’ultima opera di Dominique Cardon è la versione scritta del corso di Cultura digitale che il sociologo tiene da parecchi anni presso il collegio universitario di SciencesPO. In queste pagine è possibile riconoscere l’approccio teorico del ricercatore e lo sforzo pedagogico dell’insegnante che assume une responsabilità assai delicata : offrirci un bilancio critico, abbordabile, esauriente e efficace, della cultura digitale di oggi. In mezzo a due esigenze speculari, quella di codificare e quella di decodificare, il sociologo organizza un insieme di saperi e conoscenze interdisciplinari, muovendosi tra informatica e filosofia, sociologia e teorie dell’economia, politologia e analisi di mercato. Al centro della sua analisi, lo spazio pubblico, la democrazia internet, l’influenza degli algoritmi e dei motori di ricerca, il digital labor, il problema della sorveglianza. La nostra recensione, senza pretese di esaustività, segnala le tappe principali di una vera esporazione della cultura digitale, ceh è un’opera di divulgazione per i novizi e un utile strumento di sintesi e di indicazioni bibliografiche per i ricercatori.

Comment penser l’espace numérique et rendre compte de son caractère à la fois structuré, mouvant et collectif ? Comment trouver un dispositif qui permet un dialogue ouvert, parvenant à saisir le sens des infrastructures numériques, sans les cristalliser en une essentialisation appauvrissante ? L’échange de courriels nous a semblé le moyen le plus approprié de faire de la théorie ainsi que de mettre en place un geste de pensée qui s’accorde avec la culture numérique et qui rend possible d’envisager cette dernière avec un regard critique. Pendant un an et demi (de septembre 2015 à mars 2017), nous avons donc échangé questions et réponses, afin d’essayer d’identifier les caractéristiques du numérique — espaces, temps et enjeux politiques — en continuité avec la tradition du dialogue philosophique., How could we consider the digital space and give full account of its structured, moving, and simultaneously collective attributes ? How could we find a device that enables an open dialogue, which allows us to understand the meaning of digital infrastructures without any impoverishing essentialization ? This e-exchange appeared to us the most appropriate way to theorize and create an act of thought that fits in with the digital culture and allows a critical eye on it. For about a year and a half (from September 2015 to March 2017), we shared questions and answers, trying to identify the digital world’s characteristics — its spaces, times, political challenges —, in continuity with the philosophical dialogue.

Sampling-based optimization heuristics are algorithms which aim to find good solutions for problems that cannot be solved through exact solution strategies. They are particularly useful for the optimization of problems that are not given as explicit formulae, but which require computer simulations or physical experiments to assess the quality of a proposed solution. In such settings, sampling-based optimization heuristics are essentially the only means to obtain good solutions. Another important application of sampling-based optimization heuristics is in the optimization of problems that are too complex to be solved analytically, and which remain intractable for problem-specific algorithm designs.An important sub-class of sampling-based optimization heuristics are iterative optimization heuristics (IOHs). IOHs aim at finding good solutions by a sequential process of evaluating solution candidates, using the obtained information to adjust the strategy by which the next samples are generated, and iterating this process until a termination criterion is met.With my research, I aim to contribute to our understanding of the working principles that drive the performance of IOHs. More precisely, I aim at understanding which strategies work well for which types of problems. To this end, I study the efficiency of existing IOHs, and I compare these performances to that of a best possible solver for the given problem. For the latter, I develop and analyze complexity models that allow us to quantify the influence of certain algorithmic choices, such as the size of memory used, the strategy by which solutions can be sampled, the type of information used to select the next sampling strategies, etc. This thesis summarizes some of my research results obtained in the last nine years, since the completion of my PhD studies. We first derive improved (and often tight) bounds for the black-box complexity of the two best known benchmark problems in the theory of IOHs, OneMax and LeadingOnes, and this for various black-box models. We then demonstrate how insights obtained from such black-box complexity studies can inspire the design of efficient optimization techniques. An important result obtained through this approach is a rigorous example for a situation in which a non-static choice of the control parameters of an IOH yields a super-constant performance gain over any possible static parameter setting. This result has revived theoretical research on parameter control, which has seen significant advances since. We discuss some examples in this thesis. We conclude by discussing the role of algorithm benchmarking as a bridge between theoretical and empirical research of IOHs.

In this thesis, we present works inspired by real ants for the resolution of well known problems in computer science. We propose two supplementary approaches to these new biomimetic inspirations. The first resumes works on clustering and widens their principles in several directions. The AntClass algorithm, developed for occasion, is hybrid in the way that the artificial ants search for the number of clusters and a classic classification algorithm, the K-means algorithm, is used to reduce classification errors inherent to a stochastic method such as artificial ants. After underlying similarities and differences between the evolutionnary approaches and those based on a population of ants, we propose a common model. We finally use the Pachycondyla apicalis ants' strategy to search for food to solve global optimization problems. The contribution of this adaptation mainly lies in its simplicity. We apply the ensuring algorithm, called API, to various problems such as the optimization of numerical functions, the learning of hidden Markov models, the learning of the weights of an artificial neural network, or also to a classical combinatorial optimization problem: the traveling salesman problem.; Dans ce travail de thèse, nous présentons les travaux s'inspirant des fourmis réelles pour la résolution de problèmes en informatique. Nous proposons deux approches supplémentaires de ces nouvelles inspirations biomimétiques. La première reprend certains travaux en classification non supervisée et étend ces principes dans plusieurs directions. L'algorithme AntClass développé à cette occasion, est hybride dans le sens où la recherche du nombre de classes est effectué par des fourmis artificielles et qu'un algorithme classique en classification, les centres mobiles, est utilisé pour gommer les erreurs de classification inhérentes à une méthode stochastique telle que les fourmis artificielles. Après avoir souligné les ressemblances et différences entre les approches évolutionnaires et celles à base de population de fourmis et proposé un modèle commun, nous nous inspirons de la stratégie de recherche de nourriture d'une espèce de fourmis (Pachycondyla apicalis) pour résoudre des problèmes d'optimisation globale. L'apport de cette adaptation réside principalement dans sa simplicité. Nous appliquons l'algorithme qui en découle, appelé API, à des problèmes variés tels que l'optimisation de fonctions numériques, l'apprentissage de chaînes de Markov cachées ou des poids d'un réseau de neurones artificiels, ou encore à un problème d'optimisation combinatoire classique : le problème du voyageur de commerce.

The work presented in this thesis deals with repetitive structure inference from audio signal using string matching techniques. It aims at proposing and evaluating inference algorithms from a formal study of notions of similarity and repetition in music.We first present a method for representing audio signals by symbolic strings. We introduce alignment tools enabling similarity estimation between such musical strings, and evaluate the application of these tools for automatic cover song identification. We further adapt a bioinformatics indexing technique to allow efficient assessments of music similarity in large-scale datasets. We then introduce several specific repetitive structures and use alignment tools to analyse these repetitions. A first structure, namely the repetition of a chosen segment, is retrieved and evaluated in the context of automatic assignment of missingaudio data. A second structure, namely the major repetition, is defined, retrieved and evaluated regarding expert annotations, and as an alternative indexing method for cover song identification.We finally present the problem of repetitive structure inference as addressed in literature, and propose our own problem statement. We further describe our model and propose an algorithm enabling the identification of a hierarchical music structure. We emphasize the relevance of our method through several examples and by comparing it to the state of the art., Cette thèse rend compte de travaux portant sur l’inférence de structures répétitives à partir du signal audio à l’aide d’algorithmes du texte. Son objectif principal est de proposer et d’évaluer des algorithmes d’inférence à partir d’une étude formelle des notions de similarité et de répétition musicale.Nous présentons d’abord une méthode permettant d’obtenir une représentation séquentielle à partir du signal audio. Nous introduisons des outils d’alignement permettant d’estimer la similarité entre de telles séquences musicales, et évaluons l’application de ces outils pour l’identification automatique de reprises. Nous adaptons alors une technique d’indexation de séquences biologiques permettant une estimation efficace de la similarité musicale au sein de bases de données conséquentes.Nous introduisons ensuite plusieurs répétitions musicales caractéristiques et employons les outils d’alignement pour identifier ces répétitions. Une première structure, la répétition d’un segment choisi, est analysée et évaluée dans le cadre dela reconstruction de données manquantes. Une deuxième structure, la répétition majeure, est définie, analysée et évaluée par rapport à un ensemble d’annotations d’experts, puis en tant qu’alternative d’indexation pour l’identification de reprises.Nous présentons enfin la problématique d’inférence de structures répétitives telle qu’elle est traitée dans la littérature, et proposons notre propre formalisation du problème. Nous exposons alors notre modélisation et proposons un algorithme permettant d’identifier une hiérarchie de répétitions. Nous montrons la pertinence de notre méthode à travers plusieurs exemples et en l’évaluant par rapport à l’état de l’art.