G22.2631

Distributed Computing

M 5-7pm, WWH 102

Instructor:  Lenore Zuck (zuck@cs.nyu.edu) Office hours:  T 3-5 (706, 715 Broadway) or by appointment

Teaching Assistant:  Alexander Zaks (sasha1979@yahoo.com)

Subscribe to Mailing list!!! (instructions)


The class will be run as a combination of lectures and research seminar. It will focus on:

Models of Distributed Computing, Synchronous Network Algorithms, Asynchronous Models, Asynchronous (Shared Memory and Network) Algorithms, Failure Modes, Theory of Knowledge, and Security Protocol. This will include explaining the mathematical results that are used, with proofs kept to the barest minimum. The algorithms covered will mostly be selected from the list: leader election, mutual exclusion, Byzantine agreement, atomic commit, coordinate attack, data-link, key exchange, and authentication.

There is no textbook for the class. Lecture notes and research papers will be posted on the web.

    Since there is not textbook, students are encourages to attend practically every class. The grade will be based on the quizzes and 5 (five) assignments/mini-projects, at least two of which will be theoretical, and at most 3 of each will involve programming. It will be possible to have theoretical assignments on all five. It will also be possible to replace an assignment with a class presentation of a research paper (chosen by the instructor.)

    Prerequisites: Fundamental Algorithms (preferably with an A- or better).

    Tentative Syllabus:

    •     Introduction to Distributed Computing (Lecture 1)
    •     Leader Election in a Synchronous Ring (Lecture2 )
    •     Coordinated Attack; Knowledge (Lecture 4)
    •     Consensus and Byzantine Agreements (Lecture 5-6)
    •     Asynchronous Systems (Lecture 7)
    •     Security Protocols (Lecture 8)
    •     Guest Lecture -- Prof. Benjamin Goldberg(Lecture 9)
    •     Mutual Exclusion Algorithms (Lecture 10-11)
    •     Atomic Registers (Lecture 12)
    •     Data-Link Protocols (Lecture 13)

    Suggested Reading

    Lecture Notes

    Assignments

    Miscellaneous