CSCE 668: Distributed Algorithms and Systems
Fall 2011


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


Announcements

Back to beginning


Syllabus

Instructor: Prof. Jennifer Welch
Office: 425G Bright Bldg
Office Hours: Mondays 10:00 - 11:00 AM; Wednesdays and Fridays 11:00 AM to 12:00 noon; other times by appointment
Email: welch@cse.tamu.edu
Office Phone: 845-5076

Lecture: Monday, Wednesday, Friday, 1:50-2:40 PM, Civil Engineering (C.E.) room 223

Textbook: Distributed Computing: Fundamentals, Simulations, and Advanced Topics, Second Edition, Hagit Attiya and Jennifer Welch, John Wiley & Sons, 2004.

Course website: http://parasol.tamu.edu/people/welch/teaching/668.f11

Prerequisite: CSCE 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, proving upper and lower bounds on complexity measures, and proving impossibility results. You are expected to be familiar with the general concepts involved in designing and analyzing sequential algorithms. Such familiarity would come from CSCE 629 or CSCE 311/411 or equivalent. A good reference book for sequential algorithm analysis is Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, the MIT Press, any edition.

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. In some cases, supplementary readings will be assigned.

week of topic chapter
8/29 introduction, basic graph algorithms 1, 2
9/5 leader election 3, 14.1
9/12 mutual exclusion 4, 14.2
9/19, 9/26 consensus 5, 14.3
10/3, 10/10 causality, clock synchronization 6.1, 6.3, 13
10/17 link reversal algorithms N/A
10/24 broadcast 7, 8.1, 8.2
10/31 distributed shared memory 9
11/7 fault-tolerant shared objects 10, 15
11/14 asynchronous solvability 16
11/21 failure detectors 17
11/28 self-stabilization N/A

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 three components:

Late work policy: 10% of the maximum possible points will be deducted for each 24 hours that the assignment is late. Once solutions have been discussed or handed out, the assignment will not be accepted (grade of 0). Make-up assignments will only be available for university-excused absences. Please discuss unusual circumstances in advance, if possible, with the instructor.

Course grades will be assigned according to this scale:

% total points >= 90 80-89 70-79 60-69 < 60
letter grade A B C D F

Academic Integrity: The Aggie Honor Code states "An Aggie does not lie, cheat or steal or tolerate those who do". More information on academic integrity, plagiarism, etc. is available at the Aggie Honor System Office web site http://aggiehonor.tamu.edu/, including:

Please review this material.

For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source, reference it/him/her, whether it be a person, a paper, a book, a solution set, a web page or whatever. You MUST write up the assignments in your own words. Copying is strictly forbidden. Every assignment must be turned in with this cover sheet, which lists all sources you used.

Americans with Disabilities Act (ADA) Policy Statement: The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact Disability Services, in Cain Hall, Room B118, or call 845-1637. For additional information visit http://disability.tamu.edu.

Back to beginning


Homework

The written problems will include some from the textbook and others similar in style.

Each assignment will also list a small number of papers that are related to recent class topics. For each paper, you are to read it and write (type!) a one or two page report containing

  1. complete bibliographic reference (that is, list the title, authors, journal or conference name, page numbers, and date)
  2. summary of the main points
  3. why the results are new/interesting/significant and how they relate to the topic(s) discussed in class
  4. your critique of the paper
Be sure to include these 4 points, clearly labeled. Your report must be in your own words!

Turn in this cover sheet (click on link) with each assignment.

The homeworks and their due dates are available in the calendar section and are summarized here also as they become known.

Back to beginning

Project

Your project will involve reading at least five related papers from the literature, summarizing and critically reviewing the work, and suggesting at least five directions for future work relevant to the papers. Your topic should concern distributed algorithms and have a significant theoretical component to it.

Here are some suggested topics together with a representative recent paper to get you started finding references:
PODC = ACM Symposium on Principles of Distributed Computing;
SPAA = ACM Symposium on Parallelism in Algorithms and Architectures;
SIROCCO = International Colloquium on Structural Information and Communication Complexity

