Système distribuée, Nommage, Beep, Élection du leader, Complexité énergétique, Diffusion d'information, Clusterisation, Complexité en temps, Randomisé, Réseaux radio, Synchronisé

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.