Seminar: Distributed Algorithms

Overview · Scope · Requirements · Grading · Report · Presentation · Repository · Schedule · Milestones · Feedback · Support · Tools · Start · Material · Voting · Topics

News

• 2012-12-11: The seminar is over; all students should have received comments on their reports by email. Please remember to give feedback on this course!

Overview

This seminar course focuses on the theoretical foundations of distributed computing, including the design and analysis of distributed algorithms, models of distributed computing, and computability and computational complexity from the perspective of distributed systems. For an introduction to the research area, see the lecture course on Deterministic Distributed Algorithms.

Prior knowledge of distributed systems is not necessary. However, students are expected to have (1) a basic knowledge of discrete mathematics, (2) interest in theoretical problems, theory of computation, algorithms, and computational complexity, and (3) some prior experience of scientific writing (e.g., writing a BSc thesis).

During the seminar course, each student will read original scientific publications, write a report (in English), and give a presentation (in English). The seminar is offered in autumn 2012, during the 1st and 2nd periods; we will meet on Thursdays at 2:15pm–4:00pm, in room C220. The course is worth 3 credits, and the course code is 58307301. The course instructor is Jukka Suomela.

Scope

We will interpret distributed computing broadly. The selection of possible topics of seminar reports will include papers that are of interest to a wider algorithmic audience, and students are also encouraged to suggest their own topics. Virtually any paper published in PODC or DISC will be on-topic in this seminar, as well as many papers from ICALP track C or SPAA.

Requirements

The following parts are compulsory:

• Write a report, meet the deadlines, and use the right tools.
• Give a presentation.
• Read three reports written by other students and give feedback on them.
• Attend at least 4 presentation sessions out of 5; see the schedule. After each presentation session, you will have to give feedback on the seminar talks.

All deadlines are strict, and you will fail the course if you miss a deadline. Deadline extensions are given only in case of an illness or for similar reasons; a doctor's certificate will be required.

To play safe, try to finish your report early. It is perfectly fine to have your report finished already in September, in which case you do not need to do anything in October.

Grading

We will use the usual scale of 1–5.

The grading is based on all compulsory parts (quality of report, quality of presentation, quality of feedback), with most emphasis put on the report.

For a passing grade, you will have complete all compulsory parts in time, and your report and presentation must be of an acceptable level. In borderline cases, you will be given an opportunity to revise your report.

The highest grade should be achievable if you work hard, do your best, and listen to the feedback (both from the instructor and from other students).

This seminar course is worth 3 credits, which entails approximately 80 hours of work. The grading is calibrated so that roughly this amount of work suffices for a good grade. There is no need to overdo it. However, invest your working hours wisely — do not spend too much time reading papers, as you will also have to write something…

Seminar report

A seminar report is a short review paper: you explain some interesting results in your own words.

Content. A typical seminar report will consist of the following parts:

• an informal introduction,
• a formally precise definition of the problem that is studied,
• a brief overview of very closely related work — here you might cite approx. 3–10 papers and explain their main contributions,
• a more detailed explanation of one or two interesting results — here you might cite just 1 or 2 papers and explain some key results,
• conclusions.

Superficially, your report should look like a typical scientific article. However, it will not contain any new scientific results, just a survey of previously published work.

In comparison with a typical BSc thesis written at our department, the main difference is that a BSc thesis is typically fairly long, broad, and shallow, while a seminar report is shorter, focuses on a small number of results, and goes deeper in the details.

If you compare your seminar report with the original publications on which it is based, the main differences are these:

• Original articles often give the most general possible version of the result, making them difficult to follow — your seminar report can focus on a simple special case and explain it very clearly. Make everything as easy to understand as possible. Draw plenty of illustrations.
• Original articles often build on prior work — your seminar report should be self-contained. Whenever possible, give full proofs of all key results.
• Original articles are also advertisements that brag about the importance of the new results — your seminar report gives a more objective treatment.
• Original articles are often targeted to other experts in a narrow research area — the target audience of your seminar report is other students who take part in this seminar course.

Make sure that your seminar report (and presentation) shows that you have actually understood everything, it is completely clear to you, and now you are doing your best to explain the key ideas to others. Do not follow the structure of the original articles; come up with your own presentation that is much better than the original version! Ideally, pick ideas from several papers and synthesise.

Layout. Your seminar report should be:

• Written in English.
• A self-contained PDF document.
• Illustrated. It is OK to use colours in figures.
• 10–15 pages long. It can be a bit longer if there are exceptionally many illustrations.
• Typeset in Latex, using the standard article class with a4paper, 11pt options. No ugly tricks. No tweaking of margins. No double line spacing. No cover page.
• Looks like a professionally typeset book. Nice vector graphics. No ugly page breaks or line breaks. No overfull or underfull boxes. Correct use of mathematical symbols. Full sentences.

