Search

International audience; Mobile Ad-Hoc Networks (MANETs) assume no previous network infrastructure and wireless communication between mobile and heterogeneous nodes. An efficient broadcast protocol is therefore paramount. When some neighborhood information is available beforehand through discovery, building a virtual overlay like MultiPoint Relay (MPR) can help improve reliability and decrease cost in messages. However, MPR overlays tend to unfairly stress specific nodes who happen to be wellconnected, causing their premature death. We propose the alternating MPR protocol that strives to build several disjoint relay sets for each node, allowing broadcast messages to use each of them in turn. Our simulation of the full network stack of systems of various densities shows that alternating MPR spreads energy costs more evenly across the system, without harming reliability and at little cost in number of messages, allowing battery-powered nodes to survive longer.

International audience; Stream Processing Systems (SPSs) can present significant fluctuation in input rate. To address this issue, some existing solutions propose reconfiguring the SPS by replicating its operators. However, such reconfiguration usually induces a high system downtime cost. Moreover, reconfiguration decisions are based only on resource utilization without balancing the load between replicas. We propose in this paper a predictive SPS that dynamically defines the necessary number of replicas of each operator based not only on the current resource utilization and input rate variation but also on the events that, due to the operator's overloading, could not be processed yet and are, thus, kept in the operator's queue. In addition, our SPS implements a load balancer that distributes incoming events more evenly among replicas of an operator. Our solution has been integrated into Storm. To avoid system reconfiguration downtime, our SPS preallocates a pool of replicas where each of them can be activated or deactivated based on per operator input load predictions. Using real traffic traces with different applications, we have conducted experiments on Google Cloud Platform (GCP), evaluating our SPS and comparing it with Storm and DABS-Storm.

International audience; This paper proposes Multi-FedLS, a Cross-silo Federated Learning (FL) framework for a multi-cloud environment aiming at minimizing financial cost as well as execution time. It comprises four modules: Pre-Scheduling, Initial Mapping, Fault Tolerance, and Dynamic Scheduler. Given an application and a multi-cloud environment, the Pre-Scheduling module runs experiments to obtain the expected execution times of the FL tasks and communication delays. The Initial Mapping module receives these computed values and provides a scheduling map for the server and clients' VMs. Finally, Multi-FedLS deploys the selected VMs, starts the FL application, and monitors it. The Fault Tolerance (FT) module includes fault tolerance strategies in the FL application, such as checkpoint and replication, and detects some anomalous behaviors. In case of an unexpected increase in the communication delay or a VM failure, the FT module triggers the Dynamic Scheduler Module in order to select a new VM and resume the concerned tasks of the FL application. Some preliminary experiments are presented, confirming that some proposed strategies are crucial to efficiently execute an FL application on a multi-cloud environment.

International audience; Under the coordination of a central server, Federate Learning (FL) enables a set of clients to collaboratively train a global machine learning model without exchanging their local data. When such clients have powerful machines, it is called cross-silo FL, and they store their data in private repositories denoted silos. We are interested in this paper in cross-silo FL where silos are geographically located in different regions of multi-cloud providers. Thus, aiming at minimizing financial costs and execution times of a cross-silo FL application, we propose a model based on a scheduling problem mathematical formulation, which receives as input both the application parameters and the cloud providers' resource features where clients' data are stored and renders the best assignment of clients and server to virtual machines. This formulation is part of a framework proposal to execute FL applications in different cloud providers. Taking as a use case a Tumor-Infiltrating Lymphocytes Classification problem, an FL application whose clients' datasets spread over different cloud providers' data repositories, evaluation results show that our model is scalable and improves the execution time and financial costs of the FL application by up to 53.70% and 48.34% in a scenario with 50 clients, executing in around 200 seconds, when compared to results where VMs are randomly selected. Experimental results with client silos in different Google (GCP) and Amazon (AWS) cloud regions also confirmed the effectiveness of our proposed model in a real multi-cloud environment.

International audience; L'Étiquetage en Composantes Connexe (ECC) est une opération fondamentale de la vision numérique depuis des décennies. Bien que la majeure partie de la littérature traite des algorithmes en 2D, sur des applications telles que la vidéo-surveillance ou la conduite autonome, il y a de plus en plus besoin d'algorithmes pour traiter des images en 3D, notamment pour des applications médicales. Bien que les algorithmes d'ECC en 2D génèrent un nombre important d'accès mémoire et de comparaisons, le problème empire avec algorithmes en 3D. Il s'agit de la malédiction de la dimension. La mise en place d'un algorithme efficace doit donc résoudre ce problème. Ce papier introduit un algorithme utilisant des segments pour étiqueter des volumes en 3D. Les équivalences entre les étiquettes sont accélérées à l'aide d'une nouvelle stratégie atténuant l'impact de la dimension supérieure. Ce nouvel algorithme surpasse les algorithmes de l'État-de-l'art d'un facteur allant de ×1.5 à ×3.1 sur des images médicales et sur des images aléatoires.

International audience; Les réseaux mobiles adhoc (MANET) sont des réseaux de noeuds mobiles hétérogènes communicants par radio dans lesquels on ne fait aucune hypothèse quant à une infrastructure réseau préexistante. Ce genre de réseaux nécessite une opération de diffusion globale (broadcast) performante. Si les noeuds sont réputés ne connaître aucune caractéristique globale du système, il est néanmoins parfois possible de construire sur la seule base d'informations locales une topologie virtuelle couvrante de son voisinage à partir de messages de contrôle. MPR est un algorithme qui s'appuie sur une telle topologie pour améliorer la couverture de la diffusion et diminuer son coût en messages, en limitant la charge de la retransmission à un ensemble de voisins relais bien choisis. Malheureusement, ces topologies virtuelles couvrantes ont tendance à trop s'appuyer sur les noeuds les mieux connectés, causant une surconsommation de leur batterie. Nous proposons un nouvel algorithme, MPR alternant, qui s'efforce de constituer plusieurs ensembles disjoints de relais pour chaque noeud, permettant aux messages de diffusion de les utiliser de manière alternante. Notre simulation de la pile réseau complète de systèmes de densité variable montre que notre algorithme distribue de manière plus égalitaire les coûts énergétiques, sans dommages pour la couverture ni pour le coût en messages, permettant aux noeuds fonctionnant sur batterie de survivre plus longtemps.

International audience; Modern distributed applications are difficult to develop. The actor model is helpful as it is designed for modularity and composition. However, the actor model does not support shared state. For this, developers often use an external database, which integrates poorly and causes anomalies. We argue that some form of native shared memory is useful for a large class of distributed applications. To integrate cleanly with the actor environment, this shared memory should support the transactional causal consistency model. This model provides the strongest consistency compatible with high availability and is compatible with the actor model and its common optimizations.

International audience; Based on direct acyclic graphs, where vertices and edges respectively correspond to operators and event data flow, Stream Processing Systems (SPSs) are used to process high amounts of data in real time. Operators are allocated in the resources of the infrastructure (e.g., VMs) which are usually replicated for performance sake. We propose in this paper a predictive SPS that dynamically determines the current number of replicas required for each operator based not only on the current resource utilization and data flow variation but also on the events that, due to operator's overloading, could not be processed yet and are, thus, kept in the operator's queue. Preliminary performance results with an application that processes Twitter stream, deployed on Google Cloud Platform (GCP), are presented.

