All projects need to be implemented using Java. Any package developed should be thread-safe.

The term paper will be due on April 26. It should be approximately 6 pages (excluding references), typed and double spaced. The paper should have an abstract, introduction, description of the project, various design alternatives considered during implmentation, performance results and conclusions.

Every team is required to make a presentation. A team of three members will get 12 minutes and a team of four members will get 16 minutes (including time for questions). Each team member must present and will get about 3-4 minutes for presentation. The class presentations will begin on April 26th. You will also need to give a 10 minute demo of your project to the instructor. The sign-up sheet for the demo will be circulated later.

Please submit the names of the team members and the first three choices of the term project by March 31st .

1. Parallel Algorithms
   Implement parallel algorithms related to scientific computation. Some possible candidates are: matrix inversion, fast fourier transform, primality testing, convex hull etc.

2. Lock-free Data Structures: Lists, trees, skip lists, heaps
   Lock-free data structures allow multiple processes to share data-structures in a manner that failure of one process does not affect others. Implement efficient lock-free algorithms for trees, hashing, skiplists, heaps etc.

3. Parallel Work Scheduling and Work Distribution
   Implement work-stealing dequeue for exploiting parallelism. Apply that for parallel computation of some problems such as matrix inversion etc.
4. Concurrent/Distributed Apps for iPhone/Android
   Develop distributed applications for iPhone. 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.
5. Parallel programming with GPGPU
   Compare implementation ease and performance of some applications on general purpose CPU versus GPGPU. Develop a CUDA application using GPGPU.
6. Global Snapshot Algorithms
   Implement scalable algorithms for global snapshot as proposed by Garg, Garg and Sabharwal. click here

7. Byzantine General Agreement Protocols
   Implement a package that allows multiple processes to agree on some input in spite of presence of malicious processes. Implement and evaluate weighted Byzantine Agreement algorithms. click here

8. Internet Computing
   The goal of these projects is to learn internet computing. The goal is to develop a useful website based on available packages such as JSP, PHP, Javascript, Ajax, MySQL, .NET etc. I am providing some examples of websites that you can build but you are free to propose any other idea to me as well.
   • MyLife.com: This website keeps photos, likes/dislikes (as in facebook) with the difference that the data is kept only on the user's machine. The user has ability to change/remove the data. The goal is to ensure that the user has complete control on his/her data. The page stored at the server of MyLife.com can only store pointers to the data stored at the user's site.
   • GroupBackup.com: This website allows users to keep backup of their files on other peoples's disks. By using simple coding such as exclusive-or, the storage requirements or privacy requirements are met.
   • TennisAnyone.com: This website allows user to register and find partners for a tennis game.
   • ProjectMatch.com: This website allows students to find partners for EE 360P term project.

9. Spanning Tree
   Implement the distributed minimum spanning tree algorithm by Gallaghar, Humblet and Spira. click here

10. Web-based Distributed Program Simulator
    Design and implement an applet that allows distributed program to be tested by allowing user to change message ordering, kill processes and break communication channels. The simulator must be a multi-threaded program.
11. P2P Systems
    Compare various algorithms available for P2P data indexing. See articles on Pastry, Chord and Tapestry. Pastry .... Chord
12. Randomized Algorithms in Distributed Systems
    Implement at least three different randomized algorithms useful in distributed systems. For example dining philosopher, consensus, leader election, Byzantine Agreement etc.
13. Fusible Data Structures
    Develop a package for maintaining fused back-up for linked lists, queues and stacks using different fusion algorithms and compare the performance of updates and recovery. For fusion, click here
14. Promela Models for Distributed Programs
    Specify and verify the correctness of at least three different distributed algorithms in the book using Promela language and the SPIN model checker. The information is available here .

15. Using Hadoop for Distributed Processing
    Hadoop uses Map-Reduce paradigm for supporting fault-tolerant distributed processing. Implement some sample applications using Hadoop. Information on Map-Reduce is available here. http://labs.google.com/papers/mapreduce.html