2-13 March 2009
|
|
Bertinoro International Spring School 2009 2-13 March 2009 |
Distributed Algorithms
Prof. Roberto De Prisco
If you are attending the Bertinoro International Spring School 2009, in this page you will find useful material and information for the Distributed Algorithms course.
The exam for this class will be a take-home test. Students will have to choose 5 exercises among those proposed during the lectures (with the constraint that 2 be chosen in Part I, 2 in Part II and 1 in Part III). By April 19, 2009, students taking the exam, have to send via email (look up my email addres in my webpage) the solutions.
The material presented in the course is mostly based on the reference textbook
If you have the opportunity of bringing a copy of the book to Bertinoro, you will greatly benefit from it. I highly recommend to bring a copy of the book.
Slides for the class are now available in the following table. You should print out a copy and bring it with you at the school.
Last update (sildes - Part II): 04/03/2009
| Name | 2slides/page | 6slides/page |
|---|---|---|
| Introduction | ||
| Part I (Synchronous systems) | ||
| Part II (Asynchronous systems) | ||
| Part III (Shared memory systems) | ||
This course is an introductory course on distributed algorithms
for graduate students. The term "distributed algorithms" covers
a variety of algorithms which are designed to run on several processors
distributed over a large (or small) geographical area. Distributed
algorithms arise in a wide range of applications (e.g., telephone
systems, banking systems, airline reservation systems, nuclear
power plant control systems). Distributed algorithms can be
classified according to several attributes among which the most
important ones are: interprocess communication, synchronization and
failure model. In this course we will cover the basic timing models
(synchronous, asynchronous and partially synchronous) and mostly
concentrate on the message-passing interprocess communication model.
The failure models considered include stopping, omission and Byzantine
failures. We will use some basic distributed problems, such as leader
election and consensus, to provide a broad coverage of the various
distributed models. We will study several algorithms for the most
common distributed problems and some impossibility results.
Prerequisites: Algorithms and data structures, basic knowledge of graph, automata and probability theory.