Summary
Motivation:Within computational grids, some computing services (software components, linear algebra libraries, etc.) are made available by some servers to some clients, with some characteristics and a performance level related to the hardware supporting it. In spite of the growing popularity of such grids, several factors have delayed their actual deployment at large scale. Among them, service discovery, although efficient in many cases, does not reach several requirements, mainly in terms of flexibility, scalability and efficiency on wide-area dynamic platforms, where the number of services and requests can be extremely large. It has become crucial to propose new tools coping with these new requirements. Peer-to-peer technologies provide scalable and fault-tolerant meanings for content distribution and retrieval, and has become a field of investigation for the design of future grids.
A prefix tree overlay:Among recently proposed solutions for peer-to-peer resource discovery, a new kind of overlay has appeared, based on tries, also known as lexicographic, or prefix trees. These overlays provide an efficient way for solving range queries, and supporting searches on partial string. In this category of tools, we developed the DLPT (Distributed Lexicographic Placement Table) approach, a service discovery solution based on an indexing system structured as a prefix tree in which services are registered as declared by servers. It supports exact match requests, partial search strings, and multi-attribute range queries.
Reducing maintenance and optimizing throughput:We have developed mechanisms to easily and efficiently distribute nodes of a virtual logical tree onto processors of the underlying network, without the need for an external device like a DHT. On top of this self-contained architecture, we have designed heuristics aimed at maximizing the throughput of the system in presence of heterogeneous processors and a large range of different popularity level for services requested.
Fault-tolerance and self-stabilization:Our architecture, targeted for platforms within which processors are unreliable and constantly joining and leaving the network, requires fault-tolerance mechanisms. Replication, usually used in such systems, 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 has been written for actual message-passing environments.
We have developed a software prototype of this architecture relying on the JXTA toolbox. We have conducted early experiments on the Grid'5000 platform and obtained promising results.
Dissertation| Cédric Tedeschi. Peer-to-Peer Prefix Tree for Large Scale Service Discovery. PhD thesis, École normale supérieure de Lyon, October 2008. [ bib | .pdf ] |
Defense slides