Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Fundamentals of Distributed Algorithms - Part 1

Speaker  Marcos K. Aguilera

Affiliation  MSR-SV

Host  Chris Gould-Sandhu

Duration  01:50:39

Date recorded  3 June 2012

In this lecture, we cover the fundamentals of distributed message-passing algorithms with an emphasis on their correctness. In the first part of the lecture, we cover algorithms for synchronous systems, including algorithms for consensus, terminating reliable broadcast, and interactive consistency. We also cover some lower bounds results on how fast these algorithms can be. In the second part of the lecture, we move to more complex algorithms for asynchronous systems. We show the Fischer-Lynch-Patterson result, which states that consensus cannot be solved under failures in such systems. We then cover two classes of algorithms that can circumvent the impossibility: randomized algorithms and failure-detector-based algorithms. Finally, we move into algorithms for partially synchronous models and explain their relation to failure detectors.

©2012 Microsoft Corporation. All rights reserved.
> Fundamentals of Distributed Algorithms - Part 1