Algorithms for Distributed Systems
326.623, WS 1998/99, T811 (Start: October 5)
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.
- 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
- 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.
- Nancy A. Lynch
Distributed Algorithms, Morgan Kaufmann, San Francisco,
- Randy Chow and Theodore Johnson
Distributed Operating Systems and Algorithms, Addison Wesley, Reading,
- 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 1 and 2
- Formalize the distributed termination detection algorithm described by
Dijkstra as an I/O automaton.
- Implement the termination algorithm in DAJ (Sample
Exercises 3 and 4
- Formalize the LayeredBFS algorithm described by
Lynch as an I/O automaton.
- Implement the LayeredBFS algorithm in DAJ (Sample
Projects A and B
- Investigate and present Maekawa's voting algorithm for mutual exclusion.
- Investigate and present the invitation algorithm for leader election
Maintained by: Wolfgang Schreiner
Last Modification: March 1, 1999