CSE 6117, Winter 2016

CSE 6117
Theory of Distributed Computing
Winter 2016

Instructor: Eric Ruppert
Office: Lassonde Building, room 3042
Email: [my last name] @cse.yorku.ca
Telephone: (416) 736-2100 ext. 33979
Lectures: Mondays and Wednesday 17:30-19:00 in room 211 of Stong College
Office Hours: Wednesdays 12:00-13:00 and Fridays 14:00-15:00 or by appointment, or just drop by when I'm in.

Usually, the best way to contact me is by email. Please use your cse account when sending me email, and start your subject line with "[6117]". Send messages in plain text, without attachments.


Course Description

Can a given problem be solved in a distributed system? If so, how efficiently can it be solved? We investigate how the answers to these questions depend on aspects of the underlying distributed system including synchrony, fault-tolerance and the means of communication between processes. A tentative list of topics:

Marking scheme

Homework exercises 50%
Test 20%
Class presentation 20%
Class participation 10%

The class presentation will be a 25-minute talk summarizing the results of a research paper on the theory of distributed computing that you find in the literature. We will have some checkpoints along the way before the presentations. (More information on this to come.) Good places to look for a paper include PODC or DISC conference proceedings or the journal Distributed Computing. This survey paper has a bibliography containing lots of papers that would be suitable to choose. If you have a topic in mind, I might be able to help you find a good paper if you come talk to me.

Important Dates

First class Monday, January 4
Deadline to drop course Tuesday, January 26
Reading week (no lectures) February 15 to 19
Test in Lassonde 3033 Monday, February 29
Last class Wednesday, March 30


These will be filled in as the term progresses.
The references below are intended for students who want to read more about the topics discussed in class. Sometimes the readings might be helpful for the assignments. Sometimes they will extend the ideas covered in lectures.


There is no required textbook for the course. However, I shall sometimes recommend readings from books or papers. These references will be listed here, and the list will grow during the term. Accessing some of the links below may require you to be logged into a machine at York, so that you can access the ACM Digital Library, etc.



This list is from the 2014 version of the course, but it gives you an idea of the kinds of topics covered. I'll add and subtract items from the list during the term.

Web Pages

Previous versions of this course: Fall 2011, Fall 2014.


Try to keep your answers as simple as possible (but no simpler).

Important note on collaboration on homework assignments: It is okay to discuss the general approach to solving a problem with your classmates. However, you should not take any written notes away from such a discussion, and you should write up your solution on your own. Also, to protect yourself against charges of plagiarism, you should write on the front page of your assignment the names of any classmates that you discussed the problem with, and any outside sources that you used.

This page was last updated on April 12, 2016