Room 326

Coordination with imperfect information

Dietmar Berwanger

ENS-Cachan, France

Much of what computers do depends on what other computers do. The task of coordinating processes so that each one does its part towards achieving a
global objective poses intriguing theoretical problems. In this lecture, we
focus on the question of how to overcome the uncertainty about global conditions of action based on local, imperfect information.

In the first part, we illustrate the connection between action and knowledge using examples from distributed systems and set the stage for a
formal analysis.

In the second part, we study the complexity of designing action protocols. We use the simple, but quintessential, problem of achieving consensus without communication to show various lower bounds, mostly undecidability results.

Finally, in the third part, we present synthesis procedures for different classes of hierarchical systems.