Search

A plethora of optimized mutual exclusion lock algorithms have been designed over the past 25 years to mitigate performance bottlenecks related to critical sections and synchronization. Unfortunately, there is currently no broad study of the behavior of these optimized lock algorithms on realistic applications that consider different performance metrics, such as energy efficiency and tail latency. In this thesis, we perform a thorough and practical analysis, with the goal of providing software developers with enough information to achieve fast, scalable and energy-efficient synchronization in their systems. First, we provide a performance study of 28 state-of-the-art mutex lock algorithms, on 40 applications, and four different multicore machines. We not only consider throughput (traditionally the main performance metric), but also energy efficiency and tail latency, which are becoming increasingly important. Second, we present an in-depth analysis in which we summarize our findings for all the studied applications. In particular, we describe nine different lock-related performance bottlenecks, and propose six guidelines helping software developers with their choice of a lock algorithm according to the different lock properties and the application characteristics.From our detailed analysis, we make a number of observations regarding locking algorithms and application behaviors, several of which have not been previously discovered: (i) applications not only stress the lock/unlock interface, but also the full locking API (e.g., trylocks, condition variables), (ii) the memory footprint of a lock can directly affect the application performance, (iii) for many applications, the interaction between locks and scheduling is an important application performance factor, (iv) lock tail latencies may or may not affect application tail latency, (v) no single lock is systematically the best, (vi) choosing the best lock is difficult (as it depends on many factors such as the workload and the machine), and (vii) energy efficiency and throughput go hand in hand in the context of lock algorithms. These findings highlight that locking involves more considerations than the simple “lock – unlock” interface and call for further research on designing low-memory footprint adaptive locks that fully and efficiently support the full lock interface, and consider all performance metrics., Une multitude d’algorithmes d’exclusion mutuelle ont été conçus au cours des vingt cinq dernières années, dans le but d’améliorer les performances liées à l’exécution de sections critiques et aux verrous. Malheureusement, il n’existe actuellement pas d’étude générale et complète au sujet du comportement de ces algorithmes d’exclusionmutuelle sur des applications réalistes (par opposition à des applications synthétiques) qui considère plusieurs métriques de performances, telles que l’efficacité énergétique ou la latence. Dans cette thèse, nous effectuons une analyse pragmatique des mécanismes d’exclusion mutuelle, dans le but de proposer aux développeurs logiciels as-sez d’informations pour leur permettre de concevoir et/ou d’utiliser des mécanismes rapides, qui passent à l’échelle et efficaces énergétiquement.Premièrement, nous effectuons une étude de performances de 28 algorithmes d’exclusion mutuelle faisant partie de l’état de l’art, en considérant 40 applications et quatre machines multicoeurs différentes. Nous considérons non seulement le débit (la métrique de performance traditionnellement considérée), mais aussi l’efficacité énergétique et la latence, deux facteurs qui deviennent de plus en plus importants. Deuxièmement, nous présentons une analyse en profondeur de nos résultats. Plus particulièrement, nous décrivons neufs problèmes de performance liés aux verrous et proposons six recommandations aidant les développeurs logiciels dans le choix d’un algorithme d’exclusion mutuelle, se basant sur les caractéristiques de leur application ainsi que les propriétés des différents algorithmes.A partir de notre analyse détaillée, nous faisons plusieurs observations relatives à l’interaction des verrous et des applications, dont plusieurs d’entre elles sont à notre connaissance originales : (i) les applications sollicitent fortement les primitives lock/unlock mais aussi l’ensemble des primitives de synchronisation liées à l’exclusionmutuelle (ex. trylocks, variables de conditions), (ii) l’empreinte mémoire d’un verrou peut directement impacter les performances de l’application, (iii) pour beaucoup d’applications, l’interaction entre les verrous et l’ordonnanceur du système d’exploitation est un facteur primordial de performance, (iv) la latence d’acquisition d’un verrou a un impact très variable sur la latence d’une application, (v) aucun verrou n’est systématiquement le meilleur, (vi) choisir le meilleur verrou est difficile, et (vii) l’efficacité énergétique et le débit vont de pair dans le contexte des algorithmes d’exclusion mutuelle.Ces découvertes mettent en avant le fait que la synchronisation à base de verrou ne se résume pas seulement à la simple interface “lock – unlock”. En conséquence, ces résultats appellent à plus de recherche dans le but de concevoir des algorithmes d’exclusion mutuelle avec une empreinte mémoire faible, adaptatifs et qui implémententl’ensemble des primitives de synchronisation liées à l’exclusion mutuelle. De plus, ces algorithmes ne doivent pas seulement avoir de bonnes performances d’un point de vue du débit, mais aussi considérer la latence ainsi que l’efficacité énergétique.

