How do you know that your program is efficient? What is efficiency in the first place? First, we need to choose a complexity metric and agree that the metric is relevant. Second, we need to show that the program performs "well", having this metric in mind. Ideally, we would like to show that no program can solve the given problem with a better complexity. How to do it? We need to establish a tight lower bound, i.e. (1) find a complexity level that no program can beat, and (2) show that our program exhibits precisely this complexity.
In this lecture, we discuss popular techniques designed for establishing (tight) lower bounds in distributed computing. Models for distributed systems come in many flavors: processes may communicate through shared memory or by message passing, they may be synchronous or asynchronous, prone to failures or not, and so on. Different models require different lower bound results. Nevertheless, many of these results rely on common techniques, having to do with information transfer and the difficulty of dealing with indistinguishable scenarios. This lecture will explore and explain some of these techniques, together with their applications.
Presentation Slides and exercises