CPSC 668: Distributed Algorithms and Systems
Fall 2006

Announcements

• 11/27: Homework 7 is now available, due Mon, Dec 4.

• 11/21: Thank you for your patience these last few days with my bad cold! As several of you pointed out to me after class yesterday, there is *not* a problem with Algorithm 32, because there is only one reader and it keeps track of the latest value returned.

• 11/6: Homework 6 is now available, due Mon, Nov 20.

• 11/6: Class is cancelled for Friday, Nov. 10. Also, office hours that day. Email me if you need to reschedule office hours.

• 11/3: I'm extending the due date for HW 5 to Mon, Nov 6, at the beginning of class.

• 11/2: Typo in textbook relating to HW 5: On p. 176, line 10 of Algorithm 22, "for all k != i" should be "for all k != j". Thanks to Nikhil Gupta.

• 10/30: Clarification on Exercise 8.7 on HW 5: What is desired is a value VC to be assigned to every message so that VC(m) < VC(m') iff message m happens before message m'.

• 10/29: Homework 5 assignment is now complete (material on Ch 9 has been added).

• 10/26: I just corrected the due date for the project. It is due the last day of class, which is Mon, Dec 4 (not Fri, Dec 5 as I had it originally).

• 10/23: Homework 5 is now available, due Fri, Nov 3.

• 10/18: Here is a review for the midterm on Friday.

• 10/18: Local programming contest to be held this weekend. Anyone, undergrad or graduate student, who first started college (undergrad) no earlier than 2002 or was born no earlier than 1983 is eligible to compete. Here is the announcement:

     
  Are you good at problem solving?  Can you program?  Do you enjoy
  competition?  Would you like to represent Texas A&M?
  
  If so, come compete in the local programming competition to be held this
  coming weekend.  Here are the details:
  
  Texas A&M Local Programming Competition
  Date: Saturday, October 21
  Time: 12:00 noon for rules, warm-up, hints, and questions
        1:00 - 4:00 for contest
  Place: Room 229, H.R. Bright Building
  Refreshments (but not a meal) provided.
  Email icpc(at)cs.tamu.edu for more information.
  Note: There will also be a practice this Thursday at 7:00 in room 229 for
  those interested.
  
  The top individual finishers in this local competition will go on to
  represent Texas A&M in teams at the ACM South Central USA Regional
  programming contest on November 4.  The students also receive a free year of
  ACM membership.  The winners of the regional contest will get to compete in
  the world finals in Tokyo in March.
  
  To be eligible to compete, you must either have first started college no
  earlier than 2002, or have been born no earlier than 1983.
  

• 10/16: Thanks to Moulaali Sheik and Pu Duan for pointing out an error in the book on page 150, line 20: The error in estimating the message delay is at most d' - (d-u) (not half this quantity). Explanation: Suppose the minimum delay, d-u, is *much* smaller than the maximum delay d, and most messages have delay much closer to the minimum than the maximum. So u is very large, close to d. In the original scheme, the error is at most u/2 (which is large, since u is large). In the proposed scheme, the error is at most d' - (d-u): although the assumption is that the query and response both have equal delay (d'), it could be that the query has the minimum delay d-u and the response takes the rest of the time (2d' - (d-u)) or vice versa. This error is small, since d' and (d-u) are both small. This error propagates to line -5 of page 150.

• 10/13: Homework 4 has been scaled back: Just to the exercises for Chapters 6 and 13 and just read the Fan and Lynch paper. The rest will be postponed to the next homework. (Warning: I announced this incorrectly in class today. This is the correct announcement.)

• 10/9: Homework 4 is now available, due Wed, Oct 18.

• 10/6: Due to popular demand, I am postponing the deadline for exercises 5.20 and 5.21 (about test&set) on HW 3 to Monday, Oct 9, at the beginning of class.

• 9/22: Homework 3 is now available, due Oct 6.

• 9/21: I just fixed a typo in HW 2, problem 4.11 (I had referred to the special case of n = 1, but I meant the special case of n = 2).

• 9/18: John pointed out that my fix is broken. I'm making this problem extra credit: find, state, and prove correct invariants that allow you to prove the correctness of this algorithm.

• 9/18: Alert student John Garrison pointed out an error in the statement of Lemma 4.3 on page 69 (cf. Exercise 4.3 on HW 2). As stated, it is not true in the initial configuration. Try this modification: "If Flags[k] = has-lock and Last = k, then no processor is in entry section. Otherwise, if Flags[k] = has-lock, then (k - Last - 1) mod n processors are in entry section, each spinning on a different element of Flags."

• 9/15: Mistakes found so far in the textbook are listed on this errata page. I am collecting them, so if you find problems, please email them to me.

• 9/11: I postponed the due date for your project proposal to Wed, Sep 27.

• 9/11: Homework 2 is now available, due Sep 22.

• 9/4: Office hours rescheduled for this week. They will be Thursday, Sep 7, 2:00 - 4:00 PM, and Friday, Sep 8, 2:45 - 3:45 PM.

• 8/30: Homework 1 is now available, due Sep 8.

• 8/30: I will be putting the powerpoint lecture notes in the calendar section of the web site.

Back to beginning

Syllabus

Lecture: Monday, Wednesday, Friday, 1:50-2:40 PM, HRBB 126

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.

• 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.

Your grade will be based on three components:

• homeworks 50% -- homework will consist of written problems and paper reviews. Homework assignments will be due every couple of weeks. More information is here.

• midterm exam 25% -- an in-class midterm will be given about half-way through the semester. More information will be provided later.

• project 25% -- 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:

Collaboration: 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. Reference every source you use, whether it be a person, a book, a paper, a solution set, a web page or whatever. You MUST write up your 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.

Academic Integrity Statements: The Aggie Honor Code is "An Aggie does not lie, cheat, or steal or tolerate those who do." Upon accepting admission to Texas A&M University, a student immediately assumes a commitment to uphold the Honor Code, to accept responsibility for learning, and to follow the philosophy and rules of the Honor System. Students will be required to state their commitment on examinations, research papers, and other academic work. Ignorance of the rules does not exclude any member of the TAMU community from the requirements or the processes of the Honor System. For additional information please visit: http://www.tamu.edu/aggiehonor/ .

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

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.

• Homework 1. Due Sep 8.
• Homework 2. Due Sep 22.
• Homework 3. Due Oct 6.
• Homework 4. Due Oct 18.
• Homework 5. Due Nov 3. ** Extended to Nov 6. **
• Homework 6. Due Nov 20.
• Homework 7. Due Dec 4.

Project

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

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:

• 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:
  • ACM Symposium on Principles of Distributed Computing (PODC)
  • International Symposium on DIStributed Computing (DISC) -- formerly International Workshop on Distributed Algorithms (WDAG)
  • ACM Symposium on Theory of Computing (STOC)
  • IEEE Symposium on Foundations of Computer Science (FOCS)
  • IEEE Conference on Distributed Computing Systems (ICDCS)
  • International Conference on Principles of Distributed Systems (OPODIS)

Approaches: Some general ideas for approaches to take in your project:

1. 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.

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!

• self-stabilizing Byzantine agreement: Daliot and Dolev, PODC 2006
• failure-detector classes: Mostefaoui et al., PODC 2006
• consensus in different timing models: Keidar and Shraer, PODC 2006 (lots of open questions listed)
• game theory applied to distributed computing: Moscibroda et al., PODC 2006; Blum et al., PODC 2006; Abraham et al., PODC 2006; Keidar et al., PODC 2006
• computation on streams: Tirthapura et al., PODC 2006
• locality in distributed computing: Birk et al., PODC 2006
• gossip algorithms: Mosk-Aoyama and Shah, PODC 2006
• compact routing: Konjevod et al., PODC 2006
• wait-free shared data structures: Afek et al., PODC 2006; Fatourou and Kallimanis, PODC 2006; Attiya et al., PODC 2006
• leader election in shared memory: Golab et al., PODC 2006
• implementing fault-tolerant shared objects in message pasing: Guerraoui and Vukolic, PODC 2006
• broadcast in wireless networks: Koo et al., PODC 2006
• mutual exclusion: Fan and Lynch, PODC 2006
• transactional synchronization: Attiya et al., PODC 2006

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 technical paper in this area is:

• introduction (informal explanation of problem, why it is important/interesting, overview of the paper contents)
• definitions giving model of computation and precise problem statement
• results, including intuitive explanations
• conclusion (including open problems).

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

Deadlines:

• Fri, Sep 22 - postponed to Wed, Sep 27: 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.

• Mon, Dec 4: Written project report due.

Back to beginning

Calendar

• readings
• homework
• project
• exams

• Set 1: Introduction
• Set 2: Basic Graph Algorithms
• Set 3: Leader Election in Rings
• Set 4: Asynchronous Lower Bound for LE in Rings
• Set 5: Leader Election in Synchronous Rings
• Set 6: Mutual Exclusion in Shared Memory
• Set 7: Mutual Exclusion with Read/Write Variables
• Set 8: More Mutex with Read/Write Variables
• Set 9: Fault-Tolerant Consensus
• Set 10: Consensus with Byzantine Failures
• Set 11: Asynchronous Consensus
• Set 12: Causality
• Set 13: Clocks
• Set 14: Simulations
• Set 15: Broadcast
• Set 16: Distributed Shared Memory
• Set 17: Fault-Tolerant Register Simulations
• Set 18: Wait-Free Hierarchy
• Set 19: Problems Solvable in Asynchronous Failure-Prone Systems

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

  Monday	Tuesday	Wednesday	Thursday	Friday
  8/28 Introduction Read Chs 1 and 2	8/29	8/30 Spanning Trees; Leader Election in Rings Read Ch 3	8/31	9/1 Asynchronous Lower Bound for LE in Rings
  9/4 LE in Synchronous Rings	9/5	9/6 Randomized LE; Shared Memory Read Ch 14, sec 1, and Ch 4	9/7	9/8 Mutual Exclusion HW 1 due
  9/11 Mutex with Read/Write Variables	9/12	9/13 More Mutex with Read/Write Variables	9/14	9/15 Consensus with Crash Failures Read Ch 5
  9/18 More Consensus with Crash Failures	9/19	9/20 Consensus with Byzantine Failures	9/21	9/22 More Consensus with Byzantine Failures HW 2 due

  Monday	Tuesday	Wednesday	Thursday	Friday
  9/25 Impossibility of Asynchronous Consensus	9/26	9/27 Asynchronous Consensus Project Proposal Due	9/28	9/29 Dr. Scott Pike substitutes
  10/2 HW 2 Solutions	10/3	10/4 Causality Read Ch 6	10/5	10/6 HW 3 due
  10/9 Clock Synchronization	10/10	10/11 Byzantine Clock Synchronization Read Ch 13	10/12	10/13 More Byzantine Clock Synchronization
  10/16 HW 3 Solutions	10/17	10/18 HW 4 Solutions HW 4 due	10/19	10/20 Midterm Exam (open book, open notes)

  Monday	Tuesday	Wednesday	Thursday	Friday
  10/23 Model for Simulations Read Ch 7	10/24	10/25 Broadcast Read Ch 8	10/26	10/27 Reliable Broadcast; Distributed Shared Memory Read Ch 9
  10/30 More Distributed Shared Memory	10/31	11/1 Fault-Tolerant Register Simulations Read Ch 10	11/2	11/3 More Register Simulations
  11/6 More Register Simulations HW 5 due **new due date**	11/7	11/8 HW 5 Solutions	11/9	11/10 NO CLASS
  11/13 Wait-Free Hierarchy Read Ch 15	11/14	11/15 Problems Solvable in Asynchronous Systems Read Ch 16	11/16	11/17 More Problems Solvable in Asynchronous Systems

  Monday	Tuesday	Wednesday	Thursday	Friday
  11/20 Failure Detectors HW 6 due	11/21	11/22 NO CLASS - TAMU CLOSED	11/23 THANKSGIVING HOLIDAY	11/24 THANKSGIVING HOLIDAY
  11/27	11/28	11/29	11/30	12/1
  12/4 HW 6 due Project Due	12/5	12/6 READING DAY	12/7 READING DAY	12/8
  12/11	12/12	12/13	12/14	12/15

  Back to beginning

  ---

  Useful Links

  Distributed Computing
  • Distributed Algorithms and Systems -- see section on Other Resources for more links
  • Home Page for ACM Symposium on Principles of Distributed Computing
  Reading and Writing Research Papers
  • Some tips for reading research papers from Swarthmore. You can find lots more if you google on "how to read a research paper".
  • Advice on Research and Writing from CMU.
  Computing-Related at TAMU
  • Computer Science Department, TAMU
  • Student Computing and Information Page: central source of information about student computing at TAMU.

  Back to beginning