A plethora of optimized mutual exclusion lock algorithms have been designed over the past 25 years to mitigate performance bottlenecks related to critical sections and synchronization. Unfortunately, there is currently no broad study of the behavior of these optimized lock algorithms on realistic applications that consider different performance metrics, such as energy efficiency and tail latency. In this thesis, we perform a thorough and practical analysis, with the goal of providing software developers with enough information to achieve fast, scalable and energy-efficient synchronization in their systems. First, we provide a performance study of 28 state-of-the-art mutex lock algorithms, on 40 applications, and four different multicore machines. We not only consider throughput (traditionally the main performance metric), but also energy efficiency and tail latency, which are becoming increasingly important. Second, we present an in-depth analysis in which we summarize our findings for all the studied applications. In particular, we describe nine different lock-related performance bottlenecks, and propose six guidelines helping software developers with their choice of a lock algorithm according to the different lock properties and the application characteristics.From our detailed analysis, we make a number of observations regarding locking algorithms and application behaviors, several of which have not been previously discovered: (i) applications not only stress the lock/unlock interface, but also the full locking API (e.g., trylocks, condition variables), (ii) the memory footprint of a lock can directly affect the application performance, (iii) for many applications, the interaction between locks and scheduling is an important application performance factor, (iv) lock tail latencies may or may not affect application tail latency, (v) no single lock is systematically the best, (vi) choosing the best lock is difficult (as it depends on many factors such as the workload and the machine), and (vii) energy efficiency and throughput go hand in hand in the context of lock algorithms. These findings highlight that locking involves more considerations than the simple “lock – unlock” interface and call for further research on designing low-memory footprint adaptive locks that fully and efficiently support the full lock interface, and consider all performance metrics.; Une multitude d’algorithmes d’exclusion mutuelle ont été conçus au cours des vingt cinq dernières années, dans le but d’améliorer les performances liées à l’exécution de sections critiques et aux verrous. Malheureusement, il n’existe actuellement pas d’étude générale et complète au sujet du comportement de ces algorithmes d’exclusionmutuelle sur des applications réalistes (par opposition à des applications synthétiques) qui considère plusieurs métriques de performances, telles que l’efficacité énergétique ou la latence. Dans cette thèse, nous effectuons une analyse pragmatique des mécanismes d’exclusion mutuelle, dans le but de proposer aux développeurs logiciels as-sez d’informations pour leur permettre de concevoir et/ou d’utiliser des mécanismes rapides, qui passent à l’échelle et efficaces énergétiquement.Premièrement, nous effectuons une étude de performances de 28 algorithmes d’exclusion mutuelle faisant partie de l’état de l’art, en considérant 40 applications et quatre machines multicoeurs différentes. Nous considérons non seulement le débit (la métrique de performance traditionnellement considérée), mais aussi l’efficacité énergétique et la latence, deux facteurs qui deviennent de plus en plus importants. Deuxièmement, nous présentons une analyse en profondeur de nos résultats. Plus particulièrement, nous décrivons neufs problèmes de performance liés aux verrous et proposons six recommandations aidant les développeurs logiciels dans le choix d’un algorithme d’exclusion mutuelle, se basant sur les caractéristiques de leur application ainsi que les propriétés des différents algorithmes.A partir de notre analyse détaillée, nous faisons plusieurs observations relatives à l’interaction des verrous et des applications, dont plusieurs d’entre elles sont à notre connaissance originales : (i) les applications sollicitent fortement les primitives lock/unlock mais aussi l’ensemble des primitives de synchronisation liées à l’exclusionmutuelle (ex. trylocks, variables de conditions), (ii) l’empreinte mémoire d’un verrou peut directement impacter les performances de l’application, (iii) pour beaucoup d’applications, l’interaction entre les verrous et l’ordonnanceur du système d’exploitation est un facteur primordial de performance, (iv) la latence d’acquisition d’un verrou a un impact très variable sur la latence d’une application, (v) aucun verrou n’est systématiquement le meilleur, (vi) choisir le meilleur verrou est difficile, et (vii) l’efficacité énergétique et le débit vont de pair dans le contexte des algorithmes d’exclusion mutuelle.Ces découvertes mettent en avant le fait que la synchronisation à base de verrou ne se résume pas seulement à la simple interface “lock – unlock”. En conséquence, ces résultats appellent à plus de recherche dans le but de concevoir des algorithmes d’exclusion mutuelle avec une empreinte mémoire faible, adaptatifs et qui implémententl’ensemble des primitives de synchronisation liées à l’exclusion mutuelle. De plus, ces algorithmes ne doivent pas seulement avoir de bonnes performances d’un point de vue du débit, mais aussi considérer la latence ainsi que l’efficacité énergétique.