In wireless networks, broadcast and convergecast are the two most used communication primitives. Broadcast instructs a specific sink (or root) node to send a message to each node in the network. Convergecast instructs each node in the network to send a message to the sink. Without labels, deterministic convergecast is impossible even in a three-nodes network. Therefore, networking solutions for convergecast are based on probabilistic approaches or use underlying probabilistic medium access protocols such as CSMA/CA or CSMA/CD. In this paper, we focus on deterministic convergecast algorithms enhanced with labeling schemes. We investigate two communication modes: half-duplex (nodes either transmit or receive but not both at the same time) and full-duplex (nodes can transmit and receive data at the same time). For these two modes we investigate time and labeling lower and upper bounds. Even though broadcast and convergecast are similar, we prove that, contrary to broadcast, deterministic convergecast cannot be solved with short labels for some topologies. That is, O(log(n)) bits are necessary to solve deterministically convergecast where n is the number of nodes in the network. We also prove that O(n) communication time slots is required. We provide solutions that are optimal in the worst case scenarios, in terms of labeling and communication.

International audience; Dans cet article nous considérons les réseaux non anonymes et des problématiques dont la solution peut être capturée par un prédicat booléen Π, problématiques comme la coloration des noeuds, l'élection... Un algorithme auto-stabilisant pour Π est un algorithme distribué qui, quelle que soit la configuration initiale du réseau (c'est-à-dire une configuration où chaque noeud peut se voir attribuer une valeur arbitraire en chacune de ses variables), converge vers une configuration qui satisfait Π. Il est connu que le problème de l'élection n'admet pas d'algorithme déterministe auto-stabilisant utilisant une mémoire constante en bits à chaque noeud, autrement dit, pour certains réseaux, la taille de la mémoire par noeud doit croître en même temps que la taille du réseau. D'autre part, il existe un algorithme déterministe auto-stabilisant pour le problème de l'élection dans un anneau dont la taille mémoire par noeud est O(log log n) bits, où n est la taille du réseau. Nous montrons dans cette article que cette dernière complexité spatiale est optimale. Plus précisément, nous prouvons que tout algorithme déterministe auto-stabilisant résolvant le problème de l'élection doit utiliser une taille mémoire de Ω(log log n) bits par noeud. Nous montrons également que notre borne inférieure s'applique au-delà du problème de l'élection à tous les problèmes qui ne peuvent être résolus par des algorithmes anonymes.

Leader election is important for many fault-tolerant services in asynchronous distributed systems. By coordinating actions of a set of processes, it allows solving agreement problems like the consensus, a fundamental problem of distributed computing. Several consensus algorithms, such as Paxos, rely on an eventual leader election service, also known as the Omega failure detector. Omega returns the identity of a process in the system, ensuring that eventually the identity of the same correct process is always returned. Many leadership algorithms were proposed in the literature to implement Omega. Among those that consider dynamic systems, most of them do not choose the leader according to a topological criterion. However, the position of the leader in the network directly impacts the performance of algorithms using the leader election service, since the leader must often interact with other processes, for example, to collect information from a majority of processes in consensus algorithms. This thesis studies the eventual leader election problem in dynamic evolving networks and performance related issues. Two eventual leader election algorithms are proposed for Mobile Ad Hoc Networks. They maintain and exploit the knowledge of the network topology to eventually elect one leader per connected component with the best closeness centrality. Evaluations were conducted on simulators with different mobility models and performance results show that these algorithms present better performance than other algorithms of the literature, including fewer messages, shortest paths to the leader, and better stability., L'élection de leader est importante pour les services tolérants aux pannes dans les systèmes distribués asynchrones. En coordonnant les actions d'un ensemble de processus, elle permet de résoudre des problèmes d'accord comme le consensus, un problème fondamental en informatique distribuée. Des algorithmes de consensus, tel que Paxos, s'appuient sur un service d'élection de leader ultime, également appelé Omega. Omega renvoie l'identité d'un processus du système et garantit qu'après un certain temps, l'identité du même processus correct est toujours renvoyée. Plusieurs algorithmes d'élection de leader ont été proposés dans la littérature pour implémenter Omega. Parmi ceux considérant les systèmes dynamiques, la plupart ne choisissent pas le leader selon un critère topologique. Or, la position du leader dans le réseau impacte directement les performances des algorithmes utilisant le service d'élection, car le leader doit souvent interagir avec les autres processus pour, par exemple, collecter les informations d'une majorité de processus dans le cas du consensus. Cette thèse étudie le problème d'élection de leader ultime dans les réseaux dynamiques. Deux algorithmes d'élection sont proposés pour les réseaux mobiles ad hoc. Ceux-ci maintiennent et exploitent la connaissance de la topologie du réseau pour élire à terme un unique leader par composante connexe ayant la meilleure centralité de proximité. Des évaluations sur simulateurs avec différents modèles de mobilité montrent que ces algorithmes présentent de meilleures performances que d'autres algorithmes de la littérature, notamment moins de messages, des chemins plus courts vers le leader, et une meilleure stabilité.

We consider swarms of asynchronous oblivious robots evolving into an anonymous grid-shaped network. In this context, we investigate optimal (w.r.t. the number of robots) deterministic solutions for the terminating exploration problem. We first show lower bounds in the semi-synchronous model. Precisely, we show that at least three robots are required to explore any grid of at least three nodes, even in the probabilistic case. Then, we show that at least four (resp. five) robots are necessary to deterministically explore a $\bf(2,2)$-Grid (resp. a $\bf(3,3)$-Grid). We then propose deterministic algorithms in the asynchronous model. This latter being strictly weakest than the semi-synchronous model, all the aforementioned bounds still hold in that context. Our algorithms actually exhibit the optimal number of robots that is necessary to explore a given grid. Overall, our results show that except in two particular cases, three robots are necessary and sufficient to deterministically explore a grid of at least three nodes and then terminate. The optimal number of robots for the two remaining cases is four for the $\bf(2,2)$-Grid and five for the $\bf(3,3)$-Grid, respectively.

National audience; Federated Learning (FL) is a new area of distributed Machine Learning (ML) that emerged to deal with data privacy concerns. In FL, each client has access to a local private dataset. At every round, a client trains the model with its local dataset and sends the weights to a central server. The latter aggregates all client weights and then sends the final weights back to the clients. This approach is attractive in many domains as it allows multiple institutions to collaborate on an ML task without sharing their data. However, most ML models used in FL have millions of weights exchanged in each message. The messages sent between a client and the server can achieve gigabytes of size and are exchanged several times in the whole FL execution. This work presents a preliminary analysis of execution times and costs of a FL application in a multi-cloud scenario. Experiments were conducted considering executions on the Amazon Web Services, Google Cloud Provider, and also in both cloud providers at the same time.

International audience; This article introduces a new connected component labeling and analysis algorithm framework that is able to compute in one pass the foreground and the background labels as well as the adjacency tree. The computation of features (bounding boxes, first statistical moments, Euler number) is done on-the-fly. The transitive closure enables an efficient hole processing that can be filled while their features are merged with the surrounding connected component without the need to rescan the image. A comparison with State-of-the-Art shows that this new algorithm can do all these computations faster than all existing algorithms processing foreground and background connected components or holes.

