CS/SE Individual Practical Handout 2 - Week Beginning 21 January 2002
Last modified: 21 January 2002

Peer-to-Peer File Sharing

This is an individual project. In term 2 you are required to provide a prototype implementation of your system. The marking proforma for this part of the practical provides guidance on how to proceed and where you should direct your efforts.

Term 2 deadline: Mon 25 Feb at 17:00

Keep an eye on the eduni.dcs.cs3.ip for news, updates and clarifications.

This project is based on a design practical developed by the Chord group at MIT.

Introduction

Before beginning the implementation task you should review Handout 1 that provides the background to this practical and your design documents submitted for Part 1 of the practical. This handout tries to specify the task in a little more detail than Handout 1. Some of the details of the interfaces have been change to make the exposition clearer but there is no change in the overall task.

In response to suggestions at the Staff-Student Liason committee three different levels of task have been defined for this part of the practical. In submitting your implementation you can choose to supply a basic, enhanced or full implementation of the system. For more details see the proforma.

Your task

A peer-to-peer file system will consist of a collection of nodes that can store files. These nodes are computers whose users have agreed to make them available to store information. If such a file system were really successful it could end up having many millions of nodes. The main point of this practical is to let you consider some of the issues that arise in the construction of such systems. The main features of the system are:

There are some issues that arise from the above description:

Your design should be oriented to providing the implementation to an interface along the following lines:

// These are exceptions raised when some of the operations 
// of the system fail.

class InsertException extends Exception{}
class GetException extends Exception {}
class JoinException extends Exception {}

// The insert method publishes a document to the system.  This
// might fail for a variety of reasons, for example: the name is
// already in use, or the correspondence between the name and the
// document is not correct (e.g. it is not an SHA digest of the
// document).
//
// The get method gets a named document. Failure can arise if the 
// document cannot be found, there may be other failures.
//
// The leave method is called when the node wants to leave the
// filesystem

interface Publish {
    public void insert(byte[] document, byte[] name) throws InsertException;
    public byte[] get(byte[] name) throws GetException;
    public void leave();
}

// If we know the IP address of a node that is already running the
// filesystem we can join the filesystem.  If we provide the loopback 
// address then we create a new single node filesystem.  Join can fail
// for a variety of reasons, including the address being wrong, there
// being no filesystem running at the address, resource problems ...

interface FileSystem{
    public Publish join(String address);
}

Your goal in this part of the practical is to provide an implementation of these interfaces. The simple test harness provided assumes these are called MyFileSystem and MyPublish.

Your Implementation

In systems like this much of the effort is not in providing the service as described above but in ensuring the system has some additional qualities or features that ensure the system can be used in a real environment. For the filesystem example these include:

In providing your implementation you can choose how many of these issues you want to address. There are three kinds of implementation you can provide and the marks available differ for each:

Resources: Chord Implementation

Chord is described on a separate page. You don't have to understand its inner workings in order to use it, so you can safely skip the description. However, you may find that understanding Chord will give you better opportunities for optimisation. The interface we give here is in Java in order to simplify your design work.

You will be supplied with an implementation that supplies the basic functionality of a Chord system. It has some limited instrumentation to allow you to monitor the use of the system.

Chord assigns every participating node a 160-bit ID. Chord maps key k to the node with the smallest ID that follows k; that node is called k's successor. A Chord node does not keep a complete list of all other Chord nodes in order to perform this mapping. Instead, each node knows about a few other nodes, and sends "find successor" messages to those other nodes to help it map keys to nodes.

The API we use for our Chord-like system looks like this. Notice that I have extended the Change interface to include a method that is called each time a lookup message is performed at a node. In reading about this interface please remember that there will be one Chord system running on each node in the system.

// Each node in the system has an IP address and this is used to
// generate an id by the use of a secure hash method.
 
interface Location {
    public byte[] id();
    public String addr();
}

// The lookup method accesses the Chord system to calculate which
// Location (i.e. IP address of a node in the system) is responsible
// for a particular key.
//
// The leave method indicates that this Chord node intends to leave
// the system.

interface Chord {
    public Location lookup(byte[] key);
    public void leave();
}

// These methods are the way the Chord system interacts with other
// systems that use its services.  The method left is executed in at
// least the predecessor and successor nodes of a node that has left
// the system.  This allows us to reconfigure the system at that
// point.
//
// The method joined is executed by at least the predecessor and
// successor nodes of a new node that has just joined the Chord
// system.
//
// The lookup method is called each time we send a lookup message to
// location l to lookup the key.

interface Change{
    public void left(Location l);
    public void joined(Location l);
    public void lookup(byte[] key, Location l);
}

// When we a know a node that is running Chord, we can join the Chord
// system.  At that point we specify which methods will be called 
// when various events happen at the node.

interface StartChord {
    public Chord join(String address, Change c);
}

Deliverables and Submission

The list of deliverables is included in the proforma. To submit your practical you should create a tar or zip archive of the deliverables and the completed proforma and mail it to Stuart Anderson. Please use the title IPP: Part2 Deliverable.