CSCE 668: Distributed Algorithms and Systems
Fall 2009

Announcements

• 11/18: Homework 6 is available, due Mon, Dec 7. Turn it in on paper.

• 11/4: Homework 5 is available, due Wed, Nov 11. Turn it in on paper.

• 10/23: Due date for HW 4 postponed to Fri, Oct 30!

• 10/21: Due date for HW 4 postponed to Wed, Oct 28.

• 10/16: Homework 4 is available, due Mon, Oct 26. Turn it in electronically.

• 10/5: Homework 3 is available, due Wed, Oct 14.

• 9/29: Exam I review sheet is now available. The review session (and makeup class) is scheduled for Wednesday, Sep 30, 6:00 - 7:00 PM in room 131 Bright.

• 9/29: Dr. Stoleru's slides are here: set 1, set 2, set 3, set 4. He covered a lot of material. For Exam 1, just know generally what problem each paper was tackling and think about any connection with our course material.

• 9/28: Homework 2 is to be typed and turned in using the CSE Department turnin program (click here for instructions). Please turn in a file that is either PDF, Microsoft Word, or OpenOffice.

• 9/28: Exercises 5.15-5.20 on HW 2 have been postponed until after Exam 1.

• 9/14: Homework 2 is available, due Wed, Sep 30.

• 9/4: Homework 1 is available, due Fri, Sep 11.

• 8/31: Updated errata list for the textbook is available here.

Back to beginning

Syllabus

Teaching Assistant: Srikanth Sastry
Office: 419D Bright Bldg
Office Hours: Monday, Tuesday, Wednesday 4:00-5:00 PM; other times by appointment
Email: sastry@cse.tamu.edu
Office Phone: 862-4535

Lecture: Monday, Wednesday, Friday, 3:00-3:50 PM, HRBB 126

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

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, 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 20% -- homework will consist of written problems and paper reviews. Homework assignments will be due every couple of weeks. More information is here.

• exams 60% -- two midterms and a final, worth 20% each, will be given.

• project 20% -- a term project involving a written report. More information is here.

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:

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:

• Definitions of academic misconduct, which includes plagiarism
• List of sanctions that can be applied if academic misconduct is found.

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

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.

• Homework 1. Due Fri, Sep 11.
• Homework 2. Due Wed, Sep 30.
• Homework 3. Due Wed, Oct 14.
• Homework 4. Due Mon, Oct 26. *** postponed to Wed, Oct 28 ***
• Homework 5. Due Wed, Nov 11.

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

• graph algorithms (e.g., maximal independent set): Gfeller and Vicar, PODC 2007
• self-stabilizing Byzantine agreement: Daliot and Dolev, PODC 2006
• failure-detectors: Bhatt et al., PODC 2009
• wait-free dining philosophers: Sastry et al., SPAA 2009
• consensus in different timing models: Keidar and Shraer, PODC 2006 (lots of open questions listed)
• game theory applied to distributed computing: Demaine et al., PODC 2007
• computation on streams, data aggregation: Cormode et al., PODC 2007
• locality in distributed computing: Birk et al., PODC 2006
• gossip algorithms: Mosk-Aoyama and Shah, PODC 2006
• compact routing: Konjevod et al., PODC 2006 and PODC 2007
• wait-free shared data structures: Fatourou and Kallimanis, PODC 2007
• link-reversal algorithms: Charron-Bost et al., SPAA 2009
• leader election in shared memory: Golab et al., PODC 2006
• implementing fault-tolerant shared objects in message pasing: Aguilera et al., PODC 2009
• computing in wireless networks: Dolev et al., PODC 2009
• mutual exclusion: Hendler and Woelfel, PODC 2009
• transactional memory: Dragojevic et al., PODC 2009
• peer-to-peer systems: Slivkins, PODC 2007
• clock synchronization: Lenzen et al., PODC 2009; Kuhn et al., SPAA 2009

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

Deadlines:

• Mon, Oct 12: Turn in your project proposal -- a page describing your chosen topic and listing the 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.

• Fri, 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
• Set SS: Self-Stabilization

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

Date	Topic	Reading and Assignments Due
Mon, 8/31	Introduction	Read Chs 1 and 2
September
Wed, 9/2	Graph Algorithms; Leader Election	.
Fri, 9/4	Leader Election	Read Ch 3
Mon, 9/7	Leader Election	.
Wed, 9/9	Mutual Exclusion	Read Ch 4
Fri, 9/11	Mutual Exclusion	HW 1 due
Mon, 9/14	Mutual Exclusion	.
Wed, 9/16	Fault-Tolerant Consensus	Read Ch 5
Fri, 9/18	Fault-Tolerant Consensus	.
Mon, 9/21	Dr. Stoleru: Wireless Sensor Networks	.
Wed, 9/23	Class rescheduled	.
Fri, 9/25	Class rescheduled	.
Mon, 9/28	Consensus	.
Wed, 9/30	Consensus	HW 2 due
October
Fri, 10/2	.	EXAM I
Mon, 10/5	Consensus	.
Wed, 10/7	Causality	Read Ch 6
Fri, 10/9	Causality	.
Mon, 10/12	Clock Synchronization	Project Proposal due
Wed, 10/14	Clock Synchronization	HW 3 due Read Ch 13
Fri, 10/16	Clock Synchronization	.
Mon, 10/19	Model Simulations	Read Ch 7
Wed, 10/21	Model Simulations; Broadcast	Read Ch 8
Fri, 10/23	Broadcast	.
Mon, 10/26	Broadcast	.
Wed, 10/28	Distributed Shared Memory	Read Ch 9
Fri, 10/30	Distributed Shared Memory	HW 4 due
November
Mon, 11/2	Register Simulations	Read Ch 10
Wed, 11/4	Register Simulations	.
Fri, 11/6	Atomic Snapshot Objects	.
Mon, 11/9	Review for Exam II (HW Solutions)	.
Wed, 11/11	Review for Exam II (HW Solutions)	HW 5 due
Fri, 11/13	.	EXAM II
Mon, 11/16	Wait-Free Hierarchy	Read Ch 15
Wed, 11/18	.	.
Fri, 11/20	.	.
Mon, 11/23	.	.
Wed, 11/25	.	.
Fri, 11/27	THANKSGIVING HOLIDAY	.
Mon, 11/30	.	.
December
Wed, 12/2	.	.
Fri, 12/4	.	Project Report due
Mon, 12/7 (attend Friday classes)	.	HW 6 due
Wed, 12/15	.	FINAL EXAM 10:30 AM - 12:30 PM

Back to beginning

Useful Links

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

• Department of Computer Science and Engineering, TAMU
• TAMU Computing Services

Back to beginning