Assume a very strange lighthouse signaling system consisting of three lighthouses located on isolated rocks out of sight of each other, around a harbor. The lighthouses can signal red and blue colors and the colors combinations are used to signal to the ships approaching the harbor. If the first lighthouse is red, the second blue and the third, ships loaded with bananas are allowed to enter the harbor. One can also let a lighthouse to be turned off and thus creating more combination; off-off-off has for example been used to signal that the harbour is closed.
The lighthouses are operated by the reliable keepers that will set up the sequence of the colors for the night. A color schedule will determine which color (if any) that should be turned on for each hour of the night. Everything is prepared during the day and as soon as the sun sets the sequence is turned on automatically. Light houses have clocks that will accurately count hours during the night until the sun rises (assume ten hours to keep things simple). The lights will never fail to operate during the night.
To communicate with the lighthouses the shipping houses in the harbour have trained seals that will swim to a lighthouse and back during the day. Seals are quite good swimmers and it never takes them more than ten minutes to swim to a lighthouse. A seal can easily make 40 turns during a day and each shipping house has a trained seal for each lighthouse. The limitation is that a seal can only swim to one lighthouse, not in-between lighthouses.
The shipping houses in the harbour, each one specialized in a different cargo, are expecting one ship each night. Since the capacity of the harbor is limited it can only unload one ship in any given hour. The shipping houses compete for the best slots (not too late) during the night and will try to reserve during the night for ships holding cargo that it can unload. The shipping houses will not communicate with each other since they would probably just lie anyway to get a competitive advantage.
The protocol used by the shipping houses is quite chaotic. Each one will in the morning go down to the harbor and send three seals away with a request to set a specified color at a specified hour. The banana company would for example send the message “please set the colour red in the third hour” to the first and the third lighthouse and the same message for the color blue for the second light house. Most of the time it works but too often strange things happened; the banana and orange companies could arrive at the harbour in the middle of the night only to see a ship loaded with potatoes enter the harbor.
Design a better protocol that will allow as many shipping houses as possible to order the lighthouses to set their respective colors (include the color “off” in the color code) during the night. The protocol should avoid problems with unexpected potato ships.
Another harbor down the cost have heard about your successful protocol and they decide to adopt it. However, trained seals are hard to come by so they had to settle for almost reliable seals that will deliver their messages but without any guarantees on delivery time. How should you change the protocol so that chaos is prevented? How many color codes can you use?
When you travel trough the harbour down the cost a year later, everyone is pleased with your solution. However, sometimes they are prepared to receive a ship but no ship arrives. They know that that this could happen, since you told them, but they would like a more predictable solution. It turns out that the seals are quite reliable; in average there is only one hour every night where ships fail to show up. Having everyone prepared cost money but if they could be warned that ships might not arrive they could let half of the work force work with other things. A false warning is OK if there are not too many. Modify the protocol to make it more predictable. How many false warnings will in average occur?