Deterministic Distributed Algorithms

News · Summary · Content · Material · Schedule · Format · Grading · Tracking · Support · Feedback · Comments · More · FAQ · Glossary

Latest news

• The course will be offered again in Spring 2014.

Summary

The course on Deterministic Distributed Algorithms is offered in Spring 2012, during the 4th period. The course instructor is Jukka Suomela, and the exercise sessions are held by Juho Hirvonen.

The course provides an introduction to the theory of distributed algorithms. The topics include algorithmic techniques that can be used to solve graph problems efficiently in extremely large networks, as well as fundamental impossibility results that set limits to distributed computing. No prior knowledge of distributed systems is needed, but students are expected to have an interest in algorithmic problems and a basic knowledge of discrete mathematics.

The course is worth 4 credits, and the course code is 582661. This is an advanced (Master level) course, so it is expected that the participants have a BSc degree or equivalent.

The course is not based on any textbook; course material and presentation slides will be posted on this page. Lectures and course material will be in English.

Course content

The course is an extended version of the intensive course that was given in spring 2010.

The main themes and the learning objectives are as follows. In the course exam, if you can do everything listed in the column "Approaches learning objectives", you should be able to pass the course, and if you can do everything listed in the column "Reaches learning objectives", you should be able to get the highest grade 5/5.

Course material

The course material is a short online textbook that is freely available for download:

• A Course on Deterministic Distributed Algorithms

Additional material:

• lecture slides
• exams: 5 May 2012, 15 June 2012, 18 January 2013

Schedule

Course registration opened on 21 February 2012 in the Ilmo system.

Lectures are given on

• Tuesdays from 12:15 to 14:00 in room D122, and
• Thursdays from 10:15 to 12:00 in room D122.

The exercise sessions are held on

• Fridays from 12:15 to 14:00 in room B119.

The first lecture is on Tuesday, 13 March 2012, and the first exercise session is on 16 March. There is an Easter holiday from 5 April to 11 April. The last lecture is on Thursday, 26 April, and the last exercise session is on 27 April.

There is a course exam on 4 May 2012, and a renewal exam on 15 June 2012 (check the exam web pages for the latest information).

The course schedule is available on Google Calendar: html, ical, xml.

Format

The course is worth 4 credits, and there are 6 full weeks of lectures plus an exam. As one credit entails approx. 27 hours of work, you are expected to work 17–18 hours each week on this course.

The emphasis is on self-study; you will learn by doing. The lectures and exercise sessions are intended to support self-study, not replace it.

The course material consists of 6 short chapters of text, and with each chapter there is a selection of exercises. On week x you are expected to do the following:

• Read Chapter x.
• Have a look at the exercises in Chapter x. Solve as many of them as possible within your weekly budget of 17–18 hours. Help and support is available during the lectures and exercise sessions, and online support will also be available.
• Report your progress in the course tracking system.

Note that you are not expected to solve all exercises. Keep track of your working hours – do not overdo it. Usually, it makes sense to start with the first exercises. However, you are welcome to skip exercises that look utterly trivial to you, and focus on more interesting problems. If you get stuck, remember that help is available almost daily.

Below is the suggested weekly routine. You are free to adapt it to your needs, but keep in mind that the lectures and exercise sessions are planned so that they support this routine. In particular, make sure that you have read the relevant chapter of the course material before Tuesday's lecture.

The lectures and exercise sessions will be adapted based on the information in the course tracking system. Hence to make sure that the sessions are as useful to you as possible, remember to update the course tracking system regularly.

The beginning of the first week will be a bit more relaxed, as the material focuses on reviewing concepts from graph theory. Hence if you are only reading these instructions after the first lecture, you will still have time to catch up. However, do not expect that the exercises of the first week are trivial…

If you realise that you have taken too many courses during the 4th period, remember that you can abuse the Easter holiday for load balancing. There will be one full week without any lectures or exercise sessions in April.

Grading and requirements

The grading is based solely on the course exam, using the usual scale of 1–5. If you pass the exam, you pass the course – there are no other requirements.

In particular, you will not get any credits or points from the exercises. However, most probably

• if you work hard and solve an average number of exercises, you will do fine in the exam, and
• if you do not solve the exercises, you will fail the exam.

For an average student, 4 × 27 hours of studying during the course will be sufficient in order get an average grade in the exam.

Course tracking

There is an online course tracking system. In the system, you are expected to report your progress. All reports are anonymous.

The course tracking system serves the following purposes:

• We can adapt the lectures and exercise sessions so that they are as useful as possible.
• The problems in the exam can be selected so that they reflect the exercises that the students were able to solve during the course.
• The students can compare their progress with the progress of other students.

In the course tracking system, you will report your progress with each exercise using the following codes:

If you have registered for the course, you should have received detailed information by email; if this is not the case, please contact the course instructor.

Online support

The following online forums are available:

• You are welcome to join the Google Groups forum "DDA 2012" and use it to ask any questions related to the course.
• For real-time chat, join the IRC channel #dda-2012 on IRCnet. You can use the IRC client "irssi" on melkki.cs.helsinki.fi.

