Computer Science 612

Note. The approximate schedule for each topic is listed in parentheses. The actual schedule may be somewhat different. Also listed are the chapters in the text that refer to the material being covered. Note that not all the material covered in class will be found in the text. Supplemental reading assignments will be given for such material.

The material covered in the first 10 weeks is outlined below. Special topics will be covered in the last five weeks, including blockchains and distributed ledgers.

  1. Introduction. Model and Basic Algorithms for Message Passing Systems. (Week 1[Chapters 1 - 2]


  2. Leader Election in Rings. Algorithms and Lower Bounds in the Asynchronous and Synchronous Models. Uniform Algorithms. (Weeks 2 - 3[Chapter 3]


  3. Mutual Exclusion in the Shared Memory Model. Asynchronous Algorithms using Read-Write and More Powerful Primitives. Bounded and Unbounded Algorithms. Lower Bounds on the Number of Memory States and Registers.(Weeks 4 - 5[Chapter 4]


  4. Fault-Tolerant Consensus. Synchronous and Asynchronous Models. Shared Memory and Message Passing Models. Crash and Byzantine Failures. Algorithms, Lower Bounds and Impossibility Results. (Weeks 6 - 8[Chapter 5]


  5. Causality & Time. Clock Synchronization. Consistent Cuts.(Week 9[Chapter 6]


  6. Distributed Shared Memory. Linearizability and Sequential Consistency.(Week 10[Chapter 9]