Communications décentralisées et modèle BIP

Cette thèse regroupe plusieurs travaux sur les problèmes de communication distribuée. En particulier, nous concevons des algorithmes randomisés résolvant les problèmes d'initialisation, de comptage, de diffusion et d'élection de leader. Les algorithmes présentés dans cette thèse sont conçus pour résoudre ces problèmes pour les réseaux radio à unique ou multiple sauts et les réseaux beeps. Nous nous concentrons sur l'optimisation de la complexité en temps d'éxecution ainsi que de la complexité énergétique de ces algorithmes. Un principe communément connu pour la conception d'algorithmes randomisés fait en sorte que chaque dispositif du réseau décide du calcul à effectuer de manière aléatoire à chaque temps d'exécution de l'algorithme. Par conséquent, nous proposons un nouveau paradigme, qui fait que chaque nœud génère des variables aléatoires suivant une distribution spécifique avant de communiquer sur le réseau de manière déterministe et distribuée. Tout au long de cette thèse, nous utilisons plusieurs distributions aléatoires pour résoudre chaque problème après l'autre. Nous proposons également un nouveau paradigme de "witnessing" (ou de témoignage) pour nous aider à optimiser la complexité en énergie des algorithmes. La première partie de la thèse (les trois premiers chapitres) fournit la description des modèles, des problèmes, des algorithmes existants et des mesures de complexité considérés dans la thèse. La deuxième partie présente les nouveaux algorithmes conçus pour résoudre ces problèmes.This thesis gathers several works on distributed communication problems. In particular, we focus on designing randomized distributed algorithms addressing the naming, the counting, the broadcasting and the leader election problems. The algorithms presented in this thesis are designed to resolve these problems on single-hop and multi-hop radio and beeping networks. We focus on optimizing the time complexity and the energy complexity of these algorithms. A commonly known principle for designing distributed random- ized algorithms makes each device of the network decide which computation to perform in a randomized manner at each time slot of the execution of the algorithm. Hence, we propose a new paradigm, which makes each node generate some random variables distributed following a specific distribution before communicating on the network in a distributed deterministic man- ner. Throughout this thesis, we use several random variable distributions to resolve each problem after the other. We also propose a new witnessing paradigm to help us optimize the energy complexity of the algorithms. The first part of the thesis (the first three chapters) provides the description of the models, problems, existing algorithms and complexity measures con- sidered in the thesis. The second part presents the new algorithms designed to resolve the considered problems