102 research outputs found
Time and Space Optimal Counting in Population Protocols
No full textThis work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of (exact) counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized.
This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of counting given the optimal space per agent. In the case of randomly interacting agents (probabilistic fairness), as usual, the convergence time is measured in terms of parallel time (or parallel interactions), which is defined as the number of pairwise interactions until convergence, divided by n (the number of agents). In case of weak fairness, where it is only required that every pair of agents interacts infinitely often, the convergence time is defined in terms of non-null transitions, i.e, the transitions that affect the states of the interacting agents.
First, assuming probabilistic fairness, we present a "non-guessing" time optimal protocol of O(n log n) expected time given an optimal space of only one bit, and we prove the time optimality of this protocol. Then, for weak fairness, we show that a space optimal (semi-uniform) solution cannot converge faster than in big-omega (2^n) time (non-null transitions). This result, together with the time complexity analysis of an already known space optimal protocol, shows that it is also optimal in time (given the optimal space constrains)
Space-Optimal Naming in Population Protocols
No full textThe distributed naming problem, assigning different names to the nodes in a distributed system, is a fundamental task. This problem is non trivial, specially when the amount of memory available for the task is low, and when requirements for fault-tolerance are added. The considered distributed computation model is population protocols. In this model, a priori anonymous and indistinguishable mobile nodes (called agents), communicate in pairs and in an asynchronous manner (according to a fairness condition). Fault-tolerance is addressed through self-stabilization, in terms of arbitrary initialization of agents. This work comprises a comprehensive study on the necessary and sufficient state space conditions for naming. It is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is presented
Mechanism for coherence, atomicity and communications at clusters level : application to adaptative distributed hierarchical clustering
No full textNous nous intéressons dans cette thèse à l'organisation des systèmes distribués dynamiquesde grande taille : ensembles de machines capables de communiquer entre elles et pouvant à toutinstant se connecter ou se déconnecter. Nous proposons de partitionner le système en groupesconnexes, appelés clusters. Afin d'organiser des réseaux de grande taille, nous construisons unestructure hiérarchique imbriquée dans laquelle les clusters d'un niveau sont regroupés au seinde clusters du niveau supérieur. Pour mener à bien ce processus, nous mettons en place desmécanismes permettant aux clusters d'être les noeuds d'un nouveau système distribué exécutantl'algorithme de notre choix. Cela nécessite en particulier des mécanismes assurant la cohérence decomportement pour le niveau supérieur au sein de chaque cluster. En permettant aux clusters deconstituer un nouveau système distribué exécutant notre algorithme de clustering, nous construisonsune hiérarchie de clusters par une approche ascendante. Nous démontrons cet algorithme endéfinissant formellement le système distribué des clusters, et en démontrant que chaque exécutionde notre algorithme induit sur ce système une exécution de l'algorithme de niveau supérieur. Celanous permet, en particulier, de démontrer par récurrence que nous calculons bien un clusteringhiérarchique imbriqué. Enfin, nous appliquons cette démarche à la résolution des collisions dansles réseaux de capteurs. Pour éviter ce phénomène, nous proposons de calculer un clusteringadapté du système, qui nous permet de calculer un planning organisant les communications ausein du réseau et garantissant que deux messages ne seront jamais émis simultanément dans laportée de communication de l'un des capteursTo manage and handle large scale distributed dynamic distributed systems, constitutedby communicating devices that can connect or disconnect at any time, we propose to computeconnected subgraphs of the system, called clusters. We propose to compute a hierarchical structure,in which clusters of a level are grouped into clusters of the higher level. To achieve this goal,we introduce mechanisms that allow clusters to be the nodes of a distinct distributed system,that executes an algorithm. In particular, we need mechanisms to maintain the coherence of thebehavior among the nodes of a cluster regarding the higher level. By allowing clusters to be nodesof a distributed system that executes a clustering algorithm, we compute a nested hierarchicalclustering by a bottom-up approach. We formally define the distributed system of clusters, andprove that any execution of our algorithm induces an execution of the higher level algorithm onthe distributed system of clusters. Then, we prove by induction that our algorithm computes anested hierarchical clustering of the system. Last, we use this approach to solve a problem thatappears in sensor networks : collision. To avoid collisions, we propose to compute a clusteringof the system. This clustering is then used to compute a communication schedule in which twomessages cannot be sent at the same time in the range of a senso
Optimisation locale d'un système distribué asynchrone sujet à des défaillances
No full textInternational audienceUn système distribué est constitué d'un ensemble de noeuds de calcul, exécutant chacun un algorithme dans le but de faire émerger une propriété globale dans le système. Les noeuds n'ont cependant qu'une connaissance partielle de l'état du système distribué, au travers des communications qu'ils entretiennent entre eux (messages, mémoire partagée, ou tout autre mécanisme de communication), communications qui peuvent être sujettes à des perturbations (asynchronisme, et pertes de messages en particulier).Le système distribué évolue par l'action des algorithmes exécutés par les différents noeuds, mais peut également subir des événements non-contrôlé par l'algorithme : pannes, changements du graphe de communication, etc.Chaque noeud doit donc exécuter un algorithme visant à optimiser le fonctionnement du système sur la base d'informations partielles et incertaines. Nous présenterons dans cet exposé plus particulièrement deux mécanismes probabilistes basés sur l'observation locale de l'état du système distribué : l'un vise à la construction de plus courts chemins, et l'autre à la circulation d'un jeton unique dans un système asynchrone sujet à des pertes de messages.</p
Optimisation locale d'un système distribué asynchrone sujet à des défaillances
No full textInternational audienceUn système distribué est constitué d'un ensemble de noeuds de calcul, exécutant chacun un algorithme dans le but de faire émerger une propriété globale dans le système. Les noeuds n'ont cependant qu'une connaissance partielle de l'état du système distribué, au travers des communications qu'ils entretiennent entre eux (messages, mémoire partagée, ou tout autre mécanisme de communication), communications qui peuvent être sujettes à des perturbations (asynchronisme, et pertes de messages en particulier).Le système distribué évolue par l'action des algorithmes exécutés par les différents noeuds, mais peut également subir des événements non-contrôlé par l'algorithme : pannes, changements du graphe de communication, etc.Chaque noeud doit donc exécuter un algorithme visant à optimiser le fonctionnement du système sur la base d'informations partielles et incertaines. Nous présenterons dans cet exposé plus particulièrement deux mécanismes probabilistes basés sur l'observation locale de l'état du système distribué : l'un vise à la construction de plus courts chemins, et l'autre à la circulation d'un jeton unique dans un système asynchrone sujet à des pertes de messages.</p
Stabilization Time for Token Replications in Self-Stabilizing Random Walk Based Distributed Algorithms
No full text
Modèles stochastiques pour l'évaluation des erreurs numériques
No full textL'idée de considérer les erreurs d'arrondi comme des variables aléatoires n'est pas nouvelle. Basées sur des outils tels que l'indépendance des variables aléatoires ou le théorème central limite, plusieurs propositions ont démontré des bornes d'erreur en O(√n). Cette thèse est dédiée à l'étude de l'arrondi stochastique (SR) en tant que remplaçant du mode d'arrondi déterministe par défaut. Tout d'abord, nous introduisons une nouvelle approche pour dériver une borne probabiliste de l'erreur en O(√n), basée sur le calcul de la variance et l'inégalité de Bienaymé-Chebyshev. Ensuite, nous développons un cadre général permettant l'analyse probabiliste des erreurs des algorithmes sous SR. Dans ce contexte, nous décomposons l'erreur en une martingale plus un biais. Nous montrons que le biais est nul pour les algorithmes présentant des erreurs multilinéaires, tandis que l'analyse probabiliste de la martingale conduit à des bornes probabilistes de l'erreur en O(√n). Pour le calcul de la variance, nous montrons que le biais est négligeable au premier ordre par rapport à la martingale, et nous prouvons des bornes probabilistes de l'erreur en O(√n).The idea of assuming rounding errors as random variables is not new. Based on tools such as independent random variables or the Central Limit Theorem, various propositions have demonstrated error bounds in O(√n). This thesis is dedicated to studying stochastic rounding (SR) as a replacement for the default deterministic rounding mode. First, we introduce a new approach to derive a probabilistic error bound in O(√n) based on variance calculation and Bienaymé-Chebyshev inequality. Second, we demonstrate a general framework that allows the probabilistic error analysis of algorithms under SR. In this context, we decompose the error into a martingale plus a drift. We show that the drift is zero for algorithms with multi-linear errors, while the probabilistic analysis of the martingale term leads to probabilistic error bounds in O(√n). We show that the drift is negligible at the first order compared to the martingale term for the variance computation, and we prove probabilistic error bounds in O(√n)
Automatic classification of dynamic graphs
No full textLes réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique.Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs
- …
