|
PEPITO PEer-toPeer Implementation and TheOry
|
|||||||||||||||||||
Consistency and approximate replication models (SICS:6, UCL:12) …
Network topology and efficient diffusion algorithms (KTH:18) …
Distributed directory service (KTH:18) …
Failure detectors (INRIA:10)…
The work during this period has addressed the following topics:
Peer-to-Peer lookup services are mechanisms to locate items in a network of nodes. The items could be any type of information including documents, physical resources or simply items in naming services. An important task of the project is to study and design fully decentralized algorithms for peer-to-peer lookup in a dynamic network of peers. Generally two schemes have been previously proposed. One is based on a form of blind search by flooding the neighbourhood of a node up to a certain depth; a typical representative of this system are Gnutella and FreeNet. The second scheme is based on organizing the set of nodes in the network as a Distributed Hash-Table (DHT) and designing a routing algorithm for locating an item based on a given key. This scheme has been proposed recently; for instance in the Chord work at MIT, and the Tapestry system at Berkeley.
We have worked on a proposal of a generalized framework for service lookup based on distributed hash-tables; see [1]. For instance this proposal generalizes both Chord and Tapestry.
We have also started investigating combination of flooding based and DHT systems; see [2]. This will allow for search of items that are not key-based and also for better search performance.
Another issue that we have investigated is how to improve the mapping of the virtual peer-to-peer network into the physical network, in terms of various metrics, see [3]. This results in an adaptive virtual network that improves depending on the current conditions of the underlying physical network.
We are also working on a large-scale simulation environment for testing and evaluating various peer-to-peer algorithms.
Initial work has been done on the issue of designing adaptive failure detectors components, mainly by L. Onana. (KTH).
J. Leifer
has worked on a prototype in Ocaml of a communications library for distributed
algorithms, such as reliable broadcast and consensus, that are robust with
respect to the failure of hosts (machines) and network links. He has considered
a class of algorithms designed by S. Toueg and colleagues that make use of
failure detectors --- oracles which habitually update a list of hosts suspected
of failure, usually based on timeout information.
Nestmann and Aberer (EPFL) started discussion on the process-algebraic description of randomized distributed algorithms for constructing P-Grids (scalable data access structures used in a number of p2p-implementations).
(also WP1) Nestmann continued working on process-algebraic descriptions of consensus algorithms, and their proofs. One important obervation was the rediscovery, by accident, of failure detectors that were previously only used as an auxiliary tool in some proofs.