Courses:

Distributed Algorithms >> Content Detail



Calendar / Schedule



Calendar

LEC #TOPICSKEY DATES
1Course Overview

Synchronous Networks

Leader Election in Synchronous Ring Networks
2Basic Computational Tasks in Synchronous Networks: Leader Election

Breadth-first Search

Shortest Paths

Broadcast and Convergecast
3Breadth-first Search (cont.)

Shortest Paths (cont.)

Broadcast and Convergecast (cont.)

Spanning Trees

Minimum Spanning Trees
4Fault-tolerant Consensus

Link Failures: The Two Generals Problem

Process Failures (Stopping, Byzantine)

Algorithms for Agreement with Stopping Failures
5Exponential Information Gathering

Algorithms for Agreement with Byzantine Failures
Homework assignment 1 due
6Number-of-processes Lower Bounds for Byzantine Agreement

Weak Byzantine Agreement

Time Bounds for Consensus Problems
7Other Kinds of Consensus Problems: $k$-agreement

Approximate Agreement

Distributed Commit
8Asynchronous Distributed Computing

Formal Modeling of Asynchronous Systems using I/O Automata
9Proof Methods

Non-fault-tolerant Algorithms for Asynchronous Networks

Leader Election, Breadth-first Search, Shortest Paths, Broadcast and Convergecast
Homework assignment 2 due
10Non-fault-tolerant Algorithms for Asynchronous Networks (cont.)

Leader Election, Breadth-first Search, Shortest Paths, Broadcast and Convergecast (cont.)
11Spanning Trees

Gallager et al. Minimum Spanning Tree Algorithm
12SynchronizersHomework assignment 3 due
13Synchronizer Applications

Time, Clocks, and the Ordering of Events

Vector Timestamps
14State-machine Simulation

Synchronous vs. Asynchronous Distributed Systems

Stable Property Detection

Distributed Termination

Global Snapshots

Deadlock Detection

Asynchronous Shared-memory Systems
15Mutual Exclusion

Mutual Exclusion Algorithms
16Mutual Exclusion Algorithms (cont.)Homework assignment 4 due
17Bounds on Shared-memory for Mutual Exclusion
18Impossibility of Consensus in Asynchronous, Fault-prone, Shared-memory Systems
19Atomic Objects

Atomic Snapshot Algorithms
20Atomic Read/Write Register Algorithms

Wait-free Computability

The Wait-free Consensus Hierarchy
Homework assignment 5 due
21The Wait-free Consensus Hierarchy (cont.)
22Wait-free vs. $f$-fault-tolerant Atomic Objects
23Asynchronous Network Model vs. Asynchronous Shared-memory Model

Impossibility of Consensus in Asynchronous Networks

Failure Detectors and Consensus
Homework assignment 6 due
24Paxos Consensus Algorithm

Reliable Communication using Unreliable Channels
25Reliable Communication using Unreliable Channels (cont.)

Self-stabilizing Algorithms
26Atomic Memory Algorithms for Dynamic Networks

Rambo
Homework assignment 7 due

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.