Dans la première partie de ce mémoire, nous étudions le modèle des protocoles de population, introduit dans\cite{DBLP:conf/podc/BeauquierBCK10}. Ce modèle permet de représenter les grands réseaux de capteurs (ou agents) mobiles anonymes dotés de faibles ressources. Les contraintes de ce modèle sont si sévères que la plupart des problèmes classiques d'algorithmique répartie, tels que la collecte de données, le consensus ou l'élection d'un leader, sont difficiles à analyser, sinon impossibles à résoudre.Nous commençons notre étude par le problème de collecte de données. Celui-ci consiste principalement à transférer des valeurs réparties dans la population d'agents mobiles vers une station de base en un minimum de temps (temps de convergence). En utilisant un hypothèse d'équité, dite hypothèse de temps couvertures et introduite dans \cite{DBLP:conf/podc/BeauquierBCK10}, nous calculons des bornes optimales sur le temps de convergences de différents protocoles concrets. Ensuite, nous étudions le problème du consensus et d'élection de leader. Il a été montré que ces problèmes sont impossibles à résoudre dans le modèle original des protocoles de population. Pour contourner cette impossibilité, il est possible d'adjoindre au modèle certaines hypothèses sous la forme d'oracles. Nous proposons ensuite divers oracles permettant de résoudre le problème du consensus et d'élection de leader dans divers environnements, et nous étudions leurs puissances relatives. Ce faisant, nous développons un cadre formel permettant de représenter toutes les variétés d'oracles introduites, ainsi que leur possibles relations.Dans la seconde partie de ce mémoire, nous étudions le problème de la réplication de machine à états finis dans le modèle (classique) de communications asynchrones à passage de message. L'algorithme Paxos, introduit dans \cite{lamportPartTimeParliament,lamport01paxos} est une solution (partielle) bien connue au problème de la réplication capable de tolérer des pannes crash. Notre contribution, dans cette partie,consiste à améliorer Paxos afin qu'il puisse également tolérer des défaillances transitoires. Ce faisant, nous définissons la notions de machine répliquée pratiquement autostable. / In the first part of this thesis, we focus on a recent model, calledpopulation protocols, which describes large networksof tiny wireless mobile anonymous agents with very limited resources.The harsh constraints of the original model makes most of theclassical problems of distributed algorithmics, such as datacollection, consensus and leader election, either difficult to analyzeor impossible to solve.We first study the data collection problem, which mainly consists intransferring some values to a base station. By using a fairnessassumption, known as cover times, we compute tight bounds on theconvergence time of concrete protocols. Next, we focus on theproblems of consensus and leader election. It is shown that theseproblems are impossible in the original model. To circumvent theseissues, we augment the original model with oracles, and study theirrelative power. We develop by the way a formal framework generalenough to encompass various sorts of oracles, as well as theirrelations.In the second part of the thesis, we study the problem ofstate-machine replication in the more classical model of asynchronousmessage-passing communication. The Paxos algorithm is a famous(partial) solution to the state-machine replication problem whichtolerates crash failures. Our contribution is the enhancement of Paxosin order to tolerate transient faults as well. Doing so, we define thenotion of practically self-stabilizing replicated state-machine.

Ce manuscrit contient d'abord l'étude d'une extension du modèle des protocoles de populations, qui représentent des réseaux de capteurs asynchrones, passivement mobiles, limités en ressources et anonymes. Pour la première fois (à notre connaissance), un modèle formel de consommation d'énergie est proposé pour les protocoles de populations. A titre d'application, nous étudions à la complexité en énergie (dans le pire des cas et en moyenne) pour le problème de collecte de données. Deux protocoles prenant en compte la consommation d'énergie sont proposés. Le premier est déterministe et le second randomisé. Pour déterminer les valeurs optimales des paramètres, nous faisons appel aux techniques d'optimisation. Nous appliquons aussi ces techniques dans un cadre différent, celui des réseaux de capteurs corporels (WBAN). Une formulation de flux est proposée pour acheminer de manière optimale les paquets de données en minimisant la pire consommation d'énergie. Une procédure de recherche à voisinage variable est développée et les résultats numériques montrent son efficacité. Enfin, nous considérons le problème d'optimisation avec des paramètres aléatoires. Précisément, nous étudions un modèle semi-défini positif sous contrainte en probabilité. Un nouvel algorithme basé sur la simulation est proposé et testé sur un problème réel de théorie du contrôle. Nous montrons que notre méthode permet de trouver une solution moins conservatrice que d'autres approches en un temps de calcul raisonnable. / In this thesis, we propose a formal energy model which allows an analytical study of energy consumption, for the first time in the context of population protocols. Population protocols model one special kind of sensor networks where anonymous and uniformly bounded memory sensors move unpredictably and communicate in pairs. To illustrate the power and the usefulness of the proposed energy model, we present formal analyses on time and energy, for the worst and the average cases, for accomplishing the fundamental task of data collection. Two power-aware population protocols, (deterministic) EB-TTFM and (randomized) lazy-TTF, are proposed and studied for two different fairness conditions, respectively. Moreover, to obtain the best parameters in lazy-TTF, we adopt optimization techniques and evaluate the resulting performance by experiments. Then, we continue the study on optimization for the power-aware data collection problem in wireless body area networks. A minmax multi-commodity netflow formulation is proposed to optimally route data packets by minimizing the worst power consumption. Then, a variable neighborhood search approach is developed and the numerical results show its efficiency. At last, a stochastic optimization model, namely the chance constrained semidefinite programs, is considered for the realistic decision making problems with random parameters. A novel simulation-based algorithm is proposed with experiments on a real control theory problem. We show that our method allows a less conservative solution, than other approaches, within reasonable time.