One Hundred Prisoners and a Lightbulb --- Logic and Computation

This is a case-study in knowledge representation. We analyze the `one hundred prisoners and a lightbulb' puzzle. In this puzzle it is relevant what the agents (prisoners) {\em know}, how their knowledge {\em changes} due to {\em observations}, and how they affect the state of the world by {\em changing facts}, i.e., by their actions. These actions depend on the history of previous actions and observations. Part of its interest is that all actions are {\em local}, i.e.\ not publicly observable, and part of the problem is therefore how to disseminate local results to other agents, and make them {\em global}. The various solutions to the puzzle are presented as protocols (iterated functions from agent's local states, and histories of actions, to actions). The computational aspect is about average runtime termination under conditions of random (`fair') scheduling.