Structural Information and Communication Complexity
One of the main issues addressed in Turing's work was about computability, namely, one of his Holy Grail's quests was to answer the question "What can be mechanically computed?" Since the definition of the Turing's machine and the statement of the Turing Church's thesis, a lot of great technological advances have modified our view of what is a "computing device" Among them, distributed systems sometimes cosmetically called "cloud computing" are among the most pervasive, and force us to think again to the computability power of such systems. This is becoming more and more important because, not only the world is distributed, but more and more applications are distributed. Hence, a fundamental question is the following one: What can be computed in a distributed system? The answer to this question depends on the environment in which evolves the considered distributed system, i.e. the assumptions the system relies on. This environment is very often left implicit and nearly always not formulated in terms of precise underlying requirements. In the extreme case where the environment is such that there is no synchrony assumption and the computing entities may commit failures, many problems become impossible to solve (in these cases, a network of Turing machines where some machines may crash, is less powerful than a single reliable Turing machine) Given a distributed computing problem, it is consequently important to know the weakest assumptions (lower bounds) that give the limits beyond which the considered distributed problem cannot be solved. This talk is a short introduction to this kind of issues. It first presents concepts and results related to distributed computability, and then briefly addresses distributed complexity issues, which are the two lenses that allows us to understand and master computing. The following table summarizes the main issues encountered in distributed computing seen from
Lecture Notes in Computer Science