指数関数マーキングに基づいた最適時間FSSPアルゴリズムの実装

摘要

最適時間FSSPアルゴリズムはGoto［1962］により初めて示され，Balzer［1967］，Mazoyer［1987］らによる最適時間アルゴリズムが代表的なアルゴリズムとして知られている．Mazoyer ［1987］による6状態アルゴリズムは内部状態数が最も少ないものとして知られている．Balzer［1967］による最適時間アルゴリズムはセル空間を2分割していき，最終的に2分割できなくなれば同期するアルゴリズムである．Mazoyer［1987］による最適時間アルゴリズムはセル空間を2：1に分割していき，最終的に分割できなくなれば同期するアルゴリズムである．これらに対して最初からセル空間を指数関数の大きさに分割していくアルゴリズムがある．Goto［1962］はセル空間の長さが指数関数的に増加する複数の小区間に分割し，各小区間を同期させることにより，全体の同期を実現するFSSPアルゴリズムを考案した．その後，Gerken［1987］並びにYunes［2008］らにより，同様な分割方式を使ったアルゴリズムが提唱されている．本稿では，これまで未実装であったYunes［2008］のアルゴリズムを計算機上に実現し，その検証を行う．また，Yunes［2008］により示唆されていたRule 60を用いたアルゴリズムについても計算機上に実装を行う．