Fundamentals of Distributed Algorithms – Part 2

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.