An Introductory Course on Distributed Algorithms

This material is for use in an introductory course on distributed algorithms. The course emphasizes the coupled development of algorithms with proofs of correctness. The course uses temporal logic to develop and prove algorithms; however, the focus of course is algorithms and not logic. The course helps students understand the fundamental algorithmic concepts that underly distributed systems, but the course is not, in itself, a distributed systems course. The course material includes examples of algorithms implemented in Python. The programs are annotated thoroughly and so students don't need to know Python to understand the programs.

The course is typically taken by upper class undergraduates and beginning graduate students. Students should know the basics of graph theory and Boolean algebra before taking this course. This material is based on courses taught at the University of Texas at Austin by Jayadev Misra and Mani Chandy, and at the California Institute of Technology by Richard Murray and Mani Chandy.

The ideas underlying the course are from UNITY which is described in Parallel Program Design: A Foundation. The course uses Computation Tree Logic and Linear Temporal Logic.

The material is organized into chapters. Each chapter consists of two to five main modules with additional supporting modules containing videos, diagrams, detailed examples, assignments, and explorations of related topics. Students should look at exploratory modules based on their interests. A module can be read in under fifteen minutes. Main modules have self tests with solutions.The modules do not have to be read sequentially, though the modules dealing with the fundamentals should be read first.

Chapters

Why study distributed algorithms?

Temporal logic concepts used in this course.

Properties and composition of temporal operators.

State transition systems and predicates on states.

Proof patterns and examples of coupled development of algorithms with

proofs.

Message passing, channels, and time-line diagrams

Diffusing computations.

Global snapshots and logical time.

Termination and deadlock detection.

Global consensus and the Paxos algorithm.

Self stabilization.

Overcoming failures. Byzantine algorithms.

Managing resources shared by multiple agents.

Distributed ledgers and blockchain.

Knowledge: What does an agent know? How does it learn?

Contracts: Rely/guarantee contracts between an agent and its

environment.

Discrete and continuous state spaces.

Summary