CSC 2221 -  Introduction to Distributed Computing

                 TENTATIVE SYLLABUS
       
1. SYNCHRONOUS MESSAGE-PASSING SYSTEMS (WITH FAILURES)

   * Synchronous round model of computation
   * Models of process and link failures
   * The Coordinated Attack (CA) problem
   * Impossibility of CA in systems with link failures
   * Atomic Commit problem; 2-phase commit algorithm
   * Terminating Reliable Broadcast (TRB)
   * Simple TRB algorithm; early-stopping TRB algorithm
   * The Non-Blocking Atomic Commit problem and its relation to TRB 
   * The Consensus problem
   * Time complexity of Consensus
   * Consensus in systems with arbitrary (aka Byzantine) failures
     (with and without message authentication)

2. ASYNCHRONOUS MESSAGE-PASSING SYSTEMS

   NO FAILURES

   * Partial order of events, causality
   * Logical clocks, vector clocks
   * Chandy-Lamport snapshot algorithm

   FAILURES

   * Fault-tolerant broadcast primitives: Reliable, FIFO, Causal and Atomic Broadcast
   * Consensus + Reliable Broadcast = Atomic Broadcast
   * Impossibility of Consensus (Fischer, Lynch and Paterson theorem)
   * Using Randomization to solve Consensus (Ben-Or's algorithm)
   * Using Failure Detectors (FDs) to solve Consensus
     (Chandra-Toueg and Mostefaoui-Raynal algorithms)
   * Implementation of FDs in partially synchronous models
   * Weakest FD to solve Consensus
   * Paxos algorithm for Consensus
   * The State Machine Approach: using Consensus to implement a fault-tolerant server

4. SHARED MEMORY DISTRIBUTED COMPUTING

   NO FAILURES

   * Mutual exclusion with atomic registers
     - Dijkstra's algorithm
   * Mutual exclusion with safe registers
     - Lamport's bakery algorithm
     - Burns-Lamport one-bit algorithm

   FAILURES

   * Semantics of registers, simple register constructions
   * Translations between shared-memory and message-passing models
     - Using registers to simulate message-passing
     - Using message-passing to simulate registers
   * Higher-level shared objects
     - Linearisability
     - Wait freedom
   * Herlihy's universal construction
   * The Consensus hierarchy