CPSC 668: Distributed Algorithms and Systems
Fall 2000

Announcements

• 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 alpha-prime 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 d-3u/4, the delay from p1 to p0 should be d-u/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, e-mail 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/student-org/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

Syllabus

Lecture: Monday, Wednesday, Friday, 10:20-11:10 PM, HRBB 104

Textbook: Distributed Computing: Fundamentals, Simulations and Advanced Topics, Hagit Attiya and Jennifer Welch, McGraw-Hill, 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/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.

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

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 some 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:
  • ACM Symposium on Principles of Distributed Computing (PODC) (I have 1983--2000)
  • 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)

• The world-wide-web: Many people have copies of their papers available on line. Here are some bibliography links:
  • Collection of CS Bibliographies
  • Hypertext Bibliography Project

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. Come up with a new problem based on some application area known to you and try to solve it.

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

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

• self-stabilization (session 1 of PODC 96) -- e.g., find a self-stabilizing 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).

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.

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.

Back to beginning

Calendar

• readings
• homework
• project

Lecture note slides are available here and from the Bright building copy center:

• 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

Back to beginning

Useful Links

• Distributed Algorithms and Systems -- see section on Other Resources for more links

• Collection of Computer Science Bibliographies -- includes entries for Distributed Systems and Theory/Foundations of Computer Science

• Routing

• Computer Science Department, TAMU

• Student Computing and Information Page: central source of information about student computing at TAMU.

• Schedule of short courses offered by the CIS Computer Help and Training Group. Includes introduction to TAMU computing resources, introduction to the Internet, using netscape, Unix.

Back to beginning