Fundamentals of Distributed Algorithms – Part 1


June 4, 2012


Marcos K. Aguilera




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.


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.


  • Portrait of Marcos K. Aguilera

    Marcos K. Aguilera