Algorithms for Distributed Systems

RISC-Linz logo

Wolfgang Schreiner

326.623, SS 2000 (Start: March 6)
Monday 8:30-10:00, T811

The goal of this course is to teach students of computer science and mathematics fundamental distributed algorithms, i.e., algorithms for systems with concurrently executing components.

Distributed algorithms arise in many areas including network applications, telecommunication, distributed information processing, scientific computing, and real-time process control. Typical problems that are considered are communication and synchronization, consensus, deadlock detection, global snapshots, implementation of various kinds of distributed objects. This is particularly challenging in the absence of global clocks and faulty behaviors where many apparently innocent problems turn out to become diffult or even theoretically impossible to solve.

Students are expected to study some algorithms on their own, to implement them in Java using the DAJ system (available in public domain), and to present them in class.

Contents

Network Models
Synchronous and asynchronous networks, failure models.
Basic Algorithms
Leader election, spanning tree construction, search, shortest path, minimum spanning tree.
Distributed Consensus
Link failures, process failures, k agreement, impossibility results, randomized algorithms.
Logical Time
Basics, termination detection, consistent global snapshots.
Resource Allocation
Mutual exclusion, general resource allocation.
Group Communication
Reliable, ordered, causal multicast, group membership, virtual synchrony.
Database Techniques
Two-phase commit, three-phase commit, checkpointing and recovery.

Literature

Nancy A. Lynch
Distributed Algorithms, Morgan Kaufmann, San Francisco, California, 1996.
Randy Chow and Theodore Johnson
Distributed Operating Systems and Algorithms, Addison Wesley, Reading, MA, 1997.
Pankaj Jalote
Fault Tolerance in Distributed Systems, Prentice Hall, Englewood Cliffs, New Jersey, 1994.
Kenneth P. Birman
Building Secure and Reliable Network Applications, Manning, Greenwich, Conneticut, 1996.

Student Projects

LyHudak Mutual Exclusion
Mutual exclusion by a token with path compression.
RicartAgrawala Mutual Exclusion
Mutual exclusion by use of logical time to synchronize access to critical region.
Dijkstra Scholten Termination Detection
Termination detection by maintaining a tree of active processes.

Maintainer: Wolfgang Schreiner
Last Modification: July 19, 2000

[Up] [RISC-Linz] [University] [Search]