CSCE 668: Distributed Algorithms and Systems
Spring 2014


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


Announcements

Back to beginning


Syllabus

Instructor: Prof. Jennifer Welch
Office: 425G Bright Bldg
Office Hours: Mondays and Wednesdays 2:30 - 4:00 PM; other times by appointment
Email: welch@cse.tamu.edu
Office Phone: 845-5076

Lecture: Monday, Wednesday, Friday, 10:20-11:10 AM, Zachry 119C

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

Prerequisite: An advanced undergraduate-level or introductory graduate-level course on analysis of algorithms, 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
1/13 introduction, basic graph algorithms 1, 2
1/20 leader election 3, 14.1
1/27, 2/3 mutual exclusion 4, 14.2
2/10, 2/17 consensus 5, 14.3
2/24, 3/3 causality, clock synchronization 6.1, 6.3, 13
3/17 broadcast 7, 8.1, 8.2
3/24 distributed shared memory 9
3/31, 4/7 fault-tolerant shared objects 10, 15
4/14 asynchronous solvability, failure detectors 16, 17
4/21 self-stabilization N/A
4/28 link reversal 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 the University's Disability Services in Cain Hall, Rm. B118, or call 845-1637.

Back to beginning


Homework

Homework assignments must be typed, using LaTeX. If you do not already know LaTeX, this will be a good opportunity to learn it. Some useful links are listed here.

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

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
January
Mon, 1/13 Introduction Read Chs 1 and 2
Wed, 1/15 Basic graph algorithms Read Ch 3
Fri, 1/17 Leader election in a ring .
Mon, 1/20 MARTIN LUTHER KING HOLIDAY .
Wed, 1/22 More leader election in a ring .
Fri, 1/24 Lower bound for LE in synchronous ring HW 1 due
Mon, 1/27 Randomized LE in ring; Mutual exclusion in shared memory Read Ch 14, sec 1; Read Ch 4
Wed, 1/29 More Mutual exclusion in shared memory .
Fri, 1/31 More Mutual exclusion in shared memory; HW 1 solutions .
February
Mon, 2/3 Mutual exclusion with read-write memory .
Wed, 2/5 More mutual exclusion with read-write memory .
Fri, 2/7 Fault-Tolerant Consensus HW 2 due
Read Ch 5
Mon, 2/10 HW 2 solutions .
Wed, 2/12 EXAM 1 .
Fri, 2/14 More Fault-Tolerant Consensus .
Mon, 2/17 Byzantine-Tolerant Consensus .
Wed, 2/19 Asynchronous Consensus Impossibility .
Fri, 2/21 Randomized Asynchronous Consensus Read Ch 14, sec 3
Mon, 2/24 Causality Read Ch 6
Wed, 2/26 Vector Clocks Lower Bound and Consistent Cuts .
Fri, 2/28 Clock Synchronization .
March
Mon, 3/3 More Clock Synchronization HW 3 due
Wed, 3/5 Byzantine Clock Synchronization Read Ch 13
Fri, 3/7 Homework 3 Solutions .
Mon-Fri, 3/10-3/14 SPRING BREAK .
Mon, 3/17 Modeling Simulations; Introduction to Broadcast Read Ch 7
Wed, 3/19 Broadcast Read Ch 8
Fri, 3/21 More Broadcast .
Mon, 3/24 Distributed Shared Memory HW 4 due
Read Ch 9
Wed, 3/26 More Distributed Shared Memory .
Fri, 3/28 Yet More Distributed Shared Memory .
Mon, 3/31 Fault-Tolerant Register Simulations Read Ch 10
April
Wed, 4/2 HW Solutions / Review HW 5 due
Fri, 4/4 EXAM 2 .
Mon, 4/7 More Fault-Tolerant Register Simulations .
Wed, 4/9 Wait-Free Hierarchy Read Ch 15
Fri, 4/11 More Wait-Free Hierarchy .
Mon, 4/14 Dr. Hyun Chul Chung: Failure Detectors .
Wed, 4/16 More Failure Detectors .
Fri, 4/18 READING DAY - NO CLASSES .
Mon, 4/21 Asynchronous Solvability HW 6 due
Read Ch 16
Wed, 4/23 More Asynchronous Solvability .
Fri, 4/25 Self-Stabilization .
Mon, 4/28 Link Reversal .
Tue, 4/29 (attend Friday classes) Homework Solutions / Review HW 7 due
May
Tue, 5/6 FINAL EXAM 8:00 AM - 10:00 PM .

Back to beginning


Useful Links

LaTeX Reading and Writing Research Papers

Back to beginning