Overview · Scope · Requirements · Grading · Report · Presentation · Repository · Schedule · Milestones · Feedback · Support · Tools · Start · Material · Voting · Topics
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.
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.
The following parts are compulsory:
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.
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…
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:
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:
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:
a4paper, 11ptoptions. No ugly tricks. No tweaking of margins. No double line spacing. No cover page.
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.)
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:
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.
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:
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
latexmkin 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.
The seminar meets in room C220 as follows:
|6 Sep 2012||Introduction||J. Suomela|
|13 Sep 2012||No meeting|
|20 Sep 2012||No meeting|
|27 Sep 2012||No meeting|
|4 Oct 2012||No meeting|
|11 Oct 2012||Guest lecture||C. Lenzen||Tri, tri again|
|Feedback session||J. Suomela|
|1 Nov 2012||Guest lecture||B. Keller,
|Spectral graph theory|
|8 Nov 2012||Presentations||J.-K. Kangas||A2|
|15 Nov 2012||Presentations||J. Hirvonen||B5|
|22 Nov 2012||Presentations||M. Wahlroos||D4|
|J. Väisänen||Dangerous networks|
|29 Nov 2012||Presentations||E. Peltonen||D7|
|6 Dec 2012||No meeting|
The presentations (25 min each) are scheduled as follows:
The milestones for the seminar report are as follows:
|6 Sep 2012||Topic selected.|
|9 Sep 2012||At least one edit.|
|16 Sep 2012||At least 2 pages of text|
(e.g., a rough outline in bullet points).
|23 Sep 2012||At least 4 pages of text.|
|30 Sep 2012||At least 6 pages of text.|
At least 1 illustration.
|7 Oct 2012||At least 8 pages of text.|
|14 Oct 2012||At least 10 pages of text.|
|28 Oct 2012||Readable and understandable version.|
Most of the content in place.
|11 Nov 2012||Almost-final version ready for peer-review.|
The total length should be approx. 10–15 pages,
and there should be plenty of illustrations.
|25 Nov 2012||Feedback from peer-review.|
|2 Dec 2012||Revised version based on the feedback.|
|9 Dec 2012||Final version ready for grading.|
All deadlines are by 11:59pm, local time. Just make sure that you have pushed everything to our Git repository by the deadline.
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:
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:
Yes, the feedback is very brief, between three and five sentences of text. Again, you will not evaluate, just suggest improvements.
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.
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.
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:
Now with your favourite text editor, edit the file report.tex. Compile everything by running:
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:
And then push your own changes:
Next steps. Learn how to use the following commands:
git status git diff
For introductory material related to the field of distributed computing, see the following resources:
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:
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:
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!
A1. Shortest paths
A2. Spanning trees
B1. Colour reduction
B2. Maximal matchings
B3. Maximal independent sets
B4. Fast graph colouring
B5. Recent breakthroughs
B6. Strictly local algorithms
C1. Lower bounds for graph colouring
C2. Lower bounds for approximations
C3. Lower bounds for linear programs
D2. Computing with advice
D4. Robots in the plane
D5. Robots in a graph
D7. Wireless communication