2.9.1 The Celebrity Problem

In this section, we will work with the model of the so-called celebrity problem.

We are using a new model instead of the traffic light because it provides us with some proofs where manual interaction is necessary.

In the setting for this problem, we have a “knows” relation between persons. This relation is defined so that

• no one knows himself,

• the celebrity knows nobody,

• everybody knows the celebrity.

The problem’s goal is to find the celebrity. We want to model an algorithm that fulfills this task.