COSC6117, Winter 2002

Theory of Distributed Computing
Winter 2002

Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Mondays 14:30-16:00 in room 109 of the Farquharson Building and Wednesdays 14:30-16:00 in room 129 of the Chem & Comp Sci Building
Office Hours: Tuesdays, Thursdays 14:30-15:30 or by appointment (or just drop by my office).


For exercise 6, you can assume that processes are have unique, (and consecutive) ids 1,2,3,...,n. (This is the assumption we have been commonly making when designing shared-memory algorithms in class.)

The classes on Apr 8 and Apr 10 will be in CCB120.

Due to seminars, class begins at 3:00 on March 11, 18, 25, and at 2:30 on other days.

You can check my record of your exercise marks by typing "courseInfo 6117".

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. Possible topics include: Marking scheme

Homework exercises 80%
Class presentation 20%

Lecture Notes

One student (a "scribe") will take notes in each class and then type them in Latex. The following formatting files are useful for the scribe notes: notes.sty and template.tex.

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.

Books (on reserve in Science Library)

Papers Web Pages


I'll give you approximately one exercise per week. Each will be due two weeks after it's assigned. (The first one is a two-parter, since I didn't give any exercise in week 1.)

Updated March 26, 2002