An Optimum Solution to the Firing Squad Synchronization Problem
An Optimum Solution to the Firing Squad Synchronization Problem
复制标题
射击队同步问题的最优解
DOI：
10.1016/s0019-9958(66)90110-0
复制
发表时间：
1966
期刊：
影响因子：
--
通讯作者：
A. Waksman
中科院分区：
文献类型：
--
作者：
A. Waksman
提出了一种16状态机作为“射击班同步问题”的最优解决方案。它表明，当给定一个任意长这种机器的（但有限的）阵列，并且在一端att= 0给出命令，则可以使所有机器立即进入一个终端状态，在时间= 2n-2其中是阵列中机器的数量。机器状态转换的码本的排列方式使阵列逐渐将其自身划分为2 kequal parts，其中k是一个整数，是时间的递增函数。每个分区中的终端机器假定一个特殊的状态，以便当最后一个分区出现时，所有机器的两个邻居机器都处于此状态。这是任何机器采取终端状态的唯一条件。
A 16 state machine is proposed as an optimum solution to the “Firing Squad Synchronization Problem.”It is shown that when given an arbitrarily long (but finite) array of such machines and a command is given at one end att= 0, it is possible to cause all the machines to go to one terminal state, all at once, at timet= 2n− 2 wherenis the number of machines in the array.The code book of the state transitions of the machine is so arranged to cause the array to progressively divide itself into 2kequal parts, wherekis an integer and an increasing function of time. The end machines in each partition assume a special state so that when the last partition occurs, all the machines have for both neighbors machines at this state. This is made theonlycondition for any machine to assume terminal state.