Courses:

Distributed Algorithms >> Content Detail



Lecture Notes



Lecture Notes

This section contains documents created from scanned original files, which are inaccessible to screen reader software. A '#' symbol is used to denote such documents.

This section contains the instructor's notes that were used to structure the lectures from the Fall 2001 instance of this course. These notes are listed by the topics discussed in Fall 2001.


TOPICSNOTES
Course Overview

Synchronous Networks

Leader Election in Synchronous Ring Networks
(PDF - 1.1 MB)#
Basic Computational Tasks in General Synchronous Networks: Leader Election

Breadth-First Search

Shortest Paths, Broadcast and Convergecast
(PDF - 1.0 MB)#
Spanning Trees

Minimum Spanning Trees
(PDF - 1.2 MB)#
Fault-Tolerant Consensus Problems

Link Failures: The Two Generals Problem

Process Failures (Stopping, Byzantine)

Algorithms for Agreement with Stopping and Byzantine Failures

Exponential Information Gathering
(PDF)#
Number-Of-Processor Bounds for Byzantine Agreement

Weak Byzantine Agreement

Time Bounds for Consensus Problems
(PDF - 1.2 MB)#
Other Kinds of Consensus Problems: $k$-Agreement

Approximate Agreement

Distributed Commit
(PDF)#
Asynchronous Distributed Computing

Formal Modeling of Asynchronous Systems Using Interacting State Machines (I/O Automata)

Proof Methods
(PDF - 1.1 MB)#
Asynchronous Message-Passing Systems

Modeling Asynchronous Message-Passing Systems

Basic Computational Tasks in Asynchronous Networks

Leader Election

Breadth-First Search, Shortest Paths, Broadcast and Convergecast
(PDF - 1.2 MB)#
Spanning Trees in Asynchronous Networks

Minimum Spanning Trees
(PDF - 1.2 MB)#
Synchronizers

Synchronizer Applications

Synchronous vs. Asynchronous Distributed Systems
(PDF - 1.1 MB)#
Asynchronous Shared-Memory Systems

Modeling

The Mutual Exclusion Problem

Mutual Exclusion Algorithms
(PDF - 1.3 MB)#
More Mutual Exclusion Algorithms(PDF - 1.1 MB)#
Bounds on Shared Memory for Mutual Exclusion

Resource Allocation

The Dining Philosophers Problem
(PDF - 1.3 MB)#
Impossibility of Consensus in Asynchronous Shared Memory Systems(PDF - 1.3 MB)#
Atomic Objects
Atomic Snapshot Algorithms

Atomic Read/Write Register Algorithms
(PDF - 1.1 MB)#
Translations Between Asynchronous Network Model and Asynchronous Shared Memory Model

Impossibility of Consensus in Asynchronous Network Models

Failure Detectors

Consensus and Atomic Broadcast
(PDF - 1.0 MB)#
Time, Clocks, and the Ordering of Events

State-Machine Simulation

Applications
(PDF - 1.1 MB#)
Stable Property Detection

Distributed Termination

Global Snapshots

Deadlock Detection
(PDF)#
Reliable Communication Using Unreliable Channels(PDF - 1.2 MB)#
Timing-Based Systems

Modeling and Verification
(PDF - 1.3 MB)#
Timing-Based Systems (cont.)

Mutual Exclusion

Consensus
(PDF - 2.1 MB#)

 








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