CPSC 668: Distributed Algorithms and Systems
Spring 2008

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

Announcements

Back to beginning

Syllabus

Instructor: Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: Monday and Wednesday 10:00 - 11:30 AM; other times by appointment
Email: welch@cs.tamu.edu
Office Phone: 845-5076

Lecture: Monday, Wednesday, Friday, 9:10-10:00 PM, ZACH 119A

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

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, 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 CPSC 629 or CPSC 311 or equivalent. A good reference book for sequential algorithm analysis is Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, the MIT Press, 2002.

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
1/14 introduction, basic graph algorithms 1, 2
1/21 leader election 3, 14.1
1/28 mutual exclusion 4, 14.2
2/4, 2/11 consensus 5, 14.3
2/18, 2/25 causality, clock synchronization 6.1, 6.3, 13
3/3 broadcast 7, 8.1, 8.2
3/17 distributed shared memory 9
3/24, 3/31 fault-tolerant shared objects 10, 15
4/7 asynchronous solvability 16
4/14 failure detectors 17
4/21, 4/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:

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://www.tamu.edu/aggiehonor, 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 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. 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 the Department of Student Life, Services for Students with Disabilities in Cain Hall, Rm. B118, or call 845-1637.

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 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!

Don't forget to turn in a cover sheet 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

[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. Implementations are only appropriate as an auxiliary to some more theoretical results.

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. Read a larger number of related papers (at least 10) and write a survey paper. There should be significant added value in your survey. At minimum the papers should be well-organized, and for more credit you should provide the reader with some new insights into the papers and how they relate to each other. For some good examples, see papers published in ACM Computing Surveys, e.g., the paper by Androutsellis-Theotokis and Spinellis on peer-to-peer content distribution technologies, vol. 36, no. 4, 2004. You must also come up with a list of at least five open problems relating to your surveyed papers.

  3. Come up with a new problem based on some application area known to you and try to solve it. The problem and your approach must be relevant to the course topic and goals!
For the first two approaches 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. Part of your grade will be based on the quality of your composition (including spelling, grammar, logical flow). Typical organization for a (nonsurvey) technical paper in this area is:

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.

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

Deadlines:

Some intermediate deadlines may be added.

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):