CPSC 668: Distributed Algorithms and Systems
Fall 2002
[Announcements]
[Syllabus]
[Project]
[Calendar]
[Useful Links]
- 12/19: Project reports are now graded and available for pick-up
outside my office (415 Bright).
- 12/13: HW 5 is now graded and available for pick-up 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 pick-up 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. 225-267,
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 0-141, through consensus):
postscript
- Installment 2 (slides 142-155, logical and vector clocks):
postscript
- Installment 3 (slides 156-164, 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: 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:
- 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
| 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:
- 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 open-ended 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 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:
- 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 world-wide-web: 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:
- peer-to-peer 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)
- self-stabilization (see proceedings of Workshop on Self-Stabilization)
-- e.g., find a self-stabilizing 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 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
Distributed Computing
Computing-Related at TAMU
Back to beginning