International audience; Nous abordons le problème de la détection de terminaison (TD) dans les réseaux asynchrones. Un algorithme qui résout ce problème détecte si un algorithme distribué observé A a convergé vers une configuration qui satisfait un prédicat particulier. Il est connu que TD ne peut pas être résolu dans le contexte de l'auto-stabilisation, sauf si l'algorithme est instantanément stabilisant (snap-stabilization), c'est-à-dire qu'il se comporte toujours conformément à sa spécification, indépendamment de la configuration initiale. Un algorithme déterministe instantanément stabilisant pour TD est donné dans [7] pour les réseaux enracinés, autrement dit les réseaux où tous les noeuds exécutent le même algorithme, sauf un. Dans cet article, nous proposons un algorithme générique, déterministe, silencieux, instantanément stabilisant, qui détecte la terminaison d'un algorithme observé A, auto-stabilisant, silencieux et terminant. Notre algorithme ne nécessite pas de structure sous-jacente, ni de topologie spécifique et fonctionne dans des réseaux anonymes. Plus précisément notre algorithme n'utilise aucune hypothèse permettant de distinguer un ou plusieurs processus, de plus, il fonctionne sous les hypothèses de l'ordonnanceur le plus faible, l'ordonnanceur inéquitable. Construite audessus de n'importe quel unisson asynchrone auto-stabilisant sous-jacent U, notre solution requiert comme espace mémoire supplémentaire uniquement O(log D) bits par noeud, où D est le diamètre du réseau. Puisqu'il n'existe aucun algorithme d'unisson avec une meilleure complexité spatiale, l'espace mémoire supplémentaire de notre solution est comparable à la complexité spatiale de l'algorithme d'unisson sous-jacent. Notre algorithme fournit une réponse positive en O(max(k, k' , D)) rounds, où k et k' sont les complexités respectives en temps de stabilisation de A et U.

Immediate response, autonomy and availability is brought to edge applications, such as gaming, cooperative engineering, or in-the-field information sharing, by distributing and replicating data at the edge. However, application developers and users demand the highest possible consistency guarantees, and specific support for group collaboration. To address this challenge, COLONY guarantees Transactional Causal Plus Consistency (TCC+) globally, dovetailing with Snapshot Isolation within edge groups. To help with scalability, fault tolerance and security, its logical communication topology is tree-like, with replicated roots in the core cloud, but with the flexibility to migrate a node or a group. Despite this hybrid approach, applications enjoy the same semantics everywhere in the topology. Our experiments show that local caching and peer groups improve throughput and response time significantly, performance is not affected in offline mode, and that migration is seamless., La distribution et la réplication des données en périphérie du réseau apportent une réponse immédiate, une autonomie et une disponibilité aux applications de périphérie, telles que les jeux, l’ingénierie coopérative ou le partage d’informations sur le terrain. Cependant, les développeurs d’applications et les utilisateurs exigent les meilleures garanties de cohérence possibles, ainsi qu’un support spécifique pour la collaboration de groupe. Pour relever ce défi, Colony garantit la cohérence Transactional Causal Plus Consistency (TCC+) à échelle planétaire, en complément de l’isolation des instantanés au sein des groupes de périphérie. Pour favoriser le passage à l’échelle, la tolérance aux pannes et la sécurité, sa topologie de communication logique est arborescente, avec des racines répliquées dans le nuage principal, mais avec la possibilité de migrer un nœud ou un groupe. Malgré cette approche hybride, les applications bénéficient de la même sémantique partout dans la topologie. Nos expériences montrent que la mise en cache locale et les groupes collaboratifs améliorent considérablement le débit et le temps de réponse, que les performances ne sont pas affectées en mode hors ligne et que la migration est transparente.

Network Slicing is a major stake in 5G networks and beyond, which is mainly enabled by Network Function Virtualization (NFV) and Software Defined Networks (SDN). These two paradigms enable telcos to offer virtual networks meeting specific needs of the vertical markets on the top on the same shared physical infrastructure. An important challenge in the implementation at scale of Network Slicing is Network Slice Placement and the optimal allocation of virtualized resources. This can be formulated as a multi-objective Integer Linear Programming (ILP) problem. However, ILP suffers from combinatorial explosion when solving NP-hard problem, especially for large-scale scenarios. Heuristics and Machine Learning (ML) algorithms have been investigated as efficient means of tackling this kind of problem.This PhD thesis investigates how to optimize Network Slice Placement in distributed large-scale infrastructures focusing on online heuristic and Deep Reinforcement Learning (DRL) based approaches. First, we rely on ILP to propose a data model for enabling on-Edge and on-Network Slice Placement. In contrary to most studies related to placement in the NFV context, the proposed ILP model considers complex Network Slice topologies and pays special attention to the geographic location of Network Slice Users and its impact on the End-to-End (E2E) latency. Extensive numerical experiments show the relevance of taking into account the user location constraints. Then, we rely on an approach called the “Power of Two Choices"(P2C) to propose an online heuristic algorithm for the problem which is adapted to support placement on large-scale distributed infrastructures while integrating Edge-specific constraints. The evaluation results show the good performance of the heuristic that solves the problem in few seconds under a large-scale scenario. The heuristic also improves the acceptance ratioof Network Slice Placement Requests when compared against a deterministic online ILP-based solution.Finally, we investigate the use of ML methods, more specifically DRL, for increasing scalability and automation of Network Slice Placement considering a multi-objective optimization approach to the problem. We first propose a DRL algorithm for Network Slice Placement which relies on the Advantage Actor Critic algorithm for fast learning, and Graph Convolutional Networks for feature extraction automation. Then, we propose an approach we call Heuristically Assisted Deep Reinforcement Learning (HA-DRL), which uses heuristics to control the learning and execution of the DRL agent. We evaluate this solution trough simulations under stationary, cycle-stationary and non-stationary network load conditions. The evaluation results show that heuristic control is an efficient way of speeding up the learning process of DRL, achieving a substantial gain in resource utilization, reducing performance degradation, and is more reliable under unpredictable changes in network load than non-controlled DRL algorithms.; Le découpage du réseau est un enjeu majeur des réseaux 5G et au-delà, ce qui est principalement permis par la virtualisation des fonctions réseau (NFV) et les réseaux définis par logiciel (SDN). Ces deux paradigmes permettent aux opérateurs de télécommunications de proposer des réseaux virtuels répondant aux besoins spécifiques des marchés verticaux en utilisant une même infrastructure physique partagée. Un défi important dans la mise en oeuvre à l’échelle du découpage du réseau est le placement des tranches de réseau et l’allocation optimale des ressources virtualisées. Ce problème peut être formulé comme un problème d’optimisation multi-objectifs via la programmation linéaire en nombres entiers (ILP). Cependant, l’ILP souffre d’une explosion combinatoire lors de la résolution de problèmes NP-difficiles, en particulier pour les scénarios à grande échelle. Les heuristiques et les algorithmes d’apprentissage automatique (ML) sont envisagés comme des moyens efficaces pour résoudrece type de problème. Cette thèse examine comment optimiser le placement de tranches (slices) de réseau dans les infrastructures distribuées à grande échelle en se concentrant sur des approches heuristiques en ligne et basées sur l’apprentissage par renforcement profond (DRL). Tout d’abord, nous nous appuyons sur l’ILP pour proposer un modèle de données permettant le placement de tranches de réseau sur le bord et le coeur du réseau. Contrairement à la plupart des études relatives au placement de fonctions réseau virtualisées, le modèle ILP proposé prend en compte les topologies complexes des tranches de réseau et accorde une attention particulière à l’emplacement géographique des utilisateurs des tranches réseau et à son impact sur le calcul de la latence de bout en bout. Des expérimentations numériques nous ont permis de montrer la pertinence de la prise en compte des contraintes de localisation des utilisateurs. Ensuite, nous nous appuyons sur une approche appelée "Power of Two Choices" pour proposer un algorithme heuristique en ligne qui est adapté à supporter le placement sur des infrastructures distribuées à grande échelle tout en intégrant des contraintes spécifiques au bord du réseau. Les résultats de l’évaluation montrent la bonne performance de l’heuristique qui résout le problème en quelques secondes dans un scénario à grande échelle. L’heuristique améliore également le taux d’acceptation des demandes de placement de tranches de réseau parrapport à une solution déterministe en ligne en utilisant l’ILP. Enfin, nous étudions l’utilisation de méthodes de ML, et plus particulièrement de DRL, pour améliorer l’extensibilité et l’automatisation du placement de tranches réseau en considérant une version multi-objectif du problème. Nous proposons d’abord un algorithme DRL pour le placement de tranches réseau qui s’appuie sur l’algorithme "Advantage Actor Critic" pour un apprentissage rapide, et sur les réseaux convolutionels degraphes pour l’extraction de propriétés. Ensuite, nous proposons une approche que nous appelons "Heuristically Assisted DRL" (HA-DRL), qui utilise des heuristiques pour contrôler l’apprentissage et l’exécution de l’agent DRL. Nous évaluons cette solution par des simulations dans des conditions de charge de réseau stationnaire, ensuite cyclique et enfin non-stationnaire. Les résultats de l’évaluation montrent que le contrôle par heuristique est un moyen efficace d’accélérer le processus d’apprentissage du DRL, et permet d’obtenir un gain substantiel dans l’utilisation des ressources, de réduire la dégradation des performances et d’être plus fiable en cas de changements imprévisibles de la charge du réseau que les algorithmes DRL non contrôlés.

