CPSC 668: Distributed Algorithms and Systems
Fall 2000
[Announcements]
[Syllabus]
[Project]
[Calendar]
[Useful Links]
 11/27: Contact me by 5:00 PM today (Monday) if you plan to use
a PC projector for your presentation.
 11/27: The completed Homework 4 is now
available, due 12/1.
 11/20: My office hours on Tuesday, Nov 21, are cancelled.
Please email me (welch@cs.tamu.edu) if you need to meet.
 11/17: The corrected version of the proof of Theorem 10.3
is here in postscript (with figures).
 11/16: The first part of Homework 4 is now
available, due 12/1.
 11/16: Course evaluations postponed to Fri, Nov 17.
 11/13: Course evaluations will be done on Wed, Nov 15.
Bring a #2 pencil to class.
 11/2: Another typo in Problem 6.12 (thanks to Guangtong Cao):
The shift amount to create alphaprime should be negative!
 11/2: Concerning HW 3 due 11/6: I will not add any additional
problems. Several students pointed out to me typos in Figure 6.15
(p. 156): u should be subtracted from each delay.
So the delay from p0 to p1 should be d3u/4, the delay from p1 to p0
should be du/4, etc.
 10/25: Another problem has been added to HW 3 now.
 10/19: In order to be more convenient for more students, I am
changing my office hours. Effective immediately, my office
hours are Tue, 1:30  3:00 PM, and Thu, 3:00  4:30 PM.
You can still make an appointment to see me at other times.
 10/18: The first part of Homework 3 is now
available, due 11/6.
 10/18: If you missed class the other day, be sure to see me to
sign up for your presentation.
 10/16: HW 3 is due Mon, Nov 6, and HW 4 is due Fri, Dec 1.
The exact problems in these assignments will be announced
as the semester proceeds (depends on how fast we go).
 10/11: Programming contest:
This is to remind all of you that the programming contest will be
held this Saturday, October 14 in room 209 at 10 a.m.
Contest plans:
Participants will compete individually
Microsoft has donated over $4K worth of software to top six winners
First place gets $40, second place gets $20, and third place gets $10
Only the top two graduate students can be part of the top six winners
Languages: C/C++, Java, (and Pascal on request)
Informational meeting will be held at Bright 126 on Thurs. at 6:30.
If you cannot attend, email Eric at ers@tamu.edu
Contest will last for three hours
Refreshments will be available
TACS members may participate for free. There is a $5 fee for nonmembers.
If you're still not a member and would like to become one, some one will
be there to take applications and dues.
Note: Top six winners are required to go to regionals or do not recieve
software and/or money prizes. The top six will be grouped into two
groups.
More information about the contest such as scoring, etc. is available at
http://www.cs.tamu.edu/studentorg/acm/activities.html
We look forward to seeing you on Saturday!
Eric Schendel (Programming contes coordinator)
Mirna Carrasco Nieto (Publicity chair)
 10/10: Homework 2 due date is postponed to Monday, Oct 16.
 9/18: Homework 2 is now available, due 10/11.
 8/30: Homework 1 is now available, due 9/15.
 8/28: I forgot to mention in class that you can also get copies
of the slides from this web page (see calendar section below).
You do not have to buy them from the copy center.
 8/28: Please check the errata
page for corrections to the textbook.
Back to beginning
Instructor:
Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: 1:30  3:00 PM Tuesday and 3:00  4:30 PM Thursday
(*updated 10/19*); 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, 10:2011:10 PM, HRBB 104
Textbook:
Distributed Computing: Fundamentals, Simulations and
Advanced Topics, Hagit Attiya and Jennifer Welch,
McGrawHill, 1998.
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

8/28
 introduction
 1, 2

9/4, 9/11
 leader election
 3, 14.1

9/18, 9/25
 mutual exclusion
 4, 14.2

10/2, 10/9
 consensus
 5, 14.3

10/16
 causality and time
 6, 13

10/23
 broadcast and multicast
 7, 8

10/30
 distributed shared memory
 9

11/6, 11/13
 faulttolerant shared objects
 10, 15

11/20, 11/27
 asynchronous solvability
 17