Dynamic systems are distributed systems in which (1) processes can join or leave the system during the run, and (2) the communication graph evolves over time. The failure detector abstraction was introduced as a way to circumvent the impossibility of solving consensus in asynchronous systems prone to crash failures. A failure detector is a local oracle that provides processes in the system with unreliable information on process failures. But a failure detector that is sufficient to solve a given problem in a static system is not necessarily sufficient to solve the same problem in a dynamic system. Additionally, some existing failure detectors cannot be implemented in dynamic systems. Therefore, it is necessary to redefine existing failure detectors and provide new algorithms. In this thesis, we provide a new definition of a failure detector for k-set agreement, and prove that it is sufficient to solve k-set agreement in dynamic systems. We also design a dynamic system model and an algorithm that implements this new failure detector. Additionally, we adapt an existing failure detector for mutual exclusion and prove that it is still the weakest failure detector to solve mutual exclusion in dynamic systems, which means that it is weaker than any other failure detector capable of solving mutual exclusion.; Les systèmes dynamiques sont des systèmes distribués dans lesquels (1) les processus peuvent rejoindre ou quitter le système en cours d'exécution, et (2) le graphe de communication évolue au fil du temps. L'abstraction des détecteurs de fautes a été introduite afin de contourner l'impossibilité de résoudre le consensus dans les systèmes asynchrones sujets aux pannes franches. Mais un détecteur de fautes qui est suffisant pour résoudre un problème donné dans un système statique n'est pas nécessairement suffisant pour résoudre le même problème dans un système dynamique. Par conséquent, il est nécessaire de redéfinir les détecteurs de fautes existants et de concevoir de nouveaux algorithmes. Dans cette thèse, nous fournissons une nouvelle définition d'un détecteur de fautes pour le k-accord, et nous prouvons qu'il est suffisant pour résoudre le k-accord dans un système dynamique. Nous définissons également un modèle de système dynamique, ainsi qu'un algorithme capable d'implémenter ce nouveau détecteur de fautes dans notre modèle. De plus, nous adaptons un détecteur existant pour l'exclusion mutuelle et nous prouvons que même dans les systèmes dynamiques, il s'agit toujours du détecteur de fautes le plus faible pour résoudre l'exclusion mutuelle. Cela signifie que ce détecteur est plus faible que tous les autres détecteurs capables de résoudre l'exclusion mutuelle.

