One hundred prisoners will be kept apart and brought one at a time, in an order nobody can predict, into a room with a single light switch. Can they agree on a plan that lets one of them say, with certainty, that every prisoner has been in the room? This page builds a counting protocol that never declares too early, shows that it finishes as long as every prisoner keeps coming back, and explains what goes wrong when the switch might start in the on position.
Key terms
Light switch puzzle
Definition The light switch puzzle, in the version solved on this page, has the following rules. A group of 100 prisoners meets once to agree on a plan, and after that they are kept apart and cannot communicate. A warden then brings prisoners into a room one at a time, in any order the warden likes, and any prisoner may be brought many times. The room has a single switch with two positions, on and off, and everyone knows that it starts off. During a visit the prisoner may look at the switch and either leave it as it is or change its position. Nothing else in the room can be marked or moved, nobody sees who else comes, and nobody is told the order of visits. During any visit, the prisoner in the room may declare that all 100 prisoners have been in the room. A true declaration wins for the whole group and a false one loses for everyone, so a plan may declare only when it is certain. The order of visits is assumed to be fair, which here means that every prisoner is brought to the room again and again without end. The puzzle asks for a plan whose declaration is never false and is sure to come eventually. The resolution is a counting protocol with one counter. Each of the other 99 prisoners turns the switch on exactly once, at a visit where they find it off, and the counter turns it off and adds one to a count at every visit where they find it on, declaring when the count reaches 99. This plan never declares falsely, whatever the order of visits, and under the fairness assumption it declares after finitely many visits, although no fixed number of visits is enough for every fair order.
In plain words The switch can hold one message at a time, “a new prisoner was here”. Each prisoner other than the counter sends that message once, and the counter collects the messages one by one until there are 99 of them.
Example Take four prisoners, with A, B and C as signalers and D as the counter, so D declares at a count of 3. Suppose the visits run A, B, D, A, B, D, C, D.
| Visit | Visitor | Switch found | Action | Switch left | Count | Signals used |
|---|---|---|---|---|---|---|
| 1 | A | off | turns it on and uses the signal | on | 0 | 1 |
| 2 | B | on | waits | on | 0 | 1 |
| 3 | D | on | adds 1 and turns it off | off | 1 | 1 |
| 4 | A | off | nothing, signal already used | off | 1 | 1 |
| 5 | B | off | turns it on and uses the signal | on | 1 | 2 |
| 6 | D | on | adds 1 and turns it off | off | 2 | 2 |
| 7 | C | off | turns it on and uses the signal | on | 2 | 3 |
| 8 | D | on | adds 1, reaches 3 and declares | off | 3 | 3 |
The declaration at visit 8 is true, since A, B and C have all been in the room. At visit 2 the switch already held A’s signal, and B had to wait because one switch cannot hold two signals at once.
Counting protocol
Definition A counting protocol lets one agent count how many different agents have taken part, through a shared signal that the agents can set and clear. In the light switch puzzle it has two rules, with one prisoner chosen in advance as the counter.
- A prisoner other than the counter who finds the switch off and has not yet signaled turns it on and from then on has signaled. In every other case such a prisoner leaves the switch alone. That covers finding it on, which means waiting for a later visit, and every visit after signaling.
- The counter keeps a private count that starts at 0. On finding the switch on, the counter adds 1 and turns it off, and on finding it off, the counter changes nothing. When the count reaches 99, the counter declares.
Let be 1 when the switch is on and 0 when it is off, and let be the number of prisoners who have signaled. At every moment
This holds at the start, when all three numbers are 0 because the switch is known to be off. A signal raises and by 1, a counted signal raises the count by 1 and lowers by 1, and no other action changes any of them. Since is never negative, the count is never more than . So a count of 99 means that all 99 other prisoners have signaled, which each of them could only do in the room, and the counter is in the room when declaring, so the declaration is true.
In plain words Each signal is made once, waits on the switch until the counter collects it, and is then gone. Nothing else makes a signal, so the count can never run ahead of the number of different prisoners who have visited.
Example In the table above, after visit 5 the switch is on, the count is 1 and two prisoners have signaled, and indeed . After visit 6 the switch is off, the count is 2 and still two prisoners have signaled, and . Repeated visits, such as A’s return at visit 4, change none of the three numbers.
Distributed algorithm
Definition A distributed algorithm is a method carried out by several separate agents, each following its own rules with only its own memory and what it can observe directly, and with no central controller. The agents interact only through a shared medium, here one switch that is either on or off, and the order in which they act is set by something outside their control, here the warden. Its correctness has two parts. Safety says that nothing bad ever happens, here that no declaration is false, and it has to hold for every possible order of actions. Liveness says that something good eventually happens, here that a declaration comes, and it usually needs an assumption about the order, such as fairness.
In plain words Each prisoner sees only the switch and remembers only their own actions, so the plan has to work without anyone knowing what the others did or who comes next. Never being wrong and eventually finishing are separate promises, and each needs its own argument.
Example A rule that sounds reasonable can break safety. Suppose each prisoner other than the counter turned the switch on every time they found it off, with no limit of one signal. Then the order A, D, A, D, and so on, with these two prisoners taking turns for 198 visits, pushes the count to 99 although only A and the counter have been in the room, and the declaration is false. The limit of one signal per prisoner is what makes each counted signal stand for a different person, and safety has to be checked against unhelpful orders like this one.
Fairness assumption
Definition A fairness assumption is a condition on the order in which the agents of a distributed algorithm act, made so that the algorithm is sure to make progress. In the light switch puzzle it says that every prisoner is brought to the room infinitely often, meaning that after any visit each prisoner will be brought again at some later visit. It says nothing about how long that takes. Under this assumption the counting protocol declares after finitely many visits. A signal waiting on the switch stays there until the counter’s next visit, which comes eventually, and is then counted. When the switch is off and some prisoner has not signaled, that prisoner comes again eventually and either finds the switch off and signals, or finds it on because another prisoner has signaled first. Either way a new signal appears, each new signal is eventually counted, and only 99 signals are needed. Without the assumption the plan may never finish, and if some prisoner is never brought at all, the group cannot win, since a declaration would then be false.
In plain words Fairness promises that nobody is left out forever. It does not promise speed, so the protocol is sure to finish but not by any particular day.
Example Pick any number . The warden may bring only prisoner A for the first visits and then bring all 100 prisoners in turn, over and over. This order is fair, yet after visits the count is still 0, so no fixed number of visits is enough. A random order gives a sense of the typical time. Suppose each visit is made by one of the 100 prisoners chosen at random with equal chances, independently of earlier visits. Then the protocol finishes with probability 1, and its average running time follows from the fact that an event with probability at each visit takes visits on average. With the count at and the switch off, prisoners can signal, so a new signal takes visits on average, and the counter then takes 100 visits on average to collect it. Adding over gives an average of
visits, more than 28 years at one visit a day. Even so, no number of visits is enough for certain, because for every number there is a positive probability, however small, that only prisoner A is drawn for the first visits.
Check yourself
- Four prisoners A, B, C and the counter D follow the protocol. The first eight visits are C, D, D, A, B, D, A, C. What are the count and the switch after these visits, and what is the smallest number of further visits before D can declare?
Show the answer
Prisoner C finds the switch off and turns it on. Counter D counts 1 and turns it off, then finds it off on the next visit and does nothing. Prisoner A turns it on, B finds it on and waits, and D counts 2 and turns it off. Prisoners A and C come back with their signals already used and do nothing.
After eight visits the count is 2, the switch is off, and only B has not signaled. Prisoner B must still visit and turn the switch on, and then D must visit to count it, so at least 2 more visits are needed. The order B, D achieves this, and D declares at a count of 3.
- Change the waiting rule. A prisoner who finds the switch already on decides that their signal is now in, leaves the switch on and counts themselves as having signaled. Can the plan now declare falsely? Is it still sure to finish under a fair order?
Show the answer
It still never declares falsely. Every on position that the counter collects was made by a different prisoner who was in the room, so the count is still at most the number of different prisoners who have visited.
But it may never finish. With four prisoners, take the visits A, B, D, C, D. Prisoner A turns the switch on, B finds it on and now counts as having signaled, and D counts 1. Then C turns it on and D counts 2. All three signalers now believe they have signaled, so nobody will turn the switch on again, and the count stays at 2 forever, short of the 3 needed, however fair the later visits are. In general, each prisoner who treats someone else’s on position as their own signal makes the final count fall one further short of 99. One switch can hold only one waiting signal, and waiting is what keeps signals from merging.
- Change the starting rule. The switch may now start on or off, and nobody knows which. Show that the original plan can declare falsely, and check this repair for 100 prisoners. Each prisoner other than the counter turns the switch on twice, each time only on finding it off, and the counter declares at a count of 198.
Show the answer
With four prisoners, suppose the switch starts on and the visits are D, A, D, B, D. Counter D counts the starting position as a signal, then counts the signals of A and B, and reaches 3 and declares, although C has never been in the room.
In the repair, suppose the switch starts on. Only the counter ever turns it off, and no signaler touches it while it is on, so this starting position is counted once, at the counter’s first visit, and then cleared. After that, and from the start if the switch starts off, every on position comes from a real signal. So a count of 198 includes at least 197 real signals. If some prisoner other than the counter had never visited, at most 98 prisoners could have signaled, giving at most real signals. So the declaration is true. Under a fair order every one of the 99 prisoners eventually signals twice, giving 198 real signals, so the count reaches 198 and the counter declares.
The number 198 cannot be lowered to 197. If the switch starts on and 98 prisoners signal twice each, the count reaches while one prisoner has never come.