CPSC 668: Distributed Algorithms and Systems
Fall 2002
[Announcements]
[Syllabus]
[Project]
[Calendar]
[Useful Links]
 12/19: Project reports are now graded and available for pickup
outside my office (415 Bright).
 12/13: HW 5 is now graded and available for pickup outside
my office (415 Bright).
 12/11: Interesting seminar at 3:30 Thursday, 12/12, in 124 Bright,
by Bill Tetzlaff on finishing your PhD and job hunting.
 12/11: HW 4 is now graded and available for pickup outside
my office (415 Bright) after 1:00 PM today.
 12/3: Final installment of HW 5 is
available, due 12/9.
 11/21: First installment of HW 5 is
available, due 12/9.
 11/18: Teaching evaluations will be done this Friday, Nov 22.
Bring a number 2 pencil. Also, my office hours tomorrow
(Tuesday, Nov 19) will end at 10:00.
 11/13: Actually there are no more problems for HW 4, just
the original two. Remember, they are due Mon, 11/18.
 11/11: Office hours this week: Tue, 9:00  10:30 AM as usual;
Thu, 3:15  4:45 PM (instead of Friday afternoon).
 11/6: The first installment of
Homework 4 is now available, due 11/18.
There will be a couple more problems later.
 10/30: Due to popular demand, HW 3 deadline is postponed
further until this Friday (11/1). If you already turned it
in today, you can still resubmit on Friday if you want to.
 10/23: Homework updates: HW 3 is now complete.
Some clarifications: on problem (I), if the general is faulty,
then the nonfaulty lieutenants still have to decide on something
and guarantee agreement. On problem (J), the assignment
to the leader is *not* irrevocable, so it can change over the
course of the execution.
 10/16: The first installment of
Homework 3 is now available, due 10/28.
There will be a couple more problems later.
 10/8: Lecture on 10/9 will cover the paper
"Unreliable failure detectors for reliable distributed systems,"
by Chandra and Toueg, J. of the ACM, vol 43, no 2, pp. 225267,
March 1996. You can find it on the ACM Digital Library.
 10/8: My office hours for the rest of this week:
Tue, 10/8, 9:00  10:30 AM;
Thu, 10/10, 1:30  3:00 PM (instead of Friday, 10/11).
 10/4: My office hours today (Fri, 10/4) are postponed to
Mon, 10/7, 3:00  4:30 PM.
 9/24: There are now TWO copies of the textbook on reserve
at the library.
 9/23: Homework 2 is now complete.
 9/18: The first installment of
Homework 2 is now available, due 10/4.
There will be a couple more problems later.
 9/13: There will be no class on Wed, 9/25 and Fri, 9/27.
Makeup classes will be Wed, 9/18, 6:00  6:50 PM
and Wed, 10/2, 6:30  7:20 in our usual classroom (204 Bright).
 9/4: Homework 1 is now available, due 9/13.
 9/4: You can get postscript versions of the slides here:
 Installment 1 (slides 0141, through consensus):
postscript
 Installment 2 (slides 142155, logical and vector clocks):
postscript
 Installment 3 (slides 156164, more clocks):
postscript
 9/3: My office hours have changed. They are
Tuesdays 9:00  10:30 AM and Fridays 1:30  3:00 PM;
other times by appointment.
 9/2: Copies of slides and bibliography are available at WERC building
