Final Project Description

Details on the structure and expectations for your Distributed Algorithms final project

Project Overview and Aims

The aim of the final project is for you to explore connections between distributed computing and a topic of interest to you. Distributed computing is a vast field with connections to just about every topic in computer science (as well as many other disciplines). In class we only scratched the surface of distributed computing. Your project may examine a topic from class in greater depth, or consider something else entirely. The direction is up to you. At the end of this note, you will find suggested topics and resources.

While the topic you investigate is open-ended, the scope of your project should be quite narrow: it should focus on a single problem, model, algorithm, or application. In particular, once you’ve picked a topic, you should focus on analyzing a single article on that topic in depth. Primary literature in computer science is often highly technical, and the goal of this project is not to understand every detail of your paper. Instead, you should strive to achieve a high level conceptual understanding of the article and its significance, along with some appreciation of how the technical details connect to the bigger picture. Specifcally, your reading of the article should focus on answering the following questions:

  1. What is the motivation of the article? What question, problem, or scenario does the article address and why?

  2. How does the article formalize the problem being addressed? Does it use an existing computational model, or does it introduce a new one?

  3. What strategy or strategies does paper employ in order to solve the problem it considers?

  4. What are some applications or consequences of the work?

  5. What questions are left unresolved by the paper?

The answers to these questions will form the basis of your project.

Project Structure

Your project will consist of two components: a presentation and a written response.

Presentation

The first component of your final project is a brief in-class presentation. Your presentation should introduce and motivate your topic and give a high-level overview of the strategy employed by your chosen article. The presentation should focus on the conceptual aspects and address the 5 questions listed above.

Your presentation can be either done live or pre-recorded. The main presentation should be no more than 15 minutes long. After the presentation, there will be a brief (<5 minute) question and answer session during which your classmates can ask questions about your topic.

Write-up

The second component of your final project is a write-up about your topic. The write-up should be around 4–8 pages. The write-up should address the same material as your presentation with some added technical detail. Your write-up should serve as an accessible “reader’s guide” for your chosen paper. The write-up should also include some details—concrete examples, additional motivation/applications, references to follow-up work—that are not present in your chosen article.

Timeline

  • Week 09 (4/10–4/15): Choose a topic, find relevant article(s)
    • Friday, 4/15: submit a preliminary project proposal
  • Week 10 (4/17–4/22): Focus on reading and understanding your article, look at related literature; sign up for presentation date
  • Week 11 (4/24–4/29): Prepare presentation, begin write-up
  • Week 12 (5/02–5/07): Work on write-up, in class presentations
  • Week 13 (5/09–5/13): Work on write-up, in class presentations
  • Reading/Finals Week (05/15–05/20): Complete write-up
    • Friday 5/20, final write-up due

Topics and Resources

Topics from Other Courses

There are several courses at other universities that cover material suitable for your final project. Three such courses are:

Each of the courses listed above includes extensive lecture notes. In each case, a single chapter of the associated notes could be an appropriate topic for a final project. If you select a topic from one of these courses, be sure to focus on the contributions from one of the primary source materials (i.e., journal articles) referenced from the lecture notes.

Topics Discussed in Class

Any of the topics we discussed in class would also be appropriate for a final project, as our coverage only scratched the surface of these topics.

Other Topics

Each year, the Dijkstra Prize in distributed computing is awarded ``for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing have been evident for at least a decade.’’ We’ve seen two Dijkstra Prize winning results in our class: the Luby/Alon-Babai-Itai algorithm for maximal indpendent sets, and the Gallager-Humblet algorithm for mininmum spanning trees. The other winners of the Dijkstra Prize are listed here:

Any Dijkstra Prize winning paper could make for a good final project.

Additionally, here are some other topics that might be of interest:

  • Biological Distributed Algorithms This link is to an annual workshop on biologically inspired distributed algorithms. The schedule contains a list of authors and topics, as well as links to previous meetings.

  • Population Protocols are distributed algorithms that use a very restricted model of computation.

  • Secure Multiparty Computation combines distributed computing and cryptography in order to devise secure protocols for computer networks.

  • Massively Parallel Computation (e.g., MapReduce) refers to computation in which a large cluster of computers operate in a very well-connected network. This paradigm is in widespread use for high performance computing and “big data” analysis. A distributed computational model used to reason about massively parallel computation was first introduced in a paper by Karloff et al.

  • Deterministic Network Decomposition. This paper by Rozhon and Ghaffari solves one of the most notorious challenges in distributed computing: a deterministic distributed algorithm for the “network decomposition” problem. The solution resolves dozens of previously open problems in distributed computing concerning the power of randomness.

Journals and Conference Proceedings

The two flagship conferences on the theory of distributed computing are PODC and DISC:

Any paper or topic appearing in these venues could potentially be appropriate for a final project, though many papers here report on progress in a line of work. If you find a paper whose title/abstract sound interesting to you, it might be a good idea to look at the references in the paper to find the seminal work introducing a topic.