The 5G network specification requires ACID properties (Atomicity, Consistency, Isolation, Durability) for its distributed database. According to the CAP theorem, these properties are incompatible with high availability for a geo-distributed system. Since availability is an obligation for mobile networks, this contradiction challenges the specification. Our thesis focus on a study of the usage of data in the network that allow us to extract weaker consistency properties that are still sufficient to maintain the correctness of the data. In the case a Network Slicing, an innovation of the 5G network, we propose to study further the enforcement of one of these properties, through the example of the enforcement of a global limit on the resource usage of a slice. Slices are deployed over a potentially large are, and so is their data, which make the enforcement of a limit more challenging. We propose several algorithms placed at different points of the consistency spectrum and study their performance in a simulation of the 5G network., La spécification du réseau 5G requiert des propriétés ACID (Atomicity, Consistency, Isolation, Durability) pour sa base de données distribuée. D’après le théorème de CAP, ce niveau de cohérence est incompatible avec un système géo-distribué de haute disponibilité. Les réseaux mobiles étant sujets à des obligations de disponibilité, cette contradiction remet en question la spécification. Notre thèse se concentre sur une étude de l’usage des données dans le réseau qui nous permet d’en extraire des propriétés de cohérence plus faibles que ACID mais suffisantes pour que ces données restent correctes. Dans le cas du Network Slicing, une innovation propre aux réseaux 5G, nous proposons une étude plus approfondie de l’application d’une de ces propriétés, à travers l’exemple d’une limite qui borne globalement l’utilisation des ressources du réseau pour un slice. Les données liées à une slice sont potentiellement largement distribuées, et l’application d’une limite y est donc plus difficile. Nous proposons plusieurs algorithmes placés à différents niveaux de cohérence afin d’étudier leur performance dans une simulation du réseau 5G.

International audience; Edge applications, such as gaming, cooperative engineering, or in-the-field information sharing, enjoy immediate response, autonomy and availability by distributing and replicating data at the edge. However, application developers and users demand the highest possible consistency guarantees, and specific support for group collaboration. To address this challenge, Colony guarantees Transactional Causal Plus Consistency (TCC+) globally, strengthened to Snapshot Isolation within edge groups. To help with scalability, fault tolerance and security, its logical communication topology is forest-like, with replicated roots in the core cloud, but with the flexibility to migrate a node or a group. Despite this hybrid approach, applications enjoy the same semantics everywhere in the topology. Our experiments show that local caching and peer groups improve throughput and response time significantly, performance is not affected in offline mode, and that migration is seamless.

International audience; Weighted voting is a conventional approach to improving the performance of replicated systems based on commonly-used majority quorum systems in heterogeneous environments. In long-lived systems, a weight reassignment protocol is required to reassign weights over time in order to accommodate performance variations accordingly. The weight reassignment protocol should be consensus-free in asynchronous failure-prone systems because of the impossibility of solving consensus in such systems. This paper presents an efficient consensus-free weight reassignment protocol for atomic storage systems in heterogeneous, dynamic, and asynchronous messagepassing systems. An experimental evaluation shows that the proposed protocol improves the performance of atomic read/write storage implemented by majority quorum systems compared with previous solutions.

International audience; This paper presents CEL, a new distributed eventual leader election algorithm for dynamic networks, which exploits topological information to improve the choice of a central leader and reduce message exchanges. The algorithm has a crosslayer neighbors detection, with a neighbor-aware mechanism, to improve the sharing of topological knowledge and elect a central leader faster. It uses a self-pruning mechanism based on topological knowledge, combined with probabilistic gossip, to improve the performance of broadcast propagation. Evaluations were conducted on the OMNeT++ environment, simulating realistic MANET with interference, collision, and messages loss. Using different parameters values, we have compared CEL to Gómez-Calzado et al. algorithm [1], on the Random Walk and the Truncated Lévy Walk mobility models. The results show better performances than [1], including fewer messages sent, shortest paths to the leader, and a more stable algorithm.

International audience; Stream processing systems (SPS) have to deal with highly dynamic scenarios where its adaptation is mandatory in order to accomplish realistic applications requirements. In this work, we propose a new adaptive SPS for real-time processing that, based on input data rate variation, dynamically adapts the number of active operator replicas. Our SPS extends Storm by pre-allocating, for each operator, a set of inactive replicas which are activated (or deactivated) when necessary without the Storm reconfiguration cost. We exploit the MAPE model and define a new metric that aggregates the value of multiple metrics to dynamically changes the number of replicas of an operator. We deploy our SPS over Google Cloud Platform and results confirm that our metric can tolerate highly dynamic conditions, improving resource usage while preserving high throughput and low latency.

