Algorithms for Distributed Systems

326.623, WS 1998/99, T811 (Start: October 5)
http://www.risc.uni-linz.ac.at/courses/ws98/distalg
Wolfgang Schreiner <Wolfgang.Schreiner@risc.uni-linz.ac.at>

The goal of this course is to teach students of computer science and mathematics fundamental algorithms for the construction of distributed 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.

Exercises

Exercises 1 and 2

1. Formalize the distributed termination detection algorithm described by Dijkstra as an I/O automaton.
2. Implement the termination algorithm in DAJ (Sample Solution).

Exercises 3 and 4

1. Formalize the LayeredBFS algorithm described by Lynch as an I/O automaton.
2. Implement the LayeredBFS algorithm in DAJ (Sample Solution, Sample Solution).

Projects A and B

• Investigate and present Maekawa's voting algorithm for mutual exclusion. (Solution).
• Investigate and present the invitation algorithm for leader election (Solution).