DEPARTMENT OF COMPUTER SCIENCE
                  COURSE ANNOUNCEMENT

  Comp 290-062 Distributed and Concurrent Algorithms
     3.0 Credit Hours; meets TTh 12:30-1:45 SN 325

             Instructor: Dr. James Anderson

Purpose: The course will cover possibility and impossibility
results from the literature on distributed (message passing) and concurrent
(shared memory) algorithms.  We will also cover assertional techniques for
specifying and verifying such algorithms.  At the end of the course, students
will have a general knowledge of the distributed computing literature, and will
be able to formally reason about the correctness of concurrent and distributed
programs.

Prerequisites: Students enrolling in the course should have taken either
Comp 242 (Advanced Operating Systems) or Comp 243 (Distributed Systems).

Grading: Homework will be assigned approximately once every two weeks.
In addition, students will be required to investigate a research topic of their
choosing in some depth, and to write a research paper or survey paper on that
topic.  Depending on the size of the class, students may also be required to
present a talk on their research topic.  The talk, paper, homework, and class
participation each count equally in determining the final grade.

Probable List of Subjects: The following is a probable list of subjects
to be covered.  I am willing to make slight changes to this list based on the
interests of the class.  A list of papers for each topic will be made available
at the beginning of the semester.

  Reasoning about distributed and concurrent programs (4 weeks)
    Topics: states, actions, histories, state assertions, temporal
      assertions, safety properties, partial correctness, invariants, program
      annotations, liveness properties, total correctness, well-founded sets,
      fairness.
  Synchronization problems (4 weeks)
    Topics: mutual exclusion, readers/writers, dining philosophers,
      drinking philosophers, wait-free synchronization, performance issues.
  Deadlock/termination detection (2 weeks)
    Topics: deadlock detection, termination detection, diffusing
      computations, distributed snapshots.
  Fault tolerance (2 weeks):
    Topics: Byzantine agreement, asynchronous agreement,
      self-stabilizing systems.
  Decision algorithms (1 week):
    Topics: consensus, election.
  Miscellaneous (2 weeks):
    Topics: student presentations (if the class is small enough) or
      other topics of the class's choosing (if the class is not small enough).