You do not need to follow these forums; all essential information will be provided on this web page. Nevertheless, it might be a good idea to join the Google Groups forum or try out IRC well in advance before the course begins, just in case you should need quick help with the exercises.

You can also email Jukka Suomela or Juho Hirvonen if you have any questions!

Course feedback

If you have any comments or suggestions before or during the course, feel free to email the course instructor or drop a note on the online forums.

After the course, everyone is expected to submit course feedback using the course feedback system. Course feedback is anonymous.

I will publish a summary of the course feedback on this web page, and I will also comment on it here.

Comments on course and feedback

The key statistics of the course are as follows:

• We had approx. 24 students registered for the course.
• There were 15 students who used the course tracking system:
  • 7 students solved at least 10 problems.
  • 5 students solved at least one problem each week.
  • 1 student was able to follow all course instructions.
• In total, 10 distinct students took part in the course exam and the renewal exam:
  • 7 students passed the exam, each of them in their first attempt.
  • The distribution of the grades is: 5, 5, 5, 5, 3, 3, 1.
• Course feedback was submitted by 10 students.

The following table summarises the numerical course feedback (scale from 1 = disagree to 5 = agree).

Here are selected (adapted, abbreviated, translated, and anonymised) fragments of the free-form course feedback, both from the feedback form and from the emails that I received.

• Positive feedback:
  • course in general: liked a lot, very good, one of the best courses, interesting, enjoyed it, well organised, learned that distributed algorithms are interesting, lecturer takes teaching seriously
  • material: superb, fantastic, excellent, clear, easy-to-read, textbook-quality, comprehensive, understandable, relatively good
  • lectures: good, easy to follow without getting bored, clear, useful, relatively good
  • exercises: good, non-obligatory exercises provided extra flexibility in focusing on important and interesting things
  • tracker: helpful
• Constructive critisism:
  • course in general: demanded a lot of time; expecting 17–18 hours per week is too much; reading the chapter takes more time than the suggested 4 hours; theoretical; questionably useful
  • lectures: too much time spent on explaining simple things; lectures could have focused on more difficult parts; not everyone likes to work in groups; students were a bit passive
  • exercises: receiving some points from the exercises would have helped with the motivation; should have indicated more clearly which exercises are most important
  • tracker: did not work for me

First of all, many thanks to all of you who provided feedback, and in particular, thanks for your kind, supportive, and helpful comments! I really appreciate all kinds of feedback.

Here are my own interpretations of the main points of the feedback, with some comments:

• The course material was good. I am very happy to hear that.
• The course arrangements in general were OK, but there is room for improvement in the specifics. I have to admit that the course format was a bit experimental, and I learned a lot from this experiment. The next iteration of the course will definitely be a bit different, but it also seems that there are some ideas that could be reused in other courses.
• The workload was high, and in particular the amount of working hours that people are expected to put in a 4-credit course surprised most of the students.

I would like to comment the last point – workload – in more detail. Let us first have a look at the background. The Finnish legislation (Valtioneuvoston asetus yliopistojen tutkinnoista 794/2004, 5 §) explicitly states that one full year of studies equals 1600 working hours, which equals 60 credits; many other European countries have a very similar system.

Please note that I as a course instructor cannot really change any of this. In any case, 1600 hours per year sounds like a very reasonable number to me. For example, if you do 40 hours of studies each week, you can enjoy 12 full weeks of holidays each year.

Now if we do the math, we conclude that a 4-credit course entails approximately 107 hours of studies. Even if we allocate some working hours for the exam, we will have approximately 100/6 ≈ 17 hours of studies each week during a 6-week lecture course. This number seemed to come as a surprise to most of the students.

Unfortunately, this just happens to be the way our system works; I did not make up the numbers. Of course I could organise a course that is worth only 2 credits, and then I would expect only approximately 8 hours of studies each week, but I am not sure if the students would be happy with this approach, either.

I will try to provide some words of general advice, though. Please note that the total length of the four teaching periods is only 28 weeks, including the exam weeks. The idea is not that you compress a full working year in just 28 weeks! If you tried to do that, you would certainly be in trouble, struggling with 60-hour weeks. A simple solution is to study on your own outside the usual teaching periods – this way you can enjoy relaxed 40-hour working weeks, yet you will still have a long summer holiday.

I hope this at least clarifies the situation, even if it does not actually help that much with the workload… Once again, many thanks to all of you for taking part in the course! Have a nice summer!

Further studies

There will be a seminar course on distributed algorithms in autumn 2012.

Master's thesis topics are available from the course instructor.

FAQ

Can I take this course if I already took the 2010 version?

For all administrative purposes, these are the same course. They have the same course code, and you cannot have more than one instance of it in your degree. Of course nothing prevents you from re-doing the course.

How to draw graphs?

All illustrations in the course material, slides, etc. were created with OmniGraffle. Unfortunately, it is only available for Mac OS X, and it is commercial software. If you are looking for free, open-source software for Linux, I am not aware of anything that I could honestly recommend. Windows users might want to have a look at Microsoft Visio.

Glossary