Some lectures, presentations, notes etc…

Lectures on Distributed Computing

Slides from a short series of lectures on Distributed Computing (given at Bergen):

1. Introduction  (pdf)

The Zoo of distributed computing  where you’ll find many kind of creatures – regular or strange, benign or dangerous, dumb or rational and cunning, healthy or weak, quick or slow, boring or interesting. Centralised vs Distributed – Message passing (flooding etc) with a hint of Shared memory and PRAM etc.

2. Trees and formal message passing  model (pdf)

Flooding, spanning trees and formal description of message passing models with timing (synchronous, asynchronous).

3. Leader Election and distributed complexity (pdf)

3a. Leader election was the problem that started distributed algorithms – here, we have some fun with it starting from the ring topology to the complete topology etc…

3b. And here we explore a bit of distributed complexity via the concept of proof labelling schemes.

4. Failure and Compact Self-Healing Routing (pdf)

Distributed computing is one paradigm where work can go on despite failures of components and communication. Here, we discuss self-healing, a fault-tolerance concept for reconfigurable (peer-to-peer) systems and discuss our algorithms for compact self-healing routing.