Nervennahrung

Distributed Algorithms

31.08.2011

This winter semester I will hold a seminar on Distributed Algorithms. This course is intended for master students who are interested in understanding the theoretical background of distributed algorithms and who want to learn practically relevant distributed algorithms. This seminar addresses algorithms, which run on distributed processes or different computers connected via a network. Examples of such algorithms include leader election, general resource allocation, consensus strategies, synchronization and data access algorithms and many more. With the ubiquity of distributed computers, multi core systems and networked devices a basic knowledge of distributed algorithms and of the underlying fundamental design- and correctness principles becomes more relevant even for the non-specialist.

Despite the heterogeneity found in distributed networks, the theoretical study of algorithms in this area has revealed a core set of fundamental principles both for the design and modelling as well as for proving correctness. Examples for these design principles include

  • consensus (agreement among independent processes)
  • electing a leader (i.e.\ selecting a distinguished process and breaking possibly symmetry)
  • produce synchronicity
  • select a consistent global view (global snapshot) etc.

In this seminar you will not only learn concrete algorithms but also these underlying unifying principles.

Although the algorithms are often compact, elegant and not very long, reasoning about them is difficult because of the uncertainty introduced by concurrency and asynchronicity. To deal with these challenges, researchers and practitioners have classified systems into

  1. Synchronous network model,
  2. Asynchronous shared memory model, and the
  3. Asynchronous network model

We will cover them all and provide you with tools for reasoning about such systems. The prime, unifying model we will use to model distributed systems are input/output automatons (state machines).

Examples for proof strategies covered include

  1. invariant assertions, and
  2. simulations.

For more info, download the course description which includes references (literature) as well as hints for the logistics.

(Dieses Posting ist auf Englisch, da unser HIS Master komplett auf Englisch ist.)