copy center.
Back to beginning
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: 8455076
Home Phone: 7740680 (please don't call after 9:00 PM)
Lecture:
Monday, Wednesday, Friday, 12:401:30 PM, HRBB 204
Textbook:
Distributed Computing: Fundamentals, Simulations and
Advanced Topics, Hagit Attiya and Jennifer Welch,
McGrawHill, 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/McGrawHill
Book Company, 1990.
A background in distributed systems, faulttolerance,
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 looselycoupled and failureprone
ones. The course will cover formal models, algorithm
design and analysis, lower bounds, and impossibility proofs.
At the end of the semester you should:
 be familiar with fundamental models, problems, algorithms, lower bound
and impossibility results, and proof techniques in distributed
computing,
 be able to design new distributed algorithms for new situations,
using as building blocks the algorithms and techniques learned,
 be able to apply lower bounds and impossibility results learned
to new situations where appropriate,
 have improved ability to prove new lower bounds and impossibility
results for new situations.
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
 faulttolerant 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:
 homeworks 60%  homework will consist of written problems
(e.g., design an algorithm, extend or modify a result presented
in class). Homework assignments will be due every couple of weeks.
 project 40%  a term project involving a written report
and possibly an oral presentation.
More information is here.
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
[Purpose]
[Topic]
[Approaches]
[Written Report]
[Oral Presentation]
[Deadlines]
Purpose: This assignment has several purposes:
 introduction to the technical literature in the area,
 application of ideas and techniques presented in class in a more
extensive and openended environment than in the homework,
 practice in writing technical documents,
 practice in making oral presentations (class size permitting).
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 implementationrelated
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:
 Journals:
 Distributed Computing
 Journal of the ACM
 Information and Computation
(formerly Information and Control)
 ACM Transactions on Programming Languages and Systems
 Journal of Algorithms
 SIAM Journal on Computing
 Algorithmica
 Theoretical Computer Science
 Information Processing Letters
 Communications of the ACM (in the olden days)
 ACM Transactions on Computer Systems
 Mathematical Systems Theory
 Acta Informatica
 Journal of Computer and Systems Sciences
 IEEE Transactions on Computers
 IEEE Transactions on Software Engineering
 Conference proceedings:
 The worldwideweb: Many people have copies of their papers
available on line. Here is a bibliography link:
Approaches:
Some general ideas for approaches to take in your project:
 Read a few related theoretical distributed computing papers and
 Propose a simpler version of a problem presented in a paper and
develop a simpler solution to your problem. OR
 Discover a new connection between the papers; for instance, show
how the results in one paper can be used to improve or simplify
the results in another paper. OR
 Develop a new notation and/or result that can simplify
and/or unify the
results in these papers and redo the results in your new notation. OR
 Solve an open problem related to the papers.
 Come up with a new problem based on some application area known
to you and try to solve it.
 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:
 peertopeer systems (session 7 of PODC 02)
 compact routing (session 1 of PODC 00)
 competitive algorithms for object replication (Johnson and Singh,
PODC 00)
 group mutual exclusion (Joung, PODC 98)
 distributed data structures (Shavit and Zemach, PODC 98)
 group communication (De Prisco, et al., PODC 98; Chockler et al.,
PODC 98)
 synchronization primitives for practical machines (Moir, PODC 97;
Anderson et al., PODC 97)
 quorum systems (Malkhi et al., PODC 97; Bazzi, PODC 97)
 selfstabilization (see proceedings of Workshop on SelfStabilization)
 e.g., find a selfstabilizing version of some algorithm
 orientation / sense of direction (Flocchini et al., DISC 98)
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:
 introduction (informal explanation of problem, why it
is important/interesting, overview of the paper contents)
 formal definitions
 results, including intuitive explanations
 conclusion (including open problems).
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:
 Fri, Sep 20:
Turn in your project proposal  a page or two describing your chosen
topic and what you plan to do, and listing at least three
research papers upon which your project will be based.
A significant amount of work should go into this choice.
If your plan is not sufficiently relevant to the course, I will
not approve it, so it is best to talk with me in advance about
your plans.
 Fri, Dec 6:
Written project report due.
Back to beginning
This calendar lists all due dates as they become known for
 readings
 homework
 project
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 110
 9/3
 9/4
Simple Graph Algorithms
slides 1123
 9/5
 9/6
Leader Elec in Rings
slides 2433

9/9
Asynch LE Algs
slides 3440
 9/10
 9/11
Asynch LE Lower Bound; Synch LE Algs
slides 4150
 9/12
 9/13
Synch LE Lower Bound
slides 5161
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
WaitFree Register Implementations

11/18
WaitFree Register Implementations
HW 3 due
 11/19
 11/20
WaitFree Register Implementations
 11/21
 11/22
WaitFree Register Implementations

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

11/25
WaitFree Hierarchy
 11/26
 11/27
WaitFree Hierarchy
 11/28
THANKSGIVING HOLIDAY
 11/29
THANKSGIVING HOLIDAY

12/2
Atomic Snapshot Objects; kSet 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
Distributed Computing
ComputingRelated at TAMU
Back to beginning