2次元セルラーオートマトン上での 最適時間一斉射撃アルゴリズムの設計

日本ソフトウェア科学会第 22 回大会（2005 年度）論文集
1
2 次元セルラーオートマトン上での
最適時間一斉射撃アルゴリズムの設計
内野 博貴 †
Hiroki Uchino
†
梅尾 博司 †
Hiroshi Umeo
大阪電気通信大学大学院工学研究科
{uchino, umeo}@cyt.osakac.ac.jp
1
はじめに
１回する時間を単位とし，1 ステップと呼ぶ．
2 次元セルラーオートマトンにおける最適時間一
2-D CA における信号はの伝播速度は，1/1 のよう
斉射撃アルゴリズムは，これまでに Beyer [1], Shi-
に分数で表す．これは，1 ステップに 1 セル信号が伝
nahr [6], Teraoka, Hisaoka, Maeda, Umeo [8], Umeo, 播すると言う事を表しており，2 ステップに 1 セル
Maeda, Fujiwara [9] らにより提案されている. これ 伝播する信号は，1/2 の速度で伝播していると表す．
らのアルゴリズムは，一次元一般化一斉射撃アルゴ 以下では，1/1 の速度で伝播する信号を 1/1 信号と
リズムをベースとするものであり，Shinar [6] は 28
状態の一斉射撃アルゴリズムを，Teraoka, Hisaoka,
呼ぶ．
次に一斉射撃問題について述べる．全てのセルが
Maeda, Umeo [8] は 14 状態の最適時間アルゴリズム 静止状態であるセル空間に将軍状態 (General) と呼
を実現している．本稿では，2 次元アレイを L 字型 ばれる特殊な状態を配置する．(図 3.6) 将軍状態は，
一次元アレイの集合体ととらえ，それらの上で従来 セル空間の端 (1-D CA ならば左端，2-D CA ならば
から知られている左端あるいは右端を将軍状態とす
左上) に配置された時刻を開始時刻 (t = 0) とし，信
る一次元同期アルゴリズムを利用する．2 次元アレ
号を送信する．
イの為の最適時間アルゴリズムを提案する．アルゴ
n
リズムの構築において，Umeo [10] による計算状況
G
㨯㨯㨯
の凍結・解答手法 (Freezing-Thawing Technique) が
イズ m × n の 2 次元アレイを m + n+max(m, n) − 3
㨯㨯㨯
後に 4 節では，今後の残された問題について論ずる．
㨯㨯㨯
2 次元セルラーオートマトン
2 次元セルラーオートマトン (2-D CA) は，セル
が平面上に格子構造で配置されたモデルである．2-D
㨯㨯㨯
㨯㨯㨯
ステップで同期するアルゴリズムの詳細を示す．最
2
㨯㨯㨯
㨯㨯㨯
㨯㨯㨯
㨯㨯㨯
m
㨯㨯㨯
トマトンと一斉射撃問題について述べ，3 節では，サ
㨯㨯㨯
㨯㨯㨯
利用されている．まず 2 節では，2 次元セルラーオー
図 1: サイズ m × n の 2 次元アレイ．
CA は，縦に m 個，横に n 個のセルが配置された空
未来のある時刻 t = α において全てのセルを射撃
間を，サイズ m × n の 2-D CA と呼ぶ．
状態へ状態遷移させる状態遷移関数を作成する事が
全てのセルは，ノイマン近傍の隣接した位置にあ 一斉射撃問題の目的である．射撃状態は，t = α の時
るセル上，下，左，右と通信リンクで接続されてお
刻以外には現れる事は無く，全てのセルが射撃状態
り，通信リンクで繋がっているセル同士は 1 ステップ
になる事で一斉射撃問題は終了する．最適時間とは，
で互いの状態を読み取る事ができる．最外周に位置 「これ以上早く同期する事は不可能である」と証明さ
するセルは，壁と隣接していると仮定する．2-D CA れた時間で，最適時間で同期するアルゴリズムを最適
における状態遷移は，上，下，左，右の近傍情報と， 時間アルゴリズムと呼ぶ．1-D CA ではセル数 n のセ
自身の状態の組み合わせにより状態遷移する．状態 ル空間に対して最適時間は 2n− 2 となり，2-D CA で
遷移は全てのセルが同時に行い，セルが状態遷移を
は n× m のサイズにおいては，m+ n+max(m, n)− 3
日本ソフトウェア科学会第 22 回大会（2005 年度）論文集
2
m < n の場合，
Li = { Ci,j Ck,i |1 ≤ j ≤ i + (n − m), 1 ≤ k ≤ i}
となることが知られている．
となり，Li は 3 つのセグメントに分割される．各
3
セグメントに属するセルを以下に定義する．
最適時間一斉射撃アルゴリズム
本節では，サイズ m × n の 2 次元アレイを m +
n+max(m, n) − 3 ステップで一斉射撃する同期アル
ゴリズムを示す．以下では，一般性を失うこと無く
第 1 セグメント = {Ci,j |1 ≤ j ≤ i}
第 2 セグメント = {Ci,j |i ≤ j ≤ i + (n − m)}
第 3 セグメント = {Cj,i |1 ≤ j ≤ i}
m < n と仮定する．サイズ m × n の 2 次元アレイ M
1
2
n
3
を，図 2 に示すような m 個の L 型 (正確には，文字
Time
L を時計方向まわりに 90 °回転させたものである)1
次元アレイから構成されると考える．
n
1/3
.
.
.
.
.
.
.
.
.
.
.
1/1
Freezing signal
.
t = n-1
.
1/7
.
m
. .
. .
.
.
......
L1
L2
t=0
Thawing signal
.
t = n-1+∆t
.
. .
...
Li
Lm
1/15
図 2: m 個の L 字型 1 次元アレイから構成される 2
Frozen
次元アレイ．
1/1
1/3
half
1/7
quarter
quarter
これらを L1 ,L2 ,・
・
・,Lm で示す．分割の数学的な
定義は後述する．任意の i(1 ≤ i ≤ m) に対して，Li
斉射撃することにより，M を同期状態に導く．それ
ぞれの L 型 1 次元アレイは，3 つのセグメントに分
割される．i 番目の L 型アレイ Li (1 ≤ i ≤ m) はそ
t = 2n-2+∆t
Fire
を同時刻 T(m, n) = m + n+max(m, n) − 3 時に一
図 3: 1 次元一斉射撃アルゴリズムの凍結解凍技法を
用いて，∆t ステップの時間遅延．
れぞれ長さ i,n − m,i の 1 次元アレイからなる．各セ
グメント上では，t = 0 時に左端あるいは右端に将
軍状態を配置する一斉射撃アルゴリズムを動作させ
る．各セグメントの長さは短いので，従来から知られ
3.1
ているアルゴリズムを使用すると一般的には比較的
1 次元一斉射撃問題における凍結・解凍技法とは，
アレイ上での同期時間を遅延させる方法である．凍
早期に一斉射撃状態におちいるが，各セグメントの
同期時刻を T(m, n) に一致させるために，Umeo[13]
凍結・解凍技法
結・解凍技法は，凍結信号と解凍信号の 2 種類の信
により考案された凍結・解凍技法 (Freezing-Thawing
号を制御する事で，n 個のセルからなる 1 次元セル
Technique) を使用する．詳細は後述する．
ラーオートマトンの同期時間を遅延させることがで
きる．凍結信号は，伝播している任意の信号と衝突
[定義 1] M をサイズ m × n の 2 次元セルラーオー すると衝突したセルで停滞させる．停滞した信号は
トマトンとし，座標 (1，1) に位置するセルを C1,1 ， 解凍信号と衝突するまで，凍結信号と衝突した位置
(m, n) に位置するセルを Cm,n とする．M を L1 ∼ に停滞し続ける．この 2 種類の信号，凍結信号・解
Lm のセル列に分割する．Li (1 ≤ i ≤ m) に属するセ
ルを以下に定義する．
凍信号が通過した n 個のセル列は，同期時間が信号
の通過した時間差分遅れる．この時間差を凍結・解
日本ソフトウェア科学会第 22 回大会（2005 年度）論文集
凍技法によって発生させた遅延と呼ぶ．
Cm1
࡮࡮࡮
C11
࡮࡮࡮
3
C1,n-m
セルラーオートマトンとする．t = 0 時における将軍
Cn1
First Row
First Column
1/1
1/1
[補題 1] M を n 個のセルからなるセル空間上で最適
時間一斉射撃アルゴリズムを実行する任意の 1 次元
࡮࡮࡮
t=m-1
の位置をアレイの左端とし，∆t(≥ 1) を任意の正整
t=n-1
数とする．M は t = n − 1 + ∆t ステップ時に，外界
1/2
から右端のセルに特別な信号が与えられるものとす
る．この時，t = 2n − 2 + ∆t ステップ時に一斉射撃
するセルラーオートマトンを M から構成することが
でき，射撃に要する時間を ∆t ステップ遅延させるこ
1/2
t=3m-3
とができる (図 3 参照)．
1/1
3.2
t=2m+n-3
アレイのマーキングと将軍状態の生成
まず，最初に M を m 個の L 型アレイに分割する
ためのマーキングについて説明する．t = 0 時，M
t=m+2n-3
上の C11 に将軍状態 G が置かれ，ほかの全てのセル
図 4: 第 1 セグメント並びに第 3 セグメント上に将
は静止状態にあるとする．G から t = 0 時に 3 つの
軍状態を生成するための時間・空間図式．
信号 SV ,SD ,SH が，垂直下方，右下 45 °の方向，水
平方向に発せられる．これらの信号は 1/1 の速度で
伝播し，それぞれ t = m − 1, 2m − 2, n − 1 時に最
初の目標点である Cm1 ,Cmn ,C1n に到着する．右下
軍状態を生成する．生成された将軍は Lm 上に信号
を送信する．第 1 セグメントに生成された将軍から
45 °の方向に進む信号 SD は，C11 ，C22 ，C33 ，Cmm の信号は，SD と衝突すると，反射し第 1 セグメント
上に第 2 セグメントの開始を示す記号をマークする． を凍結させる為の凍結信号となる．この時，第 1 セ
次に Cm1 ならびに C1n に到達した信号 SV ,SH はそ グメント上を 1/2 の速度で伝播する信号は冷凍・解
こで反射し，伝達速度を 1/2 に減速して再び C を 凍の制御に使用するため信号を凍結させない．第 1
11
目指して先程の道筋を逆方向に戻る．SV は新たな
セグメントに生成された将軍が送信した信号と，SD
行に到達する度に，各 L 型アレイの第 1 セグメント
が衝突した地点 Cmm に第 2 セグメントを一斉射撃
を一斉射撃する為の将軍状態を生成する．Li 上には
する為の将軍状態を生成する．第 2 セグメントに生
t = 3m − 2i − 1 時に将軍状態が作られる．SH は第 1 成された将軍は第 1 セグメントに生成された将軍と
セグメント上に同様に第 3 セグメントを一斉射撃す 同様の信号を送信する．第 2 セグメントの将軍が送
る為の将軍状態を生成する．L の第 3 セグメントに 信した信号は，第 3 セグメントの将軍が送信した信
i
対しては，t = 2m + n − 2i − 1 時に将軍状態が作ら
れる．SH による将軍状態の生成は，後ほど説明する
理由により，t = 2m + n − 3 の時間に C1,n−m 上で
号と衝突し，第 2 セグメントと第 3 セグメントを凍
結させる．凍結した 3 つのセグメントを解凍する信
号は，第 1 セグメントを解凍する信号は第 2 セグメ
終了する．
ントより，第 2 セグメントを解凍する信号は第 3 セ
3.3
2 セグメントより伝播される．凍結したセグメント
は，解凍信号を異なるセグメントから受け取る事で，
グメントより，第 3 セグメントを解凍する信号は第
Li の一斉射撃
まず，Lm 上での一斉射撃アルゴリズムを説明す
る．m < n と仮定した Lm の時間空間図式を図 5 に
示す．Lm は SV の信号が到達する t = m − 1 時間に
Cm1 に第 1 セグメントを一斉射撃する為の将軍状態
を生成する．同様に，SH の信号が到達する t = n − 1
時間に C1n に第 3 セグメントを一斉射撃する為の将
3 つのセグメントは単一での動作をせず，異なるセグ
メントの影響を受ける．
Li のセル列も基本的には Lm のセル列と同様のア
ルゴリズムで動作する．Lm のアルゴリズムと異なる
点は，Lm のアルゴリズムが第 2 セグメントの将軍を
生成する位置を SD との衝突地点だったが，Li のア
日本ソフトウェア科学会第 22 回大会（2005 年度）論文集
ルゴリズムは SD の軌跡と衝突すると第 2 セグメン
トの将軍状態を生成する事と，1,2,3 セグメント目の
3.4
4
m > n と仮定した場合
m > n の場合と m < n の場合の違いは，第 2 セグ
将軍を生成する時間が異なる事の 2 点である．
メントの位置と第 2 セグメントへ解凍信号を送るセ
L1 のセル列は，第 1，第 3 セグメントの長さが 1 グメントが異なる事である．m > n と仮定した場合，
となったセル列である．L1 は他のセル列と異なり特 SD は Ln の第 3 セグメントを伝播する信号と衝突し
殊な形になってしまう為，凍結を用いない最適時間 Cnn に第 2 セグメントの将軍状態を生成する．この第
一斉射撃アルゴリズムを用いてセル列を同期させる． 2 セグメントの将軍は n < m の場合に生成された将
[補題 2] Li を [定義 1] で表したセル列とする．Li
を左端 Ci,1 ，右端 C1,i+(n−m) の 1 次元配列として
軍とは異なり，Cn1 方向へ信号を伝播せず，Cmn の
方向へ信号を伝播する．さらに，他の Li (1 ≤ i ≤ n)
も Ln と平行に信号を伝播する．各 Li の第 2 セグメ
考える．Li には 3 つの信号が伝播される．左端に
ントは第 1 セグメントと衝突すると，m < n の第 3
m + 2(m − i) − 1 の時間に到達する信号．右端に セグメントと衝突した動作を対称にとる．すなわち，
n + 2(m − i) − 1 の時間に到達する信号．左端より 第 2 セグメントは第 3 セグメントの解凍信号を生成
m の位置に 2i の時間に到達する信号．これら 3 つの し，第 1 セグメントは，第 2 セグメントの解凍信号
信号が Li に伝播された場合，上記のアルゴリズムを を伝播する．このように，サイズの異なる場合でも
使用する事により，Li を同期させる事ができる．
第 2 セグメントの動作を変更する事で，いかなるサ
イズの m × n の場合においてもこのアルゴリズムは
動作する．
G
m
Sv
SH
1/1
n
n
SH
G
SD
1/1
1/2
i
SD
1/1
1/1
m
1/1
1/1
Sv
1/2
n-m
n-m
m
n-m
i
m
i
n-m
t=m-1
t=m+2(m-i)-1
1/1
t=2m-2
t=3m-i-2
1/1
1/2
1/2
1/2
t=m+n-2
∆t2
∆t3
t=2m+n-2
1/1
∆t1
1/1
t=m+2n-i-2
t=m+2n-3
t=m+2n-3
図 5: Lm 及び Li 上での一斉射撃．
t=n+2(m-i)-1
1/1
1/2
∆t1
t=2n-2
t=n-1
1/1
1/2
1/2
∆t2
t=2m+n-i-2
t=2m+n-2
∆t3
日本ソフトウェア科学会第 22 回大会（2005 年度）論文集
3.5
最適時間一斉射撃アルゴリズム
5
手法を考案した．考案したアルゴリズムを Gerken[2]
M をサイズ m × n の 2 次元セルラーオートマトン
の 7 状態アルゴリズムをベースにシミュレーター上
とする．M を [定義 1] の L1 ∼Lmin(m,n) に分割する． へ部分的な実装を行った．実装したアルゴリズムは
分割したセル列は，[補題 2] のアルゴリズムを用いる 状態数，ルール数が膨大な数になった．
ことによって m + n+max(m, n) − 3 の時間で同期す
参考文献
る事ができる．以上を次の定理にまとめる．
[定理 3] 任意のサイズ m × n(m ≥ 2, n ≥ 2) の 2 次
元セルラーオートマトンを m + n+max(m, n) − 3 ス
テップで同期させる M が存在する．
3.6
コンピューター上への実装
m = 8，n = 5 の場合におけるシミュレーション結
果を図 6 に示す．
Step:0
1
2
3
4
5
6
7
1
G
S
S
S
S
S
S
S
2
S
S
S
S
S
S
S
S
3
S
S
S
S
S
S
S
4
S
S
S
S
S
S
S
5
S
S
S
S
S
S
S
Step:3
1
1
2
8
Step:1
Step:2
1
S
1
S
2
S
S
S
S
S
S
1
2
3
4
5
6
7
1
XY
X
S
S
S
S
S
2
Y
S
S
S
S
S
S
S
3
S
S
S
S
S
S
S
4
S
S
S
S
S
S
S
5
S
S
S
S
S
S
8
Step:4
1
2
2
3
4
5
6
7
XY
X
X
X
S
S
S
S
1
XY
X
Y
XY
X
S
S
S
S
S
2
Y
XY
Y
Y
8
2
3
4
5
6
7
XY
X
X
S
S
S
S
S
Y
XY
S
S
S
S
S
S
3
Y
S
S
S
S
S
S
S
4
S
S
S
S
S
S
S
S
5
S
S
S
S
S
S
S
S
1
2
3
4
5
6
7
X
Step:5
8
8
3
4
5
6
7
X
X
X
S
S
S
1
XY
X
X
X
X
S
S
X
S
S
S
S
S
2
Y
XY
X
S
S
S
S
S
XY
S
S
S
S
S
3
Y
Y
XY
X
S
S
S
S
8
3
Y
Y
S
S
S
S
S
S
3
4
Y
S
S
S
S
S
S
S
4
Y
S
S
S
S
S
S
S
4
Y1
S
Y
S
S
S
S
S
5
S
S
S
S
S
S
S
S
5
T61
S
S
S
S
S
S
S
5
T62
TR
S
S
S
S
S
S
Step:6
1
2
3
4
5
6
Step:7
1
2
3
4
5
6
2
3
4
5
6
7
8
1
XY
X
X
X
X
X
X
S
1
XY
X
X
X
X
X
X
Y61
1
XY
X
X
X
X
X
X1
Y62
2
Y
XY
X
S
S
S
S
S
2
Y
XY
X
S
S
S
S
S
2
Y
XY
X
S
S
S
S
YR
3
Y
Y
XY
X
S
S
S
S
3
Y1
Y
XY
X
S
S
S
S
3
T61
S
XY
X
S
S
S
S
4
T61
S
Y
XY
S
S
S
S
4
T62
TR
Y
XY
X
S
S
S
4
T6
TR1
T6
XY
X
S
S
S
T6
TR1
T6
S
S
S
S
S
5
T6
TR2
T_
TR
S
S
S
S
5
T6
TR
T_1
TS
T11
S
S
S
1
2
3
4
5
6
7
8
8
Step:11
5
Step:9
7
8
1
XY
X
X
X
X
X
Y61
Y6
2
Y1
XY
X
S
S
S
S
YR1
3
T62
TR
XY
X
4
T6
TR2
T_
T71
5
T6
TR
T62
T_
Step:12
S
S
S
Y6
S
S
S
S
S
S
T12 TRQ
Step:10 1
7
2
3
4
5
6
7
2
3
4
5
6
XY
X
X
X
X
X1
Y62
Y6
1
Y1
X
X
X
X
Y61
Y6
Y6
T61
XY
X
S
S
S
YR
YR2
2
T62
T71
S
S
S
S
YR1
YR
3
T6
TR1 T11
S
S
S
S
Y_
3
T6
TR2 T12 TRQ
S
Y6
Y_1
4
T6
TR
T_1
T72 TRQ
S
S
YR
4
T6
TR
T_2
T7
5
T6
TR
T6
T_1
S
5
T6
TR
T6
T_2
Step:13
T1
TR1 T6Q
1
2
3
4
5
6
7
8
1
2
S
X
X
X1
Y62
Y6
Y6
1
T6
TR
2
T6
T72 TRQ
S
S
YR
YR2
YR
2
T6
T7
S
Y_
Y62
3
T6
TR
T1
TR2
T_
44
Y_
4
T6
TR
T_
T7
TR T_1R 44
TR T_1R 4L
5
T6
TR
T6
T_
T1
3
T6
TR
T1
T6
TR
T_
T7
TR2
T6
TR
T6
T_
T1
Step:15 1
2
TR1 T6Q
7
8
Step:16
3
4
5
6
1
2
1
T6
TR
T_
4L_K
Y6
Y6
Y6
Y6
1
T6
TR
2
T6
T7
TR T_1R 44k_ YR
YR
YR
2
T6
T7
Y_
3
4
5
Y6
Y6
Y6
1
T6
TR
T6
Y1
Y62
Y6
Y6
Y6
YR1
YR
YR
2
T6
T7
TR2
T_
44
YR2
YR
YR
4L
Y_1
F
F
F
F
F
F
F
F
4
F
F
F
F
F
F
F
F
5
F
F
F
F
F
F
F
F
Y6
Y6
T6
T4
T1F
T4
T6
T4
T6
TLk
T4
T6
T6
T4
T6
T4
T1F
T4
TR
3
Y4
5
TL
T1K
F
8
Y6
Y4
4
TR
TR
F
7
Y6
3
TLk
TL
7
6
Y6
YL
TR
TL
TR
F
5
Y6
44KK YR
T1K
TR
T6
TL 4LKK
T6 4LKK
T6
Y6
44FF Y4
TL 4LKK YL
TR
T6
F
4
T4
T6
6
3
TLk
5
F
2
T4
T6
3
F
Step:17 1
T6
4
5
8
2
Y6
F
L6K_
1
T_ 44KK Y4
F
Y_2
T_
Y_2
TR
Y6
TR
4
44
T1K
YR
TR
F
TRR T_2
T_
Y6
T1K
F
T7
T6
YR
T4
3
TR T_1R 4L
T_
TR
6
TLk
F
T1
TR
T6
Y6
TRR T_2 4Lk_
F
TR
T6
5
T6
2
T6
4
Y6
T_
F
3
5
4
T1
8
L6
4Lk_
TR
7
Y_1
3
TR
F
6
TL
TR
7
Y6
2
TRR TL2 44k_ YR
T6
F
S
4L
5
T6
F
S
T_
S
T6
1
TR2
Y61
3
2
Step:14 1
T1
4
TRR T_2
8
TR1 T6Q
8
X
5
Step:18 1
7
S
7
3
T_
6
1
X
TR1 T6Q
4
T_ L6KK
1
2
T6
4
Step:8
1
1
5
8
T6 4LKK
44FF Y4
T6 4LKK
8
図 6: コンピューター上への実装．
4
おわりに
1 次元セルラーオートマトンにおける最適時間一
斉射撃アルゴリズムを，2 次元セルラーオートマトン
における最適時間一斉射撃アルゴリズムに拡張する
[1] W. T. Beyer: Recognition of topological invariants
by iterative arrays. Ph.D. Thesis, MIT, (1969), pp.
144.
[2] Hans-D., Gerken: Über Synchronisations - Probleme bei Zellularautomaten. Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, (1987), pp. 50.
[3] A. Grasselli: Synchronization of cellular arrays:
The firing squad problem in two dimensions. Information and Control, vol. 28(1975), pp. 113-124.
[4] E. F. Moore: The firing squad synchronization
problem. in Sequential Machines, Selected Papers
(E. F. Moore, ed.), Addison-Wesley, Reading MA.,
(1964), pp. 213-214.
[5] H. B. Nguyen and V. C. Hamacher: Pattern synchronization in two-dimensional cellular space. Information and Control, vol. 26(1974), pp. 12-23.
[6] I. Shinahr: Two- and three-dimensional firing
squad synchronization problems. Information and
Control, vol. 24(1974), pp. 163-180.
[7] H. Szwerinski: Time-optimum solution of the
firing-squad-synchronization-problem
for
ndimensional rectangles with the general at an
arbitrary position. Theoretical Computer Science,
vol. 19(1982), pp. 305-320.
[8] M. Teraoka, M. Hisaoka, M. Maeda and H. Umeo:
A state-efficient implementation of synchronization algorithms for two-dimensional cellular arrays
-Extended abstract-. Proc. of the Tenth International Symposium on Artificial Life and Robotics,
pp. 350-353, (2005).
[9] H. Umeo, M. Maeda and N. Fujiwara: An efficient mapping scheme for embedding any onedimensional firing squad synchronization algorithm onto two-dimensional arrays. Proc. of the 5th
International Conference on Cellular Automata
for Research and Industry, LNCS 2493, SpringerVerlag, pp.69-81(2002).
[10] H. Umeo: A simple design of time-efficient firing squad synchronization algorithms with faulttolerance. IEICE Trans. on Information and Systems, vol. E87-D, No.3, pp.733-739, (2004).
[11] A. Waksman: An optimum solution to the firing
squad synchronization problem. Information and
Control, vol. 9 (1966), pp. 66-78.