Dynamic systems are distributed systems in which (1) processes can join or leave the system during the run, and (2) the communication graph evolves over time. The failure detector abstraction was introduced as a way to circumvent the impossibility of solving consensus in asynchronous systems prone to crash failures. A failure detector is a local oracle that provides processes in the system with unreliable information on process failures. But a failure detector that is sufficient to solve a given problem in a static system is not necessarily sufficient to solve the same problem in a dynamic system. Additionally, some existing failure detectors cannot be implemented in dynamic systems. Therefore, it is necessary to redefine existing failure detectors and provide new algorithms. In this thesis, we provide a new definition of a failure detector for k-set agreement, and prove that it is sufficient to solve k-set agreement in dynamic systems. We also design a dynamic system model and an algorithm that implements this new failure detector. Additionally, we adapt an existing failure detector for mutual exclusion and prove that it is still the weakest failure detector to solve mutual exclusion in dynamic systems, which means that it is weaker than any other failure detector capable of solving mutual exclusion.; Les systèmes dynamiques sont des systèmes distribués dans lesquels (1) les processus peuvent rejoindre ou quitter le système en cours d'exécution, et (2) le graphe de communication évolue au fil du temps. L'abstraction des détecteurs de fautes a été introduite afin de contourner l'impossibilité de résoudre le consensus dans les systèmes asynchrones sujets aux pannes franches. Mais un détecteur de fautes qui est suffisant pour résoudre un problème donné dans un système statique n'est pas nécessairement suffisant pour résoudre le même problème dans un système dynamique. Par conséquent, il est nécessaire de redéfinir les détecteurs de fautes existants et de concevoir de nouveaux algorithmes. Dans cette thèse, nous fournissons une nouvelle définition d'un détecteur de fautes pour le k-accord, et nous prouvons qu'il est suffisant pour résoudre le k-accord dans un système dynamique. Nous définissons également un modèle de système dynamique, ainsi qu'un algorithme capable d'implémenter ce nouveau détecteur de fautes dans notre modèle. De plus, nous adaptons un détecteur existant pour l'exclusion mutuelle et nous prouvons que même dans les systèmes dynamiques, il s'agit toujours du détecteur de fautes le plus faible pour résoudre l'exclusion mutuelle. Cela signifie que ce détecteur est plus faible que tous les autres détecteurs capables de résoudre l'exclusion mutuelle.

Distributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time.; Les systèmes à grande échelle comme les Grilles ou les Nuages (Clouds) mettent à disposition pour les utilisateurs des ressources informatiques hétérogènes. Dans les Nuages, les accès aux ressources sont orchestrés par des contrats permettant de définir un niveau de qualité de service (temps de réponse, disponibilité ...) que le fournisseur doit respecter. Ma thèse a donc contribué à concevoir de nouveaux algorithmes distribués de verrouillage de ressources dans les systèmes large échelle en prenant en compte des notions de qualité de service. Dans un premier temps, mes travaux de thèse se portent sur des algorithmes distribués de verrouillage ayant des contraintes en termes de priorités et de temps. Deux algorithmes d'exclusion mutuelle ont été proposés : un algorithme prenant en compte les priorités des clients et un autre pour des requêtes avec des dates d'échéance. Dans un second temps, j'ai abordé le problème de l'exclusion mutuelle généralisée pour allouer de manière exclusive plusieurs types de ressources hétérogènes. J'ai proposé un nouvel algorithme qui réduit les coûts de synchronisation en limitant la communication entre processus non conflictuels. Tous ces algorithmes ont été implémentés et évalués sur la plateforme nationale Grid 5000. Les évaluations ont montré que nos algorithmes satisfaisaient bien les contraintes applicatives tout en améliorant de manière significative les performances en termes de taux d'utilisation et de temps de réponse.

Distributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time.; Les systèmes à grande échelle comme les Grilles ou les Nuages (Clouds) mettent à disposition pour les utilisateurs des ressources informatiques hétérogènes. Dans les Nuages, les accès aux ressources sont orchestrés par des contrats permettant de définir un niveau de qualité de service (temps de réponse, disponibilité ...) que le fournisseur doit respecter. Ma thèse a donc contribué à concevoir de nouveaux algorithmes distribués de verrouillage de ressources dans les systèmes large échelle en prenant en compte des notions de qualité de service. Dans un premier temps, mes travaux de thèse se portent sur des algorithmes distribués de verrouillage ayant des contraintes en termes de priorités et de temps. Deux algorithmes d'exclusion mutuelle ont été proposés : un algorithme prenant en compte les priorités des clients et un autre pour des requêtes avec des dates d'échéance. Dans un second temps, j'ai abordé le problème de l'exclusion mutuelle généralisée pour allouer de manière exclusive plusieurs types de ressources hétérogènes. J'ai proposé un nouvel algorithme qui réduit les coûts de synchronisation en limitant la communication entre processus non conflictuels. Tous ces algorithmes ont été implémentés et évalués sur la plateforme nationale Grid 5000. Les évaluations ont montré que nos algorithmes satisfaisaient bien les contraintes applicatives tout en améliorant de manière significative les performances en termes de taux d'utilisation et de temps de réponse.

