EE 382 N Vijay Garg Spring 2011
Term Paper
A term paper is required for EE 382N. The paper will be due on 13th May. It should be approximately 8 pages excluding references. The source code developed for the project should be submitted as a soft copy. Many projects require you to implement multiple algorithms. The goal is to implement and evaluate the performance of these algorithms.

A project should be done by a team of three students. The list of projects given below is just suggestive; you can work on any other topic related to distributed systems.

Implementing and extending Map Reduce Framework

Use MapReduce framework to solve different distributed computing problems. Which distributed computing tasks are not handled by MapReduce easily? Find other commonly used patterns for distributed programming. http://labs.google.com/papers/mapreduce.html

Scalable Global Snapshot Algorithms

Implement and compare algorithms for global snapshot. Implement a subset of the following algorithms: freezing, Mattern's algorithm, Tree based algorithm, Grid-based algorithm, Hypercube-based algorithm. click here

P2P Systems

Compare various algorithms available for P2P data indexing. See articles on Pastry, Chord and Tapestry. Pastry Chord

Randomized Algorithms in Distributed Systems

Implement at least two different randomized algorithms useful in distributed systems. For example dining philosopher , consensus , Byzantine Agreement etc.

Distributed Apps for iPhone/Andriod

Develop distributed applications for iPhone/Andriod. Here are some suggestions: (i) Global scheduling: A set of friends download the app. They use the app to determine first available meeting time. (ii) Chatroom (iii) Lunch invite (iv) survey etc.

Cloud Computing

Implement a service based on cloud computing platform such as Amazon's EC2.

Global Predicate Detection Algorithms

Design and implement a distributed algorithm for detecting global predicates expressed in BTL (Basis Temporal Logic) as specified in the DISC'07 paper by Ogale and Garg. pdf

Fusion based Fault-Tolerance

Develop a P2P (Chord-like system) that uses fusion to provide fault-tolerance. For fusion, click here For Chord, click here

Error Correcting Codes for Fault-tolerance

Compare performance of Reed-Solomon codes with LDPC codes for maintaining fused tables as backups. For fusion, click here

Distributed Simulation

Write a program that simulates a queuing network. The program should use different processors to simulate the behavior of different queues. Compare conservative and optimistic distributed simulation algorithms.

Distributed Agreement

Implement an algorithm for agreement in asynchronous systems under crash failures (e.g. Lamport's Paxos based algorithm and Chandra and Toueg's failure detector based consensus algorithm.)

Byzantine Agreement

Investigate algorithms for Byzantine agreement proposed in literature. Implement at least two algorithms ( Lamport, Shostak and Pease's algorithm , Ben-Or, Dolev and Hoch Algorithm.

Weighted Byzantine Agreement

Implement and evaluate weighted Byzantine Agreement algorithms. click here

Accurate Byzantine Agreement with Feedback

Design and implement algorithms for Accuarate Byzantine agreement. Compare various weight-update strategies. click here

Message Processing Toolkit

Design and implement a message processing toolkit that allows rapid development of message passing programs. A message processor takes as input a stream of messages (or multiple streams) and a command. It outputs one or multiple streams. A message processor can be used as message translator for interoperability between different protocols/versions, a message filter for appropriate routing of incoming messages, a message auditor for accounting purposes or a message logger for fault-tolerance. Use XML as the message format for the incoming message. Use various XML technologies (XQuery, XSLT, XPATH etc.) for this package. Design an interesting distributed application using your toolkit.

Visual Dashboard

Design and implement a visual dashboard to launch and control distributed programs. You would need to design methods by which a distributed program can be exercised under various faults and message reorderings.

Channel Predicate Detectors

Build a package for sensors based on channel predicates. Implement the centralized and the distributed token based algorithm by Garg, Chase, Mitchell and Kilgore. click here

Simulating CSP in Java

Implement a package in Java that allows CSP style programs to be written. In particular, you will have to implement blocking sends and selective communication. Alternatively, use JCSP to implement some sample concurrent programs.

Parallel programming in GPGPU

Compare implementation ease and performance of some applications on general purpose CPU versus GPGPU. Develop some Map-Reduce application using GPGPU.