International audience; Nowadays, there is a shift in the deployment model of Cloud and Edge applications. Applications are now deployed as a set of several small units communicating with each other - the microservice model. Moreover, each unit - a microservice, may be implemented as a virtual machine, container, function, etc., spanning the different Cloud and Edge service models including IaaS, PaaS, FaaS. A microservice is instantiated upon the reception of a request (e.g., an http packet or a trigger), and a rack-level or data-center-level scheduler decides the placement for such unit of execution considering for example data locality and load balancing. With such a configuration, it is common to encounter scenarios where different units, as well as multiple instances of the same unit, may be running on a single server at the same time.When multiple microservices are running on the same server not necessarily all of them are doing actual processing, some may be busy-waiting - i.e., waiting for events (or requests) sent by other units. However, these "idle" units are consuming CPU time which could be used by other running units or cloud utility functions on the server (e.g., monitoring daemons). In a controlled experiment, we observe that units can spend up to 20% - 55% of their CPU time waiting, thus a great amount of CPU time is wasted; these values significantly grow when overcommitting CPU resources (i.e., units CPU reservations exceed server CPU capacity), where we observe up to 69% - 75%. This is a result of the lack of information/context about what is running in each unit from the server CPU scheduler perspective.In this paper, we first provide evidence of the problem and discuss several research questions. Then, we propose an handful of solutions worth exploring that consists in revisiting hypervisor and host OS scheduler designs to reduce the CPU time wasted on idle units. Our proposal leverages the concepts of informed scheduling, and monitoring for internal and external events. Based on the aforementioned solutions, we propose our initial implementation on Linux/KVM.

We consider online learning for optimal network slice placement under the assumption that slice requests arrive according to a non-stationary Poisson process. We propose a framework based on Deep Reinforcement Learning (DRL) combined with a heuristic to design algorithms. We specifically design two pure-DRL algorithms and two families of hybrid DRL-heuristic algorithms. To validate their performance, we perform extensive simulations in the context of a large-scale operator infrastructure. The evaluation results show that the proposed hybrid DRL-heuristic algorithms require three orders of magnitude of learning episodes less than pure-DRL to achieve convergence. This result indicates that the proposed hybrid DRL-heuristic approach is more reliable than pure-DRL in a real non-stationary network scenario., arXiv admin note: text overlap with arXiv:2105.06741

International audience; Due to the rise of AI applications, machine learning (ML) libraries, often written in Python, have become far more accessible. ML libraries tend to be updated periodically, which may deprecate existing APIs, making it necessary for application developers to update their usages. In this paper, we build a tool to automate deprecated API usage updates. We first present an empirical study to better understand how updates of deprecated ML API usages in Python can be done. The study involves a dataset of 112 deprecated APIs from Scikit-Learn, TensorFlow, and PyTorch. Guided by the findings of our empirical study, we propose MLCatchUp, a tool to automate the updates of Python deprecated API usages, that automatically infers the API migration transformation through comparison of the deprecated and updated API signatures. These transformations are expressed in a Domain Specific Language (DSL). We evaluate MLCatchUp using a dataset containing 267 files with 551 API usages that we collected from public GitHub repositories. In our dataset, MLCatchUp can detect deprecated API usages with perfect accuracy, and update them correctly for 80.6% of the cases. We further improve the accuracy of MLCatchUp in performing updates by adding a feature that allows it to accept an additional user input that specifies the transformation constraints in the DSL for context-dependent API migration. Using this addition, MLCatchUp can make correct updates for 90.7% of the cases.

International audience; FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks. In this article, we propose a round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity (Class TC^R of Time-varying Graph formalism). Initially, processes only know the number of processes N in the system and their identifier. Due to the dynamics of the network links, messages can be lost. Since no unbounded timestamp is used to identify a message, its size is bounded to 2N + O(log(N)) + msgSize bits where msgSize is the bound size in bits of the broadcast data. We also present an FIFO atomic broadcast algorithm in Class TC^R that uses the proposed FIFO broadcast and deliver primitives.

Tool Paper; International audience; Machine learning (ML) libraries are gaining vast popularity, especially in the Python programming language. Using the latest version of such libraries is recommended to ensure the best performance and security. When migrating to the latest version of a machine learning library, usages of deprecated APIs need to be updated, which is a time-consuming process. In this paper, we propose MLCatchUp, an automated API usage update tool for deprecated APIs of popular ML libraries written in Python. MLCatchUp automatically infers the required transformation to migrate usages of deprecated API through the differences between the deprecated and updated API signatures. MLCatchUp offers a readable transformation rule in the form of a domain specific language (DSL). We evaluate MLCatchUp using a dataset of 267 real-world Python code containing 551 usages of 68 distinct deprecated APIs, where MLCatchUp achieves 90.7% accuracy. A video demonstration of MLCatchUp is available at https://youtu.be/5NjOPNt5iaA.

The evaluation of the impact of using Machine Learning in the management of softwarized networks is considered in multiple research works. Beyond that, we propose to evaluate the robustness of online learning for optimal network slice placement. A major assumption to this study is to consider that slice request arrivals are non-stationary. In this context, we simulate unpredictable network load variations and compare two Deep Reinforcement Learning (DRL) algorithms: a pure DRL-based algorithm and a heuristically controlled DRL as a hybrid DRL-heuristic algorithm, to assess the impact of these unpredictable changes of traffic load on the algorithms performance. We conduct extensive simulations of a large-scale operator infrastructure. The evaluation results show that the proposed hybrid DRL-heuristic approach is more robust and reliable in case of unpredictable network load changes than pure DRL as it reduces the performance degradation. These results are follow-ups for a series of recent research we have performed showing that the proposed hybrid DRL-heuristic approach is efficient and more adapted to real network scenarios than pure DRL., arXiv admin note: substantial text overlap with arXiv:2105.06741, arXiv:2108.02495

International audience; Building scalable and highly available geo-replicated file systems is hard. These systems need to resolve conflicts that emerge in concurrent operations in a way that maintains file system invariants, is meaningful to the user, and does not depart from the traditional file system interface. Conflict resolution in existing systems often leads to unexpected or inconsistent results. This paper introduces ElmerFS, a geo-replicated, truly concurrent file system designed with the aim of addressing these challenges. ElmerFS is based on two key ideas: (1) the use of Conflict-Free Replicated Data Types (CRDTs) for representing file system structures, which ensures that replicas converge to a correct state, and (2) conflict resolution rules, which are determined by the choice of CRDT types and their composition, designed with the principle of being intuitive to the user. We argue that if the state of the file system after resolving a conflict conveys to the user the resolved conflict in an intuitive way, the user can complement or reverse it using traditional file system operations. We discuss the challenges in the design of geo-replicated weakly consistent file systems, and present the design of ElmerFS.

International audience; Whenever a bug or vulnerability is detected in the Linux kernel, the kernel developers will endeavour to fix it by introducing a patch into the mainline version of the Linux kernel source tree. However, many users run older "stable" versions of Linux, meaning that the patch should also be "backported" to one or more of these older kernel versions. This process is error-prone and there is usually a long delay in publishing the backported patch. Based on an empirical study, we show that around 8% of all commits submitted to Linux mainline are backported to older versions, but often more than one month elapses before the backport is available. Hence, we propose a patch backporting technique that can automatically transfer patches from the mainline version of Linux into older stable versions. Our approach first synthesizes a partial transformation rule based on a Linux mainline patch. This rule can then be generalized by analysing the alignment between the mainline and target versions. The generalized rule is then applied to the target version to produce a backported patch. We have implemented our transformation technique in a tool called FixMorph and evaluated it on 350 Linux mainline patches. FixMorph correctly backports 75.1% of them. Compared to existing techniques, FixMorph improves both the precision and recall in backporting patches. Apart from automation of software maintenance tasks, patch backporting helps in reducing the exposure to known security vulnerabilities in stable versions of the Linux kernel.

