Projects

Computer Science 612
Possible Reading Projects

A reading project would involve reading a set of one or two conference or journal papers on the same topic or related topics and and preparing an oral presentation. You may choose a set of theoretical papers or a combination of experimental and theoretical papers.

The presentation should not just be a listing of the results of the paper. It should be a critical analysis comparing the results. This may include a discussion of the different models studied or the differences in the problems tackled. If you are interested in doing a more involved project with original results, possibly leading to a publication, I would be happy to work with you on it. This could be done as a continuation of the class project over the summer. In that case, think about the open problems arising from the research papers you are presenting and how you think these could be tackled. The subsequent work would involve solving any of these problems or giving a plausible approach for solving them. In the case of theoretical papers, this would mean improving algorithms or lower bounds, or looking at variations of the model or the problem itself. In the case of experimental papers, some thought should go into formalizing the concepts derived.

Here are some possible topics. Some of these are quite broad and you would need to narrow down the scope to a specific sub-topic. For example, you may look at fault-tolerant or probabilistic versions of these problems, or restrict yourself to synchrony or asynchrony. On the other hand, you may want to compare crash and Byzantine failures, synchronous and asynchronous systems, or probabilistic and deterministic results. Also, please feel free to pick your own topic from outside this list. I would like to talk to each of you individually as you choose your topic. You are encouraged to talk to me as early as possible.

Projects should be done individually. Each student will be giving an oral presentation on your topic. All students are expected to be present during all presentations, and will need to evaluate the other presentations.

We will schedule these presentations towards the end of the semester.

  • Clock Synchronization

     

  • Wait-Free or Lock-Free Synchronization

     

  • Distributed Shared Memory (Implementations and Consistency Conditions)

     

  • Counting and Balancing Networks

     

  • Distributed File Systems

     

  • Byzantine Agreement

     

  • Group Mutual Exclusion

     

  • Data Link Protocols

     

  • Distributed Data Structures

     

  • Failure Detectors

     

  • Connection Management Protocols

     

  • Implementing Shared Data Objects

     

  • Partially Synchronous Systems

     

  • Self-Stabilization

     

  • Load Balancing

     

  • Algorithms for Ad-Hoc Networks

     

  • Group Communication

     

  • Quorum Systems

     

  • Distributed Storage

Here are some conference proceedings and journals where you can look for papers on distributed computing:

  • Conference proceedings:
    • ACM Symposium on Principles of Distributed Computing (PODC)
    • International Symposium on Distributed Computing (DISC)
    • IEEE Conference on Distributed Computing Systems (ICDCS)
    • ACM Symposium on Theory of Computing (STOC)
    • IEEE Symposium on Foundations of Computer Science (FOCS)
    • ACM Workshop on Principles of Mobile Computing (POMC)
    • ACM International Conference on Mobile Computing and Networking (MobiCom)

     

  • Journals:
    • Distributed Computing
    • Journal of the ACM
    • SIAM Journal on Computing
    • Information and Computation
    • Acta Informatica
    • Journal of Algorithms
    • Theoretical Computer Science
    • ACM Transactions on Computer Systems
    • ACM Transactions on Programming Languages and Systems
    • IEEE Transactions on Computers