A parallel wakeup problem and multi-room light switch strategies
For researchers in distributed computing and combinatorial puzzles, this work provides exact bounds and characterizations for a variant of the wakeup problem.
This paper resolves open questions about the minimum number of switch states needed for prisoners to solve a multi-room light switch problem, and characterizes when a symmetric wakeup solution exists for given numbers of processors and registers.
The wakeup problem in distributed computing asks for a symmetric protocol that enables one of several processors to eventually guarantee that all (or, in a more general setting, enough) other processors have acted, using a shared register but no global clock. Dropping the symmetry requirement gives a well-known exercise often phrased in terms of prisoners entering, in an unknown sequence, a room equipped with a single binary switch, and using it to communicate. Kane and Kominers recently analysed a more general version of the latter with multiple parallel and indistinguishable rooms. We answer some open questions of Kane and Kominers regarding the minimum number of switch states needed for the prisoners to solve the problem. We also consider the symmetric ``wakeup'' version of this scenario, and establish exactly for which numbers of processors and registers a solution is possible.