National audience; Le Cloud computing marque une nouvelle avancée vers l'infrastructure informatique dématérialisée. Le Cloud fournit des ressources informatiques, logicielles ou matérielles, accessible à distance en tant que service. L'adoption de ce modèle soulève un certain nombre de défis, notamment au sujet de la qua- lité de service (QoS) des services fournis. En effet, alors qu'on assiste à une multiplication de services similaires sur le Cloud (stockage, environnement de développement, bureautique, etc.), rien ne nous permet d'évaluer la qualité d'un service rendu. Cet article présente une solution pour intégrer la QoS et le contrat SLA (Service Level Agreement) comme éléments à part entière du Cloud. Les contributions de cet article sont les suivantes. Premièrement, nous proposons le modèle de Cloud SLAaaS (SLA aware as a Service) qui apporte une dimension supplémentaire au paradigme de Cloud Computing. Deuxiè- mement, nous présentons le langage Cloud Service Level Agreement (CSLA) qui permet la définition et l'établissement d'un contrat qui supporte l'instabilité de la QoS dans un environnement hautement dynamique comme le Cloud en gérant finement la violation. Enfin, nous développons deux stratégies dirigées par CSLA pour pouvoir contrôler dynamiquement et de manière autonome la taille et la forme du Cloud pour répondre aux contraintes de SLA : i) une stratégie de planification de capacité pour le redimensionnement sur mesure et ii) une stratégie de verrouillage d'exclusion mutuelle pour assurer un accès exclusif à des ressources partagées sur le Cloud.

