100 Prisoners and Light Bulb Counter Protocol

Scenario

100 prisoners are in individual cells. In the prison courtyard, there is a interrogation room containing a single light bulb controlled by an ON/OFF toggle switch. The initial state of the light bulb is unknown (could be ON or OFF). At each discrete time step, the warden escorts one prisoner selected uniformly at random into the room. The prisoner may choose to toggle the switch or leave it as found. Any prisoner at any visit may declare: "All 100 prisoners have visited this room at least once." If the statement is correct, all go free; if wrong, all are executed.

Your Task

1. Design a decentralized protocol ensuring declaration with probability 1 that accounts for the unknown initial bulb state.
2. Designate a single Counter and define the action rules for Regular prisoners and the Counter.
3. Calculate the required count threshold to guarantee that every prisoner has entered the room.

Constraints

• Unknown initial bulb state.
• Uniform random prisoner selection with replacement.

Examples If each regular prisoner turns the bulb ON at most twice, the counter must log $2 \times 99 = 198$ turn-offs.