From: www.dcs.ed.ac.uk/teaching/cs3/os/slides/sync.ppt -

Railways in the High Andes 

 High in the Andes Mountains, there are two circular railway lines.  One line is in Peru, the other in Bolivia.  They share a common section of track where the lines cross a mountain pass that lies on the international border (near Lake Titicaca?). 

 Unfortunately, the Peruvian and Bolivian trains occasionally collide when simultaneously entering the common section of track (the mountain pass).  The trouble is, alas, that the drivers of the two trains are both blind and deaf, so they can neither see nor hear each other.

 The two drivers agreed on the following method of preventing collisions.  They set up a large bowl at the entrance to the pass.  Before entering the pass, a driver must stop his train, walk over to the bowl, and reach into it to see it it contains a rock.  If the bowl is empty, the driver finds a rock and drops it in the bowl, indicating that his train is entering the pass; once his train has cleared the pass, he must walk back to the bowl and remove his rock, indicating that the pass in no longer being used.  Finally, he walks back to the train and continues down the line.

 If a driver arriving at the pass finds a rock in the bowl, he leaves the rock there; he repeatedly takes a siesta and rechecks the bowl until he finds it empty.  Then he drops a rock in the bowl and drives his train into the pass. 

        A smart aleck graduate from the University of La Paz (Bolivia) claimed that subversive train schedules made up by Peruvian officials could block the train forever.    Explain

        The Bolivian driver just laughed and said that could not be true because it never happened.       Explain

        Unfortunately, one day the two trains crashed.    Explain 

 Following the crash, the graduate was called in as a consultant to ensure that no more crashes would occur.  He explained that the bowl was being used in the wring way.  The Bolivian driver must wait at the entry to the pass until the bowl is empty, drive through the pass and walk back to put a rock in the bowl.  The Peruvian driver must wait at the entry until the bowl contains a rock, drive through the pass and walk back to remove the rock from the bowl.  Sure enough, his method prevented crashes.

 Prior to this arrangement, the Peruvian train ran twice a day and the Bolivian train ran once a day.  The Peruvians were very unhappy with the new arrangement. Explain

 The graduate was called in again and was told to prevent crashes while avoiding the problem of his previous method.  He suggested that two bowls be used, one for each driver.  When a driver reaches the entry, he first drops a rock in his bowl, then checks the other bowl to see if it is empty.  If so, he drives his train through the pass. Stops and walks back to remove his rock.  But if he finds a rock in the other bowl, he goes back to his bowl and removes his rock.  Then he takes a siestas, again drops a rock in his bowl and re-checks the other bowl, and so on, until he finds the other bowl empty. 

        This method worked fine until late in May, when the two trains were simultaneously blocked at the entry for many siestas.       Explain