12/4
 presentations
 .

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 some 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 are some bibliography links:
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:
 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)
 failure detectors (Mostefaoui and Raynal, PODC 00; Yang 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 (session 1 of PODC 96)  e.g., find a selfstabilizing
version of some algorithm
 orientation / sense of direction (Flocchini et al., DISC 98)
 Extensions, discussed in the chapter notes of the text, to
material covered in the text.
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:
You will be allotted some number of minutes (depending on the size of the
class) for your presentation. This is a STRICT limit. In order to
maximize the effectiveness of your presentation, you should carefully
plan what you will say and PRACTICE. This is not enough time to go
into technical details. A good organization is:
 describe the problem,
 explain why it is important,
 give an overview of what you did,
 conclude and describe any interesting related open problems.
You should use overhead transparencies, either drawn neatly by hand or
computergenerated. Judicious use of color, drawings and humor
is encouraged.
Deadlines:
 Sep 29:
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.
 Dec 4:
Written project report due.
If class size permits oral presentations, they will be scheduled later.
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 are available here and
from the Bright building copy center:
 Installment 1 (slides 0141, through consensus):
postscript
 Installment 2 (slides 142155, logical and vector clocks):
postscript
 Installment 3 (slides 156164, more clocks):
postscript
Monday
 Tuesday
 Wednesday
 Thursday
 Friday

8/28
Introduction
Slides 113
Read Ch 12
 8/29
 8/30
Graph Algorithms
Slides 1425
 8/31
 9/1
LE in Rings
Slides 2637
Read Ch 3

9/4
LE in Rings
Slides 3849
 9/5
 9/6
Review LE Algorithms
 9/7
 9/8
LE in Rings
Slides 5057

9/11
Randomized LE Alg
Slides 5863
Read Ch 14.1
 9/12
 9/13
ME in Shared Memory
Slides 6471
Read Ch 4
 9/14
 9/15
ME in Shared Memory
Slides 7282
HW 1 due

9/18
ME in Shared Memory
Slides 8387
Read Ch 14.2
 9/19
 9/20
ME in Shared Memory
Slides 8893
 9/21
 9/22
FaultTolerant Consensus
Slides 9498; Aguilera & Toueg
Read Ch 5

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

9/25
Aguilera & Toueg,
Byzantine Proc Lower Bound
Slides 107110
 9/26
 9/27
Exponential Tree Alg
Slides 111118
 9/28
 9/29
Phase King Alg
Slides 119122
Project Proposal Due

10/2
Guest lecture by Prof. Bettati
 10/3
 10/4
Guest lecture by Prof. Vaidya
 10/5
 10/6
Guest lecture by Prof. Amato

10/9
WaitFree Impossibility
Slides 123128
 10/10
 10/11
1Resilient Impossibility
Slides 129135
 10/12
 10/13
Randomized Consensus
Slides 136141
Read Ch 14.3

10/16
Logical & Vector Clocks
Slides 142150
HW 2 due
Read Ch 6
 10/17
 10/18
Consistent Cuts
 10/19
 10/20
Physical Clocks

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

10/23
Clock Skew Upper Bound
 10/24
 10/25
Clock Skew Lower Bound
 10/26
 10/27
FaultTolerant Clock Synch
Read Ch 13

10/30
FaultTolerant Clock Synch
 10/31
 11/1
Simulation Model
Read Ch 7
 11/2
 11/3
Broadcast
Read Ch 8

11/6
Multicast
HW 3 due
 11/7
 11/8
DSM
Read Ch 9
 11/9
 11/10
DSM

11/13
Register Simulations
Read Ch 10
 11/14
 11/15
Register Simulations
 11/16
 11/17
Snapshot Objects

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

11/20
WaitFree Hierarchy
Read Ch 15
 11/21
 11/22
WaitFree Hierarchy
 11/23
THANKSGIVING HOLIDAY
 11/24
THANKSGIVING HOLIDAY

11/27
Asynchronous Solvability
Read Ch 17.117.3
 11/28
 11/29
Student Presentations
 11/30
 12/1
Student Presentations
HW 4 due

12/4
Student Presentations
Project Report Due
 12/5
 12/6
READING DAY
 12/7
READING DAY
 12/8
FINAL EXAMS START

12/11
 12/12
 12/13
 12/14
 12/15

Back to beginning
Distributed Computing
ComputingRelated at TAMU
Back to beginning