International audience; Les traits d'un objet sont les outils avec laquelle l'enfant commence à explorer le monde et à comprendre ses dimensions. La multiplication de ces traits se fait selon deux modèles différents : par addition des atomes de sens dans la théorie des traits sémantiques, et par morcellement des référentiels dans la théorie du contraste. Mais dans la pratique, il y a souvent des propriétés qui ne servent à rien, parce qu'elles ne construisent aucune différence utile avec aucun autre objet du même registre. Un objet n'est donc pas défini par l'ensemble de ses traits sémantiques. Il est défini par celles de ses propriétés qui construisent des contrastes avec des objets voisins Chaque fois qu'un objet dispose d'une propriété qui fait contraste par rapport à l'ensemble où il s'inscrit, l'enfant crée un nouveau nom pour définir son sous-ensemble. Le contraste permet en effet de théoriser le mécanisme de morcellement et de discrimination. Chaque fois que, dans un champ, certains éléments possèdent un trait sémantique qui permet de le contraster aux autres, le champ se morcelle : ce trait devient la propriété différentielle d'un sous-ensemble qui reçoit un nom. Ce processus apparaît chez l'enfant après la période correspondant aux surextensions et au premier vocabulaire, en gros au moment de l'explosion du vocabulaire entre 1 an et demi et 2 ans (Clark, 1988). Divers chercheurs dont Khaterine Nelson (1974) ont tenté de montrer que les catégorisations opérées par l'enfant ne reposent pas sur un ensemble de traits sémantiques perçus mais plutôt sur la mémorisation d'une expérimentation motrice, d'une investigation active de type piagétien. Dans des travaux menés en collaboration avec Jérôme Bruner, Nelson (1986) en est venue à l'idée que l'expérience qui structure le sens d'un mot n'est pas tant liée à une expérimentation de l'objet qu'à la prise en compte de la séquence de la vie quotidienne qui lui est associée.

Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of different groups. It is also called the "congenial talking philosophers problem".An example of application interesting is a CD jukebox (documentation, films...) on Internet: several users wishing to reach some CD will be able to do it at the same time instead of awaiting the end of the request of the other users. Effective solutions, written in the message passing model and based on the quorums on the one hand and the circulation of token on the other hand are presented in this thesis.We tackle also the problem of the mutual exclusion of group on the ad hoc mobile networks and we have proposed an algorithm which is sensitive to link formation and link breaking and thus which is suitable for ad hoc mobile networks.; L'exclusion mutuelle de groupe est une généralisation de l'exclusion mutuelle. Ce problème a été présenté par Joung et quelques algorithmes pour le problème ont été proposés en incorporant ds algorithmes d'exclusion mutuelle. L'exclusion mutuelle de groupe se produit naturellement dans une situation ou une ressource peut être partagée par des processus du même groupe, mais pas par des processus de différents groupes. Il est aussi appelé "problème des philosophes parlant d'une même voix". Un exemple d'application intéressant est un serveur CD (documentation, films...) sur Internet: plusieurs utilisateurs désirant accéder au même CD pourront le faire en même temps au lieu d'attendre la fin de la requête des autres utilisateurs. Des solutions efficaces, écrites dans le modèle à passage de messages et basées sur les quorums d'une part et sur la circulation de jeton d'autre part sont présentées dans cette thèse.Nous abordons aussi le problème de l'exclusion mutuelle de groupe sur les réseaux mobiles ad hoc et nous proposons un algorithme qui est sensible aux formations et coupures de liens et est ainsi approprié pour les réseaux mobiles ad hoc.

Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of different groups. It is also called the "congenial talking philosophers problem".An example of application interesting is a CD jukebox (documentation, films...) on Internet: several users wishing to reach some CD will be able to do it at the same time instead of awaiting the end of the request of the other users. Effective solutions, written in the message passing model and based on the quorums on the one hand and the circulation of token on the other hand are presented in this thesis.We tackle also the problem of the mutual exclusion of group on the ad hoc mobile networks and we have proposed an algorithm which is sensitive to link formation and link breaking and thus which is suitable for ad hoc mobile networks., L'exclusion mutuelle de groupe est une généralisation de l'exclusion mutuelle. Ce problème a été présenté par Joung et quelques algorithmes pour le problème ont été proposés en incorporant ds algorithmes d'exclusion mutuelle. L'exclusion mutuelle de groupe se produit naturellement dans une situation ou une ressource peut être partagée par des processus du même groupe, mais pas par des processus de différents groupes. Il est aussi appelé "problème des philosophes parlant d'une même voix". Un exemple d'application intéressant est un serveur CD (documentation, films...) sur Internet: plusieurs utilisateurs désirant accéder au même CD pourront le faire en même temps au lieu d'attendre la fin de la requête des autres utilisateurs. Des solutions efficaces, écrites dans le modèle à passage de messages et basées sur les quorums d'une part et sur la circulation de jeton d'autre part sont présentées dans cette thèse.Nous abordons aussi le problème de l'exclusion mutuelle de groupe sur les réseaux mobiles ad hoc et nous proposons un algorithme qui est sensible aux formations et coupures de liens et est ainsi approprié pour les réseaux mobiles ad hoc.

