Lecture Summary
ECE 428/CS 425/CSE 424 Distributed Systems, Fall 2005
 Chapter/section numbers below refer to that from 4th edition of the textbook, unless otherwise specified -- if you are using third edition of the textbook, you can identify relevant chapters by comparing the tables of contents for the two editions, which can be accessed from the textbook web links provided on homepage for this course. Readings listed below in the entry for a lecture may actually correspond to multiple lectures in the vicinity of that lecture. Not all topics listed for reading may be covered in class. Some readings may be assigned ahead of the corresponding lectures.

  1. 8/25/05 (lecture by Prof. Yih-Chun Hu): Course handout distributed. Introduction to the course. (slides)
    Reading: Chapter 1

  2. 8/30/05: Programming assignment 0. Clock synchronization. Synchronization in synchronous systems. Uncertainty (u) in message delay. For n processes, optimum bound on clock skew is u(1 - 1/n). Proof that, for 2 processes, the optimum bound on skew is u/2. Cristian's algorithm. (slides)
    Reading: Sections 11.1 through 11.5 from chapter 11 (4th edition) on Time and Global States (or Sections 10.1 through 10.5 from 3rd edition)

  3. 9/1/05: Berkely algorithm. NTP. Logical clocks. Happened before relation. Lamport clock. Vector clocks. (slides)
    Reading: Sections 11.1 through 11.5 from chapter 11 (4th edition) on Time and Global States (or Sections 10.1 throug h 10.5 from 3rd edition)

  4. 9/6/05: Global states. Consistent and inconcistent cuts. Chandy and Lamport's "snapshot" algorithm (slides)

  5. 9/8/05: Consensus in distributed systems
    Reading: Section 12.5 of 4th edition (or Section 11.5 from 3rd edition). Sections 1, 2 and 3 of the paper Impossibility of Distributed Consensus with One Faulty Process, Fischer, Lynch and Paterson, Journal of the ACM, April 1985.

  6. 9/13/05: Consensus in distributed systems. Algorithm OM(m) for Byzantine agreement with m failures. Proof of FLP result for asynchronous systems. (slides)
    Reading: OM(m) algorithm from Section 3 of the paper The Byzantine Generals Problem by Lamport, Shostak, Pease, in ACM Transactions on Programming Languages and Systems, 1982.

  7. 9/15/05: Consensus in distributed systems. Proof of FLP result for asynchronous systems. Consensus in synchronous systems with up to f crash-stop failures. Mutual exclusion. (slide set 1 slide set 2)
    Reading: Section 11.2 on Mutual Exclusion from 4th edition (or 10.2 of 3rd edition)

  8. 9/20/05: Mutual exclusion. (slides)
    Reading: Section 12.2 on Mutual Exclusion from 4th edition (or 11.2 of 3rd edition)

  9. 9/22/05: Multicast. (slides)
    Reading: Section 12.4 on Multicast from 4th edition (or 11.4 of 3rd edition)

  10. 9/27/05: Elections. (slides)
    Readings: Section 12.3 on Elections from 4th edition (or 11.3 of 3rd edition)

  11. 9/29/05: Elections (Bully algorthm). Determining maximum recoverable state with independent checkpointing and message logging.
    Readings: Sections 1.1, 1.2, and 2.1 (you can omit the proofs) of Distributed System Fault Tolerance Using Message Logging and Checkpointing, David Johnson, Ph.D. thesis, Rice University, December 1989.

  12. 10/4/05: State interval index, dependency vector, system state, optimistic and pessimistic message logging, checkpointing, rollbak recovery, consistent state, determining maximum recoverable state.
    Failure detector. (slides)
    Readings: See readings in previous lecture (from Johnson's thesis)
    Sections 2.3.2,
    Section 11.1 (4th edition) or 10.1 (3rd edition).

  13. 10/6/05: Networking. (slide set 1, slide set 2)
    Readings: Sections 3.1 through 3.4 from Chapter 3 (Networking and Internetworking)

  14. 10/11/05: Peer-to-peer systems. (slide set 1, slide set 2)
    Readings:
    Gnutella Protocol Specification,
    SIGCOMM paper on Chord (Sections 1 through 4: You may omit the proofs)

  15. 10/13/05: Peer-to-peer systems (Chord). Dynamic source routing in ad hoc networks.
  16. 10/18/05 (Prof. Yih-Chun Hu): Security
    Readings: Chapter 7 (Security). Lecture notes (PDF file) br>
  17. 10/20/05: Mid-term test (in class)

  18. 10/25/05 (Prof. Yih-Chun Hu): Security
    Readings: Chapter 7 (Security)
  19. 10/27/05: Dynamic source routing (DSR) in ad hoc networks. Weak duplicate address detection (weak DAD) in ad hoc networks. Transactions.
    Slides for DSR (see relevant slides describing DSR protocol), slides for weak DAD slides for transactions
    Readings:
    • relevant paper on DSR to be provided here
    • Weak Duplicate Address Detection in Mobile Ad Hoc Networks, N. H. Vaidya, ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), June 2002.
    • Sections 13.1 through 13.3 of 4th edition - from chapter on Transactions (Sections 12.1 through 12.3 of 3rd edition)

  20. 11/1/05: Transactions. Concurrency control (slides set 1, set 2)
    Readings: Sections 13.4-13.7 of 4th edition (or 12.4-12.7 of 3rd edition)
    Chapter 14 of 4th edition (or chapter 13 of 3rd edition)

  21. 11/3/05: Concurrency control.

  22. 11/8/05 (Charles Yang): RPCs and Distributed Objects (slides)

  23. 11/10/05: Concurrency control.

  24. 11/15/05: Distributed transactions (slides).
    Readings: Chapter 14 of 4th edition (or chapter 13 of 3rd edition)
  25. 11/17/05: Replication control (slide set 1).
    Readings: Sections 15.1-15.3 of 4th edition (or sections 14.1-14.3 of 3rd edition)
  26. 11/29/05 (Prof. Indranil Gupta): Replication control (slide set 2)
    Readings: Chapter 15.4 of 4th edition (or chapter 14.4 of 3rd edition)

  27. 12/1/05 (Prof. Yih-Chun Hu): Distributed file systems (slides)
    Readings: Chapter 8 on Distributed File Systems

  28. 12/6/05: Distributed shared memory (slides)
    Readings: Chapter 18 on Distributed Shared Memory from 4th edition (or chapter 16 from 3rd edition), and the slides above

  29. 12/8/05 (last lecture for the course): Transactions and replication (slides)
    Readings: Chapter 15.5 of 4th edition (or chapter 14.5 of 3rd edition) -- only Quorum Consensus Methods (section 15.5.5 from 4th edition, and section 14.5.5 from 3rd edition) required for the final exam.
Return to the home page for ECE 428