International audience; Les algorithmes à phases ou à round comme l'algorithme de Paxos sont généralement très coûteux en messages. Si l'ajout d'un temporisateur et/ou de mécanisme système d'agrégation dans les couches basses permet d'en réduire le coût, cela se fait au prix d'une dégradation de leurs performances. Dans cet article, nous proposons un mécanisme générique d'agrégation des messages qui permet d'exploiter les propriétés de ces algorithmes pour réduire le nombre de message sans dégrader les performances de l'algorithme initial. En outre, notre mécanisme ne nécessite pas de modifications de l'algorithme ciblé et peut adresser le cas d'algorithmes s'exécutant en concurrence sur les mêmes noeuds. Nos expérimentations sur l'algorithme de Paxos ont ainsi montré qu'il est possible d'économiser jusqu'à environ 40% de messages sans dégrader significativement la latence des consensus.

International audience; Cet article présente un nouvel algorithme de segmentation d'images en régions basé sur l'approche Split & Merge. Les algorithmes de Split & Merge ont par nature, un temps d'exécution dépendant des données car le critère d'arrêt de ces deux étapes est lié à l'homogénéité de chaque région. Si les précédents algorithmes ont permis de rendre l'étape de Split bien moins sensible aux données, l'étape de Merge, bien plus complexe, reste toujours très sensible au contenu de l'image. Une structure TTA (Three Table Array) est introduite dans l'étape de Merge pour éliminer les réallocations mémoire dues aux fusions de tableaux. Comme cette structure entraîne une perte de localité lors du parcours des tableaux, nous proposons d'ajouter deux mécanismes implémentant un cache logiciel afin d'en limiter l'impact. Une étude expérimentale menée sur un système embarqué (carte Nvidia Jetson NX) a montré que notre algorithme de Merge est 10.6 fois plus rapide que l'état de l'art pour des images 960 × 720 tout en ayant un temps d'exécution bien moins sensible aux images segmentées.

International audience; Development of an HPC simulation code may take years of a domain scientists' work. Over that timespan, the computing landscape evolves, efficient programming best practices change, APIs of performance libraries change, etc. A moment then comes where the entire codebase requires a thorough performance lift. In the luckiest case, the required intervention is limited to a few hot loops. In practice, much more is needed. This paper describes an activity of programmatic refactoring of ≈200k lines of C code by means of source-to-source translation. The context is that of a so-called high level support provided to the domain scientists community by a HPC service center. The motivation of this short paper is the immediate reuse potential of these techniques.

Designing distributed applications involves a fundamental trade-off between safety and performance as described by CAP theorem. We focus on the cases where safety is the top requirement.For the subclass of state-based distributed systems, we propose a proof methodology for establishing that a given application maintains a given invariant. Our approach allows reasoning about individual operations separately. We demonstrate that our rules are sound, and with a mechanized proof engine, we illustrate their use with some representative examples. For conflicting operations, the developer can choose between conflict resolution or coordination. We present a novel replicated tree data structure that supports coordination-free concurrent atomic moves, and arguably maintains the tree invariant. Our analysis identifies cases where concurrent moves are inherently safe. For the remaining cases we devise a conflict resolution algorithm. The trade-off is that in some cases a move operation "loses". Given the coordination required by some application for safety, it can be implemented in many different ways. Even restricting to locks, they can use various configurations, differing by lock granularity, type, and placement. The performance of each configuration depends on workload. We study the "coordination lattice", i.e., design space of lock configurations, and define a set of metrics to systematically navigate them., La conception d'applications distribuées implique fondamentalement un compromis entre la sûreté et les performances. Nous nous concentrons sur les cas où la sûreté est la principale exigence. Dans le cadre des systèmes distribués basés sur l'état, nous proposons une méthodologie de preuve pour établir qu'une application donnée maintient un invariant donné. Notre approche permet de raisonner sur les opérations individuelles séparément. Nous démontrons que nos règles sont correctes et, à l'aide d'un moteur de preuve, nous illustrons leur utilisation par quelques exemples représentatifs. Pour les opérations conflictuelles, le développeur peut choisir entre la résolution de conflit ou la coordination. Nous présentons une nouvelle structure de données en forme d'arbre répliqué qui prend en charge les déplacements atomiques concurrents sans coordination et qui maintient l'invariant de l'arbre. Notre analyse identifie les cas où les déplacements concurrents sont intrinsèquement sûrs. Pour les autres cas, nous concevons un algorithme de résolution des conflits. La contrepartie est que dans certains cas, une opération de déplacement est "perdante". Étant donné la coordination requise par certaines applications pour la sûreté, elle peut être implémentée de nombreuses façons différentes. Même en se limitant aux verrous, ceux-ci peuvent utiliser diverses configurations qui diffèrent par: la granularité, le type et le placement. La performance de chaque configuration dépend de la charge de travail. Nous étudions le "treillis de coordination", l'espace de conception des configurations de verrouillage, et définissons un ensemble de mesures pour y naviguer systématiquement.

National audience

National audience

National audience

In 2017, NIST shook the cryptographic world by starting a process for standardizing post-quantum cryptography. Sixty-four submissions have been considered for the first round of the on-going NIST Post-Quantum Cryptography (PQC) process. Multivariate cryptography is a classical post-quantum candidate that turns to be the most represented in the signature category. At this stage of the process, it is of primary importance to investigate efficient implementations of the candidates. This article presents MQsoft, an efficient library which permits to implement HFE-based multivariate schemes submitted to the NIST PQC process such as GeMSS, Gui and DualModeMS. The library is implemented in C targeting Intel 64-bit processors and using avx2 set instructions. We present performance results for our library and its application to GeMSS, Gui and DualModeMS. In particular, we optimize several crucial parts for these schemes. These include root finding for HFE polynomials and evaluation of multivariate quadratic systems in F2. We propose a new method which accelerates root finding for specific HFE polynomials by a factor of two. For GeMSS and Gui, we obtain a speed-up of a factor between 2 and 19 for the keypair generation, between 1.2 and 2.5 for the signature generation, and between 1.6 and 2 for the verifying process. We have also improved the arithmetic in F2n by a factor of 4 compared to the NTL library. Moreover, a large part of our implementation is protected against timing attacks., IACR Transactions on Cryptographic Hardware and Embedded Systems, Volume 2019, Issue 3

We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in B α ∈ L [ y ] , where L = Q ( α ) is a simple algebraic extension of the rational numbers. We revisit two approaches for the problem. In the first approach, using resultant computations, we perform a reduction to a polynomial with integer coefficients and we deduce a bound of O ˜ B ( N 8 ) for isolating the real roots of B α , where N is an upper bound on all the quantities (degree and bitsize) of the input polynomials. The bound becomes O ˜ B ( N 7 ) if we use Pan's algorithm for isolating the real roots. In the second approach we isolate the real roots working directly on the polynomial of the input. We compute improved separation bounds for the roots and we prove that they are optimal, under mild assumptions. For isolating the real roots we consider a modified Sturm algorithm, and a modified version of descartes ' algorithm. For the former we prove a Boolean complexity bound of O ˜ B ( N 12 ) and for the latter a bound of O ˜ B ( N 5 ) . We present aggregate separation bounds and complexity results for isolating the real roots of all polynomials B α k , when α k runs over all the real conjugates of α. We show that we can isolate the real roots of all polynomials in O ˜ B ( N 5 ) . Finally, we implemented the algorithms in C as part of the core library of MATHEMATICA and we illustrate their efficiency over various data sets.