In this PhD thesis, we are interested in the notion of snap-stabilization. Thus, we first proposed two solutions to the depth-first search problem in arbitrary rooted networks. These two protocols are written in the state model and work under a distributed unfair daemon: the weakest scheduling assumption of the model. The first one is based on IDs lists. The other one uses a question mechanism instead of the IDs lists. We then propose two snap-stabilizing applications obtained with the previously presented depth-first search protocols. These two applications allow us to evaluate some global network properties. Actually, the first application marks the cutnodes and the bridges of the network. The second application allows us to evaluate if a given set of processors is a cutset of the network. Finally, in the last part, we generalize our approach by studying an efficient semi-automatic transformer that snap-stabilizes service protocols with a unique initiator. A depth-first search protocol as well as a breath-first spanning tree construction protocol show how our method is easy. Our depth-first search protocol is not only easy to write but its complexity is a trade-off between the list-based and the question-based solutions. Finally, using a counting property of our transformer, we show how to use this depth-first search protocol to solve in few lines the mutual exclusion problem in a snap-stabilizing manner.; Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de parcours en profondeur pour des réseaux enracinés quelconques. Ces deux protocoles sont écrits dans le modèle à états et fonctionnent sous l'hypothèse d'un démon distribué inéquitable : le démon le plus général du modèle. Le premier est basé sur des listes d'identités. Le second utilise un principe de question/réponse pour remplacer les listes d'identités. Nous proposons ensuite deux applications instantanément stabilisantes obtenues à partir de nos deux protocoles de parcours en profondeur. Ces deux applications évaluent des propriétés globales sur le réseau. La première application permet de marquer les points d'articulation et les isthmes du réseau. La seconde application permet d'évaluer si un ensemble donné est un ensemble séparateur du réseau. Enfin, dans une dernière partie, nous adoptons une approche plus générale en étudiant un protocole efficace permettant de transformer semi-automatiquement des protocoles de service mono-initiateurs en protocoles instantanément stabilisants. Un protocole de parcours en profondeur et un protocole de construction d'arbre en largeur illustrent la facilité avec laquelle nous pouvons rendre instantanément stabilisants ce type protocole grâce à notre transformateur. Le protocole de parcours en profondeur est non seulement trivial à écrire mais les performances obtenues en font un compromis quasi idéal entre les protocoles à listes et à questions présentés précédemment. Enfin, grâce à une propriété de comptage due à notre transformateur, nous montrerons comment utiliser ce protocole de parcours pour résoudre en quelques lignes l'exclusion mutuelle de manière instantanément stabilisante.

In this PhD thesis, we are interested in the notion of snap-stabilization. Thus, we first proposed two solutions to the depth-first search problem in arbitrary rooted networks. These two protocols are written in the state model and work under a distributed unfair daemon: the weakest scheduling assumption of the model. The first one is based on IDs lists. The other one uses a question mechanism instead of the IDs lists. We then propose two snap-stabilizing applications obtained with the previously presented depth-first search protocols. These two applications allow us to evaluate some global network properties. Actually, the first application marks the cutnodes and the bridges of the network. The second application allows us to evaluate if a given set of processors is a cutset of the network. Finally, in the last part, we generalize our approach by studying an efficient semi-automatic transformer that snap-stabilizes service protocols with a unique initiator. A depth-first search protocol as well as a breath-first spanning tree construction protocol show how our method is easy. Our depth-first search protocol is not only easy to write but its complexity is a trade-off between the list-based and the question-based solutions. Finally, using a counting property of our transformer, we show how to use this depth-first search protocol to solve in few lines the mutual exclusion problem in a snap-stabilizing manner.; Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de parcours en profondeur pour des réseaux enracinés quelconques. Ces deux protocoles sont écrits dans le modèle à états et fonctionnent sous l'hypothèse d'un démon distribué inéquitable : le démon le plus général du modèle. Le premier est basé sur des listes d'identités. Le second utilise un principe de question/réponse pour remplacer les listes d'identités. Nous proposons ensuite deux applications instantanément stabilisantes obtenues à partir de nos deux protocoles de parcours en profondeur. Ces deux applications évaluent des propriétés globales sur le réseau. La première application permet de marquer les points d'articulation et les isthmes du réseau. La seconde application permet d'évaluer si un ensemble donné est un ensemble séparateur du réseau. Enfin, dans une dernière partie, nous adoptons une approche plus générale en étudiant un protocole efficace permettant de transformer semi-automatiquement des protocoles de service mono-initiateurs en protocoles instantanément stabilisants. Un protocole de parcours en profondeur et un protocole de construction d'arbre en largeur illustrent la facilité avec laquelle nous pouvons rendre instantanément stabilisants ce type protocole grâce à notre transformateur. Le protocole de parcours en profondeur est non seulement trivial à écrire mais les performances obtenues en font un compromis quasi idéal entre les protocoles à listes et à questions présentés précédemment. Enfin, grâce à une propriété de comptage due à notre transformateur, nous montrerons comment utiliser ce protocole de parcours pour résoudre en quelques lignes l'exclusion mutuelle de manière instantanément stabilisante.