Structures et systèmes répartis

The distributed system model is opposed to the traditional "client/server" model because of the absence of a central server. Removing such central server has benefits since the whole network does not depend on a single point of failure anymore, the system is more robust. But this removal has a cost: the server centralizes data and has a global (full) knowledge of the system. Contrarily, in a distributed system, no entity has such a global knowledge of the system and its state. Each entity exchanges data with a subset of the system entities. We then speak about local (or partial) view of the system. In this thesis, we study the structure induced by these local visions along with the impact of this structure on distributed applications. Our study will use different distributed system models: the partially synchronous model, the peer-to-peer model and the sensor network model. Our approach breaks down in three parts: i) we show the impact of communication structures on distributed applications an show how to capture this impact. Then, ii) we show how ssumptions on the communication structure allow solving two traditional problems of distributed systems. Finally, iii) we show how to transform these communication structures into logical and explicit structures, in our case we build a coordinate system.Le modèle du système réparti s'oppose au modèle classique dit ''client-serveur'' par l'absence de serveur central. Supprimer ce serveur a des conséquences bénéfiques: le réseau entier ne dépend plus de cette unique entité et ainsi un système réparti est plus robuste. Mais cette suppression a aussi un coût: le serveur centralise les données et a une connaissance globale (ou totale) du système. Dans un système réparti au contraire, aucune entité n'a de connaissance globale du système et de son état. Chaque entité échange de l'information avec un sous-ensemble des entités du système. On parle alors de vision locale (ou partielle) du système. Dans cette thèse, nous nous intéressons à la structure induite par ces visions locales et à son impact sur les applications réparties. Notre étude prend pour contexte différents modèles des systèmes répartis: le modèle partiellement synchrone, le modèle pair-à-pair et le modèle des réseaux de capteurs fixes. Notre approche se divise en trois parties: 1) nous montrons l'impact des structures de communication sur les applications réparties, et proposons une manière de capturer cet impact. Ensuite, 2) nous montrons comment l'utilisation d'hypothèses sur ces structures permet de résoudre deux problèmes classiques des systèmes répartis. Enfin 3) nous montrons comment transformer ces structures de communication en des structures logiques et explicites: les systèmes de coordonnées