International audience; The vulnerability window of a hypervisor regarding a given security flaw is the time between the identification of the flaw and the integration of a correction/patch in the running hypervisor. Most vulnerability windows, regardless of severity, are long enough (several days) that attackers have time to perform exploits. Nevertheless, the number of critical vulnerabilities per year is low enough to allow an exceptional solution. This paper introduces hypervisor transplant, a solution for addressing vulnerability window of critical flaws. It involves temporarily replacing the current datacenter hypervisor (e.g., Xen) which is subject to a critical security flaw, by a different hypervisor (e.g., KVM) which is not subject to the same vulnerability. We build HyperTP, a generic framework which combines in a unified way two approaches: in-place server micro-rebootbased hypervisor transplant (noted InPlaceTP) and live VM migration-based hypervisor transplant (noted MigrationTP). We describe the implementation of HyperTP and its extension for transplanting Xen with KVM and vice versa. We also show that HyperTP is easy to integrate with the OpenStack cloud computing platform. Our evaluation results show that HyperTP delivers satisfactory performance: (1) MigrationTP takes the same time and impacts virtual machines (VMs) with the same performance degradation as normal live migration. (2) the downtime imposed by InPlaceTP on VMs is in the same order of magnitude (1.7 seconds for a VM with 1 vCPU and 1 GB of RAM) as in-place upgrade of homogeneous hypervisors based on server micro-reboot. CCS Concepts • Security and privacy → Virtualization and security. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

International audience; In-memory key-value stores are critical components that help scale large internet services by providing low-latency access to popular data. Memcached, one of the most popular key-value stores, suffers from performance limitations inherent to the Linux networking stack and fails to achieve high performance when using high-speed network interfaces. While the Linux network stack can be bypassed using DPDK based solutions, such approaches require a complete redesign of the software stack and induce high CPU utilization even when client load is low. To overcome these limitations, we present BMC, an inkernel cache for Memcached that serves requests before the execution of the standard network stack. Requests to the BMC cache are treated as part of the NIC interrupts, which allows performance to scale with the number of cores serving the NIC queues. To ensure safety, BMC is implemented using eBPF. Despite the safety constraints of eBPF, we show that it is possible to implement a complex cache service. Because BMC runs on commodity hardware and requires modification of neither the Linux kernel nor the Memcached application, it can be widely deployed on existing systems. BMC optimizes the processing time of Facebook-like small-size requests. On this target workload, our evaluations show that BMC improves throughput by up to 18x compared to the vanilla Memcached application and up to 6x compared to an optimized version of Memcached that uses the SO_REUSEPORT socket flag. In addition, our results also show that BMC has negligible overhead and does not deteriorate throughput when treating non-target workloads.

The tree is an essential data structure in many applications. In a distributed application, such as a distributed file system, the tree is replicated.To improve performance and availability, different clients should be able to update their replicas concurrently and without coordination. Such concurrent updates converge if the effects commute, but nonetheless, concurrent moves can lead to incorrect states and even data loss. Such a severe issue cannot be ignored; ultimately, only one of the conflicting moves may be allowed to take effect. However, as it is rare, a solution should be lightweight. Previous approaches would require preventative cross-replica coordination, or totally order move operations after-the-fact, requiring roll-back and compensation operations. In this paper, we present a novel replicated tree that supports coordination-free concurrent atomic moves, and provably maintains the tree invariant. Our analysis identifies cases where concurrent moves are inherently safe, and we devise a lightweight, coordination-free, rollback-free algorithm for the remaining cases, such that a maximal safe subset of moves takes effect. We present a detailed analysis of the concurrency issues with trees, justifying our replicated tree data structure. We provide mechanized proof that the data structure is convergent and maintains the tree invariant. Finally, we compare the response time and availability of our design against the literature.; L’arbre est une structure de données essentielle. Quand l’application est distribuée, par exemple dans un système de fichiers distribué, l’arbre est répliqué. Pour améliorer les performances et la disponibilité, les différents clients doivent pouvoir mettre à jour leurs répliques simultanément et sans coordination. Celles-ci convergent si les mises à jour commutent entre elles ; néanmoins, même dans ce cas, des opérations “move” concurrentes peuvent conduire à des états incorrects, et même à la perte de données. Au bout du compte, entre deux opérations “move” en conflit, seule l’une des deux peut être autorisée à prendre effet. Cependant, comme ce cas est rare, la solution doit être légère. Les approches précédentes nécessitaient une coordination préventive des répliques, ou des retours en arrière a posteriori. Dans cet article, nous présentons un nouvel arbre répliqué, qui met en œuvre une opération “move” atomique sans coordination, et dont nous prouvons qu’il maintient l’invariant d’arbre.Notre analyse identifie les cas où les “move” concurrents sont intrinsèquement sûrs, et proposons un algorithme léger, sans coordination et sans retour-arrière, pour les autres cas, de sorte qu’un sous-ensemble maximal et sûr de “move” prenne effet. Nous présentons une analyse détaillée des problèmes de cohérence dans les arbres. Nous fournissons une preuve mécanisée que la structure des données est convergente et maintientl’invariant d’arbre. Enfin, nous comparons le temps de réponse et la disponibilité de notre concept à la littérature.

The tree is an essential data structure in many applications. In a distributed application, such as a distributed file system, the tree is replicated.To improve performance and availability, different clients should be able to update their replicas concurrently and without coordination. Such concurrent updates converge if the effects commute, but nonetheless, concurrent moves can lead to incorrect states and even data loss. Such a severe issue cannot be ignored; ultimately, only one of the conflicting moves may be allowed to take effect. However, as it is rare, a solution should be lightweight. Previous approaches would require preventative cross-replica coordination, or totally order move operations after-the-fact, requiring roll-back and compensation operations. In this paper, we present a novel replicated tree that supports coordination-free concurrent atomic moves, and provably maintains the tree invariant. Our analysis identifies cases where concurrent moves are inherently safe, and we devise a lightweight, coordination-free, rollback-free algorithm for the remaining cases, such that a maximal safe subset of moves takes effect. We present a detailed analysis of the concurrency issues with trees, justifying our replicated tree data structure. We provide mechanized proof that the data structure is convergent and maintains the tree invariant. Finally, we compare the response time and availability of our design against the literature.; L’arbre est une structure de données essentielle. Quand l’application est distribuée, par exemple dans un système de fichiers distribué, l’arbre est répliqué. Pour améliorer les performances et la disponibilité, les différents clients doivent pouvoir mettre à jour leurs répliques simultanément et sans coordination. Celles-ci convergent si les mises à jour commutent entre elles ; néanmoins, même dans ce cas, des opérations “move” concurrentes peuvent conduire à des états incorrects, et même à la perte de données. Au bout du compte, entre deux opérations “move” en conflit, seule l’une des deux peut être autorisée à prendre effet. Cependant, comme ce cas est rare, la solution doit être légère. Les approches précédentes nécessitaient une coordination préventive des répliques, ou des retours en arrière a posteriori. Dans cet article, nous présentons un nouvel arbre répliqué, qui met en œuvre une opération “move” atomique sans coordination, et dont nous prouvons qu’il maintient l’invariant d’arbre.Notre analyse identifie les cas où les “move” concurrents sont intrinsèquement sûrs, et proposons un algorithme léger, sans coordination et sans retour-arrière, pour les autres cas, de sorte qu’un sous-ensemble maximal et sûr de “move” prenne effet. Nous présentons une analyse détaillée des problèmes de cohérence dans les arbres. Nous fournissons une preuve mécanisée que la structure des données est convergente et maintientl’invariant d’arbre. Enfin, nous comparons le temps de réponse et la disponibilité de notre concept à la littérature.