Plagiarism. No kind of plagiarism will be tolerated, no matter how slight it is.

Everything that you write in your seminar report must be written in your own words. Use appropriate citations to make it clear which result comes from which publication.

All illustrations and examples should be your own original work. There is usually no need to use the same example as what was used in the original publications; by constructing your own examples you are also forcing yourself to actually understand the details of the result.

(If it is absolutely necessary to reuse illustrations or examples from other sources, make it very explicit in your report, with appropriate citations, and make sure you are not violating anyone else's copyrights. Remember that simply re-drawing a figure does not make it your own work.)

Presentation

You will give a presentation on the topic of your seminar report. You can focus on some parts of your report.

Content. The presentation gives an informal overview of the topic of the seminar report.

Make sure that everyone in the audience gets a very good idea of the following:

1. Precisely what was the problem that was studied? What was the model of computation? What are the assumptions?
2. Precisely what is the result?

After that, you can try to explain why the result is true. For example, you might give a high-level overview of the algorithm, or illustrate it with some examples, or explain some interesting parts of the proof. All of this can be very informal — after all, there is very little time, and if someone is interested in the details, they can read your seminar report.

Slides. You will have to prepare presentation slides that support your presentation (for example, just using a whiteboard is not sufficient).

You can prepare your presentation in any format, as long as you can give the presentation using the IT equipment that is available in room C220. You can bring your own laptop, but make sure you have a plan B in case something goes wrong — it is your responsibility that your show starts on time.

Timing. The length of a presentation is 25 minutes, followed by 5 minutes for questions and discussion.

Timing is difficult, and timing is very important in presentations. Make sure that you rehearse your presentation, and double-check the timing. Ideally, prepare your presentation so that you can easily calibrate the timing on the fly.

Git repository

There is a shared Git repository for our seminar course.

Location. The repository is available at the CS department's computers, in the following directory:

/home/group/dasem12/dasem12.git

At the CS department (e.g., on melkinkari.cs.helsinki.fi), the right command for cloning is:

git clone /home/group/dasem12/dasem12.git dasem12

On your own computer, first configure ssh so that ssh cs takes you to melkinkari.cs.helsinki.fi, using whichever authentication method you prefer. Then clone:

git clone ssh://cs/home/group/dasem12/dasem12.git dasem12

See the quick start guide to get started.

Uses. All students will keep up-to-date versions of their reports in the repository: both the full source code, as well as the compiled PDF version. There is no need to explicitly send around draft versions of your seminar report. Just make sure that everything is up-to-date in the Git repository, and the instructor and other students can find it there.

Feedback from one student to another is also provided through the Git repository, as plain text files.

Structure. In the repository, there is one subdirectory per student. If your name is John Doe, you will find your files in the subdirectory j.doe. This is your own area; you can add any files that you need there, you can edit everything that you find there.

In your own subdirectory, you are required to create the following files, in due time:

• report.tex — The Latex source code of your report. It should compile cleanly by simply running latexmk in this directory.
• report.pdf — The compiled version of your report.
• presentation.* — Your presentation slides.
• presentation-feedback-j.doe.txt – Your feedback on John Doe's presentation, plain text.
• report-feedback-j.doe.txt – Your feedback on John Doe's report, plain text.

Use UTF-8 (or plain ASCII) as the encoding in the Latex source code and in the text files. All file names should be in plain ASCII; avoid strange characters and whitespace.

Once again, you will only edit your own subdirectory, while you are free to read everyone else's subdirectories.

Schedule

The seminar meets in room C220 as follows:

The presentations (25 min each) are scheduled as follows:

Milestones

The milestones for the seminar report are as follows:

All deadlines are by 11:59pm, local time. Just make sure that you have pushed everything to our Git repository by the deadline.

Feedback

You will receive feedback on your seminar report regularly throughout the course, and you will also receive feedback on your presentation after your talk.

Typically, the course instructor will provide at least some feedback each week — either common comments to all students or individual comments specifically on your work.

You will also receive brief feedback on your presentation from all students, and more detailed feedback on your report from three students. Just check everyone else's directories in the Git repository to find feedback on your work.

Giving feedback on reports. You will read the reports of those three students whose presentations are right after your presentation, wrapping around to the beginning. That is, if there are 15 presentations in total, and your presentation is 13th, you will read the reports related to the 14th, 15th, and 1st presentation. See the milestones for the deadlines.

You will find the reports that you are supposed to read in the Git repository, and you will write your feedback as plain text files in your own directory in the Git repository; see the structure of the repository for more details on the file naming conventions. Your feedback should contain the following parts:

1. In your own words, describe the main idea of the report. This should be one or two paragraphs of text.
2. Give some concrete, high-level ideas of how the report could be further improved to make it easier to follow, more enjoyable to read, more clear with the technical details, etc. This should be one or two paragraphs of text.
3. List all mistakes that you spotted: misspellings, typographic details, etc. This list is as long as needed.

Please note that you are not expected to evaluate the report; there is no need to say if the report is good or bad. Just tell how it can be even further improved — there is always room for that.

Giving feedback on presentations. You will have to take part in at least 4 presentation sessions, and in those sessions, you will have to give feedback on all presentations (except your own presentation).

The deadline for giving feedback on presentations if the end of the week — if a presentation was on Thursday, you will have three days to write your feedback. Ideally, do it right after the presentations.

Your feedback should contain the following parts:

1. In your own words, describe the main idea of the presentation. This should be one or two sentences of text. Note that the main idea of the presentation is not necessarily the same as the main idea of the report; a talk can have a different focus.
2. Give some concrete ideas of how the presentation could have been improved. This should be two or three sentences of text.

Yes, the feedback is very brief, between three and five sentences of text. Again, you will not evaluate, just suggest improvements.

Online support

For real-time chat, join the IRC channel #dasem12 on IRCnet. You can use the IRC client "irssi" on melkki.cs.helsinki.fi.

You can also email Jukka Suomela if you have any questions.

Tools

To pass this seminar course, you will have to use the following tools.

Latex. You will have to use Latex to typeset your seminar report. Make sure that you have read at least lshort and short-math-guide first. If you need help, check the FAQ or ask at TeX StackExchange.

If you do not have Latex, download TeX Live 2012 (for GNU/Linux) or MacTeX 2012 (for Mac OS X). On the CS department's computers, use melkinkari.cs.helsinki.fi, as it has an up-to-date version of Latex.

Always use the pdflatex command, never latex. I strongly recommend that you use latexmk or a similar tool to compile your report — direct interaction with Latex is a bit painful.

Git. We have a shared Git repository, for both version control and collaboration. If you are new to Git, our quick start guide helps you to get started. After that, there is plenty of documentation available.

Drawing tools. You will need a vector graphics editor for drawing illustrations. It is absolutely necessary that you can export drawings in the PDF format for inclusion in your seminar report. For GNU/Linux, you can try, e.g., Inkscape or Ipe. For OS X, OmniGraffle might be a good option.

Presentation tools. You will also need a tool for preparing your presentation slides. Latex experts may want to use Beamer; for the rest of us, LibreOffice Impress, Microsoft PowerPoint, or Apple Keynote will do.

Quick start

Open an ssh connection to melkinkari.cs.helsinki.fi.

Preparations. You will do this only once.

cd ~
git clone /home/group/dasem12/dasem12.git dasem12

Now you will have a directory ~/dasem12 in your home directory.

Editing. If your name is John Doe:

cd ~/dasem12/j.doe

Now with your favourite text editor, edit the file report.tex. Compile everything by running:

latexmk

Open the document report.pdf and make sure that it looks good. Commit your changes:

git add -A
git commit -m 'Explanation of my edits.'

Collaboration. First pull everyone else's changes:

git pull

And then push your own changes:

git push

Next steps. Learn how to use the following commands:

git status
git diff

Background material

For introductory material related to the field of distributed computing, see the following resources:

• Principles of Distributed Computing (lecture collection).
• A Course on Deterministic Distributed Algorithms (online textbook).
• N. A. Lynch (1996): Distributed Algorithms. Morgan Kaufmann.

Selecting your topic

The deadline for selecting your topic is 6 September 2012.

Own topic. If you have your own suggestion of a topic, please email the course instructor before the first meeting.

From the list. If you prefer the suggested topics, proceed as follows:

• In your own subdirectory in our Git repository, create the text file topics.txt.
• In the text file, list the codes of all topics in the order of preference, the most preferred topic first and the least preferred topic last.

As there are 19 topics, the file topics.txt has to contain 19 lines of text. All lines have to be distinct. Each line consists of a two-character code (for example, "A1") followed by the newline character (ASCII code 10). Therefore the total size of the file should be precisely 19 × 3 = 57 bytes.

The file has to be in the Git repository on 6 September 2012. The topics will be assigned on 7 September 2012.

The topics will be assigned as follows:

• In special cases, some topics may be pre-assigned. Such topics are first removed from all preference lists.
• The remaining topics are assigned so that we maximise the minimum preference. That is, we will find the smallest integer k such that everyone gets a topic among the first k topics given in their list.

Suggested topics

The articles listed after each topic are merely examples of possible starting points for further reading. Please remember that you can also suggest your own topic!

A. Global problems

A1. Shortest paths

• S. Holzer, R. Wattenhofer (2012):
  Optimal distributed all pairs shortest paths and applications,
  Proc. PODC 2012.

A2. Spanning trees

• R. G. Gallager, P. A. Humblet, P. M. Spira (1983):
  A distributed algorithm for minimum-weight spanning trees,
  ACM Transactions on Programming Languages and Systems, 5(1):66–77.

B. Local problems

B1. Colour reduction

• A. Panconesi, R. Rizzi (2001):
  Some simple distributed algorithms for sparse networks,
  Distributed Computing, 14(2):97–100.
• R. Cole, U. Vishkin (1986):
  Deterministic coin tossing with applications to optimal parallel list ranking,
  Information and Control, 70(1):32–53.

B2. Maximal matchings

• M. Hańćkowiak, M. Karoński, A. Panconesi (2001):
  On the distributed complexity of computing maximal matchings,
  SIAM Journal on Discrete Mathematics, 15(1):41–57.

B3. Maximal independent sets

• Y. Métivier, J. M. Robson, S.-D. Nasser, A. Zemmari (2009):
  An optimal bit complexity randomised distributed MIS algorithm,
  Proc. SIROCCO 2009.
• M. Luby (1986):
  A simple parallel algorithm for the maximal independent set problem,
  SIAM Journal on Computing, 15(4):1036–1055.

B4. Fast graph colouring

• L. Barenboim, M. Elkin (2009):
  Distributed (Δ+1)-coloring in linear (in Δ) time,
  Proc. STOC 2009.
• F. Kuhn (2009):
  Weak graph colorings: distributed algorithms and applications,
  Proc. SPAA 2009.

B5. Recent breakthroughs

• L. Barenboim, M. Elkin, S. Pettie, J. Schneider (2012):
  The locality of distributed symmetry breaking,
  Proc. FOCS 2012.

B6. Strictly local algorithms

• M. Naor, L. Stockmeyer (1995):
  What can be computed locally?
  SIAM Journal on Computing, 24(6):1259–1277.

C. Lower bounds

C1. Lower bounds for graph colouring

• N. Linial (1992):
  Locality in distributed graph algorithms,
  SIAM Journal on Computing, 21(1):193–201.

C2. Lower bounds for approximations

• A. Czygrinow, M. Hańćkowiak, W. Wawrzyniak (2008):
  Fast distributed approximations in planar graphs,
  Proc. DISC 2008.

C3. Lower bounds for linear programs

• F. Kuhn, T. Moscibroda, R. Wattenhofer (2004):
  What cannot be computed locally!
  Proc. PODC 2004.

D. Models of computing

D1. Beeping

• Y. Afek, N. Alon, Z. Bar-Joseph, A. Cornejo, B. Haeupler, F. Kuhn (2011):
  Beeping a maximal independent set,
  Proc. DISC 2011.

D2. Computing with advice

• P. Fraigniaud, C. Gavoille, D. Ilcinkas, A. Pelc (2007):
  Distributed computing with advice: information sensitivity of graph coloring,
  Proc. ICALP 2007.

D3. Verification

• A. Korman, S. Kutten (2007):
  Distributed verification of minimum spanning trees,
  Distributed Computing, 20(4):253–266.
• P. Fraigniaud, A. Korman, D. Peleg (2011):
  Local distributed decision,
  Proc. FOCS 2011.

D4. Robots in the plane

• O. Feinerman, A. Korman, Z. Lotker, J.-S. Sereni (2012):
  Collaborative search on the plane without communication,
  Proc. PODC 2012.
• B. Kempkes, P. Kling, F. Meyer auf der Heide (2012):
  Optimal and competitive runtime bounds for continuous, local gathering of mobile robots,
  Proc. SPAA 2012.

D5. Robots in a graph

• A. Dessmark, P. Fraigniaud, D. R. Kowalski, A. Pelc (2006):
  Deterministic rendezvous in graphs,
  Algorithmica, 46(1):69–96.

D6. Routing

• C. Lenzen (2012):
  Optimal deterministic routing and sorting on the congested clique.

D7. Wireless communication

• C. Avin, Y. Emek, E. Kantor, Z. Lotker, D. Peleg, L. Roditty (2009):
  SINR diagrams: towards algorithmically usable SINR models of wireless networks,
  Proc. PODC 2009.

D8. Consensus

• B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, C. Scheideler (2011):
  Stabilizing consensus with the power of two choices,
  Proc. SPAA 2011.