Computer Science 612
Syllabus

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 6 weeks is outlined below.

  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 Asysnchronous and Synchronous Models. Uniform Algorithms. Randomized Algorithms and Impossibility Results. (Weeks 2 - 3) [Chapters 3, 14.1]

  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. Randomized Algorithms. (Weeks 4 - 5) [Chapters 4, 14.2]

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


    Back to CS612 homepage