線形化可能性を保証する共有レジスタの無待機な実現に関する研究

須田 克朗 (9751058)

各プロセスが実時間タイマを持つ分散システム上での線形化可能性を保証す る共有レジスタの無待機な実現を考察する．すべてのプロセスに既知で，0 ＜ u ≦ d である定数 d, u に対し，すべてのメッセージ遅延は [d-u, d] の範囲であ ることを仮定する．本論文では，放送に信頼性のあるシステムにおいて，read 操作の最悪応答時間が u，write操作の最悪応答時間が d であるような線形化 可能かつ無待機な実現を示す．また，放送に信頼性のないシステムにおいて，read 操作，write操作の最悪応答時間がともに d である，線形化可能かつ無待機な 実現を示す．