A parallel wakeup problem and multi-room light switch strategies
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911697398136832 |
|---|---|
| author | Haslegrave, John Russell, Paul A. Walters, Mark |
| author_facet | Haslegrave, John Russell, Paul A. Walters, Mark |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19488 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A parallel wakeup problem and multi-room light switch strategies Haslegrave, John Russell, Paul A. Walters, Mark Distributed, Parallel, and Cluster Computing Discrete Mathematics Combinatorics 68W15, 68M14, 91A28 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. |
| title | A parallel wakeup problem and multi-room light switch strategies |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics Combinatorics 68W15, 68M14, 91A28 |
| url | https://arxiv.org/abs/2605.19488 |