CIS 630, Term Project

Fall 2008

The goal of this project is to extend your knowledge of some area of distributed systems by actually implementing a distributed system. Given the range of experience among students in the class, the main criteria in evaluating your project will be what you have learned and discovered from the project, not necessarily the amount of work involved or the amount of code written or the number of pages of written report. You are here to demonstrate that you have learned something when you take a class, and that is the metric used to evaluate your success. Thus, you should define your project with this strongly in mind and prepare submissions that communicate what you have learned.

That said, however, it is reasonable to expect that some of the more interesting things happen after serious thinking, design considerations, development, and testing. Due to the limited time available in the quarter, the projects will be a team effort of 4-5 individuals. It is hoped that with several people involved, more significant projects can be tackled than what would be possible alone. In this case, the project can also serve as a useful prototype experience for those of you interested in advanced work in the distributed systems field. Furthermore, it is occasionally useful to have a project that you can invoke when applying for jobs later to demonstrate your experience. This is an opportunity to get one of those under your belt for building your resume.

There are three aspects to the project:

1. Problem definition and literature background.
2. Design.
3. Implementation and experimentation.

The problem definition and literature background should explore and describe the problem or area of interest and provide some background material in this area, such as a few papers in the relevant research or technical literature. Consider what are the important problems, to what degree these problems are understood and solved, how do different solutions interrelate, and what are the important issues for the future. Original thoughts, solutions, and insights are strongly encouraged. Because of the time limits of the quarter and our emphasis on software implementation, this stage is generally expected to be very limited. For example, read a couple of papers, think hard for a while, and write your project proposal.

The design should try to map out a software solution that is implementable within the available time and computer resources. With the intended "prototyping" nature of the projects, design, implementation, and evaluation may be performed iteratively. However, think before coding.

In the implementation and experimentation phase, the design, or some aspect of the design is implemented to demonstrate feasibility. The experimentation involves developing a reasonable hypothesis and designing and performing an experiment to test this hypothesis.

The course project can build on other work you have done either at Oregon or elsewhere, provided that there is a clear component that fits the above considerations that is done as part of this course.

Structuring the project

The project is to be structured into the following three stages (or requirements):

1. Initial proposal (due Oct. 16): A written proposal describing the area and problems to be explored, the motivations for choosing this area, possible directions of investigation, proposed type of project, and the expected results. (1-3 pages)
2. Interim status reports (not required): I would encourage each group to meet with me during the project to go over the status of the work, including new issues, problem and insights.
3. Demonstration (to be scheduled during finals week): The demonstration should provide some working evidence of the work accomplished, ideally demonstrating some point to the project (i.e., the performance of some critical aspect to the design, etc.).
4. Final report and presentation (due Dec. 8): A final description of what was attempted, what was accomplished, and what was learned from the project. Ideally, this will be a revision of the proposal, changing the descriptions of proposed work to descriptions of accomplished work; refining the goals and objectives, including a brief literature survey for completeness and extended with some final conclusions and observations. The idea is for this to be an accumulation of the previous steps, not an entirely new document. (Note: This page erroneously listed the date as Dec. 9. The inal meeting date as stated in the syllabus and finals schedule is the 8th.)

Ideas

Below are some ideas that you can use to define your project. You are encouraged to pursue something that is of interest to your team and not grudgingly take on a project below that you find boring. You will find that working on a project you are truly interested in is much more satisfying than one you regard as a dull obligation.

• Distributed ray tracer

  Write a distributed ray tracing application which is composed of a server that hands out tasks (such as rendering a subimage of a larger image) for worker clients to execute. Show how the performance for a complex scene improves as clients are added. Deal with the case where clients die without completing their work, so the final image has no holes.

• Network-based multiplayer game

  Write a network-based multiplayer game. Focus on the issues that a concurrent set of players causes, such as contention for resources in the game. Examples could include some sort of capture the flag game or competition in which ordering of events is important. If you choose to write a game, keep in mind that your grade will be primarily based on the distributed systems aspect of the project, not graphics or other topics outside the context of the course.

• Robust Linda-style tuple-space

  Build upon the ideas from Programming assignment 2 in which you implement a basic Linda-style tuple space for distributed computing, but build in mechanisms for dealing with failure on both the client and server side. Design a system in which the tuple-space server is redundant to compensate for server failures, and where clients can fail without taking tasks that are incomplete with them. Ensure that a task assigned to a client that dies before completing it can be acquired by another client later, and not irretrievably lost. If you choose this one, I can provide the papers that are related to assignment #2 before it is assigned so you can get a timely start on the project.

• Implement a common distributed system in Erlang

  Erlang is a language designed for distributed systems, and makes building them easy relative to other languages like C. It is valid to choose a distributed system that already exists based on C or related languages, and determine how the system would best be translated to utilize Erlang to it's fullest potential. This project would have to demonstrate that the team has acquired a good knowledge of Erlang, and understands how to best represent aspects of the system in Erlang versus the original language.

• Write a distributed web-crawler

  Crawling the web to index web pages for things like a search engine is a time consuming task. Write a program that can use multiple machines to work together to crawl the web. Working together would ensure that all of the machines have work to do, and if one runs out, another can provide it with new pages to crawl. Ensure that the crawler agents don't crawl pages twice. Do an experiment to study how many pages one, two, four, and so on, agents can index in a fixed period of time. Provide a tool to search the results that the agents discover. This could be either a client-server or peer-to-peer system.