Fundamentals of Distributed Algorithms – Part 1

Date

June 4, 2012

Speaker

Marcos K. Aguilera

Affiliation

MSR-SV

Overview

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.

Speakers

Marcos K. Aguilera

Marcos K. Aguilera is a senior researcher at Microsoft Research in Silicon Valley, which he joined in 2008. Prior to that, he was a researcher at HP Labs and Compaq Systems Research Center (SRC). Marcos obtained his PhD in computer science from Cornell University in 2000. His interests include practice of distributed systems and theory of distributed computing.

People

  • Portrait of Marcos K. Aguilera

    Marcos K. Aguilera

‚Äč