The tree is an essential data structure in many applications. In a distributed application, such as a distributed file system, the tree is replicated.To improve performance and availability, different clients should be able to update their replicas concurrently and without coordination. Such concurrent updates converge if the effects commute, but nonetheless, concurrent moves can lead to incorrect states and even data loss. Such a severe issue cannot be ignored; ultimately, only one of the conflicting moves may be allowed to take effect. However, as it is rare, a solution should be lightweight. Previous approaches would require preventative cross-replica coordination, or totally order move operations after-the-fact, requiring roll-back and compensation operations. In this paper, we present a novel replicated tree that supports coordination-free concurrent atomic moves, and provably maintains the tree invariant. Our analysis identifies cases where concurrent moves are inherently safe, and we devise a lightweight, coordination-free, rollback-free algorithm for the remaining cases, such that a maximal safe subset of moves takes effect. We present a detailed analysis of the concurrency issues with trees, justifying our replicated tree data structure. We provide mechanized proof that the data structure is convergent and maintains the tree invariant. Finally, we compare the response time and availability of our design against the literature.; L’arbre est une structure de données essentielle. Quand l’application est distribuée, par exemple dans un système de fichiers distribué, l’arbre est répliqué. Pour améliorer les performances et la disponibilité, les différents clients doivent pouvoir mettre à jour leurs répliques simultanément et sans coordination. Celles-ci convergent si les mises à jour commutent entre elles ; néanmoins, même dans ce cas, des opérations “move” concurrentes peuvent conduire à des états incorrects, et même à la perte de données. Au bout du compte, entre deux opérations “move” en conflit, seule l’une des deux peut être autorisée à prendre effet. Cependant, comme ce cas est rare, la solution doit être légère. Les approches précédentes nécessitaient une coordination préventive des répliques, ou des retours en arrière a posteriori. Dans cet article, nous présentons un nouvel arbre répliqué, qui met en œuvre une opération “move” atomique sans coordination, et dont nous prouvons qu’il maintient l’invariant d’arbre.Notre analyse identifie les cas où les “move” concurrents sont intrinsèquement sûrs, et proposons un algorithme léger, sans coordination et sans retour-arrière, pour les autres cas, de sorte qu’un sous-ensemble maximal et sûr de “move” prenne effet. Nous présentons une analyse détaillée des problèmes de cohérence dans les arbres. Nous fournissons une preuve mécanisée que la structure des données est convergente et maintientl’invariant d’arbre. Enfin, nous comparons le temps de réponse et la disponibilité de notre concept à la littérature.

International audience; Since its commercialization in 1971, the microprocessor, a modern and integrated form of the central processing unit, has continuously broken records in terms of its integrated functions, computing power, low costs and energy saving status. Today, it is present in almost all electronic devices. Sound knowledge of its internal mechanisms and programming is essential for electronics and computer engineers to understand and master computer operations and advanced programming concepts.This book in five volumes focuses more particularly on the first two generations of microprocessors, those that handle 4- and 8-bit integers. Microprocessor 5 – the fifth and final volume of this series of books – first presents the hardware and software aspects of the development chain of a microprocessor-based digital system. Finally, to round up the series and offer a historical perspective, the architectures of the first microcomputers are detailed. A comprehensive approach is used, with examples drawn from current and past technologies that illustrate theoretical concepts, making them accessible.

International audience; We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [Kushilevitz, Ostrovsky, and Rosén, J. Comput. Syst. Sci., 58 (1999), pp. 129--136] and [Gál and Rosén, SIAM J. Comput., 31 (2002), pp. 1424--1437]. More concretely, we consider the randomness complexity of the basic Boolean function \tt and, that serves as a building block in the design of many private protocols. We show that \tt and cannot be privately computed using a single random bit, thus giving the first nontrivial lower bound on the 1-private randomness complexity of an explicit Boolean function, $f: \{0,1\}^n \rightarrow \{0,1\}$. We further show that and, on any number of inputs $n$ (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of $n=3$ players), improving the upper bound of 73 random bits implicit in [Kushilevitz, Ostrovsky, and Rosén, J. Comput. Syst. Sci., 58 (1999), pp. 129--136]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of \tt and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for \tt xor, which is 1-random, and for several degenerate functions).

National audience

International audience; Nested/Extended Page Table (EPT) is the current hardware solution for virtualizing memory in virtualized systems. It induces a significant performance overhead due to the 2D page walk it requires, thus 24 memory accesses on a TLB miss (instead of 4 memory accesses in a native system). This 2D page walk constraint comes from the utilization of paging for managing virtual machine (VM) memory. This paper shows that paging is not necessary in the hypervisor. Our solution Compromis, a novel Memory Management Unit, uses direct segments for VM memory management combined with paging for VM's processes. This is the first time that a direct segment based solution is shown to be applicable to the entire VM memory while keeping applications unchanged. Relying on the 310 studied datacenter traces, the paper shows that it is possible to provision up to 99.99% of the VMs using a single memory segment. The paper presents a systematic methodology for implementing Compromis in the hardware, the hypervisor and the datacenter scheduler. Evaluation results show that Compromis outperforms the two popular memory virtualization solutions: shadow paging and EPT by up to 30% and 370% respectively.

We propose to demonstrate a network slice placement optimization solution based on Deep Reinforcement Learning (DRL), referred to as Heuristically-controlled DRL, which uses a heuristic to control the DRL algorithm convergence. The solution is adapted to realistic networks with large scale and under non-stationary traffic conditions (namely, the network load). We demonstrate the applicability of the proposed solution and its higher and stable performance over a non-controlled DRL-based solution. Demonstration scenarios include full online learning with multiple volatile network slice placement request arrivals., Comment: arXiv admin note: substantial text overlap with arXiv:2010.08295

International audience; We revisit the problem of integer factorization with number-theoretic oracles, including a well-known problem: can we factor an integer N unconditionally, in deterministic polynomial time, given the value of the Euler totient $ϕ(N)$? We show that this can be done, under certain size conditions on the prime factors of N. The key technique is lattice basis reduction using the LLL algorithm. Among our results, we show for example that if N is a squarefree integer with a prime factor $p > √ N$ , then we can recover p in deterministic polynomial time given $ϕ(N)$. We also shed some light on the analogous problems for Carmichael's function, and the order oracle that is used in Shor's quantum factoring algorithm.