3状態相互排他アルゴリズムの安定時間の下限について

摘要

3状態相互排他アルゴリズムは，ダイクストラによって提唱された最初の自己安定アルゴリズムの一つである．その正しさについてはいくつもの研究で証明されているが，安定時間に関しては精度の高い解析がなされてこなかった．本研究では，モデル検査によって得られた知見から安定時間に関する解析を試みる．結果として安定時間の下限を表す式が得られた．