Peer-to-Peer Prefix Tree for Large Scale Service Discovery

The problem studied in this thesis is the service discovery on platforms distributed at large scale, a service being a computing service (software components, scientific computing libraries, or binaries) offered with some characteristics and a performance level related to the hardware supporting it. Traditional approaches, designed for reliable and small scale environments, rely upon centralized solutions, unable to scale well in geographically distributed unreliable platforms. Our contribution centers around three main parts. 1) We propose a novel approach called DLPT (Distributed Lexicographic Placement Table), whose design is inspired by peer-to-peer systems. It calls upon an indexing system structured as a prefix tree. This structure supports multi-attribute range queries. 2) We study the mapping of nodes of this tree onto heterogeneous processors of the dynamic underlying network. We propose and adapt some load balancing heuristics for this kind of architectures. 3) Our architecture, targeted for platforms within which processors are unreliable and constantly joining and leaving the network, requires fault-tolerance mechanisms. Replication, usually used, is costly and unable to manage transient faults. We propose alternative best-effort mechanisms based on the self-stabilization theory for the construction and maintenance of prefix trees in a peer-to-peer environment. Among the mechanisms provided, one is proven to be snap-stabilizing. This means that the tree is rebuilt in an optimal time after an arbitrary number of faults. This approach is written in a coarse grain communication model and assumes several restrictions on initial topology handled, making it hard to implement on real platforms. To address these drawbacks, another self-stabilizing protocol is given for actual message-passing environments. Finally, we present a software prototype of this architecture and its first promising experiments on the Grid'5000 platform.Cette thèse étudie la découverte de services (composants logiciels, exécutables, librairies scientifiques) sur des plates-formes distribuées à grande échelle. Les approches traditionnelles, proposées pour des environnements stables et relativement petits, s'appuient sur des techniques centralisées impropres au passage à l'échelle dans des environnements géographiquement distribués et instables. Notre contribution s'articule autour de trois axes. 1) Nous proposons une nouvelle approche appelée DLPT (Distributed Lexicographic Placement Table), qui s'inspire des systèmes pair-à-pair et s'appuie sur un réseau de recouvrement structuré en arbre de préfixes. Cette structure permet des recherches multi-attributs sur des plages de valeurs. 2) Nous étudions la distribution des noeuds de l'arbre sur les processeurs de la plate-forme sous-jacente, distribuée, dynamique et hétérogène. Nous proposons et adaptons des heuristiques de répartition de la charge pour ce type d'architectures. 3) Notre plate-forme cible, par nature instable, nécessite des mécanismes robustes pour la tolérance aux pannes. La réplication traditionnellement utilisée s'y avère coûteuse et incapable de gérer des fautes transitoires. Nous proposons des techniques de tolérance aux pannes best-effort fondées sur la théorie de l'auto-stabilisation pour la construction d'arbres de préfixes dans des environnements pair-à-pair. Nous présentons deux approches. La première, écrite dans un modèle théorique à gros grain, permet de maintenir des arbres de préfixes instantanément stabilisants, c'est-à-dire reconstruits en un temps optimal après un nombre arbitraire de fautes. La deuxième, écrite dans le modèle à passage de messages, permet l'implantation d'une telle architecture dans des réseaux très dynamiques. Enfin, nous présentons un prototype logiciel mettant en oeuvre cette architecture et présentons ses premières expérimentations sur la plate-forme Grid'5000