COSC6117, Winter 2008

COSC6117
Theory of Distributed Computing
Winter 2008

Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Email: [my last name] @cs.yorku.ca
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Tuesdays 11:30-13:00 in room 122 of the Chemistry Building and Thursdays 11:30-13:00 in room 2009 of Vari Hall
Office Hours: Tuesdays and Thursdays, 13:00-14:00, or by appointment, or just drop by when I am in my office.

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

Announcements

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 80%
Class presentation 20%

The 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. Before you start working on this, you should check with me that the paper you choose is appropriate. You will also have to hand in a short (~2 pages) written summary of what you are presenting. 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.

Lectures

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.

References

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.

Books

Papers

This list is from last year's 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: Winter 2002, Fall 2003, Fall 2004, Winter 2006.

Exercises

Updated March 31, 2008