CPSC 668: Distributed Algorithms and Systems
Fall 2002


[Announcements] [Syllabus] [Project] [Calendar] [Useful Links]


Announcements

Back to beginning


Syllabus

Instructor: Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: Tue 9:00 - 10:30 AM and Fri 1:30 - 3:00 PM (*updated 9/3*); other times by appointment
Email: welch@cs.tamu.edu
Office Phone: 845-5076
Home Phone: 774-0680 (please don't call after 9:00 PM)

Lecture: Monday, Wednesday, Friday, 12:40-1:30 PM, HRBB 204

Textbook: Distributed Computing: Fundamentals, Simulations and Advanced Topics, Hagit Attiya and Jennifer Welch, McGraw-Hill, 1998. NOTE: The book is out of print so you are not required to purchase it. Slides, handouts, and reserve copies will be used.

Prerequisite: CPSC 629 (Analysis of Algorithms) or equivalent, or permission of the instructor.

THIS IS A THEORETICAL COURSE. The emphasis will be on proving correctness of algorithms and proving upper and lower bounds on complexity measures. You are expected to be familiar with the general concepts involved in designing and analyzing sequential algorithms. Such familiarity would come from CPSC 629 or CPSC 311 or equivalent. A good reference book for sequential algorithm analysis is Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, The MIT Press/McGraw-Hill Book Company, 1990.

A background in distributed systems, fault-tolerance, operating systems, or networking would be helpful in appreciating possible applications of the results in the course, but is not essential.


Course Goals: In this course we will take a theoretical approach to studying distributed computer systems, especially loosely-coupled and failure-prone ones. The course will cover formal models, algorithm design and analysis, lower bounds, and impossibility proofs. At the end of the semester you should:

Course Content and Tentative Schedule: The course will cover the following topics. The relevant chapters of the textbook are indicated.

week of topic chapter
9/2 introduction 1, 2
9/9 leader election 3, 14.1
9/16 mutual exclusion 4, 14.2
9/23 guest lectures N/A
9/30, 10/7 consensus 5, 14.3
10/14 failure detectors N/A
10/21, 10/28 causality and time 6, 13
11/4 broadcast and multicast 7, 8
11/11 distributed shared memory 9
11/18, 11/25 fault-tolerant shared objects 10, 15
12/2, 12/9 asynchronous solvability 17

Assignments and Grading: All assignments will be announced in class and posted on the course web page calendar. If you cannot turn in an assignment on time, discuss the situation in advance with the instructor.

Your grade will be based on two components:

Course grades will be assigned according to this scale:
A for 90% or above of the total points,
B for 80 to 89%,
C for 70 to 79%,
D for 60 to 69%,
and F for less than 60%.

Collaboration: Discussion of concepts with others and consulting written sources is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden.

University Regulations, Section 42, define scholastic dishonesty to include acquiring answers from any unauthorized source, working with another person when not specifically permitted, observing the work of other students during any exam, providing answers when not specifically authorized to do so, informing any person of the contents of an exam prior to the exam, and failing to credit sources used. Disciplinary actions range from grade penalty to expulsion.

Back to beginning


Project

[Purpose] [Topic] [Approaches] [Written Report] [Oral Presentation] [Deadlines]

Purpose: This assignment has several purposes:

I encourage you to discuss your project with me as often as you like, and at any stage, especially early on.

Topic: Your project will involve reading several related papers from the literature, summarizing and critically reviewing the work, and either extending the work in some way or simplifying the results by making some simplifying assumptions.

Your topic should concern distributed algorithms and have a significant theoretical component to it. An implementation-related topic is possible if it relates somehow to theory, for instance, a simulation to verify or discover the average case performance of some algorithm.

Some good places to look for distributed computing papers are:

Approaches: Some general ideas for approaches to take in your project:

  1. Read a few related theoretical distributed computing papers and

  2. Come up with a new problem based on some application area known to you and try to solve it.

  3. Study a distributed algorithm that is used as the basis of a commercial product (remember that the World Wide Web is a giant distributed systems).
For Approach 1, here are some ideas for problems to consider together with a representative recent paper to get you started finding references:

Written Report: The report is to be typed, at least 10 pages long and no more than 20 pages long. If you believe you have a good reason why the length of your paper should not conform to these guidelines, discuss it with me in advance. Part of your grade will be based on the quality of your composition (including spelling, grammar, logical flow). Typical organization for a technical paper in this area is:

As a general rule, very little, if any, of your paper should consist of copying the contents of the papers you read, and of course if you do quote from a paper, be sure to credit the source.

Oral Presentation: More information will appear here if class size permits.

Deadlines:

Back to beginning


Calendar

This calendar lists all due dates as they become known for Follow the links in the calendar to get details on the assignments.

Lecture note slides and bibliography are available from the WERC building copy center.

Monday Tuesday Wednesday Thursday Friday
9/2
Introduction
slides 1-10
9/3
9/4
Simple Graph Algorithms
slides 11-23
9/5
9/6
Leader Elec in Rings
slides 24-33
9/9
Asynch LE Algs
slides 34-40
9/10
9/11
Asynch LE Lower Bound; Synch LE Algs
slides 41-50
9/12
9/13
Synch LE Lower Bound
slides 51-61
HW 1 due
9/16
Randomized LE
9/17
9/18
Mutual Exclusion
Makeup class 6:00 - 6:50 PM, 204 HRBB
9/19
9/20
Mutual Exclusion
Project proposal due
9/23
Consensus, Crash Algorithm
9/24
9/25
NO CLASS
9/26
9/27
NO CLASS

Monday Tuesday Wednesday Thursday Friday
9/30
Consensus Round Lower Bound
10/1
10/2
Byzantine Consensus Algorithms
Makeup class 6:30 - 7:20 PM, 204 HRBB
10/3
10/4
Asynchronous Consensus Impossible
HW 2 due
10/7
Asynchronous Consensus Impossible
10/8
10/9
Failure Detectors
10/10
10/11
More Failure Detectors
10/14
Logical and Vector Clocks
10/15
10/16
More on Vector Clocks
10/17
10/18
Consistent Cuts
10/21
Clock Synchronization
10/22
10/23
Lower Bound on Clock Skew
10/24
10/25
Processor Lower Bound for Byz. Clock Synch.

Monday Tuesday Wednesday Thursday Friday
10/28
Formal Model for Simulations
10/29
10/30
More Modeling
10/31
11/1
Broadcast
HW 3 due
11/4
Reliable Broadcast; Multicast
11/5
11/6
Distributed Shared Memory
11/7
11/8
SC Lower Bound
11/11
SC Algorithm
11/12
11/13
Lin. Lower Bounds
11/14
11/15
Wait-Free Register Implementations
11/18
Wait-Free Register Implementations
HW 3 due
11/19
11/20
Wait-Free Register Implementations
11/21
11/22
Wait-Free Register Implementations

Monday Tuesday Wednesday Thursday Friday
11/25
Wait-Free Hierarchy
11/26
11/27
Wait-Free Hierarchy
11/28
THANKSGIVING HOLIDAY
11/29
THANKSGIVING HOLIDAY
12/2
Atomic Snapshot Objects; k-Set Consensus
12/3
12/4
12/5
12/6
Project report due
12/9
HW 5 due
12/10
12/11
READING DAY
12/12
READING DAY
12/13
12/16
12/17
12/18
12/19
12/20

Back to beginning


Useful Links

Distributed Computing Computing-Related at TAMU

Back to beginning