sundar (10/11/82)
Here is something to 'chew' for your minds. I would like to see lots of these in the news. Makes it more interesting to spend time reading the news. Also I would like to know what appropriate group this will address. *************************** There are n number of uniformed people with guns in their hands taking aim at a poor prisoner destined to be executed. n is unknown. To prevent excessive pain due to gunshot wounds, it is desired that all gun men fire their guns at the same time give or take few nanoseconds. There is no fire chief who calls 'Fire!' so that everybody will fire the same time. Instead the gunmen have to synchronize themselves somehow. Each gunman can talk to only his immediate neighbours. Being separate beings, each gunman operates at his own speed (no central clock). How much time it will take before prisoner is relieved of all his problems? What assumptions are required in order to find a solution? **************************** I might have an answer. ----------------------- This problem was given to me by one of my Profs. He had seen it and its solution somewhere but couldn't quite remember it. ----------------------
branish (10/12/82)
The firing squad synchronization problem was devised about the year
1957 by John Myhill. It was first solved by John McCarthy and
Marvin Minsky, with the definitive solution coming from MIT
by Professor E. Goto of the University of Tokyo.
I first saw this problem in Minsky, Marvin L. (1967), Computation:
Finite and Infinite Machines, where it was reprinted from
Moore, Edward F. (1956), Sequential machines: Selected Papers.
I should be afraid to sign my name,
Gus Branish
Penn State University
(...allegra!psuvax!branish)