Contents

Introduction

1. This Website

Distributed Systems: Basics

1. Distributed Systems are Everywhere: Short Video
2. A Model of Distributed Systems
   1. A model of distributed systems video
   2. Examples
   3. Code Examples
      1. Example: SumPosAndNeg.py
      2. Example Engine for Elementary Simulator: Engine.py
      3. Example Passing Tokens: PassingTokens.py
      4. Example Greatest Common Divisor: gcd.py
      5. Example Distributed Greatest Common Divisor: gcd_distributed.py
      6. Example: For later chapter -- Global Snapshots: GlobalSnapshots.py
   4. FAQ
   5. More about Limitations of the Model
   6. Video about Message Delivery on Different Channels
   7. Review
3. Data flow in Computations
   1. States: Examples
   2. Dataflow and Computations: Examples
   3. Distributed Systems Introduction: Video
   4. Timelines, Dataflow, and States: Video
   5. States: FAQ
   6. Dataflow and Computations: FAQ
   7. Computations: More Examples
   8. A video of a computation: sequence of states
   9. States: Review
   10. Dataflow and Computations: Review
4. Cuts of Dataflow Graphs
   1. Consistent Cuts and Computations: Examples
   2. Cuts of Dataflow Graphs: Review

Snapshots and Clocks

1. Global snapshots
   1. Snapshots Video
   2. Video on States Before and After Snapshots
   3. Examples and Details
   4. FAQ
   5. Review
2. Applications of Global Snapshots
3. Logical Clocks
4. Video on Logical Clocks
5. Video on Vector Clocks
6. Global Snapshots with Logical Clocks
7. Global Snapshots with Logical Clocks Video
8. Detecting Termination
9. Video on Detecting Termination
10. Detecting Database Deadlock
11. Detecting Database Deadlock Video

Agent knowledge

1. What Agents Know

Diffusing and Gossip computations

1. The Dijkstra-Scholten diffusing computation algorithm
2. Diagrams showing Diffusing Computation
3. Applications of Diffusing Computation
4. Combining Algorithms: How an Agent determines a Global Snapshot.
5. Diffusing Computation: A Small Self Test

Consensus Algorithms

1. Impossibility of asynchronous consensus with faulty agents
2. Serializable transactions in faulty systems.
3. The Paxos algorithm
4. Paxos Self Test
5. The Raft algorithm: Not done

Byzantine faults

Algorithms dealing with Byzantine faults

1. Byzantine algorithms with written messages
2. Byzantine algorithms with written messages Video
3. Byzantine algorithms with oral messages

Cryptocurrency

1. Introduction to cryptographic hash functions.
2. Introduction to cryptographic hash functions - Presentation.
3. BitCoin algorithm
4. Etherium algorithm

Proofs of Correctness of Sequential Programs

1. Basics: Introduction
2. Nondeterministic iteration
3. Predicates
4. Hoare triples
5. States & Invariant
6. Proving termination.
7. Examples: correctness.
   1. Sorting
   2. Shortest paths in a graph
   3. Distributed averaging
   4. Agents forming patterns in flight
   5. Earliest meeting time of concurrent agents

Distributed Collaboration

1. Mutual Exclusion: Distributed Dining philosophers
2. Mutual Exclusion: Distributed Dining philosophers Slides
3. Distributed Resource Management: Drinking philosophers
4. Distributed Resource Management: Drinking philosophers Slides
5. Rendezvous in Distributed Systems: Committee Coordination

Self stabilization

1. Self stabilization of a token ring

Clock synchronization

1. Network and Precision Time Protocols
2. Clock synchronization in distributed systems

Cloud-computing algorithms

1. Map-reduce
2. Millwheel

Stream algorithms

1. Finding repeated elements in streams: Misra & Gries
2. Finding repeated elements in streams: Approximate algorithms

Distributed data structures

1. Distributed tables: hashing
2. Distributed data: BigTable

Continuous distributed systems

1. Asynchronous averaging

Temporal Logic Applications

1. State transition systems. Safety. Always, Next operators.
2. Progress. Eventually. Leads-To
3. More about Leads-To
4. Examples with Leads-To and Eventually

---

K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology