# CSCE 668: Distributed Algorithms and Systems Spring 2014

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

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

• homeworks 40% -- homework will consist of work-out problems, literature surveys 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.

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:

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.

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