The Firing Squad Synchronization Problem on Squares, Toruses and Rings
The Firing Squad Synchronization Problem on Squares, Toruses and Rings
复制标题
正方形、环面和圆环上的射击队同步问题
DOI：
10.1142/s0129054107004875
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Mimmo Parente
中科院分区：
文献类型：
--
作者：
J. Gruska;S. L. Torre;Mimmo Parente
众所周知，解决射击队同步问题（FSSP）需要时间 2n - 1，n 是士兵的数量。我们还知道，解决一个由 n × n 士兵组成的方阵需要相同的时间。本文的主要成果是为方形网络上的 FSSP 提供了一种新的解决方案。我们的解决方案在两个方面是最优的：它是通信最优的（所谓的 1 位解决方案），也是时间最优的，因为它需要 2n - 1 时间。它还用作构建块，在方形环面上构建非常有效的解决方案。我们的方法也适用于线性形状的网络，并在环上产生几乎最佳的时间和通信解决方案。特别是，对于具有 n 行和 n 个处理器环的方形环面，如果 n 是偶数，我们的解决方案是时间和通信最佳的。否则，它是通信最佳的，但与同步时间下限仅相差 1 个时间单位。
It is well known that a solution for the Firing Squad Synchronization Problem (FSSP) takes time 2n - 1, n being the number of soldiers. It is also known that a solution on a square of n × n soldiers takes the same time. The main result of this paper is a new solution for the FSSP on networks shaped as squares. Our solution is optimal in two aspects: it is communication optimal (the so-called 1-bit solution) and is also time optimal, as it takes 2n - 1 time. It is also used as a building block to construct a very efficient solution on the square torus. Our approach applies also to linearly shaped networks and yields on the ring almost optimal time & communication solutions. In particular, for the square torus with n rows and rings of n processors, if n is even our solution is time & communication optimal. Otherwise, it is communication-optimal but does not match the lower bound on the time of a synchronization just by 1 time unit.