Distributed Computing

T 5-7pm, WWH 101

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

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

  1. 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.
  2. Selected papers/research directions of current interest, some covered by outside researchers.
The textbook is:
  1. Distributed Algorithm by Nancy A. Lynch,
    Morgan Kaufmann Publishers Inc., 1996
  2. The lectures will include material that is not in the textbook, therefore students are encourages to attend practically every class. Course work will entail reading material from the book. Pop quizzes may be employed to encourage reading. 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 (Lecture 4)
    •     Knowledge and Common Knowledge (Lecture 5)
    •     Consensus and Byzantine Agreements (Lecture 6-7)
    •     A Model for Asynchronous Systems (Lecture 8)
    •     Mutual Exclusion Algorithms (Lecture 9-10)
    •     Atomic Registers (Lecture 11)
    •     Asynchronous Network Models (Lecture 12)
    •     Data-Link Protocols (Lecture 13)
    •     Security Protocols (Lecture 14)


    Lecture Notes