Written Report: The report is to be typed, at least 10 pages long and no more than 20 pages long. Part of your grade will be based on the quality of your composition (including spelling, grammar, logical flow). Suggested outline:

  1. introduction: informal explanation of problem, why it is important/interesting, overview of the paper contents
  2. overview of how your chosen papers fit together and relate to each other
  3. summaries of the papers with your critiques
  4. open problems
  5. conclusion
  6. reference list
Your report must be written in your own words! If you feel the need to quote directly from another paper, be sure to put the quote inside quotation marks and cite the source; very little, if any, of your paper should consist of direct quotations.

Deadlines:

Back to beginning


Calendar

This calendar lists all due dates as they become known for Powerpoint lecture slides (links will be populated as the slides are updated):

Follow the links in the calendar to get details on the assignments.

Date Topic Reading and Assignments Due
Mon, 8/29 Introduction Read Chs 1 and 2
Wed, 8/31 Basic Graph Algorithms .
September
Fri, 9/2 Leader Election in a Ring Read Ch 3
Mon, 9/5 Leader Election in a Ring .
Wed, 9/7 Dr. Josef Widder: Leader Election in a Ring Read Ch 14, Sec 14.1.1-14.1.3
Fri, 9/9 Mutual Exclusion Read Ch 4
Mon, 9/12 Mutual Exclusion HW 1 due
Wed, 9/14 Mutual Exclusion .
Fri, 9/16 Mutual Exclusion .
Mon, 9/19 Mutual Exclusion .
Wed, 9/21 Consensus Read Ch 5
Fri, 9/23 Consensus .
Mon, 9/26 Consensus HW 2 due
Wed, 9/28 Consensus .
Fri, 9/30 Consensus .
October
Mon, 10/3 Consensus Read Ch 14, Sec 14.1.4 and 14.3
Wed, 10/5 Causality Read Ch 6
Fri, 10/7 Causality .
Mon, 10/10 Clock Synchronization HW 3 due
Mon, 10/10 makeup class
(4:30 - 5:30 PM, 302 HRBB)
review for midterm .
Wed, 10/12 NO CLASS .
Fri, 10/14 . MIDTERM EXAM (firm)
Mon, 10/17 Clock Synchronization Project Proposal due;
Skim Ch 13
Wed, 10/19 Simulations Read Ch 7
Fri, 10/21 Broadcast Read Ch 8
Mon, 10/24 Distributed Shared Memory Read Ch 9
Wed, 10/26 Distributed Shared Memory .
Fri, 10/28 Fault-Tolerant DSM;
material is from Attiya, Bar-Noy, and Dolev paper,
just won Dijkstra Award
Read Ch 10
Mon, 10/31 Register Simulations HW 4 due
November
Wed, 11/2 Register Simulations; Golab et al. paper .
Fri, 11/4 Wait-Free Hierarchy Read Ch 15
Mon, 11/7 Wait-Free Hierarchy .
Wed, 11/9 Asynchronous Solvability Read Ch 16
Fri, 11/11 Asynchronous Solvability .
Mon, 11/14 Failure Detectors HW 5 due
Skim Ch 17; read Section 17.2, Theorem 17.2 (typo in statement) and its proof, and Section 17.4
Wed, 11/16 Failure Detectors .
Fri, 11/18 Self-Stabilization .
Mon, 11/21 Self-Stabilization; Link Reversal .
Wed, 11/23 Link Reversal .
Fri, 11/25 THANKSGIVING HOLIDAY .
Mon, 11/28 Link Reversal .
December
Wed, 11/30 Link Reversal .
Fri, 12/2 Link Reversal Project Report due
Mon, 12/5 (attend Friday classes) Homework Solutions HW 6 due
Tue, 12/13 . FINAL EXAM 10:30 AM - 12:30 PM

Back to beginning


Useful Links

Reading and Writing Research Papers

Back to beginning